On the Reachability Problem for 5-Dimensional Vector Addition Systems
Hopcroft, John E.; Pansiot, J.
The reachability set for vector addition systems of dimension less than or equal to five are shown to be effectively computable semilinear sets. Thus reachability, equvalence and containment are decidable up to dimension 5. An example of a non-semilinear reachability set is given for dimension 6. Keywords and phrases: Vector addition system, Petri net, semilinear set, algorithms, decidability.
computer science; technical report
Previously Published As