# Improved Algorithm for Reachability in d-VASS

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Apr 2024.

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

- [Reachability in Symmetric VASS](https://mlsanity.com/paper/2506.23578/) (2025)

## Abstract (arXiv)

An mathsfFd upper bound for the reachability problem in vector addition systems with states (VASS) in fixed dimension is given, where mathsfFd is the d-th level of the Grzegorczyk hierarchy of complexity classes. The new algorithm combines the idea of the linear path scheme characterization of the reachability in the 2-dimension VASSes with the general decomposition algorithm by Mayr, Kosaraju and Lambert. The result improves the mathsfFd + 4 upper bound due to Leroux and Schmitz (LICS 2019).