Incremental approach to computation of elementary siphons for arbitrary simple sequential processes with resources

Abstract

Computation of elementary siphons proposed by Li et al. is essential for deadlock control and expensive since complete siphon enumeration of the Petri net is needed, and the number of strict minimal siphons (SMS) grows quickly and exponentially with the size of the net. They assumed that the siphon constructed from each resource circuit is an elementary one and proposed a polynomial algorithm to compute elementary siphons. However, the author demonstrates a counter example where there may be an exponential number of resource circuits. Hence, constructing elementary siphons from resource circuits will result in an exponential number of elementary siphons, which is wrong. The author then develops a polynomial algorithm to find elementary siphons, which also constructs all SMS on the way. This is because, in the method proposed by Li et al., a linear algebraic expression must be established for each dependent siphon, which implies, all SMS must be located. However, all elementary siphons with polynomial complexity can be located.