Regarding electronic versions, i.e. (g-zipped) postscript files or pdf-files, 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.71-93 (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.253-265 (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.67-74
• Jancar P.: Undecidability of Bisimilarity for Petri Nets and Related Problems; Theoretical Computer Science 148, 1995, pp.281-301 (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 context-free languages; Acta Informatica 33, 1996, pp.409-420 (Springer-Verlag)
• Jancar P., Kucera A.: Bisimilarity of processes with finite-state 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. 476--503 (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. 287--312 (Univ. Magdeburg)
• Jancar P.: A note on well quasi-orderings for powersets; Information Processing Letters 72, 1999, pp. 155-160 (Elsevier)
• Jancar P.: Decidability of bisimilarity for one-counter processes; Information and Computation 158, 2000, pp. 1-17 (Academic Press)

  The paper deals with one-counter 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.: Non-primitive recursive complexity and undecidability for Petri net equivalences; Theoretical Computer Science 256, 2001, pp. 23--30 (Elsevier)

  The paper recalls undecidability of all action based behavioural equivalences for labelled place/transition Petri nets

  (Jancar P.: All action-based behavioural equivalences are undecidable for labelled Petri nets; Bull. of EATCS, No. 56, June 1995, pp.86--88),

  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 bisimulation-like equivalences with finite-state processes; Theoretical Computer Science 258, 2001, pp. 409--433 (Elsevier)

  The paper studies a general approach to (bisimulation-like) equivalences (of possibly infinite state processes) with finite-state processes. (A preliminary version appeared in Proc. ICALP'98.)

• Jancar P., Kucera A., Moller F., Sawa Z.: DP lower bounds for equivalence-checking and model-checking of one-counter automata; Information and Computation Vol. 188 (2004), pp. 1--19 (Elsevier, Academic Press)

  (A preliminary version appeared at FOSSACS'02.)

• Sawa Z., Jancar P.: Behavioural Equivalences on Finite-State Systems are PTIME-hard; 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 P-hardness result for bisimilarity to the whole range of relations between bisimilarity and trace preorder.

• Kucera A., Jancar P.: Equivalence-checking on infinite-state systems: Techniques and results; in the journal Theory and Practice of Logic Programming (Cambridge University Press), 6(3):227-264, 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.119-136

(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.99--127, 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. 30--45
• 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 22-29, 2002, Proceedings, Lecture Notes in Computer Science . Volume. 2540, Springer 2002, pp. 41--73

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.446-457
• Howell R., Jancar P., Rosier L.: Single-path 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.202-210
• Jancar P., Mraz F., Platek M.: Characterization of context-free languages by erasing automata; in Proc. MFCS 1992, Prague, August 1992, Lecture Notes in Computer Science, Vol. 629, Springer 1992, pp.307-314
• 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.527-536
• 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.581-592
• 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.349-363
• 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.348-362
• 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.283-292
• 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.478-489
• Jancar P.: Bisimulation equivalence is decidable for one-counter processes; in Proc. ICALP'97, Bologna, Italy, July 1997, Lecture Notes in Computer Science, Vol. 1256, Springer 1997, pp. 549-559
• 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. 505-512
• Jancar P., Kucera A., Mayr R.: Deciding bisimulation-like equivalences with finite-state processes; in Proc. ICALP'98, Aalborg, Denmark, July 1998, Lecture Notes in Computer Science , Vol. 1443, Springer 1998, pp. 200-211
• Jancar P., Mraz F., Platek M., Vogel J.: Different types of monotonicity for restarting automata; in Proc. FST-and-TCS'98, Chennai, India, December 1998, Lecture Notes in Computer Science, Vol. 1530, Springer 1998, pp. 343--354

  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. 301--310

  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 One-Counter Machines; in Proc. SOFSEM'99 (Milovy, Czech Rep., November 1999), Lecture Notes in Computer Science , Vol. 1725, Springer 1999, pp. 404-413

  A short proof for the decidability of simulation preorder of one-counter processes (without zero-tests), using a (nontrivial) modification of the `colouring technique', is given (based on Jancar P., Moller F.: Simulation of One-Counter 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 one-counter processes; in Proc. STACS 2000 (Lille, France, February 2000), Lecture Notes in Computer Science , Vol. 1770, Springer 2000, pp. 334-345

  A further elaboration of (bi)simulation problems for one-counter processes. In particular, it shows an effective construction of (a description of) the maximal simulation relation for a given one-counter process without zero tests.

• Sawa Z., Jancar P.: P-hardness 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. 326--335

• Jancar P., Kucera A., Moller F., Sawa Z.: Equivalence-Checking with One-Counter 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 8-12, 2002, Proceedings. Lecture Notes in Computer Science . Volume. 2303, Springer 2002, pp. 172--186
• Jancar P.: Strong Bisimilarity on Basic Parallel Processes is PSPACE-complete; In Proceedings 18th LiCS (Logic in Computer Science), (Ottawa, Canada, June 2003), IEEE Computer Society, 2003, pp. 218--227

  A new technique (of DD-functions) 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. 159--173

  Using a new technique (of DD-functions) recently used for BPP (Basic Parallel Processes), and an additional insight for BPA-processes, 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. 507--520
• 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 20-25, 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. 277-291
• 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. 47--56

Publications in other conferences and workshops

• Jancar P.: Fairness in Petri nets; in Proc. SOFSEM'88, Malenovice, pp.27-30, November 1988. (In Czech)
• Jancar P.: A proof of halting under fairness constraints; in Proc. SOFSEM'89, Zdiar, pp.35-38, Nov.1989. (In Czech)
• Jancar P.: P-SPACE-completeness of the reachability problem for deterministic Petri nets; in Proc. SOFSEM'90, Janske Lazne, pp.41-44, November 1990. (In Czech)
• Jancar P., Mraz F., Platek M.: Forgetting automata and the Chomsky hierarchy; in Proc. SOFSEM'92, Zdiar, pp. 41-44, November 1992.
• Jancar P.: Bisimilarity on Infinite-State Systems; in Proc. SOFSEM'93, Hrdonov, Czech Rep., pp. 37-40, November 1993
• Jancar P.: On a decidability border for temporal logics on Petri nets; in Proc. SOFSEM'94, Milovy, Czech Rep., pp. 39-44, November 1994.
• Jancar P., Mraz F., Platek M., Prochazka M., Vogel J.: Restarting automata, Marcus grammars and context-free languages; in Dassow J., Rozenberg G., Salomaa A. (eds.): Developments in language theory II, World Scientific 1996, pp. 102-111

  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. 191--202
• 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 FBI-HH-B-213/98, Univ. Hamburg, Juli 1998, pp. 71-83
• Jancar P., Moller F.: Simulation of One-Counter 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 Infinite-State 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)

• Jancar P.: A concise proof of Commoner's theorem ( ps-file , pdf-file ); Petri Nets Newsletter No. 49, October 1995, p.43

  This note contains a 1-page proof of Commoner's Theorem for free-choice Petri nets.

• Jancar P.: Bouziane's transformation of the Petri net reachability problem and incorrectness of the related algorithm;

  I studied in detail a controversial paper by Z. Bouziane, which appeared in Proc. FOCS'98 and claimed to show a new (primitive recursive) algorithm for the Petri net reachability problem. Here you can find an explanation of Bouziane's approach and an exposition of its serious flaw.

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 20-23, 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 non-accessible here, send me email to Petr.Jancar@vsb.cz .