2 papers
cs.CC2025
Reachability in Geometrically -Dimensional VASS
Yuxi Fu, Yangluo Zheng, Qizhe Yang
Reachability of vector addition systems with states (VASS) is Ackermann complete~\cite{leroux2021reachability,czerwinski2021reachability}. For -dimensional VASS reachability it…
cs.LO2020
Reachability is Tower Complete
Yuxi Fu, Qizhe Yang
A complete characterization of the complexity of the reachability problem for vector addition system has been open for a long time. The problem is shown to be Tower complete.