List of Petr Jancar's publications
(last update 31 August 2006,
generally one can refer, e.g., to
DBLPentry )
Regarding electronic versions, i.e. (gzipped) postscript files
or pdffiles, see Important Notes below.
Note:
My name is Jan\v{c}ar in TeX which is not reflected below
(similarly for some other Czech names).
Publications in Journals

Jancar P.: Decidability of a Temporal Logic Problem for Petri
Nets;
Theoretical Computer Science
74, 1990, pp.7193
(Elsevier)
The key point in the is the decidability of termination
for marked place/transition Petri nets
under the weak fairness constraint (an almost always enabled transition
must fire infinitely many times). It is shown by an (exponential)
reduction to the reachability problem and slightly generalized
by showing a relevant decidable temporal logic fragment.
(A preliminary version appeared at STACS'89.)

Howell R., Jancar P., Rosier L.:
Completeness Results for Single
Path Petri Nets;
Information and Computation
106, 1993,
pp.253265 (Academic Press)
The paper shows
PSPACE completeness of basic problems for strictly deterministic
place/transition Petri nets
(only one maximal transition sequence
is enabled at such nets).
(A preliminary version appeared at MFCS'91.)

Jancar P.:
Nondeterministic forgetting automata are less powerful
than DLBAs;
Acta Mathematica et Informatica Universitatis
Ostraviensis
1, 1993, pp.6774

Jancar P.:
Undecidability of Bisimilarity for Petri Nets and
Related Problems;
Theoretical Computer Science
148, 1995, pp.281301
(Elsevier)
The paper mainly shows undecidability of bisimilarity
for labelled place/transition Petri nets.
Also a new (short) proof for undecidability of reachability set
equality (and containment) is given.
Some decidability results are also included.
(A preliminary version appeared at STACS'94.)

Jancar P., Mraz F., Platek M.:
Forgetting automata and
contextfree languages;
Acta Informatica
33, 1996, pp.409420 (SpringerVerlag)

Jancar P., Kucera A.: Bisimilarity of processes with
finitestate systems ;
Electronic Notes in Theoretical Computer Science
9, 1997 (2000),
14 pp. (among selected papers of Infinity'97)

Jancar P., Esparza J., Moller F.:
Petri nets and regular
processes;
Journal of Computer and System Sciences ,
Vol. 59, No. 3, Dec 1999, pp. 476503
(Academic Press)
The paper studies (un)decidability of trace equivalence
and bisimulation equivalence (in the strong and weak case)
of Petri nets and finite state processes; it also
addresses the finiteness (or regularity) problem.
(Prelimininary versions of parts of the paper appeared
in Proc. CONCUR'95, ICALP'96.)

Jancar P., Mraz F., Platek M., Vogel J.:
On Monotonic
Automata with a Restart Operation;
Journal of Automata, Languages and
Combinatorics
Vol. 4, No. 4, 1999, pp. 287312 (Univ. Magdeburg)

Jancar P.:
A note on well quasiorderings for powersets;
Information Processing Letters
72, 1999, pp. 155160
(Elsevier)

Jancar P.:
Decidability of bisimilarity for onecounter
processes;
Information and Computation 158, 2000, pp. 117
(Academic Press)
The paper deals with onecounter processes
(can be viewed as Petri nets with one unbounded place which
can be tested for zero). A `colouring technique' is used;
the positive case is witnessed by a `regular' (semilinear)
colouring of the plane.
(A preliminary version appeared at ICALP'97.)

Jancar P.:
Nonprimitive recursive complexity and
undecidability for Petri net equivalences;
Theoretical Computer Science
256, 2001, pp. 2330
(Elsevier)
The paper recalls undecidability of all action based
behavioural equivalences for labelled place/transition Petri nets
(Jancar P.: All actionbased behavioural equivalences are
undecidable for labelled Petri nets;
Bull. of EATCS, No. 56, June 1995, pp.8688),
and undecidability of the reachability set equality.
The nonprimitive recursivity of these problems
is shown for bounded nets (the bound not being given in input).

Jancar P., Kucera A., Mayr R.:
Deciding bisimulationlike
equivalences with finitestate processes;
Theoretical Computer Science
258, 2001, pp. 409433
(Elsevier)
The paper studies a general approach to (bisimulationlike) equivalences
(of possibly infinite state processes) with finitestate processes.
(A preliminary version appeared in Proc. ICALP'98.)

Jancar P., Kucera A., Moller F., Sawa Z.:
DP lower bounds for equivalencechecking and modelchecking
of onecounter automata;
Information and Computation
Vol. 188 (2004),
pp. 119
(Elsevier, Academic Press)
(A preliminary version appeared at FOSSACS'02.)

Sawa Z., Jancar P.:
Behavioural Equivalences on FiniteState Systems are PTIMEhard;
in the journal Computing and Informatics (CaI),
Vol. 24, 2005, pp. 513  528
A preliminary version appeared at Sofsem 2001.
It generalizes the previously known Phardness result
for bisimilarity to the whole range of relations between bisimilarity
and trace preorder.

Kucera A., Jancar P.:
Equivalencechecking on infinitestate systems: Techniques and
results;
in the journal
Theory and Practice of Logic Programming
(Cambridge University Press),
6(3):227264, 2006.
(it is an extended version of the invited paper at SOFSEM'02)
Publications in Research Monographs

Jancar P., Mraz F., Platek M.,
Vogel J.: On Restarting Automata with Rewriting;
in New Trends in Formal Languages (Control, Cooperation
and Combinatorics), Eds. G. Paun, A. Salomaa,
Lecture Notes in Computer Science ,
Vol. 1218, Springer
Verlag
1997,
pp.119136
(Participation on) Invited Papers in Conference Proceedings

Chytil M., Jancar P.:
Synchronization and communication of processes ;
invited lecture, in Proc. SOFSEM'84,
Lipt.Jan, pp.99127, November 1984. (In Czech)

Jancar P., Moller F.:
Techniques for decidability
and undecidability of bisimilarity  an invited tutorial;
in Proc. CONCUR'99 (Eindhoven, The Netherlands, August 1999),
Lecture Notes in Computer Science , Vol. 1664,
Springer 1999, pp. 3045

Kucera A., Jancar P.:
Equivalence checking with infinite state systems: Techniques and
results.
In: Grosky, W. I., Plasil, F.(Eds.)
SOFSEM 2002: Theory and Practice of Informatics.
29th Conference on Current Trends in Theory and Practice of Informatics,
Milovy, Czech Republic, November 2229, 2002, Proceedings,
Lecture Notes in Computer Science . Volume. 2540, Springer 2002,
pp. 4173
Publications in Conference Proceedings of the Springer Series
"Lecture Notes in Computer Science", or IEEE Computer Society
or Kluwer

Jancar P.: Decidability of Weak Fairness in Petri Nets;
in Proc. of Symposium on Theoretical Aspects of Computer
Science (STACS) 1989, Paderborn(FRG), February 1989,
Lecture Notes in Computer Science ,
Vol. 349, Springer 1989,
pp.446457

Howell R., Jancar P., Rosier L.: Singlepath Petri nets;
in Proc. of Mathematical Foundations of Computer Science
(MFCS) 1991, Poland, Sept. 1991,
Lecture Notes in Computer Science,
Vol. 520, Springer 1991, pp.202210

Jancar P., Mraz F., Platek M.: Characterization of contextfree
languages by erasing automata; in Proc. MFCS 1992, Prague,
August 1992,
Lecture Notes in Computer Science,
Vol. 629, Springer 1992, pp.307314

Jancar P., Mraz F., Platek M.: A taxonomy of forgetting automata;
in Proc. MFCS 1993, Gdansk, Poland,
September 1993, Lecture Notes in Computer Science, Vol. 711,
Springer 1993, pp.527536

Jancar P.: Decidability questions for bisimilarity of Petri nets
and some related problems; in Proc. STACS 1994, Caen,
France, February 1994,
Lecture Notes in Computer Science, Vol. 775,
Springer 1994, pp.581592

Jancar P.:
High undecidability of weak bisimilarity for Petri
nets;
in Proc. of Colloquium on Trees in Algebra
and Programming (CAAP) 1995 (part of TAPSOFT'95), Aarhus,
Denmark, May 1995,
Lecture Notes in Computer Science,
Vol. 915, Springer 1995, pp.349363

Jancar P., Moller F.: Checking regular properties of Petri
nets;
in Proc. CONCUR'95,
Philadelphia, U.S.A., August 1995,
Lecture Notes in Computer Science, Vol. 962, Springer 1995,
pp.348362

Jancar P., Mraz F., Platek M., Vogel J.:
Restarting automata; in Proc. Fundamentals of
Computation Theory (FCT) 1995, Dresden, Germany, August 1995,
Lecture Notes in Computer Science, Vol. 965,
Springer 1995, pp.283292

Jancar P., Esparza J.: Deciding finiteness of Petri nets up
to bisimulation; in Proc. ICALP'96, Paderborn, Germany, July
1996,
Lecture Notes in Computer Science, Vol. 1099,
Springer 1996, pp.478489

Jancar P.: Bisimulation equivalence is decidable for
onecounter processes; in Proc. ICALP'97, Bologna, Italy, July
1997,
Lecture Notes in Computer Science, Vol. 1256,
Springer 1997, pp. 549559

Mraz F., Platek M., Jancar P., Vogel J.: Monotonic
rewriting automata with a restart operation;
in Proc. SOFSEM'97, Milovy, Czech Rep.,
Lecture Notes in Computer Science, Vol. 1338,
Springer 1997, pp. 505512

Jancar P., Kucera A., Mayr R.: Deciding bisimulationlike
equivalences with finitestate processes;
in Proc. ICALP'98, Aalborg, Denmark, July
1998,
Lecture Notes in Computer Science , Vol. 1443,
Springer 1998, pp. 200211

Jancar P., Mraz F., Platek M., Vogel J.:
Different types of monotonicity for restarting automata;
in Proc. FSTandTCS'98, Chennai, India, December 1998,
Lecture Notes in Computer Science, Vol. 1530,
Springer 1998, pp. 343354
Also included in the book ``Komplexit\"at, Graphen und Automaten''
[to 60th birthday of G. Wechsung, edited by J. Vogel, K. Wagner,
Jena, Germany, February 1999])

Dufourd C., Jancar P., Schnoebelen Ph.:
Boundedness of
Reset P/T Nets;
in Proc. ICALP'99
(Prague, Czech Rep., July 1999),
Lecture Notes in Computer Science , Vol. 1644,
Springer 1999, pp. 301310
The paper shows the exact frontier of (un)decidability
of boundedness for Petri nets with reset arcs;
for 2 arcs it is decidable (there is a `regular', or `semilinear'
witness), while for 3 arcs it is undecidable (reduction from
the `bounded space' problem for Minsky counter machines).

Jancar P., Moller F., Sawa Z.:
Simulation Problems for OneCounter Machines;
in Proc. SOFSEM'99 (Milovy, Czech Rep., November 1999),
Lecture Notes in Computer Science , Vol. 1725,
Springer 1999, pp. 404413
A short proof for the decidability of simulation preorder
of onecounter processes (without zerotests),
using a (nontrivial) modification of the `colouring
technique', is given (based on
Jancar P., Moller F.:
Simulation of OneCounter Nets via Colouring;
Uppsala CSD reports Rep. 159,
February 1999). In addition,
undecidability when allowing zero tests is shown.

Jancar P., Kucera A., Moller F.:
Simulation and bisimulation over onecounter processes;
in Proc. STACS 2000
(Lille, France, February 2000),
Lecture Notes in Computer Science , Vol. 1770,
Springer 2000, pp. 334345
A further elaboration of (bi)simulation problems for
onecounter processes. In particular, it shows an effective
construction of (a description of) the maximal simulation
relation for a given onecounter process without zero tests.

Sawa Z., Jancar P.:
Phardness of Equivalence Testing on Finite State Processes;
in Proc. SOFSEM'01
(Piestany, Slovakia, November 2001),
Lecture Notes in Computer Science , Vol. 2234,
Springer 2001, pp. 326335

Jancar P., Kucera A., Moller F., Sawa Z.:
EquivalenceChecking with OneCounter Automata: A Generic Method
for Proving Lower Bounds;
In: Nielsen, M., Engberg, U. (Eds.)
Foundations of Software Science and Computation Structures,
5th International Conference, FOSSACS 2002.
Grenoble, France, April 812, 2002, Proceedings.
Lecture Notes in Computer Science . Volume. 2303, Springer 2002,
pp. 172186

Jancar P.:
Strong Bisimilarity on Basic Parallel Processes is
PSPACEcomplete;
In Proceedings 18th LiCS (Logic in Computer Science),
(Ottawa, Canada, June 2003), IEEE Computer Society, 2003,
pp. 218227
A new technique (of DDfunctions)
is introduced, which enables to show that bisimilarity
for Basic Parallel Processes is in PSPACE.

Jancar P., Kucera A., Moller F.:
Deciding Bisimilarity between BPA and BPP Processes;
In: Amadio, R., Lugiez, D. (Eds.)
CONCUR 2003  Concurrency theory
(14th International Conference).
Marseille, France, September 2003, Proceedings.
Lecture Notes in Computer Science .
Volume. 2761, Springer 2003,
pp. 159173
Using a new technique (of DDfunctions) recently used for BPP
(Basic Parallel Processes),
and an additional insight for BPAprocesses, the decidability result
in the title is established.

Jancar P., Srba J.:
Highly Undecidable Questions for Process Algebras.
In Proceedings of 3rd IFIP International Conference on
Theoretical Computer Science (TCS'04).
(Toulouse, France, August 2004).
Kluwer Academic Publishers 2004.
pp. 507520

Mark Schaefer, Walter Vogler, Petr Jancar:
Determinate STG Decomposition of Marked Graphs.
In Proc:
Applications and Theory of Petri Nets 2005
26th International Conference, ICATPN 2005, Miami, FL, June 2025, 2005,
Series: Lecture Notes in Computer Science, Vol. 3536
Ciardo, Gianfranco; Darondeau, Philippe (Eds.)
Springer Verlag 2005,
p. 365  384

Jancar P., Srba J.:
Undecidability Results for Bisimilarity on Prefix
Rewrite Systems;
in Aceto, L., Ingolfsdottir, A. (Eds.)
Foundations of Software Science and Computation Structures,
9th International Conference, FOSSACS 2006.
Vienna, Austria, March 2006, Proceedings.
Lecture Notes in Computer Science. Volume 3921, Springer 2006,
pp. 277291

J. Esparza and P. Jancar and A. Miller:
On the Complexity of Consistency and Complete State
Coding for Signal Transition Graphs;
in Proceedings of the 6th International Conference on Application
of Concurrency to System Design (ACSD 2006). Turku, Finland, June
2006, IEEE Computer Society 2006, pp. 4756
Publications in other conferences and workshops

Jancar P.: Fairness in Petri nets;
in Proc. SOFSEM'88, Malenovice, pp.2730, November 1988. (In
Czech)

Jancar P.: A proof of halting under fairness
constraints; in Proc. SOFSEM'89, Zdiar, pp.3538,
Nov.1989. (In Czech)

Jancar P.: PSPACEcompleteness of the reachability
problem for deterministic Petri nets; in Proc. SOFSEM'90,
Janske Lazne, pp.4144, November 1990. (In Czech)

Jancar P., Mraz F., Platek M.: Forgetting automata and the
Chomsky hierarchy; in Proc. SOFSEM'92, Zdiar, pp. 4144,
November 1992.

Jancar P.: Bisimilarity on InfiniteState Systems; in Proc.
SOFSEM'93, Hrdonov, Czech Rep., pp. 3740, November 1993

Jancar P.: On a decidability border for temporal logics on
Petri nets; in Proc.
SOFSEM'94, Milovy, Czech Rep., pp. 3944, November 1994.

Jancar P., Mraz F., Platek M., Prochazka M., Vogel J.:
Restarting automata, Marcus grammars and contextfree languages;
in Dassow J., Rozenberg G., Salomaa A. (eds.):
Developments
in language theory II, World Scientific 1996, pp. 102111
A revised version of the paper presented at the conference
Developments in Language Theory
(DiLT) 1995, Magdeburg, Germany, July 1995

Jancar P., Mraz F., Platek M., Prochazka M., Vogel J.:
Deleting automata with a restart operation;
in Proc.
Developments in Language Theory
(DiLT) 1997 (ed. S. Bozapalidis), Aristotle Univ. Thessaloniki,
Greece, July 1997, pp. 191202

Jancar P., Mraz F., Platek M., Vogel J.:
On monotony for restarting automata;
in Proc. of the MFCS'98 workshop `Mathematical linguistics' (ed.
M. Kudlek), as Report FBIHHB213/98, Univ. Hamburg, Juli 1998,
pp. 7183

Jancar P., Moller F.:
Simulation of OneCounter Nets via Colouring;
in Proc. of the workshop Journees Systemes Infinis
(ed. A. Finkel), LSV ENS Cachan, France,
November 1998

Jancar P., Kot M.:
Bisimilarity on normed Basic Parallel
Processes can be decided in time $O(n^3)$;
in Proc. of the Third Intern. Workshop
on Automated Verification of InfiniteState Systems  AVIS'04
(affiliated with ETAPS'04), Barcelona, Spain, April 2004

Platek M., Jancar P.:
Linear list automata with a lookahead window;
in Workshop Formale Methoden der Linguistik und 14.
Theorietag Automaten und Formale Sprachen.
Preprint 2/2004, Institut f\"ur Informatik,
Universit\"at Potsdam, 2004.
Further papers (with content not covered
in the above publications)
Editorship

Jancar P., Kretinsky M.:
Proceedings of the MFCS'98 Workshop on Concurrency,
Electronic Notes in Theoretical Computer Science
18, 1998 (2000)
http://www.elsevier.nl/locate/entcs/volume18.html

Brim, L.; Jancar, P.; Kretinsky, M.; Kucera, A. (Eds.):
CONCUR 2002  Concurrency Theory,
13th International Conference, Brno, Czech Republic,
August 2023, 2002. Proceedings,
Lecture Notes in Computer Science. Volume. 2421,
Springer 2002
Theses

Jancar P.: /in Czech/ Mathematical theory of categorial grammars;
Master thesis, Charles Univ., Prague, April 1982

Jancar P.: /in Czech/ Decidability questions for some Petri net
dynamic properties; Ph.D. thesis, Charles Univ. Prague,
September 1987

Jancar P.:
Decidability Questions for Equivalences on Petri Nets;
Habilitation thesis, Faculty of Informatics, Masaryk University,
Brno, April 1995
Important Notes:
 The copyrights for journal and conference proceedings papers
generally belong to the publisher of the journal or proceedings. All
papers may be downloaded for personal or research purposes only.
 The provided files might be modified,
not corresponding precisely to the referenced version.
 If you have any trouble with downloading, or you request
something nonaccessible here, send me email to
Petr.Jancar@vsb.cz .