3 papers
cs.FL2026
3-VASS Reachability is in EXPSPACE
Weijun Chen, Bo Fu, Yuxi Fu +4
A VASS can be viewed as a finite-state automaton manipulating a fixed number (called its dimension) of counters holding non-negative values. The reachability problem, asking whethe…
cs.LO2024
Improved Algorithm for Reachability in -VASS
Yuxi Fu, Qizhe Yang, Yangluo Zheng
An upper bound for the reachability problem in vector addition systems with states (VASS) in fixed dimension is given, where is the -th level of…
cs.FL2023
Reachability in 3-VASS is in Tower
Qizhe Yang, Yuxi Fu
The reachability problem for vector addition systems with states (VASS) has been shown to be \textsc{Ackermann}-complete. For every , a completeness result for the -dim…