Complexity analysis of the backward coverability algorithm for VASS

DOI10.1007/978-3-642-24288-5_10MaRDI QIDQ3172868zbMATH OpenOpenAlexFDO

Authors Laura Bozzelli, Pierre Ganty

Publication date 7 October 2011

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-24288-5_10

zbMATH Keywords

vector addition system with states

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• The ideal view on Rackoff's coverability technique
• The ideal view on Rackoff's coverability technique
• Efficient Algorithms for Asymptotic Bounds on Termination Time in VASS
• Reachability in two-dimensional vector addition systems with states is PSPACE-complete
• A polynomial-time algorithm for reachability in branching VASS in dimension one

Cited in

(12)

• Regular separators for VASS coverability languages
• The ideal view on Rackoff's coverability technique
• A lower bound for the coverability problem in acyclic pushdown VAS
• Ratio and weight quantiles
• Regular separability of well-structured transition systems
• The ideal view on Rackoff's coverability technique
• On the length of strongly monotone descending chains over \(\mathbb{N}^d\)
• Coverability in VASS revisited: improving Rackoff's bounds to obtain conditional optimality
• Automatic WSTS-based repair and deadlock detection of parameterized systems
• Data flow analysis of asynchronous systems using infinite abstract domains
• Verification of Immediate Observation Population Protocols
• Deciding fast termination for probabilistic VASS with nondeterminism

This page was built for publication: Complexity analysis of the backward coverability algorithm for VASS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3172868)