A lower bound for the coverability problem in acyclic pushdown VAS
From MaRDI portal
Publication:2656343
DOI10.1016/j.ipl.2020.106079MaRDI QIDQ2656343
Ranko Lazić, Matthias Englert, Juliusz Straszyński, Piotr Hofman, Jérôme Leroux, Sławomir Lasota
Publication date: 11 March 2021
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: http://wrap.warwick.ac.uk/146756/1/WRAP-lower-bound-coverability-problem-acyclic-pushdown-VAS-Englert-2021.pdf
context-free grammars; theory of computation; one-counter machines; coverability problem; pushdown vector addition systems
68Qxx: Theory of computing
Related Items
Coverability in 2-VASS with one unary counter is in NP, Flat Petri nets (invited talk), Recent advances on reachability problems for valence systems (invited talk)
Cites Work
- The complexity of membership problems for circuits over sets of integers
- On boundedness problems for pushdown vector addition systems
- What makes Petri nets harder to verify: stack or data?
- Coverability Is undecidable in one-dimensional pushdown vector addition systems with resets
- On the Coverability Problem for Pushdown Vector Addition Systems in One Dimension
- Hyper-Ackermannian bounds for pushdown vector addition systems
- The reachability problem for Petri nets is not elementary