On the Coverability Problem for Pushdown Vector Addition Systems in One Dimension

DOI10.1007/978-3-662-47666-6_26zbMath1440.68177arXiv1503.04018OpenAlexW1506909315MaRDI QIDQ3449486

Grégoire Sutre, Jérôme Leroux, Patrick Totzke

Publication date: 4 November 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1503.04018

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items (10)

On the Coverability Problem for Pushdown Vector Addition Systems in One Dimension ⋮ Unnamed Item ⋮ A lower bound for the coverability problem in acyclic pushdown VAS ⋮ The emptiness problem for valence automata over graph monoids ⋮ Coverability in 2-VASS with one unary counter is in NP ⋮ Recent advances on reachability problems for valence systems (invited talk) ⋮ Unboundedness Problems for Languages of Vector Addition Systems. ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the Boundedness Problem for Higher-Order Pushdown Vector Addition Systems

Cites Work

• Unnamed Item
• The covering and boundedness problems for vector addition systems
• Automatic verification of recursive procedures with one integer parameter.
• The covering and boundedness problems for branching vector addition systems
• Semigroups, Presburger formulas, and languages
• Alternating Vector Addition Systems with States
• Nonelementary Complexities for Branching VASS, MELL, and Extensions
• On the Coverability Problem for Pushdown Vector Addition Systems in One Dimension
• Hyper-Ackermannian bounds for pushdown vector addition systems
• Reachability in Two-Dimensional Vector Addition Systems with States Is PSPACE-Complete
• Reachability in Petri Nets with Inhibitor Arcs
• CONCUR 2004 - Concurrency Theory
• Vector addition system reachability problem

This page was built for publication: On the Coverability Problem for Pushdown Vector Addition Systems in One Dimension