# Reachability in Vector Addition Systems is Primitive-Recursive in Fixed Dimension

arXiv: https://arxiv.org/abs/1903.08575 · HTML: https://mlsanity.com/paper/1903.08575/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Mar 2019.

## Built on by (most cited first, 5 of 5)

- [Improved Ackermannian lower bound for the Petri nets reachability problem](https://mlsanity.com/paper/2105.08551/) (2021)
- [Detailed Balanced Chemical Reaction Networks as Generalized Boltzmann Machines](https://mlsanity.com/paper/2205.06313/) (2022)
- [Bi-reachability in Petri nets with data](https://mlsanity.com/paper/2405.16176/) (2024)
- [Reachability in Symmetric VASS](https://mlsanity.com/paper/2506.23578/) (2025)
- [Reachability in 3-VAS](https://mlsanity.com/paper/2608.04786/) (2026)

## Abstract (arXiv)

The reachability problem in vector addition systems is a central question, not only for the static verification of these systems, but also for many inter-reducible decision problems occurring in various fields. The currently best known upper bound on this problem is not primitive-recursive, even when considering systems of fixed dimension. We provide significant refinements to the classical decomposition algorithm of Mayr, Kosaraju, and Lambert and to its termination proof, which yield an ACKERMANN upper bound in the general case, and primitive-recursive upper bounds in fixed dimension. While this does not match the currently best known TOWER lower bound for reachability, it is optimal for related problems.