A Class of Petri Nets That a Necessary and Sufficient Condition for Reachability is Obtainable

Abstract

The central issue of this paper is to find a class of Petri nets that a necessary and sufficient condition for reachability is obtainable. For this purpose, some classes of Petri nets are defined by stractural conditions related to directed circuits.A necessary and sufficient condition for reachability can be obtained for a trap circuit Petri net (tc-net) where a set of places on any circuit forms a trap, and for a deadlock circuit Petri net (dc-net) where a set of places on any cicruit forms a deadlock. A tc-net is a subclass of normal Petri nets. For a normal Petri net, a sufficient condition for reachability is obtained.Reachability for a conflict free Petri net can be decided by finding a firable firing sequence for finite minimal solutions of the matrix equation. This property is also true for larger classes of Petri nets than conflict-free. These are a non-decreasing circuit Petri net (ndc-net) where number of tokens on any circuit is nondecreasing for any firings of transitions, and a non-increasing circuit Petri net (nic-net) where number of tokens on any circuit is non-increasing for any firings of transitions. A ndc-net and a nic-net are subclasses of a tc-net and a dc-net, respectively.