An Algorithm to Compute the Minimal Siphons in S4PR Nets

Minimal siphons in the class of S4PR nets have become a conceptual and practical central tool. Therefore the availability of efficient algorithms to compute the minimal siphons is very important. In this paper we try to take advantage from the particular properties of the siphons in S4PR to obtain an efficient algorithm. These properties allow to express minimal siphons as the union of pruned minimal siphons containing only one resource. The pruning operation is defined as a relation and represented in a graph. The computation of the minimal siphons is based in the maximal strongly connected components of this graph. The algorithm is very economic in memory in all intermediate steps with respect to the classical algorithms.