×

zbMATH — the first resource for mathematics

Coverability Is undecidable in one-dimensional pushdown vector addition systems with resets. (English) Zbl 07121146
Filiot, Emmanuel (ed.) et al., Reachability problems. 13th international conference, RP 2019, Brussels, Belgium, September 11–13, 2019. Proceedings. Cham: Springer (ISBN 978-3-030-30805-6/pbk; 978-3-030-30806-3/ebook). Lecture Notes in Computer Science 11674, 193-201 (2019).
Summary: We consider the model of pushdown vector addition systems with resets. These consist of vector addition systems that have access to a pushdown stack and have instructions to reset counters. For this model, we study the coverability problem. In the absence of resets, this problem is known to be decidable for one-dimensional pushdown vector addition systems, but decidability is open for general pushdown vector addition systems. Moreover, coverability is known to be decidable for reset vector addition systems without a pushdown stack. We show in this note that the problem is undecidable for one-dimensional pushdown vector addition systems with resets.
For the entire collection see [Zbl 1419.68007].
MSC:
68Qxx Theory of computing
PDF BibTeX XML Cite
Full Text: DOI