zbMATH — the first resource for mathematics

Reversal-bounded counter machines revisited. (English) Zbl 1173.68562
Ochmański, Edward (ed.) et al., Mathematical foundations of computer science 2008. 33rd international symposium, MFCS 2008, Toruń Poland, August 25–29, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-85237-7/pbk). Lecture Notes in Computer Science 5162, 323-334 (2008).
Summary: We extend the class of reversal-bounded counter machines by authorizing a finite number of alternations between increasing and decreasing mode over a given bound. We prove that extended reversal-bounded counter machines also have effective semi-linear reachability sets. We also prove that the property of being reversal-bounded is undecidable in general even when we fix the bound, whereas this problem becomes decidable when considering Vector Addition System with States.
For the entire collection see [Zbl 1154.68021].

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