A polynomial complexity 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-S³PR. A polynomial algorithm is developed to decide whether a more general class of Petri nets, S³PR, has potential deadlock, which can model a wide class of flexible manufacturing systems. First, the definitions of L-S³PR and S³PR are presented with illustrations. Then the concept of resource circuits and the way to find them from a net structure are proposed. We show the approach to obtain a minimal siphon S from a resource circuit. It is also proved that if a minimal siphon derived from a resource circuit does not contain the support of any P-invariant, it is not a potential deadlock. A minimal siphon that can be emptied is the real cause of the non-liveness in an S³PR. Finally, an example is given to illustrate our results.