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

reachabilityPetri netssemilinear setsvector addition systems with stateslinear path schemes

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

(21)

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

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)