The Polynomial Complexity of Vector Addition Systems with States
Florian Zuleger · Lecture notes in computer science · 2020
Abstract Vector addition systems are an important model in theoretical computer science and have been used in a variety of areas. In this paper, we consider vector addition systems with states over a parameterized initial configuration. For these systems, we are interested in the standard notion of computational time complexity, i.e., we want to understand the length of the longest trace for a fixed vector addition system with states depending on the size of the initial configuration. We show that the asymptotic complexity of a given vector addition system with states is either $$\varTheta (N^k)$$ Θ(Nk) for some computable integerk, whereNis the size of the initial configuration, or at least exponential. We further show thatkcan be computed in polynomial time in the size of the considered vector addition system. Finally, we show that $$1 \le k \le 2^n$$ 1≤k≤2n , wherenis the dimension of the considered vector addition system.