A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> Deadlock prevention and siphon <s> This paper exploits the potential of siphons for the analysis of Petri nets, It generalizes the well-known Commoner condition and is based on the notion of potential deadlocks which are siphons that eventually become empty. A linear programming based sufficient condition under which a siphon is not a potential deadlock is obtained. Based on the new sufficient condition, a mathematical programming approach and a mixed-integer programming approach are proposed for checking general Petri nets and structurally bounded Petri nets respectively without explicitly generating siphons. Stronger results are obtained for asymmetric choice nets and augmented marked graphs. In particular, we show that an asymmetric choice net is live iff it is potential-deadlock-free and an augmented marked graph is live and reversible iff it is potential-deadlock-free. <s> BIB001 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> Deadlock prevention and siphon <s> This paper presents a deadlock prevention method for a class of flexible manufacturing systems where deadlocks are caused by unmarked siphons in their Petri net models. This method is an iterative approach consisting of two main stages. At each iteration, a fast deadlock detection technique developed by mixed integer programming is used to find an unmarked maximal siphon. An algorithm is formalized that can efficiently obtain an unmarked minimal siphon from the maximal siphon. The first stage, called siphons control, of the proposed method is to add, for each unmarked minimal siphons, a control place to the original net with its output arcs to the sink transitions of the minimal siphon. The objective is to prevent a minimal siphon from being unmarked. The second stage, called augmented siphons control, is to add a control place to the modified net with its output arcs to the source transitions of the resultant net if the resource places are removed. The second stage is required since adding control places... <s> BIB002 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> Deadlock prevention and siphon <s> Liveness-enforcing supervision of sequential resource allocation systems is currently a well-defined problem, underlying the operation of many contemporary technological systems, spanning a wide spectrum of applications. This technical note provides a brief overview of the currently available results, delineating, both, our major analytical understandings/characterizations concerning the problem concepts/structure and its complexity, and also, our ability to synthesize effective and computationally tractable solutions to it. The last part of the document identifies open/unaddressed research issues, the resolution of which will extent the power of the current theory and will allow the integration of the developed results in the broader control frameworks managing the behavior of these environments. <s> BIB003 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> Deadlock prevention and siphon <s> One of the most interesting developments from, both, a theoretical and a practical perspective, in the emerging theory of resource allocation systems (RAS), is the characterization of the non-liveness of many RAS classes through the Petri net (PN)-based structural object of empty, or more generally, deadly marked siphon. The work presented in this paper seeks to develop a general theory that provides a unifying framework for all the relevant existing results, and reveals the key structures and mechanisms that connect the RAS non-liveness to the concept of deadly marked - and in certain cases, empty - siphon. By taking this generalizing approach, the developed results allow also the extension of the siphon-based characterization of non-liveness to broader RAS classes, and provide a clear and intuitive explanation for the cases where the RAS non-liveness cannot be attributed to such a siphon-based construct. <s> BIB004 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> Deadlock prevention and siphon <s> A variety of important Petri net-based methods to prevent deadlocks arising in flexible manufacturing systems (FMS) are to add some control places and related arcs to strict minimal siphons (SMS) such that no siphon can be emptied. Since the number of minimal siphons grows in general exponentially with respect to a Petri net size, their disadvantages lie in that they often add too many additional places to the net, thereby making the resulting net model much more complex than the original one. This paper explores ways to minimize the new additions of places while achieving the same control purpose. It proposes for the first time the concept of elementary siphons that are a special class of siphons. The set of elementary siphons in a Petri net is generally a proper subset of the set of all SMS. Its smaller cardinality becomes evident in large Petri net models. This paper proves that by adding a control place for each elementary siphon to make sure that it is marked, deadlock can be successfully prevented. Compared with the existing methods, the new method requires a much smaller number of control places and, therefore, is suitable for large-scale Petri nets. An FMS example is used to illustrate the proposed concepts and policy, and show the significant advantage over the previous methods. <s> BIB005 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> Deadlock prevention and siphon <s> The paper addresses the problem of enumerating minimal siphons in an ordinary Petri net. The algorithms developed in this work recursively use a problem partitioning procedure to reduce the original search problem to multiple simpler search subproblems. Each subproblem has specific additional place constraints with respect to the original problem. Some results on algorithm correctness, convergence, and computational complexity are provided, as well as an experimental evaluation of performance. The algorithms can be applied to enumerate minimal, place-minimal siphons, or even siphons that are minimal with respect to given subsets of places. <s> BIB006 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> Deadlock prevention and siphon <s> A siphon-based algorithm for deadlock prevention of a type of Petri nets called S3PMR, which is a subclass of S3PGR2, is presented in this correspondence. The proposed method is an iterative approach by adding two kinds of control places called ordinary control (OC) places and weighted control (WC) places to the original model to prevent siphons from being unmarked. An OC place with ordinary arcs, which optimally prevent a siphon from becoming unmarked, is employed whenever it is possible, and otherwise, the WC places that adopt a conservative policy of controlling the release of parts into the system are used. Furthermore, this algorithm is not only for the subclass Petri nets but also for S3PR, ES 3PR, S2LSPR, and S3PGR2 nets. The authors prove the liveness and reversibility of the controlled net, and hence establish the correctness of the deadlock prevention policy. Finally, numerical experiments indicate that the proposed policy appears to be more permissive than closely related approaches in the literature <s> BIB007 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> Deadlock prevention and siphon <s> The concept of elementary siphons of Petri nets is first proposed in our previous work. However, their definitions can cause confusion when there exist weakly independent siphons in a net. In this correspondence, we redefine elementary siphons and show the significance of this improvement <s> BIB008 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> Deadlock prevention and siphon <s> This paper develops a two-stage approach to synthesizing liveness-enforcing supervisors for flexible manufacturing systems (FMS) that can be modeled by a class of Petri nets. First, we find siphons that need to be controlled using a mixed integer programming (MIP) method. This way avoids complete siphon enumeration that is more time-consuming for a sizable plant model than the MIP method. Monitors are added for only those siphons that require them. Second, we rearrange the output arcs of the monitors on condition that liveness is still preserved. The liveness is verified by an MIP-based deadlock detection method instead of much time-consuming reachability analysis. Experimental studies show that the proposed approach is more efficient than the existing ones and can result in more permissive and structurally simpler liveness-enforcing supervisors than all the known existing methods. This paper makes the application of siphon-based deadlock control methods to industrial-size FMS possible <s> BIB009 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> Deadlock prevention and siphon <s> This correspondence corrects an algorithm by Huang et al. [International Journal of Production Research, 2001, 39, 283–305] that is used in the development of a deadlock prevention policy for a class of flexible manufacturing systems (FMS) where deadlocks are caused by unmarked siphons in their Petri net models. The algorithm was initially designed to derive a minimal siphon from a maximal unmarked siphon that can be obtained due to the MIP (Mixed Integer Programming)-based deadlock detection method. Also, some minor mistakes detected in the same paper are corrected. <s> BIB010 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> Deadlock prevention and siphon <s> This correspondence develops a methodology to synthesize supervisors for a special class of Petri nets that can well model many flexible manufacturing systems. In our previous work, siphons in a Petri net are divided into elementary and dependent ones on the condition that all emptiable minimal siphons are computed. In this research, a mixed integer programming (MlP)-based deadlock detection technique is used to find some, in general not all, minimal siphons in a plant model without complete siphon enumeration. For each siphon found, depending on its noncontrollability, a monitor is added such that it is invariant-controlled. Our siphon control method guarantees that no emptiable control-induced siphon is generated due to the addition of the monitors. The siphon control process proceeds iteratively until there is no unmarked siphon in the supervisor of a plant model. Compared with the existing approaches, the novel deadlock prevention policy can usually lead to a structurally simple liveness-enforcing supervisor by adding only a small number of monitors and arcs. More importantly, complete siphon enumeration is avoided. A practical flexible manufacturing system (FMS) example is utilized to illustrate the proposed methods. <s> BIB011 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> Deadlock prevention and siphon <s> Effective resolution for deadlock problems plays an important role in the operation of automated flexible manufacturing systems (FMS). Based on P-invariants and elementary siphons of Petri nets, a deadlock prevention policy is developed for a special class of Petri nets that can well model many FMS. Siphons in a plant net model are divided into elementary and dependent ones. For each elementary siphon, a monitor is added to the plant model such that the siphon is invariant-controlled. Our method guarantees that no emptiable control-induced siphon is generated due to the addition of the monitors. When all elementary siphons are controlled, the controllability of a dependent siphon is ensured by properly setting the control depth variables of its related elementary siphons. An FMS example is utilized to illustrate the proposed methods. <s> BIB012 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> Deadlock prevention and siphon <s> Over the last two decades, a great deal of research has been focused on solving deadlock problems in resource allocation systems such as computer communication systems, workflow systems, and flexible manufacturing systems, resulting in a wide variety of approaches. As a well-defined problem in resource allocation systems, deadlock prevention based on a Petri net formalism has received an enormous amount of attention in the literature. This paper intends to review and compare a variety of Petri net-based deadlock prevention policies reported in the literature. Their comparison is done in terms of structural complexity, behavior permissiveness, and computational complexity. This paper should facilitate engineers in choosing a suited method for their industrial application cases. <s> BIB013 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> Deadlock prevention and siphon <s> In this paper, we deal with the problem of modeling railway networks with Petri nets so as to apply the theory of supervisory control for discrete event systems to automatically design the system controller. We provide a modular representation of railway networks in terms of stations and tracks including sensors and semaphores. We first ensure safeness and local liveness imposing both generalized mutual exclusion constraints and constraints also involving the firing vector. The detailed model used in this first step can be abstracted, considering a higher level description of a railway network that belongs to the class of ES PR (extended simple sequential process with resources) nets and show that global liveness may be enforced by adding appropriate monitor places designed using siphon analysis. In our approach, this can be done without an exhaustive computation of all siphons and we can characterize the cases in which the procedure can be recursively applied, giving a simple test for closed-loop net to remain an ES PR net. <s> BIB014 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> Deadlock prevention and siphon <s> This paper addresses the deadlock problems in flexible manufacturing systems (FMS) by using a Petri net siphon control method and the theory of regions. The proposed policy consists of two stages. The first one, called siphons control, is to add, for every siphon that we identify, a monitor to the original net model such that it is optimally invariant controlled. In the second stage, the theory of regions is utilized to derive the net supervisors such that deadlocks can be prevented. The first-stage work significantly lowers the computational cost compared with the approach where the theory of regions is used alone. An FMS example is presented to illustrate the technique. By varying the markings of given net structures, this paper shows its computational advantages. <s> BIB015 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> Deadlock prevention and siphon <s> As a structural object, siphons are well recognized in the analysis and control of deadlocks in resource allocation systems modeled with Petri nets. Many deadlock prevention policies characterize the deadlock behavior of the systems in terms of siphons and utilize this characterization to avoid deadlocks. This paper develops a novel methodology to find interesting siphons for deadlock control purposes in a class of Petri nets, i.e., a system of simple sequential processes with resources . Resource circuits in an are first detected, from which, in general, a small portion of emptiable minimal siphons can be derived. The remaining emptiable ones can be found by their composition. A polynomial-time algorithm for finding the set of elementary siphons is proposed, which avoids complete siphon enumeration. It is shown that a dependent siphon can always be controlled by properly supervising its elementary siphons. A computationally efficient deadlock control policy is accordingly developed. Experimental study shows the efficiency of the proposed siphon computation approach. <s> BIB016 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> Deadlock prevention and siphon <s> Petri nets have been proved to be a tool with prominent capabilities to describe discrete event systems, such as flexible manufacturing systems (FMS), thanks to their excellent properties over other models. Characterization in terms of special structural elements in a Petri net called siphons has been a major approach for the investigation of deadlock-freeness in context of FMS. Utilizing the optimal elementary siphons and the modified mixed integer programming (MIP) algorithm proposed in this paper, one can detect and solve deadlock problems arising in FMS in an iterative mode with tractable computational complexity. Moreover, the MIP approach can be exploited to implement the flexibility enhancement in the resultant net system so that the obtained system is less restricted. In contrast to the conventional typical policies, this approach evolves without explicitly enumerating all the strict minimal siphons. Its legitimacy and feasibility are proved and validated through an experimental study. <s> BIB017 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> Deadlock prevention and siphon <s> Deadlock prevention is a crucial step in the modeling of flexible manufacturing systems. In the Petri net framework, deadlock prevention policies based on siphon control are often employed, since it is easy to specify generalized mutual exclusion constraints that avoid the emptying of siphons. However, such policies may require an excessive computational load and result in impractical oversized control subnets. This is often a consequence of the redundancy in the control conditions derived from siphons. In this paper, a novel method is proposed that provides small size controllers, based on a set covering approach that conveniently relates siphons and markings. Some examples are provided to demonstrate the feasibility of the approach and to compare it with other methods proposed in the literature. <s> BIB018 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> Deadlock prevention and siphon <s> A fair amount of research has shown the importance of siphons in the analysis and control of deadlocks in a variety of resource allocation systems by using a Petri net formalism. In this paper, siphons in a generalized Petri net are classified into elementary and dependent ones, as done for ordinary nets in our previous work. Conditions are derived under which a dependent siphon is controlled by properly supervising its elementary siphons, which indicates that the controllability of dependent siphons in an ordinary Petri net is a special case of that in a generalized one. The application of the controllability of dependent siphons is shown by considering the deadlock prevention problem for a class of resource allocation systems, namely, G-system that allows multiple resource acquisitions and flexible routings in a flexible manufacturing system with machining, assembly, and disassembly operations. We develop a monitor-based deadlock prevention policy that first adds monitors for elementary siphons only to a G-system plant model such that the resultant net system satisfies the maximal controlled-siphon property (maximal cs-property). Then, by linear programming, initial tokens in the additional monitors are decided such that liveness is enforced to the supervised system. Also, a simplified live marking relationship for a G-system between the initial tokens of the source places and those of the resource places is derived. Finally, the proposed deadlock prevention methods are illustrated by using an example. <s> BIB019 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> Deadlock prevention and siphon <s> The importance of siphons is well recognized in the analysis and control of deadlocks in a Petri net. To minimize the number of siphons that have to be explicitly controlled, siphons in a net are divided in a net into elementary and dependent ones. The concepts of token-rich, token-poor, and equivalent siphons are newly presented. More general conditions under which a dependent siphon can be always marked are established. The existence of dependent siphons in a Petri net is investigated. An algorithm is developed to find the set of elementary siphons in a net system for deadlock control purposes. The application of the proposed elementary siphon concept to the existing deadlock control policies is discussed. A few different-sized manufacturing examples are used to demonstrate the advantages of elementary siphon-based policies. The significant value of the proposed theory via a particular deadlock control policy is shown. Finally, some interesting and open problems are discussed. <s> BIB020 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> Deadlock prevention and siphon <s> We propose a revised mixed-integer programming (MIP) method to directly compute unmarked siphons with a minimal number of places. This eliminates the need to deduce a minimal siphon from an unmarked maximal siphon obtained from the traditional MIP method proposed by Chu et al. The revised MIP test reports smaller siphons earlier than larger siphons and adds monitors to basic siphons before compound siphons. This results in adding fewer monitors and reaching more states. <s> BIB021 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> Deadlock prevention and siphon <s> As a structural object of Petri nets, siphons play a key role in the development of deadlock prevention policies for resource allocation systems. Elementary siphons are a novel concept in net theory. Based on graph theory, this paper proposes an effective algorithm with polynomial complexity to find a set of elementary siphons for a linear system of simple sequential processes with resources (LS3 PR), a subclass of Petri nets, which can model many flexible manufacturing systems. The algorithm is established through the use of a resource directed graph and complementary sets of strict minimal siphons (SMS) of the net. The upper bound of the number of SMS in such a net is identified. A running example is used to demonstrate the proposed method. <s> BIB022 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> Deadlock prevention and siphon <s> Even for a simple automated manufacturing system (AMS), such as a general single-unit resource allocation system, the computation of an optimal or maximally permissive deadlock-avoidance policy (DAP) is NP-hard. Based on its Petri-net model, this paper addresses the deadlock-avoidance problem in AMSs, which can be modeled by systems of simple sequential processes with resources. First, deadlock is characterized as a perfect resource-transition circuit that is saturated at a reachable state. Second, for AMSs that do not have one-unit resources shared by two or more perfect resource-transition circuits that do not contain each other, it is proved that there are only two kinds of reachable states: safe states and deadlock. An algorithm for determining the safety of a new state resulting from a safe one is then presented, which has polynomial complexity. Hence, the optimal DAP with polynomial complexity can be obtained by a one-step look-ahead method, and the deadlock-avoidance problem is polynomially solved with Petri nets for the first time. Finally, by reducing a Petri-net model and applying the design of optimal DAP to the reduced one, a suboptimal DAP for a general AMS is synthesized, and its computation is of polynomial complexity. <s> BIB023 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> Deadlock prevention and siphon <s> This paper focuses on the problem of deadlocks in automated flexible manufacturing systems (FMS) where deadlocks are caused by unmarked siphons in their Petri net models. A deadlock prevention policy is proposed for a subclass of Petri nets, S^3PMR that can well model a large class of FMS. We distinguish siphons in such a net model by elementary and dependent ones. For each elementary siphon, a monitor is added to the plant model such that it is invariant-controlled. The monitor addition way guarantees that no emptiable control-induced siphon is generated due to the presence of monitors in the resultant net. This novel deadlock prevention policy can usually lead to a more permissive supervisor by adding a small number of monitors and arcs than the existing methods for the design of liveness-enforcing Petri net supervisors. Experimental study indicates that the proposed policy appears to be more permissive than closely related approaches in the literature. <s> BIB024 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> Deadlock prevention and siphon <s> For the purpose of deadlock control, siphons in a Petri net (PN) can be divided into elementary and dependent ones; the latter can further be distinguished by strongly and weakly dependent siphons (WDS). The computation of the elementary siphons in a PN is essential but expensive since a complete siphon enumeration is needed. The results reported in the literature show that the control of WDS is quite conservative. Li et al. present two open problems. First, for what kinds of PN, we can definitely find a set of elementary siphons such that no WDS can be derived? Secondly, could we develop an algorithm to find a set of elementary siphons that can minimise the number of WDS in a net? The aim here is to answer the first problem for an systems of simple sequential processes with resources (S3PR) by investigating its structural conditions under which there are no WDS in it. The authors address such an issue by using an incremental approach for the synthesis of subnets (to compute an strict minimal siphon) of a strongly connected resource component. At each step, the authors add a PP-handle Hi with at least one interior resource place. The structural condition for the absence of WDS is derived and show that the maximal class of S3PR is a 2c+-system. <s> BIB025 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> Deadlock prevention and siphon <s> We propose adding monitors to each basic siphon and find conditions for a compound siphon to be already controlled. This (1) relieves the problem of siphon enumeration, which grows exponentially, and (2) reduces the number of subsequent time-consuming mixed integer programming (MIP) iterations. <s> BIB026 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> Deadlock prevention and siphon <s> In Petri-net (PN) modeling of flexible manufacturing systems, deadlock prevention is often addressed by means of siphon-control methods. Constraints that avoid the emptying of siphons can be easily implemented using additional places suitably connected to the PN transitions. Efficient siphon-based techniques achieve highly permissive solutions using as few control places as possible. One such technique employs a set-covering approach to optimally match emptiable siphons to critical markings. In this paper, a modified version of the method is proposed that achieves the same results in terms of permissivity and size of the control subnet but avoids full siphon enumeration. This greatly reduces the overall computational time and memory requirements and allows the applicability of the method to large-size models. <s> BIB027 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> Deadlock prevention and siphon <s> Resource Allocation Systems: Concepts and Problems.- Logical Control of Disjunctive / Conjunctive Resource Allocation Systems.- Sequential RAS Admitting Optimal Nonblocking Supervision of Polynomial Complexity.- Polynomial-Kernel Nonblocking Supervisory Control Policies for Single-Unit RAS.- Logical Control of RAS with Complex Process Flows.- Performance-Oriented Modelling and Control of Logically Controlled RAS.- Epilogue. <s> BIB028 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> Deadlock prevention and siphon <s> Over the last two decades, a number of deadlock control policies based on Petri nets were proposed for flexible manufacturing systems (FMSs). As a structural object of a Petri net, siphons are widely used in deadlock control. For system of sequential systems with shared resources (S4R), the current deadlock control policies based on max or max′-controlled siphons tend to overly restrict the behaviour of a controlled system. The controllability conditions of a siphon are relaxed by a new concept called max″-controlled ones. We conclude that an S4R is live if all its siphons are max″-controlled. Compared with the existing ones, the proposed one is more general. Examples are given to illustrate it. <s> BIB029 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> Deadlock prevention and siphon <s> A siphon-based algorithm for deadlock prevention of Petri nets called Algorithm H2 is proposed in the above paper. However, the illustrative examples for Algorithm H2 are incorrect because of the redundant weighted control (WC) places which control some marked siphons. This correspondence modifies the illustrative examples by removing the redundant control places and getting a maximally permissive control for the original net. As no WC place is presented in the modified examples, the examples cannot well illustrate Algorithm H2. <s> BIB030 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> Deadlock prevention and siphon <s> The resource-transition circuit ( RTC) and siphon are two different structural objects of Petri nets and used to develop deadlock control policies for automated manufacturing systems. They are related to the liveness property of Petri net models and thus used to characterize and avoid deadlocks. Based on them, there are two kinds of methods for developing deadlock controllers. Such methods rely on the computation of all maximal perfect RTCs and strict minimal siphons (SMSs), respectively. This paper concentrates on a class of Petri nets called a system of simple sequential processes with resources, establishes the relation between two kinds of control methods, and identifies maximal perfect RTCs and SMSs. A graph-based technique is used to find all elementary RTC structures. They are then used to derive all RTCs. Next, an iterative method is developed to recursively construct all maximal perfect RTCs from elementary ones. Finally, a one-to-one correspondence between SMSs and maximal perfect RTCs and, hence, an equivalence between two deadlock control methods are established. <s> BIB031
Siphons are well recognized to be tied with deadlocks in FMS, which is true in either ordinary or generalized Petri nets. The fact was adequately represented by Reveliotis BIB003 BIB004  BIB028 . In short, a siphon is a set of places. Once a siphon loses all its tokens, it remains unmarked under any subsequent markings that are reachable from the current marking. It is evident that if a siphon is emptied under a certain marking, some of its output transitions would never enable which leads to a local or global deadlock. In recent years, many researches about deadlock prevention have been done based on siphon, adding monitors for strict minimal siphons to achieve deadlock prevention BIB030 BIB013 . As a result, the first step to design a siphon-based deadlock prevention control policy is to compute strict minimal siphons. In order to deal with the inherent complexity of computing siphons in Petri nets, Chu and Xie BIB001 proposed a deadlock detection method by solving a mixed integer programming (MIP) problem. It is used extensively BIB002 BIB007 BIB010 BIB014 BIB021  . Given a Petri net, Chu and Xie achieved the algorithm that computes maximum unmarked siphon by MIP. Motivated by the fact that deadlock control is usually concerned with minimal siphons in a Petri net, Huang BIB002 BIB007 ，Li and Liu BIB010 et al. Investigated minimal siphon extraction methods from a maximal unmarked siphon. The experiment data shows that MIP-based method is more efficient than any methods that depend on a complete siphon enumeration. But MIP-based method also suffers definitely from an exponential complexity problem with respect to the size of its plant net model BIB002 BIB007 BIB010 BIB014 BIB021  . It means that this method cannot be applied widely in actual large scale FMS  . In order to tackle the computational complexity problem of MIP-based method, Li and Zhou  BIB015 BIB016 BIB022 pioneered in utilizing resource circuits to compute strict minimal siphons for S 3 PR. By analyzing the structural characteristics of a resource circuit, the sufficient condition of which the siphons related to resource circuits are strict minimal siphons is proposed. Compared with MIP-based approach, this approach improves the computational efficiency. However, there is no complete algorithm of computing strict minimal siphons through resource circuits proposed. Wang et al. BIB022 proposed a sufficient and necessary condition under which the resource circuits can generate strict minimal siphons in L-S 3 PR. Then they proposed a strict minimal siphons extraction method based on graph theory and resource circuits. But this method cannot compute strict minimal siphons in S 3 PR, because L-S 3 PR is a subclass of S 3 PR. Recently, many scholars have been studying about this work, such as Xing, Wang, etc BIB031 BIB023 . Wang  proposed the necessary and sufficient conditions for loop resource subsets to generate strict minimal siphons. A method to compute strict minimal siphons has been developed in his paper. Also, the experimental study shows that the resource circuit-based method is an effective way to compute strict minimal siphons for S 3 PR. Compared with the method based on resource circuits, the resource circuit-based method has a higher computational efficiency via many randomly generated examples. Even in a Petri net with simple structure, the number of its strict minimal siphons can be proved to be, in the worst case, exponential with its structural size. If all strict minimal siphons are controlled without considering any difference among them, the resulting liveness-enforcing Petri net supervisors are structurally complex in theory. For the structural complexity problem in a liveness-enforcing Petri net supervisor, strict minimal siphons in a Petri net are divided into several categories for deadlock control purpose. Li and Zhou BIB005 BIB008 classified strict minimal siphons of a Petri net into two categories: elementary and dependent siphons. They proved that under some conditions, a live supervisor can be obtained by controlling elementary siphons only, which avoids the redundant monitors and hence significantly improves the computational efficiency. Thus elementary siphon theory is widely adopted in deadlock prevention control strategies for which it simplify the structure of supervisor BIB017 BIB011 . Unfortunately, there is not only one set of elementary siphons in a Petri net. So it should be cautious when choose elementary siphons BIB018 . For S 3 PR, Li et al. BIB023 proposed an iterative deadlock prevention policy based on elementary siphon utilizing MIP deadlock detection. This method doesn't need to compute all strict minimal siphons. What we need to do are to find a maximal empty siphon and extract a strict minimal siphon fromt each iteration. If the extracted siphon belongs to elementary siphon, it is controlled explicitly. If it belongs to dependent siphon, we should judge its controllability to decide whether control this dependent siphon explicitly or not. The termination condition for iteration is to find no emptiable siphon by MIP. To a large extent, the method improves the computational complexity and structural complexity of method proposed in BIB028 , but has no clear improvement on behavioral permissiveness. After that, it got further improved BIB009 . Deadlock control policy in BIB009 has two steps: the first step, just as BIB023 does, is to add a monitor for each elementary siphon and be sure that output arc of monitor points to source transition of Petri net model; the second step is to remove output arc of monitor from source transition. It is worth noting that the premise of which output arc can be removed is that the remove would not disable the controlled system. This approach makes the behavioral permissiveness of a controller get a obvious improvement. The deadlock prevention policies underlying the idea of elementary siphons can also be found in BIB012 BIB024 . In addition, the condition proposed in BIB005 is too conservative, in many cases, to judge the controllability of dependent siphons. Subsequently, many scholars aim at solving this defect BIB019 BIB020 BIB025  BIB029 BIB026 . An idea is proposed which to some extent is similar to that of elementary siphons. Pirrodi et al. developed a selective siphon control policy in which the concepts of essential and dominated siphons are proposed BIB027 BIB006 . By solving set covering problems, essential siphons are found to ensure that dominated siphons are controlled. However, this approach is NP-hard in theory. In the design of deadlock prevention supervisor based on siphons, the computational complexity is contributed by the computation of strict minimal siphons, while the structural complexity is because the controllability problem of strict minimal siphons can not be solved effectively. The majority of existing deadlock prevention policies intended to add control places to strict minimal siphons in order to prevent the occurrence of deadlocks. Hence, the chief task of deadlock prevention policies based on strict minimal siphons is to compute strict minimal siphons. It is noteworthy that many scientists show great research interests in such research field, and achieve many algorithms to compute strict minimal siphons. Unfortunately, these algorithms don't have high efficiency, especially in large systems. For instance, there is a system containing 86 places and 70 transitions  . As is known, the resource circuit-based approach offers much higher computational efficiency than some direct strict minimal siphons computation approaches such as the INA-based method  and the sign matrix method. But it costs at least one hour to compute all strict minimal siphons using the resource circuit-based approach  BIB015 BIB016 BIB022 . In addition, the model of FMS will be more complex and larger in actual application. A great number of deadlock prevention policies are hard to be applied to large-scale systems for the reason of the restriction of computation efficiency of strict minimal siphons.