Vector addition system

Vector addition systems were introduced by Richard M. Karp and Raymond E. Miller in 1969,[1] and generalized to vector addition systems with states (VASS) by John E. Hopcroft and Jean-Jacques Pansiot in 1979.

[2] Both VAS and VASS are equivalent in many ways to Petri nets introduced earlier by Carl Adam Petri.

Reachability in vector addition systems is Ackermann-complete (and hence nonelementary).

More precisely, it is a finite directed graph with arcs labelled by integer vectors.

VASS have the same restriction that the counter values should never drop below zero.

Example of a vector addition with states. In this VASS, e.g., q(1,2) can be reached from p(0,0), but q(0,0) cannot be reached from p(0,0).