The Reachability Problem for Two-Dimensional Vector Addition Systems with States

DOI10.1145/3464794MaRDI QIDQ5056423zbMATH OpenOpenAlexFDO

Authors Michael Blondin, Matthias Englert, Stefan Göller, Christoph Haase, Ranko Lazić, Pierre McKenzie, Patrick Totzke, Alain Finkel

Publication date 8 December 2022

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3464794

zbMATH Keywords

linear path schemesPetri netsreachabilitysemilinear setsvector addition systems with states

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• scientific article; zbMATH DE number 7559504
• scientific article; zbMATH DE number 7559493
• Reachability in two-dimensional vector addition systems with states is PSPACE-complete
• scientific article; zbMATH DE number 4035164
• scientific article; zbMATH DE number 3878366
• The complexity of reachability in affine vector addition systems with states
• scientific article; zbMATH DE number 7407775
• Reachability in two-dimensional unary vector addition systems with states is NL-complete
• scientific article; zbMATH DE number 4092784
• Vector addition system reachability problem: a short self-contained proof

Cited in

(25)

• Vector and scalar reachability problems in \(\operatorname{SL}(2, \mathbb{Z})\)
• Vector Addition System Reversible Reachability Problem
• scientific article; zbMATH DE number 6000698 (Why is no real title available?)
• Z-reachability problem for games on 2-dimensional vector addition systems with states is in P
• 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
• Z-reachability problem for games on 2-dimensional vector addition systems with states is in P
• Polynomial vector addition systems with states
• Multi-Dimensional Long-Run Average Problems for Vector Addition Systems with States
• New pumping technique for 2-dimensional VASS
• scientific article; zbMATH DE number 7407775 (Why is no real title available?)
• Coverability in 2-VASS with one unary counter is in NP
• Dimension-minimality and primality of counter nets
• Lower bounds for the reachability problem in fixed dimensional VASSes
• Invariants for one-counter automata with disequality tests
• Improved algorithm for reachability in d-VASS
• Coverability in VASS revisited: improving Rackoff's bounds to obtain conditional optimality
• Reachability in restricted chemical reaction networks
• Monus semantics in vector addition systems with states
• The geometry of reachability in continuous vector addition systems with states
• Linear reachability problems and minimal solutions to linear Diophantine equation systems
• Box-reachability in vector addition systems
• On the reachability problem for two-dimensional branching VASS
• Galois energy games: to solve all kinds of quantitative reachability problems
• Reachability in vector addition system with states parameterized by geometric dimension

This page was built for publication: The Reachability Problem for Two-Dimensional Vector Addition Systems with States

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