Reachability is Tower Complete

Abstract

A complete characterization of the complexity of the reachability problem for vector addition system has been open for a long time. The problem is shown to be Tower complete.

arXiv commentWe apply to with draw this paper because there is a fatal error. At the moment we do not know how correct the mistake

References in corpus (3)

• Reachability in Vector Addition Systems is Primitive-Recursive in Fixed Dimension
• The General Vector Addition System Reachability Problem by Presburger Inductive Invariants
• Complexity Bounds for Ordinal-Based Termination