In: SIGACT News, Vol. 28, No. 2, pages 70-79. June 1997.
Abstract: A novel algorithm for determining the reachability of a marking in acyclic Petri nets is proposed. For this algorithm, a Petri net is represented in the matrix form, with a given pair of initial and target markings. The algorithm is based on the creation of a temporal ordering relation for transition firings and on using this relation for determining the shortest sequence of transition firings transforming the initial marking into the target one. By solving the fundamental equation of the Petri net, the algorithm determines initially whether the target marking is reachable from the given initial marking, and, in case it is, produces the shortest sequence of transition firings which transforms the initial marking into the target one.
Keywords: Reachability; acyclic Petri nets.