Reachability in two-dimensional vector addition systems with states is PSPACE-complete

DOI10.1109/LICS.2015.14MaRDI QIDQ4635789zbMATH OpenWikidataFDO

Authors Michael Blondin, Stefan Göller, Christoph Haase, Pierre McKenzie, Alain Finkel

Publication date 23 April 2018

Published in 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.4259

zbMATH Keywords

computational complexitydecidabilityreachability analysis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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)

Abstract: Determining the complexity of the reachability problem for vector addition systems with states (VASS) is a long-standing open problem in computer science. Long known to be decidable, the problem to this day lacks any complexity upper bound whatsoever. In this paper, reachability for two-dimensional VASS is shown PSPACE-complete. This improves on a previously known doubly exponential time bound established by Howell, Rosier, Huynh and Yen in 1986. The coverability and boundedness problems are also noted to be PSPACE-complete. In addition, some complexity results are given for the reachability problem in two-dimensional VASS and in integer VASS when numbers are encoded in unary.

Recommendations

• The Reachability Problem for Two-Dimensional Vector Addition Systems with States
• Reachability in two-dimensional unary vector addition systems with states is NL-complete
• Polynomial vector addition systems with states
• Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states
• Z-reachability problem for games on 2-dimensional vector addition systems with states is in P

Cited in

(37)

• Multi-Dimensional Long-Run Average Problems for Vector Addition Systems with States
• scientific article; zbMATH DE number 7559503 (Why is no real title available?)
• Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states
• Completeness results for conflict-free vector replacement systems
• Z-reachability problem for games on 2-dimensional vector addition systems with states is in P
• The reachability problem for branching vector addition systems requires doubly-exponential space
• Complexity analysis of the backward coverability algorithm for VASS
• Reachability in two-dimensional unary vector addition systems with states is NL-complete
• When reachability meets Grzegorczyk
• On the complexity of resource-bounded logics
• scientific article; zbMATH DE number 7561336 (Why is no real title available?)
• Z-reachability problem for games on 2-dimensional vector addition systems with states is in P
• Polynomial-space completeness of reachability for succinct branching VASS in dimension one
• Integer vector addition systems with states
• Reachability problem for polynomial iteration is PSPACE-complete
• Forward analysis and model checking for trace bounded WSTS
• On the coverability problem for pushdown vector addition systems in one dimension
• Querying best paths in graph databases
• On decidability and complexity of low-dimensional robot games
• Affine extensions of integer vector addition systems with states
• CONCUR 2004 - Concurrency Theory
• Trace inclusion for one-counter nets revisited
• New pumping technique for 2-dimensional VASS
• Regular separability of one counter automata
• scientific article; zbMATH DE number 7559493 (Why is no real title available?)
• Strategic reasoning with a bounded number of resources: the quest for tractability
• Coverability in 2-VASS with one unary counter is in NP
• The geometry of reachability in continuous vector addition systems with states
• Lower bounds for the reachability problem in fixed dimensional VASSes
• scientific article; zbMATH DE number 7559504 (Why is no real title available?)
• Projections of vector addition system reachability sets are semilinear
• The Reachability Problem for Two-Dimensional Vector Addition Systems with States
• scientific article; zbMATH DE number 7649936 (Why is no real title available?)
• Polynomial vector addition systems with states
• The complexity of reachability in affine vector addition systems with states
• Deterministic weighted automata under partial observability
• scientific article; zbMATH DE number 1759422 (Why is no real title available?)

This page was built for publication: Reachability in two-dimensional vector addition systems with states is PSPACE-complete

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