zbMATH — the first resource for mathematics

Simulation and bisimulation over one-counter processes. (English) Zbl 0962.68121
Reichel, Horst (ed.) et al., STACS 2000. 17th annual symposium on Theoretical aspects of computer science. Lille, France, February 17-19, 2000. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1770, 334-345 (2000).
Summary: We show an effective construction of (a periodicity description of) the maximal simulation relation for a given one-counter net. Then we demonstrate how to reduce simulation problems over one-counter nets to analogous bisimulation problems over one-counter automata. We use this to demonstrate the decidability of various problems, specifically testing regularity and strong regularity of one-counter nets with respect to simulation equivalence, and testing simulation equivalence between a one-counter net and a deterministic pushdown automaton. Various obvious generalizations of these problems are known to be undecidable.
For the entire collection see [Zbl 0933.00044].

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)