Reachability in Vector Addition Systems is Ackermann-complete

2021/04/28 by Czerwiński, Wojciech, Orlikowski, Łukasz · 9 citations
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.2104.13866

Abstract

Vector Addition Systems and equivalent Petri nets are a well established models of concurrency. The central algorithmic problem for Vector Addition Systems with a long research history is the reachability problem asking whether there exists a run from one given configuration to another. We settle its complexity to be Ackermann-complete thus closing the problem open for 45 years. In particular we prove that the problem is F_k-hard for Vector Addition Systems with States in dimension 6k, where F_k is the k-th complexity class from the hierarchy of fast-growing complexity classes.

Cited by

• General Decidability Results for Systems with Continuous Counters
• A Note on the Parameterised Complexity of Coverability in Vector Addition Systems
• History-Constrained Systems
• Polynomial Equivalence of Extended Chemical Reaction Models
• Continuous Petri Nets for Fast Yield Computation: Polynomial-Time and MILP Approaches
• Box-Reachability in Vector Addition Systems
• Reasoning about Rare-Event Reachability in Stochastic Vector Addition Systems via Affine Vector Spaces
• Algebraic Closure of Matrix Sets Recognized by 1-VASS
• Reachability in symmetric VASS

Related

• Improved Ackermannian lower bound for the Petri nets reachability\n problem
• Reachability in fixed dimension vector addition systems with states
• Reachability and Related Problems in Vector Addition Systems with Nested Zero Tests
• New Lower Bounds for Reachability in Vector Addition Systems
• Geometry of Reachability sets of Vector Addition Systems