A polynomial algorithm to find a set of elementary siphons in a class of Petri nets

摘要

The concept of siphons plays an important role in the analysis of Petri nets. In particular, criteria for liveness and reachability of some subclasses of Petri nets can be stated in terms of siphons. However, the computation of these structural components can be time consuming or even impossible. Recently, a variety of deadlock control policies that rely on partial siphon computation and enumeration have been developed. We propose a polynomial algorithm to find a set of elementary siphons in a class of Petri nets called systems of simple sequential processes with resources, S/sup 3/PR for short. Based on them, other siphons, called dependent ones, can be composed by simple set operations. Case studies show that the proposed algorithm is more computationally efficient than INA, integrated net analyzer, a widely used Petri net analysis tool.