An Approach for Enumerating Minimal Siphons in a Subclass of Petri Nets

Abstract

Siphons, as a structural object of Petri nets (PNs), are closely related to deadlock-freedom in PNs. Efficient siphon computation is of great importance in developing siphon-based deadlock control strategies with good performance. This paper is concerned with the enumeration of minimal siphons in a subclass of PNs called systems of sequential systems with shared resources (S <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">4</sup> PR). First, a method with polynomial complexity is proposed to decide whether a subset of resource places can generate a minimal siphon. Next, by utilizing the technique of problem partitioning, we develop an approach to compute all minimal siphons in S <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">4</sup> PR. The proposed approach is illustrated by an example and its advantage is finally demonstrated via a comparison with other approaches.