The decidability of the reachability problem for vector addition systems (Preliminary Version)

Let V be a finite set of integral vectors in Euclidian N-space, and let a be an integral point in the first orthant of N-space. The reachability set R(a,V) is the set of integral points b in the first orthant such that there is a polygonal path γ from a to b satisfying (i) all of γ lies in the first orthant, and (ii) the edges of γ are translates of the vectors in V. The reachability problem for the vector addition system (a,V) asks for an algorithm to decide which integral points b are in R(a,V). In this paper we give an algorithm to solve this problem.