A Polynomial Algorithm to Decide the Liveness for a Class of Petri Nets

In this paper, we extend the liveness characterization results on a subclass of Petri nets, L-S3PR. A polynomial algorithm is developed to decide whether a more general class of Petri nets, S³PR, has potential deadlocks, which can model a wide class of flexible manufacturing systems (FMS). The concept of resource circuits and the way to find them from a net structure are proposed. We show an approach to find a minimal siphon from a resource circuit, which is the cause of the non-liveness in an S³PR. Finally, some examples are given to illustrate our results. As a complement, the direct approach to avoid deadlock by configuring the initial marking are also proposed