  Vector Addition Systems with States (VASS) consists of a finite state space
equipped with d counters, where in each transition every counter is
incremented, decremented, or left unchanged. VASS provide a fundamental model
for analysis of concurrent processes, parametrized systems, and they are also
used as abstract models for programs for bounds analysis. While termination is
the basic liveness property that asks the qualitative question of whether a
given model always terminates or not, the more general quantitative question
asks for bounds on the number of steps to termination. In the realm of
quantitative bounds a fundamental problem is to obtain asymptotic bounds on
termination time. Large asymptotic bounds such as exponential or higher already
suggest that either there is some error in modeling, or the model is not useful
in practice. Hence we focus on polynomial asymptotic bounds for VASS. While
some well-known approaches (e.g., lexicographic ranking functions) are neither
sound nor complete with respect to polynomial bounds, other approaches only
present sound methods for upper bounds. In this work our main contributions are
as follows: First, for linear asymptotic bounds we present a sound and complete
method for VASS, and moreover, our algorithm runs in polynomial time. Second,
we classify VASS according the normals of the vectors of the cycles. We show
that singularities in the normal are the key reason for asymptotic bounds such
as exponential and non-elementary for VASS. In absence of singularities, we
show that the asymptotic complexity bound is always polynomial and of the form
${\Theta}(n^k)$, for some k $\leq$ d. We present an algorithm, with time
complexity polynomial in the size of the VASS and exponential in dimension d,
to compute the optimal k.
