Abstract
In this paper, we analyse the complexity of the reachability, containment, and equivalence problems for two classes of vector addition systems with states (VASSs): finite VASSs and 2-dimensional VASSs. Both of these classes are known to have effectively computable semilinear reachibility sets (SLSs). By giving upper bounds on the sizes of the SLS representations, we achieve upper bounds on each of the aforementioned problems. In the case of the finite VASSs, the SLS representation is simply a listing of the reachability set; therefore, we derive a bound on the norm of any reachable vector based on the dimension, number of states, and amount of increment caused by any move in the VASS. The bound we derive shows an improvement of two levels in the primitive recursive hierarchy over results previously obtained by McAloon (1984), thus answering a question posed by Clote (1986). We then show this bound to be optimal. We feel that the techniques we use in deriving our upper bounds represent an original approach to the problem, and since they yield improvements over previous results, we feel these techniques may have applications to other problems. In the case of 2-dimensional VASSs, we analyse an algorithm given by Hopcroft and Pansiot (1979) that generates an SLS representation of the reachability set. Specifically, we show that the algorithm operates in 2
2
cln
nondeterministic time, where
l is the length of the binary representation of the largest integer in the VASS,
n is the number of transitions, and
c is some fixed constant. We also give examples for which this algorithm will take 2
2
dln
nondeterministic time for some positive constant
d. Finally, we give a method of determinizing the algorithm in such a way that it requires no more than 2
2
cln
deterministic time. From this upper bound and special properties of the generated SLSs, we derive upper bounds of
Dtime(2
2
cln
) for the three problems mentioned above.
