The decidability of the reachability problem for vector addition systems (Preliminary Version)
- 1 January 1977
- proceedings article
- Published by Association for Computing Machinery (ACM)
Abstract
Let V be a finite set of integral vectors in Euclidian N-space, and let &abarbelow; be an integral point in the first orthant of N-space. The reachability set R(&abarbelow;,V) is the set of integral points &bbarbelow; in the first orthant such that there is a polygonal path &ggr; from &abarbelow; to &bbarbelow; satisfying (i) all of &ggr; lies in the first orthant, and (ii) the edges of &ggr; are translates of the vectors in V. The reachability problem for the vector addition system (&abarbelow;,V) asks for an algorithm to decide which integral points &bbarbelow; are in R(&abarbelow;,V). In this paper we give an algorithm to solve this problem.This publication has 0 references indexed in Scilit: