A. E. Kostin
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.
Index Terms
- The novel algorithm for determining the reachability in acyclic Petri nets
Recommendations
Yet another reachability algorithm for Petri nets
A new algorithm for the determination of reachability of a marking in generalized Petri nets is proposed. The algorithm is based on the matrix-equation approach. Given a Petri net, a so called complemented Petri net is created that consists of the given ...
Structuring Acyclic Petri Nets for Reachability Analysis and Control
The incidence matrices—from places to transitions and vice versa—of an acyclic Petri net can obtain a block-triangular structure by reordering their rows and columns. This allows the efficient solution of some reachability problems for acyclic Petri ...
A reachability algorithm for general petri nets based on transition invariants
MFCS'06: Proceedings of the 31st international conference on Mathematical Foundations of Computer ScienceA new reachability algorithm for general Petri nets is proposed. Given a Petri net with an initial and a target markings, a so called complemented Petri net is created first that consists of the given Petri net and an additional, complementary ...
Comments