In: Avtomatika i Vychislitel'naya Tekhnika, Vol. 24, No. 2, pages 16-22. 1990. In Russian.
Also in: Automatic Control and Computer Sciences, Vol. 24, No. 2, pages 13-19. 1990. English translation.
Abstract: The article establishes that the problem of reachability of a marking in a Petri net is algorithmically solvable. A matrix-dynamic method is proposed and described for this purpose; for any Petri net with specified initial and object markings, it determines whether the object marking is reachable from the initial one, and, if the answer is affirmative, it provides the shortest sequence of transitions for carrying the initial marking to the object one. The method is based on backward motion from the object to the initial marking, with generation of a finite tree of preceding markings.
Keywords: algorithmic reachability problem solution; matrix-dynamic method; shortest transition sequence.