On selective unboundedness of VASS
From MaRDI portal
Publication:355513
DOI10.1016/j.jcss.2013.01.014zbMath1285.68094arXiv1011.0217MaRDI QIDQ355513
Publication date: 24 July 2013
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1011.0217
exponential space; place boundedness problem; regularity detection problem; vector addition systems with states
68Q60: Specification and verification (program logics, model checking, etc.)
Related Items
Unnamed Item, Unnamed Item, Unnamed Item, On the complexity of resource-bounded logics, Small vertex cover makes Petri net coverability and boundedness easier, Strategic reasoning with a bounded number of resources: the quest for tractability, Coverability Trees for Petri Nets with Unordered Data
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The residue of vector sets with applications to decidability problems in Petri nets
- An analysis of the nonemptiness problem for classes of reversal-bounded multicounter machines
- On the reachability problem for 5-dimensional vector addition systems
- Petri nets and regular languages
- Reduction and covering of infinite reachability trees
- A unified approach for deciding the existence of certain petri net paths
- A structure to decide reachability in Petri nets
- Reversal-bounded multipushdown machines
- The covering and boundedness problems for vector addition systems
- Lectures on Petri nets. 1: Basic models. Advances in Petri nets
- A multiparameter analysis of the boundedness problem for vector addition systems
- Counter machines and verification problems.
- Verifying programs with unreliable channels
- Small vertex cover makes Petri net coverability and boundedness easier
- Relationships between nondeterministic and deterministic tape complexities
- Parallel program schemata
- Taming Past LTL and Flat Counter Systems
- Modelchecking counting properties of 1-safe nets with buffers in paraPSPACE
- ON YEN'S PATH LOGIC FOR PETRI NETS
- Model Checking Coverability Graphs of Vector Addition Systems
- The Reachability Problem for Vector Addition System with One Zero-Test
- Decidability of LTL for Vector Addition Systems with One Zero-Test
- Mixing Coverability and Reachability to Analyze VASS with One Zero-Test
- Fast Acceleration of Ultimately Periodic Relations
- Reversal-Bounded Counter Machines Revisited
- On Yen’s Path Logic for Petri Nets
- An Algorithm for the General Petri Net Reachability Problem
- Bounds on Positive Integral Solutions of Linear Diophantine Equations
- Reversal-Bounded Multicounter Machines and Their Decision Problems
- An NP-complete number-theoretic problem
- Vector addition system reachability problem
- On Context-Free Languages
- Well-structured transition systems everywhere!