Reachability in Two-Dimensional Vector Addition Systems with States Is PSPACE-Complete

DOI10.1109/LICS.2015.14zbMath1401.68095arXiv1412.4259MaRDI QIDQ4635789

Michael Blondin, Pierre McKenzie, Stefan Göller, Christoph Haase, 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) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (17)

Forward analysis and model checking for trace bounded WSTS ⋮ On the Coverability Problem for Pushdown Vector Addition Systems in One Dimension ⋮ Trace inclusion for one-counter nets revisited ⋮ Unnamed Item ⋮ Coverability in 2-VASS with one unary counter is in NP ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Strategic reasoning with a bounded number of resources: the quest for tractability ⋮ On decidability and complexity of low-dimensional robot games ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the complexity of resource-bounded logics ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Multi-Dimensional Long-Run Average Problems for Vector Addition Systems with States ⋮ Unnamed Item

This page was built for publication: Reachability in Two-Dimensional Vector Addition Systems with States Is PSPACE-Complete