Revisiting Ackermann-hardness for lossy counter machines and reset Petri nets. (English) Zbl 1287.68059

Schnoebelen, Philippe

Hliněný, Petr (ed.) et al., Mathematical foundations of computer science 2010. 35th international symposium, MFCS 2010, Brno, Czech Republic, August 23–27, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-15154-5/pbk). Lecture Notes in Computer Science 6281, 616-628 (2010).

Summary: We prove that coverability and termination are not primitive-recursive for lossy counter machines and for reset Petri nets.
For the entire collection see [Zbl 1194.68039].

MSC:

68Q17	Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q05	Models of computation (Turing machines, etc.) (MSC2010)
68Q85	Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)