An Algorithm for the General Petri Net Reachability Problem

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.

Authors

• Ernst W. Mayr

Keywords

• Decidability
• Petri net
• Reachability problem
• Vector addition system