Improved Algorithm for Reachability in $d$-VASS

Abstract

An ${\mathsf{F}}_d$ upper bound for the reachability problem in vector addition systems with states (VASS) in fixed dimension is given, where ${\mathsf{F}}_d$ 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 ${\mathsf{F}}_{d+4}$ upper bound due to Leroux and Schmitz (LICS 2019).

36 pages