The Reachability Problem for Vector Addition Systems is Not Elementary

ABSTRACT. The reachability problem for Vector Addition Systems is currently known to be decidable (best upper bound is cubic-Ackermann) and ExpSpace-hard. We provide a better lower bound showing that in fact problem is not elementary. The construction is based on the observation that certain kind of fraction equations can have surprisingly involved solutions and Vector Addition Systems are able to implement that phenomenon.

Authors

• Wojciech Czerwiński

Keywords

No keywords are indexed for this paper.