Improved Algorithm for Reachability in $d$-VASS
<|reference_start|>Improved Algorithm for Reachability in $d$-VASS: 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).<|reference_end|>
@article{fu2024improved,
    title={Improved Algorithm for Reachability in $d$-VASS},
    author={Yuxi Fu, Qizhe Yang, Yangluo Zheng},
    journal={arXiv preprint arXiv:2404.14781},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.14781},
    primaryClass={cs.LO cs.FL}
}