Improved Algorithm for Reachability in $d$-VASS

Document detail

ID

oai:arXiv.org:2404.14781

Topic

Computer Science - Logic in Comput... Computer Science - Formal Language...

Author

Fu, Yuxi Yang, Qizhe Zheng, Yangluo

Year

2024

listing date

5/1/2024

Keywords

science computer algorithm

Metrics

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).

;Comment: 36 pages

Fu, Yuxi,Yang, Qizhe,Zheng, Yangluo, 2024, Improved Algorithm for Reachability in $d$-VASS