zbMATH — the first resource for mathematics

The reachability problem for vector addition system with one zero-test. (English) Zbl 1343.68160
Murlak, Filip (ed.) et al., Mathematical foundations of computer science 2011. 36th international symposium, MFCS 2011, Warsaw, Poland, August 22–26, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-22992-3/pbk). Lecture Notes in Computer Science 6907, 145-157 (2011).
Summary: We consider here a variation of Vector Addition Systems where one counter can be tested for zero, extending the reachability proof by Leroux for Vector Addition System to our model. This provides an alternate, and hopefully simpler to understand, proof of the reachability problem that was originally proved by Reinhardt.
For the entire collection see [Zbl 1219.68020].

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