Paper Info
Title
Reachability in Two-Dimensional Vector Addition Systems with States is PSPACE-complete.
Abstract
Known to be decidable since 1981, there still remains a huge gap between the best known lower and upper bounds for the reach ability problem for vector addition systems with states (VASS). Here the problem is shown PSPACE-complete in the two-dimensional case, vastly improving on the doubly exponential time bound established in 1986 by Howell, Rosier, Huynh and Yen. Cover ability and bounded ness for two-dimensional VASS are also shown PSPACE-complete, and reach ability in two-dimensional VASS and in integer VASS under unary encoding are considered.
Year
DOI
Venue
2014
10.1109/LICS.2015.14
Logic in Computer Science
Keywords
Field
DocType
Parikh images,bounded regular languages,reachability,semi-linear sets,vector addition systems with states
Integer,Discrete mathematics,Combinatorics,Exponential function,Unary operation,PSPACE-complete,Reachability,Decidability,Mathematics,Encoding (memory),Bounded function
Journal
Volume
ISSN
Citations 
abs/1412.4259
1043-6871
12
PageRank 
References 
Authors
0.62
13
5
Name
Order
Citations
PageRank
Michael Blondin1279.06
Alain Finkel2263.30
Stefan Göller314815.10
Christoph Haase414612.94
P. McKenzie51528.23