ABSTRACT
Reachability graph analysis and structural analysis are two important Petri net analysis techniques for deadlock control. Based on the reachability graph of a Petri net model, an optimal supervisor can always be obtained since it carries the complete behavior information of a net model (Uzam, 2002; Uzam and Zhou, 2006). However, the number of reachable markings increases exponentially with respect to its size and the initial marking. A complete state enumeration always suers from the state explosion problem. The computation of a reachability graph is known to be very time-consuming or even impossible. Based on the structural analysis, a deadlock control policy is generally carried out in terms of a special structure of a net (Wu, 1999; Wu and Zhou, 2001; Xing et al., 1996; Yamalidou et al., 1996). Siphons, particularly minimal siphons, are one of the special structures. As a structural object of Petri nets, siphons are closely related to the deadlocks. Thus, they are widely used in the development of deadlock control policies (Ezpeleta et al., 2004; Ghaari et al., 2003; Huang et al., 2001; Jeng and Xie, 2005; Kumaran et al., 1994; Li et al., 2007, 2008; Li and Zhou, 2004, 2006; Piroddi et al., 2008;
Zhou DiCesare, 1991). the number of siphons in a Petri net increases exponentially with respect to its size. Thus, the calculation of all siphons is computationally expensive. Even all the siphons are found, identifying minimal siphons from a large number of siphons is still time-consuming. This fact motivates us to find more ecient approaches to compute minimal siphons.
