A lower bound for the coverability problem in acyclic pushdown VAS

DOI10.1016/j.ipl.2020.106079OpenAlexW3112000701MaRDI 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

zbMATH Keywords

context-free grammarstheory of computationone-counter machinescoverability problempushdown vector addition systems

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (3)

Coverability in 2-VASS with one unary counter is in NP ⋮ Recent advances on reachability problems for valence systems (invited talk) ⋮ Flat Petri nets (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

This page was built for publication: A lower bound for the coverability problem in acyclic pushdown VAS