Technical Reports

A List by Author: Petr Janèar

e-mail:

jancar(a)osu.cz

Reachability Games on Extended Vector Addition Systems with States

by Tomá¹ Brázdil, Petr Janèar, Antonín Kuèera, A full version of the paper presented at ICALP 2010. February 2010, 38 pages.

FIMU-RS-2010-02. Available as Postscript, PDF.

Abstract:

We consider two-player turn-based games with zero-reachability and zero-safety objectives generated by extended vector addition systems with states. Although the problem of deciding the winner in such games is undecidable in general, we identify several decidable and even tractable subcases of this problem obtained by restricting the number of counters and/or the sets of target configurations.

MFCS`98 Workshop on Concurrency - Preproceedings

by Petr Janèar, Mojmír Køetínský, Pre-proceedings of the MFCS`98 Workshop on Concurrency (the PS file is NOT provided, as it is too large (approx. 30MB); take pdf (3.5 MB) instead). July 1998, 209 pages.

FIMU-RS-98-06. Available as Postscript, PDF.

Abstract:

This volume contains the pre-proceedings of the MFCS`98 Workshop on Concurrency, which took place in Brno, Czech Republic, August 27-29, 1998, as a satellite event of the 23rd international symposium on Mathematical Foundations of Computer Science. It is composed of two invited papers delivered by Javier Esparza (Munich) and Faron Moller (Uppsala), and of 17 contributed papers selected out of 24 submissions. The revised (and full) version of the proceedings should appear as a volume of Electronic Notes in Theoretical Computer Science (Elsevier).

Bisimulation Equivalence is Decidable for One-Counter Processes

by Petr Janèar, Accepted for presentation at the 24th International Colloquium on Automata, Languages, and Programming (ICALP`97). May 1997, 13 pages.

FIMU-RS-97-06. Available as Postscript, PDF.

Abstract:

It is shown that bisimulation equivalence is decidable for the processes generated by (nondeterministic) pushdown automata where the pushdown behaves like a counter, in fact. Also regularity, i.e. bisimulation equivalence with some finite-state process, is shown to be decidable for the mentioned processes.

Bisimilarity of Processes with Finite-state Systems

by Petr Janèar, Antonín Kuèera, These results will be presented at INFINITY`97 workshop. May 1997, 19 pages.

FIMU-RS-97-02. Available as Postscript, PDF.

Abstract:

We describe a general method for deciding bisimilarity for pairs of processes where one process has finitely many states. We apply this method to pushdown processes and to PA processes. We also demonstrate that the mentioned problem is undecidable for `state-extended` PA processes.