Computation of strict minimal siphons in a class of Petri nets based on problem decomposition

Efficient siphon computation plays an important role in deadlock control. This work, based on problem decomposition, develops a new method to compute all strict minimal siphons (SMS) in a class of Petri nets called Systems of Simple Sequential Processes with Resources (S3PR). It is proved to be of polynomial complexity with respect to the number of SMSs. Therefore, it is readily applicable to an S3PR with a large number of SMSs. Its superiority over the existing methods is validated via experimental results.