I'm a PhD student in BASICS lab, Shanghai Jiao Tong University where I'm advised by Prof. Yuxi Fu.
My research interest lies in theoretical computer science, especially automata theory.
Previously, I earned my bachelor's degree from the Department of Computer Science and Engineering at Shanghai Jiao Tong University in 2021.
Publications
Improved Algorithm for Reachability in d-VASS
Yuxi Fu, Qizhe Yang* and Yangluo Zheng ICALP 2024
Abstract: An Fd upper bound for the reachability problem in vector addition systems with states (VASS) in fixed dimension is given, where Fd 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 Fd+4 upper bound due to Leroux and Schmitz (LICS 2019).
Reachability in Vector Addition System with States Parameterized by Geometric Dimension
Yangluo Zheng CONCUR 2025 (to appear)
Abstract: The geometric dimension of a Vector Addition System with States (VASS), emerged in Leroux and Schmitz (2019) and formalized by Fu, Yang, and Zheng (2024), quantifies the dimension of the vector space spanned by cycle effects in the system. This paper explores the VASS reachability problem through the lens of geometric dimension, revealing key differences from the traditional dimensional parameterization. Notably, we establish that the reachability problem for both geometrically 1-dimensional and 2-dimensional VASS is PSPACE-complete, achieved by extending the pumping technique originally proposed by Czerwiński et al. (2019).
Reachability in Geometrically d-Dimensional VASS
Yuxi Fu, Yangluo Zheng, Qizhe Yang manuscript
Abstract: Reachability of vector addition systems with states (VASS) is Ackermann complete [5, 19]. For d-dimensional VASS reachability it is known that the problem is NP-complete [10] when d = 1, PSPACE-complete [1] when d = 2, and in Fd[8] when d > 2. A geometrically d-dimensional VASS is a D-dimensional VASS for some D ≥ d such that the space spanned by the displacements of the circular paths admitted in the D-dimensional VASS is d-dimensional. It is proved that the Fd upper bounds remain valid for the reachability problem in the geometrically d-dimensional VASSes with d > 2.