In: Avtomatika i Telemekhanika, Vol. 49, No. 11, pages 3-39. November 1988. In Russian.
Also in: Automation and Remote Control, Vol. 49, No. 11, pages 1393-1422. November 1988. English translation.
Abstract: The paper reviews the current status of the reachability problem for Petri nets. Following the ideas of Mayr (1984), a complete decidability proof of the reachability problem is presented. Some related topics are also considered: decidability of Presburger arithmetic, semilinear sets, vector addition graphs, reachability graphs, etc.
Keywords: reachability problem decidability; control systems; Presburger arithmetic; semilinear set; vector addition graphs.