zbMATH — the first resource for mathematics

Undecidability of weak bisimulation equivalence for 1-counter processes. (English) Zbl 1039.68084
Baeten, Jos C. M. (ed.) et al., Automata, languages and programming. 30th international colloquium, ICALP 2003, Eindhoven, The Netherland, June 30 – July 4, 2003. Proceedings. Berlin: Springer (ISBN 3-540-40493-7/pbk). Lect. Notes Comput. Sci. 2719, 570-583 (2003).
Summary: We show that checking weak bisimulation equivalence of 1-counter nets (Petri nets with only one unbounded place) is undecidable. This implies the undecidability of weak bisimulation equivalence for 1-counter machines. The undecidability result carries over to normed 1-counter nets/machines.
For the entire collection see [Zbl 1029.00041].

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
Full Text: Link