In: Theoretical Computer Science, Vol. 46, pages 107-140. 1986.
Abstract: The authors analyse the complexity of the reachability, containment, and equivalence problems for two calsses of vector addition systems with states (VASSs): finite VASSs and 2-dimensional VASSs. Both of these classes are known to have effectively computable semilinear reachabiblty sets (SLSs). By giving upper bounds on the sizes of the SLS representations, the authors achieve upper bounds on each of the aforementioned problems.