Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states (Q1096388): Difference between revisions

The containment and equivalence problems for vector addition systems (VASs) (or equivalently, vector addition systems with states (VASSs) or Petri nets) are, in general, undecidable. They are decidable, however, for classes of VASs (VASSs, Petri nets) whose reachability sets are effectively computable semilinear sets (SLSs). The authors analyse the complexity of the reachability, containment, and equivalence problems for two classes of VASSs. Both of these classes are known to have effectively computable SLSs. By giving upper bounds on the sizes of the SLS representations, they achieve upper bounds on each of the mentioned problems. The techniques they use in deriving their upper bounds represent an original approach to the problem. These techniques may have applications to other problems.