A multiparameter analysis of the boundedness problem for vector addition systems (Q1819938)

The authors give a careful analysis of the complexity of the boundedness problem (BP; ''is the reachability set infinite?'') for vector addition systems (VAS) and vector addition systems with states (VASS), which are known to be equivalent to Petri nets. Upper and lower bounds for the complexity are given in dependence of three parameters: k: dimension of vectors, l: maximal bit length of vector components, n: number of states. The BP for such VASS(k,l,n) can be solved in \(O((l+\log n)*2^{c*k*\log k})\) nondeterministic space for some constant c (an improvement of Rackoff's result). Lipton's lower bound is improved to \(O((l+\log n)*2^{c*k})\). Furthermore, some complexity results for fixed small k and connections to nets of communicating finite state machines (CFSM) are given.