Elementary Siphons of BS3PR

Unlike other techniques, Li et al. add control nodes and arcs for only elementary siphons, thus reducing the number of control nodes and arcs required for deadlock con-trol in Petri net supervisors. Their method suffers from the expensive computation of all SMS (Strict Minimal Siphons). We propose a graphic-algebra approach to compute ele-mentary siphons without the knowledge of SMS. We show that each SMS corresponds to a strongly connected resource subnet (sub-SCC) whose characteristic T-vector ζ can be computed as a linear sum of that of all resource places in the subnet. An SMS in-cludes all resource places in the subnet plus all input operation places of transitions with positive components in ζ. We propose Algorithm 2 to find all sub-SCC. We prove that any sub-SCC N’, containing an elementary resource circuit c as a proper subset and N ’ = N ” ∪ c, N ” ∩ c = {r}, corresponds to a dependent siphon. Hence, elementary siphons are closely related to (and can be constructed from) elementary (called basic) circuits and in general, combinations of elementary circuits may contribute to elementary siphons. For a simple basic subclass of S3PR (called BS3PR), the set of elementary siphons is identical to that synthesized from elementary (basic) circuits. As a result, we simplify Algorithm 2 to find all elementary circuits. It is more efficient than traditional algorithms by termi-nating earlier upon detecting that the net is not a BS3PR