Polynomial vector addition systems with states

DOI10.4230/LIPICS.ICALP.2018.134MaRDI QIDQ5002821zbMATH OpenFDO

Authors Jérôme Leroux

Publication date 28 July 2021

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2018.134

zbMATH Keywords

formal verificationinfinite-state systemKosaraju-Sullivan algorithmlinear algebrareachability problemvector additions system with states

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Reachability in two-dimensional vector addition systems with states is PSPACE-complete
• When reachability meets Grzegorczyk
• The polynomial complexity of vector addition systems with states
• Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states
• The Reachability Problem for Two-Dimensional Vector Addition Systems with States

Cites work

• A structure to decide reachability in Petri nets
• An Algorithm for the General Petri Net Reachability Problem
• Analyzing Reachability for Some Petri Nets With Fast Growing Markings
• Bounds on Positive Integral Solutions of Linear Diophantine Equations
• Demystifying Reachability in Vector Addition Systems
• scientific article; zbMATH DE number 1302047 (Why is no real title available?)
• scientific article; zbMATH DE number 559221 (Why is no real title available?)
• Minimal solutions of linear diophantine systems : bounds and algorithms
• On the reachability problem for 5-dimensional vector addition systems
• The Complexity of the Finite Containment Problem for Petri Nets
• The covering and boundedness problems for vector addition systems

Cited in

(25)

• Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states
• Reachability problem for polynomial iteration is PSPACE-complete
• The polynomial complexity of vector addition systems with states
• Co-finiteness and co-emptiness of reachability sets in vector addition systems with states
• Catching a structural bug with a flower
• Reachability in register machines with polynomial updates
• Alternating vector addition systems with states
• Deciding fast termination for probabilistic VASS with nondeterminism
• Integer vector addition systems with states
• On selective unboundedness of VASS
• The reachability problem for branching vector addition systems requires doubly-exponential space
• Balanced State Representations with Polynomial Algebra
• Reachability in two-dimensional vector addition systems with states is PSPACE-complete
• Reachability in two-dimensional unary vector addition systems with states is NL-complete
• Vector addition system reversible reachability problem
• Affine extensions of integer vector addition systems with states
• Multi-Dimensional Long-Run Average Problems for Vector Addition Systems with States
• When reachability meets Grzegorczyk
• The complexity of reachability in affine vector addition systems with states
• Exhibition of a structural bug with wings
• Co-finiteness and co-emptiness of reachability sets in vector addition systems with states
• Long-Run Average Behavior of Vector Addition Systems with States
• Fast termination and workflow nets
• The geometry of reachability in continuous vector addition systems with states
• Asymptotic complexity estimates for probabilistic programs and their VASS abstractions

This page was built for publication: Polynomial vector addition systems with states

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