zbMATH — the first resource for mathematics

Lossy counter machines decidability cheat sheet. (English) Zbl 1287.68101
Kučera, Antonín (ed.) et al., Reachability problems. 4th international workshop, RP 2010, Brno, Czech Republic, August 28–29, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-15348-8/pbk). Lecture Notes in Computer Science 6227, 51-75 (2010).
Summary: Lossy counter machines (LCMs) are a variant of Minsky counter machines based on weak (or unreliable) counters in the sense that they can decrease nondeterministically and without notification. This model, introduced by R. Mayr [Theor. Comput. Sci. 297, No. 1–3, 337–354 (2003; Zbl 1044.68119)], is not yet very well known, even though it has already proven useful for establishing hardness results.
In this paper we survey the basic theory of LCMs and their verification problems, with a focus on the decidability/undecidability divide.
For the entire collection see [Zbl 1194.68049].

68Q45 Formal languages and automata
68Q60 Specification and verification (program logics, model checking, etc.)
Full Text: DOI