  We consider the problems of language inclusion and language equivalence for
Vector Addition Systems with States (VASSes) with the acceptance condition
defined by the set of accepting states (and more generally by some
upward-closed conditions). In general the problem of language equivalence is
undecidable even for one-dimensional VASSes, thus to get decidability we
investigate restricted subclasses. On one hand we show that the problem of
language inclusion of a VASS in k-ambiguous VASS (for any natural k) is
decidable and even in Ackermann. On the other hand we prove that the language
equivalence problem is Ackermann-hard already for deterministic VASSes. These
two results imply Ackermann-completeness for language inclusion and equivalence
in several possible restrictions. Some of our techniques can be also applied in
much broader generality in infinite-state systems, namely for some subclass of
well-structured transition systems.
