An algorithm for the general Petri net reachability problem
EW Mayr - Proceedings of the thirteenth annual ACM symposium …, 1981 - dl.acm.org
EW Mayr
Proceedings of the thirteenth annual ACM symposium on Theory of computing, 1981•dl.acm.orgAn algorithm is presented for the general Petri net reachability problem based on a
generalization of the basic reachability construction which is symmetric with respect to the
initial and final marking. Sets of transition sequences described by finite automata are used
for approximations to firing sequences, and the approximation error is assessed by uniformly
constructable Presburger expressions. The approximation algorithm is iterated until a
sufficient criterion for reachability can be given, not-withstanding the remaining uncertainty.
generalization of the basic reachability construction which is symmetric with respect to the
initial and final marking. Sets of transition sequences described by finite automata are used
for approximations to firing sequences, and the approximation error is assessed by uniformly
constructable Presburger expressions. The approximation algorithm is iterated until a
sufficient criterion for reachability can be given, not-withstanding the remaining uncertainty.
An algorithm is presented for the general Petri net reachability problem based on a generalization of the basic reachability construction which is symmetric with respect to the initial and final marking. Sets of transition sequences described by finite automata are used for approximations to firing sequences, and the approximation error is assessed by uniformly constructable Presburger expressions. The approximation algorithm is iterated until a sufficient criterion for reachability can be given, not-withstanding the remaining uncertainty.