Deadlock analysis and control based on Petri nets: A siphon approach review

Abstract

Deadlocks should be eliminated in highly automated manufacturing systems since their occurrence implies the stoppage of the whole or partial system operation. Over the past decades, Petri nets are increasingly becoming one of the most popular and full-fledged mathematical tools to deal with deadlock problems due to their inherent characteristics. In a Petri net formalism, liveness is an important property of system safeness, which implies the absence of global and local deadlock situations in an automated manufacturing system. The liveness assessment can be performed by verifying the satisfiability of certain predicates on siphons, a well-known structural object in Petri nets. Therefore, siphons have received much attention to analyze and control systems modeled with Petri nets. Particularly, elementary siphon theory plays a key role in the development of structurally simple liveness-enforcing Petri net supervisors, leading to a variety of deadlock control approaches. This survey studies on the state-of-the-art elementary siphon theory of Petri nets including refined concepts of elementary siphons and their extended version, computation methods of siphons and elementary ones, controllability conditions, and their application to deadlock control. As a reference, this work attempts to provide a comprehensive and updated research survey on siphons, elementary siphons, and their applications to the deadlock resolution in Petri nets.

Keywords

Petri net deadlock prevention structural analysis siphon elementary siphon

Introduction

An automated manufacturing system (AMS)^1,2 is a system consisting of a set of interconnected stations for material processing that is capable of automatically processing a wide variety of types of pieces simultaneously and controlled by computers. An AMS has characteristics of high degree of automation, high degree of integration, and high degree of flexibility. The flexibility means that a system can swiftly adjust the production volume, the process routing, and the product quality. AMSs offer flexibility and efficiency far beyond traditional material handling requirements. The development of AMSs can trace to the later half of the 20th century, and this manufacturing technique is used in facilities of varying scale all over the world.

Nowadays, information technology is extensively applied to contemporary AMSs, which renders that modern AMSs are becoming software-intensive systems. The reliability, safety, and other miscellaneous requirements of a system are satisfied by control software. Deadlock problems in AMSs^{3–17,320,326} have received increasing attention from both industry and academy since deadlocks can not only cause a partial or whole stoppage in a system, but also bring about catastrophic consequences in highly automated systems. The occurrences of deadlocks^18–21 often deteriorate the allocation of resources and may give rise to serious economy loss in highly AMSs.

Petri nets^{22–47,313,321–324,329} can be used in all stages starting from modeling to control implementation. And both plant and supervisor models can be unified in the formalism of Petri nets. This feature can greatly facilitate modeling, open-loop system analysis and synthesis, control implementation, and closed-loop system analysis and evaluation. On one hand, computation related to Petri net models can be inexpensive by fully utilizing their structural information. On the other hand, a set of systematic mathematical analysis approaches has been developed for studying Petri nets that promotes their popularity, which includes reachability analysis as well as structure-based linear algebraic methods. Actually, Petri nets have attracted much interest over the past decades to cope with deadlock issues, leading to a deluge of deadlock control strategies.^{48–117,312,314,325}

At present, deadlock resolution methods in AMSs modeled with Petri nets are mainly classified into three strategies: deadlock detection and recovery, deadlock avoidance, and deadlock prevention. Many achievements have been made among these strategies in the literature. Deadlock detection and recovery^{17,55,118–121,311,317,327} uses an online mechanism. When a deadlock occurs, it is detected and then the system is put back to a deadlock-free state. Deadlock avoidance^{4,11,12,15,48,53,54,56,57,73,106,107,109,122–136,319} is a resources allocation mechanism, behind which an online control policy is used to make a correct decision to proceed among the feasible evolutions. Deadlock prevention^{6,49,71,72,75,77,82,91,95–98,103,111,137–146,308–310,315,328} is usually achieved using an off-line computational mechanism to control the request for resources to ensure that deadlocks never occur. Furthermore, it is worth mentioning that Petri nets have been extensively applied to the problems of scheduling,^147–150 reconfiguration,^151,152 and other applications.^153–171

Motivated by the established Petri net analysis techniques, deadlock prevention is usually developed by utilizing two major techniques, reachability analysis^172–183 and structural analysis methods.^{131,184–205,316,318} There are three important criteria in evaluating the performance of a liveness-enforcing supervisor for a system to be controlled: behavioral permissiveness, structural complexity, and computational complexity. Determining how to design a maximally permissive Petri net supervisor is always a significant problem. Owing to the fact that a reachability graph can fully reflect the behavior of a Petri net system, reachability graph-based policies^{100,101,206–214} can always obtain a highly or even maximally permissive liveness-enforcing supervisor. However, the computation is very expensive.

One of the most interesting past developments is the use of some structural objects to derive liveness-enforcing supervisors for Petri nets modeling AMSs. As a major structural object, siphons are closely related to deadlocks. In a Petri net, in case that a siphon is emptied or insufficiently marked, all its related transitions can never be enabled, which indicates the permanent blocking of part or all processes in the net system. Siphons are extensively utilized in the analysis and control of deadlocks in AMSs modeled by Petri nets, leading to a large number of siphon-based deadlock control strategies. However, the power of the siphon-based liveness-enforcing approaches is degraded and deteriorated by the fact that the number of strict minimal siphons (SMSs) in a Petri net grows quickly beyond practical limits and often grows exponentially with respect to the net size. They suffer from the computational complexity problem due to the fact that, generally, a complete siphon enumeration in a Petri net is non-deterministic polynomial (NP)-complete. Furthermore, they usually cause liveness-enforcing Petri net supervisors with more complicated structure than the plant net model that is originally built.

In order to cope with above problems, elementary siphon theory is developed by Li and Zhou.^215,216 SMSs in a Petri net model can be categorized into elementary siphons and dependent ones. The latter can be further distinguished by strongly and weakly dependent siphons. The upper bound of the elementary siphons in a net is no greater than the smaller one of place and transition counts. They prove that in some cases, by designing a monitor for each elementary siphon to make it controlled, deadlock can be successfully prevented. A dependent siphon can be implicitly controlled by properly arranging the number of tokens that can stay at its elementary siphons. The results mentioned above have widely applied to a variety of elementary siphon–related deadlock control approaches^{139,217–233} in the literature. This article mainly aims to reveal, first, how the elementary siphon theory of Petri nets can be used to troubleshoot deadlock problems, and second, how the refined concept of elementary siphons in a Petri net improves the existing deadlock control policies.

The rest of this article is organized as follows. In section “Siphons and controllability conditions,” siphons and their controllability conditions are presented. Section “Elementary siphon theory” expounds the elementary siphon theory in detail, including the concepts of elementary siphons and augmented ones, as well as their controllability conditions. Section “Computation of siphons and elementary siphons” surveys the computation methods of siphons and elementary siphons. The wide applications of siphon-based deadlock control approaches, a complete or partial siphon enumeration, elementary siphons, and related combined techniques are reviewed in section “Siphon-based deadlock control policies.” Section “Concluding remarks” concludes this article.

Siphons and controllability conditions

Siphons and traps

As a structural object of Petri nets, siphons play a significant role in the analysis of their behavioral properties, particularly liveness. Some major definitions and properties are reviewed first, and more details can be found in the works by Li and Zhou³¹ and Murata.³⁴ Basic definitions and notations can be found in Appendix 1.

Definition 1

A nonempty place set $S \subseteq P$ is a siphon if ${}^{•}S \subseteq S^{•}$ . $S \subseteq P$ is a trap if $S^{•} \subseteq^{•} S$ . A siphon (respectively (resp.) trap) is minimal if there is no siphon (resp. trap) contained in it as a proper subset. A minimal siphon S is said to be strict if ${}^{•}S \subset S^{•}$ , that is, it contains no marked trap.

Property 1

Let $S_{1}$ and $S_{2}$ be two siphons (resp. traps). Then, $S_{1} \cup S_{2}$ is a siphon (resp. trap).

Corollary 1

If I is a P-semiflow, then $| | I | |$ is both a siphon and trap.

Note that, since a P-invariant depends on both the topological structure of a net and the arcs weights, the converse of Corollary 1 is not true. However, a siphon or trap is only related with the topological structure. Corollary 1 indicates that a siphon can never be emptied if it contains the support of a P-semiflow and the support is initially marked.

Example 1

Take the net shown in Figure 1 as an example. It has four siphons $S_{1} = {p_{1}, p_{2}, p_{3}}$ , $S_{2} = {p_{3}, p_{4}}$ , $S_{3} = {p_{2}, p_{3}, p_{5}}$ , and $S_{4} = {p_{3}, p_{5}}$ , where $S_{1}$ , $S_{2}$ , and $S_{4}$ are minimal. By ${{}^{•}S}_{4} = {t_{2}, t_{3}}$ and $S_{4}^{•} = {t_{1}, t_{2}, t_{3}}$ , we have ${{}^{•}S}_{4} \subset {S_{4}}^{•}$ , which means that $S_{4}$ is an SMS. In Figure 1, $S_{1}$ , $S_{2}$ , and $S_{3}$ are both siphons and traps since ${{}^{•}S}_{1} = S_{1}^{•}$ , ${{}^{•}S}_{2} = S_{2}^{•}$ , and ${{}^{•}S}_{3} = S_{3}^{•}$ .

Figure 1.

A Petri net $(N, M_{0})$ .

Property 2

Let $M \in R (N, M_{0})$ be a marking of net $(N, M_{0})$ and S be a siphon. If $M (S) = 0$ , then $\forall M' \in R (N, M)$ , $M' (S) = 0$ .

Property 3

Let $M \in R (N, M_{0})$ be a marking of net $(N, M_{0})$ and S be a trap. If $M (S) > 0$ , then $\forall M' \in R (N, M)$ , $M' (S) > 0$ .

These two properties indicate that once a siphon is emptied, it remains unmarked at any subsequent markings that are reachable from the current marking, and once a trap is marked at a marking, it is always marked at the subsequent markings. An empty siphon S means that $∄ t \in S^{•}$ , t is enabled. By Definition 1, all transitions belong to the postset of a siphon can never be enabled once it is emptied. Therefore, they are dead, which leads to the fact that a net containing these transitions is not live. As a result, siphons as an important structure object and their markedness or emptiness are closely related with the liveness and deadlock-freedom of a Petri net.

Controllability conditions of siphons

The controllability concept of a Petri net can be found in the works by Murata³⁴ and Barkaoui and Pradat-Peyre.²³⁴ A net is said to be completely controllable if any marking is reachable from any other marking.³⁴ In an ordinary Petri net, a siphon is said to be controlled if it cannot be unmarked at any reachable marking.^31,235 If a Petri net is generalized, owing to the weights of arcs, the non-emptiness of a siphon is not sufficient for the absence of dead transitions, and the controllability of a siphon is much more complex. This part reviews the controllability of siphons in the literature.

Ordinary Petri nets

Theorem 1

Let $(N, M_{0})$ be an ordinary net and $Π$ be the set of its siphons.^31,234 The net is deadlock-free if $\forall S \in Π$ , $\forall M \in R (N, M_{0})$ , $M (S) > 0$ .

Theorem 2

Let $(N, M)$ be an ordinary net that is in a deadlock state.^31,234 Then, ${p \in P | M (p) = 0}$ is a siphon.

Theorem 1 means that if no (minimal) siphon eventually becomes empty, an ordinary Petri net is deadlock-free. Theorem 2 implies that if an ordinary net is dead, then all unmarked places form a siphon.

Corollary 2

A deadlocked ordinary Petri net contains at least one empty siphon.^31,234

Definition 2

A siphon S is said to be controlled in an ordinary Petri net system $(N, M_{0})$ if $\forall M \in R (N, M_{0})$ , $M (S) > 0$ .^31,234

Definition 3

Siphon S in an ordinary net system $(N, M_{0})$ is invariant-controlled by P-invariant I at $M_{0}$ if $I^{T} M_{0} > 0$ and $\forall p \in P \ S$ , $I (p) \leq 0$ , or equivalently, $I^{T} M_{0} > 0$ and $| | I | |^{+} \subseteq S$ .^31,234

At an initial marking $M_{0}$ , if a siphon S is controlled by a P-invariant I, S cannot be emptied, that is, S is marked at any reachable marking $M \in R (N, M_{0})$ . In essence, the controllability of siphon S by adding a monitor is ensured by the fact that the number of tokens outflows from S is restricted by a marking invariant law imposed on the Petri net, which is implemented by a P-invariant whose support contains the monitor.

Generalized Petri nets

An empty siphon in an ordinary net can cause some transitions to be disabled forever. The case in a generalized Petri net is much more complicated. Owing to the weighted arcs, an insufficiently marked siphon leads to the occurrence of deadlocks.

Corollary 3

Let $N = (P, T, F, W)$ be a deadlocked net at marking M.³¹ Then, it has at least one siphon S such that $\forall p \in S$ , $\exists t \in p^{•}$ such that $W (p, t) > M (p)$ .

On the whole, the controllability concept is concerned with the enabling and firing of transitions connected with the considered siphons.

Max-controlled conditions

Barkaoui and colleagues^234,236 first propose the concepts of max-controlled siphons and cs-property (controlled-siphon property) for Petri nets. Barkaoui et al.²³⁷ conclude that an asymmetric choice net with homogeneous valuation is live if it satisfies the cs-property. A marked S⁴PR net is live if it satisfies the cs-property, which means that the cs-property is a sufficient but not necessary condition for the liveness of an S⁴R.^31,238

Definition 4

Let $(N, M_{0})$ be a net system and S be a siphon of N.²³⁴S is said to be max-marked at a marking $M \in R (N, M_{0})$ if $\exists p \in S$ such that $M (p) \geq ma x_{p^{•}}$ , where $ma x_{p^{•}} = \max {W (p, t) | t \in p^{•}}$ .

Definition 5

A siphon is said to be max-controlled if it is max-marked at any reachable marking.²³⁴

Definition 6

$(N, M_{0})$ satisfies the cs-property (controlled-siphon property) if each minimal siphon of N is max-controlled.²³⁴

Property 4

If $(N, M_{0})$ satisfies the cs-property, it is deadlock-free.²³⁷

Property 5

If $(N, M_{0})$ is live, it satisfies the cs-property.²³⁷

A siphon satisfying the max-controlled property means that it can be always marked sufficiently to allow firing a transition associated with the siphon once at least. A Petri net is deadlock-free if it satisfies the cs-property.

Proposition 1

Let $(N, M_{0})$ be a Petri net and S be a siphon of N.²³⁴ If there exists a P-invariant I such that $\forall p \in (| | I | |^{-} \cap S)$ , $ma x_{p^{•}} = 1$ , $| | I | |^{+} \subseteq S$ and $I^{T} M_{0} > \sum_{p \in S} I (p) (ma x_{p^{•}} - 1)$ , then S is max-controlled.

Example 2

For the generalized net in Figure 2(a), it has two P-invariants $I_{1} = p_{2} + p_{6}$ and $I_{2} = p_{2} + 2 p_{3} + p_{5}$ . Trivially, $I = I_{2} - I_{1} = 2 p_{3} + p_{5} - p_{6}$ is also a P-invariant. Let $S = {p_{3}, p_{5}}$ . Since ${}^{•}S \subset S^{•}$ , S is an SMS. It can be found that $| | I | |^{+} = S$ , $| | I | |^{-} \cap S = \emptyset$ , and $I^{T} M_{0} = M_{0} (p_{5}) + 2 M_{0} (p_{3}) - M_{0} (p_{6}) = 1$ . We have $\sum_{p \in S} I (p) (ma x_{p^{•}} - 1) = I (p_{3}) (ma x_{p_{3}^{•}} - 1) + I (p_{5}) (ma x_{p_{5}^{•}} - 1) = 0$ . In consequence, S is max-controlled owing to $I^{T} M_{0} > \sum_{p \in S} I (p) (ma x_{p^{•}} - 1)$ . The reachability graph of the net in Figure 2(a) is shown in Figure 2(b).

Figure 2.

(a) A Petri net $(N, M_{0})$ and (b) the reachability graph of $(N, M_{0})$ .

Barkaoui et al.²³⁷ propose a more important result about the equivalence between liveness and cs-property in an ordered P/T system. Ordered P/T systems (not necessarily bounded) include a number of subclasses of Petri nets, such as asymmetric choice (AC) systems,²³⁴ Join Free (JF) systems, Equal Conflict (EC) systems,²³⁹ and Extended Free Choice (EFC) nets.

Theorem 3

Let $(N, M_{0})$ be an ordered P/T system.²³⁷ The two following statements are equivalent: (1) $(N, M_{0})$ satisfies the cs-property and (2) $(N, M_{0})$ is live.

Max′-controlled conditions

The max′-controlled condition of siphons is first proposed by Chao²³⁸ in S⁴PR for the sake of reducing the restriction of the max-controlled condition. Zhong and Li²⁴⁰ refine this concept and develop a formal definition of self-max′-controlled conditions for WS³PR. They conclude that a WS³PR is live if each SMS is self-max′-controlled. Motivated by the work of Chao,²³⁸ Hou et al.²²² propose the formal definitions of max′-controlled conditions for S⁴PR. The following results are mainly from the works by Chao²³⁸ and Hou et al.²²²

Let $N = (P, T, F, W)$ be a Petri net and $S \subseteq P$ be a subset of places.²³⁸ The subnet generated by $X = S \cup^{•} S$ is denoted by $N_{S}$ , where $N_{S} = (S,^{•} S, F_{X}, W_{X})$ . The set of input places of $N_{S}$ is called the set of input places of S, denoted as $P_{S}^{in}$ .²²²

Definition 7

Let $Π$ be the set of minimal siphons in a net $(N, M_{0})$ .³¹ It is said to be well-initially-marked if $\forall S \in Π$ , $M_{\max} (S) = M_{0} (S)$ , where $M_{\max} (S) = \max {M (S) | M \in R (N, M_{0})}$ .

Definition 8

Let S be a siphon of a well-initially-marked S⁴PR $(N, M_{0})$ .²²²S is said to be max′-marked at marking $M \in R (N, M_{0})$ if: (1) $\exists p \in S^{P}$ such that $M (p) \geq 1$ , or (2) $\exists p \in S^{R}$ such that $M (p) \geq ma x_{t \in (p^{•} \cap {([S] \cap P_{S}^{in})}^{•})} {W (p, t)}$ .

Definition 9

Let S be a siphon of a well-initially-marked S⁴PR $(N, M_{0})$ .²²²S is said to be max′-controlled if S is max′-marked at any reachable marking $M \in R (N, M_{0})$ .

Theorem 4

Let $(N, M_{0})$ be a well-initially-marked S⁴PR.²³⁸N is live if every siphon in N is max′-controlled.

Example 3

In the net shown in Figure 3, S is an SMS with $S^{P} = S \cap P_{A} = {p_{3}, p_{6}, p_{8}}$ and $S^{R} = S \cap P_{R} = {p_{9}, p_{10}}$ . Then, we have $[S] = {p_{2}, p_{5}}$ and $P_{S}^{in} = {p_{2}, p_{5}}$ . Note that $[S]^{•} = {t_{2}, t_{5}}$ , $p_{9}^{•} \cap [S]^{•} = {t_{5}}$ , and $p_{10}^{•} \cap [S]^{•} = {t_{2}}$ . For $p_{9} \in S^{R}$ , $M' (p_{9}) = ma x_{t \in (p_{9}^{•} \cap {([S] \cap P_{S}^{in})}^{•})} {W (p_{9}, t)} = W (p_{9}, t_{5}) = 1$ . As a result, S is max′-marked at $M'$ .

Figure 3.

An S⁴PR $(N_{1}, M_{0_{1}})$ .

Max″-controlled conditions

Liu et al.²⁰¹ present the max″-controllability condition of siphons to relax the max′-controllability condition.

Definition 10

Let S be a siphon in a well-marked S⁴PR $(N, M_{0})$ .²⁰¹S is said to be max″-controllable if the following conditions hold:

M is an initial marking;

$\exists p \in S^{P}$ such that $M (p) \geq 1$ ;

$\exists r \in S^{R}$ , $\min \sum_{t \in T'} α (t, r) \cdot W (t, r) + M (r) \geq ma x_{t' \in r^{•} \cap [S^{•}]} {W (r, t')}$ , where $T' = {t | t \in^{•} r \cap [S]^{•}, \forall r' \in^{•} t \cap P_{R}, M (r') \geq W (r', t), M (P_{A} \cap^{•} t) \geq 1}$ , $α_{t}$ denotes the times that t is fired from marking M, and $\min \sum_{t \in T'} α_{t} \cdot W (t, r)$ can be solved by the following mixed integer program

m i n \sum_{t \in T^{'}} α \cdot W (t, r)

p \in^{•} t \cap P_{A}, M (p) \geq 1, t_{x} \in p^{•} \cap T^{'}

\sum α_{t_{x}} \leq M (p)

r^{'} \in^{•} t \cap P_{R}, t_{y} \in {r^{'}}^{•} \cap T^{'}

\sum α_{t_{y}} \cdot W (r', t_{y}) \leq M (r')

t \in^{•} r \cap [S]^{•}

\min {\frac{M (r') - \sum α_{t_{y}} \cdot W (r', t_{y})}{W (r', t)}, M (p) - \sum α_{t_{x}}} < 1

α_{t} \in N

Definition 11

Let S be a siphon in a well-marked S⁴PR $(N, M_{0})$ .²⁰¹S is said to be max″-controlled if $\forall M \in R (N, M_{0})$ , S is max″-marked at M.

Theorem 5

Let $(N, M_{0})$ be a well-marked S⁴PR.²⁰¹ The net is live if all its siphons are max″-controlled.

${Max}^{★}$ -controlled conditions

Liu and Barkaoui²⁴¹ present the $ma x^{★}$ -controllability condition of siphons to relax the existing controllability conditions for GS³PR nets.

Definition 12

Let S be a strict siphon in a well-marked GS³PR net $(N, M_{0})$ .²⁴¹S is said to be $ma x^{★}$ -marked (non- $ma x^{★}$ -marked) at $M \in R (N, M_{0})$ if at least one (none) of the following conditions hold:

$\exists p \in S^{P}$ , $M (p) \geq 1$ ;

$\exists r \in S^{R}$ , $M (r) \geq ma x_{t \in T_{r}^{c}} W (r, t)$ ;

$\exists t \in T_{S}^{c}$ , $e_{pt} = 1$ , and $e_{r t} = 1$ (t is enabled at M).

Theorem 6

Let $(N, M_{0})$ be a well-marked GS³PR net and $Π \neq \emptyset$ be the set of SMS.²⁴¹ It is live if $\forall S \in Π$ , S is $ma x^{★}$ -controlled.

W-controlled conditions

A sufficient and necessary siphon (NS) controllability condition named W-control is developed by Guan et al.,²⁴² under which the liveness and maximal permissiveness of a WS³PR can be ensured if all its siphons are W-controlled.

Definition 13

Let S be a siphon in a marked WS³PR $(N, M_{0})$ with $N = (P_{A} \cup P_{0} \cup P_{R}, T, F, W)$ .²⁴²S is said to be W-marked at $M \in R (N, M_{0})$ if $\exists t \in^{•} S^{R} \cap S^{R •}$ , $M' \in R (N, M)$ such that $\exists M ″ \in R (N, M')$ satisfies $M ″ (r) \geq W (r, t)$ , where ${r} =^{•} t \cap P_{R}$ .

Definition 14

Let S be a siphon in a marked WS³PR $(N, M_{0})$ .²⁴²S is said to be W-controlled if S is W-marked at any marking $M \in R (N, M_{0})$ .

Theorem 7

Let $(N, M_{0})$ be a marked WS³PR.²⁴² The net is live if and only if all its siphons are W-controlled.

Note that max-controllability,²³⁴ max′-controllability,^222,238 and max″-controllability²⁰¹ can be utilized in S⁴PR, and all of them are sufficient but not necessary conditions. $Ma x^{★}$ -controllability and W-controllability are both necessary and sufficient. The former is proposed for GS³PR, and the latter is developed for WS³PR.

Elementary siphon theory

Elementary siphons

The theory of elementary siphons is proposed by Li and Zhou,²¹⁵ which is essential to the development of a structurally simple monitor-based liveness-enforcing supervisor and has been applied in designing live controlled systems for S³PR²³⁵ extensively. It is shown that a dependent siphon can be implicitly controlled by properly supervising the number of tokens staying in its elementary siphons. By explicitly controlling elementary siphons via monitors, a liveness-enforcing controlled system can be found. The following definitions are from the work by Li and Zhou.²¹⁵

Elementary and dependent siphons

Definition 15

Let $S \subseteq P$ be a place subset of Petri net $N = (P, T, F, W)$ .²¹⁵P-vector $λ_{S}$ is called the characteristic P-vector of S if $\forall p \in S$ , $λ_{S} (p) = 1$ ; otherwise, $λ_{S} (p) = 0$ . $η_{S} = [N]^{T} λ_{S}$ is called the characteristic T-vector of S, where $[N]^{T}$ is the transpose of incidence matrix $[N]$ .

Definition 16

Let $N = (P, T, F, W)$ be a net with $| P | = m$ , $| T | = n$ and $Π = {S_{1}, S_{2}, \dots, S_{k}}$ be a set of siphons of N, $m, n, k \in N^{+}$ .²¹⁵ Let $λ_{S_{i}}$ ( $η_{S_{i}}$ ) be the characteristic P(T)-vector of siphon $S_{i}$ , $i \in N_{k} = {1, \dots, k}$ . $[λ]_{k \times m} = [λ_{S_{1}} | λ_{S_{2}} | \dots | λ_{S_{k}}]^{T}$ and $[η]_{k \times n} = [λ]_{k \times m} \times [N]_{m \times n} = [η_{S_{1}} | η_{S_{2}} | \dots | η_{S_{k}}]^{T}$ are called the characteristic P- and T-vector matrices of the siphons in N, respectively.

Definition 17

Let $η_{S_{α}}$ , $η_{S_{β}}$ , …, $η_{S_{γ}}$ be a linearly independent maximal set of matrix $[η]$ .²¹⁵ Then, $Π_{E} = {S_{α}, S_{β}, \dots, S_{γ}}$ is called a set of elementary siphons in N. $S \notin Π_{E}$ is called a strongly dependent siphon if $η_{S} = \sum_{S_{i} \in Π_{E}} a_{i} η_{S_{i}}$ , where $a_{i} \geq 0$ . $S \notin Π_{E}$ is called a weakly dependent siphon if $\exists A, B \subset Π_{E}$ such that $A \neq \emptyset$ , $B \neq \emptyset$ , $A \cap B = \emptyset$ , and $η_{S} = \sum_{S_{i} \in A} a_{i} η_{S_{i}} - \sum_{S_{i} \in B} a_{i} η_{S_{i}}$ , where $a_{i} > 0$ .

Theorem 8

$| Π_{E} | \leq \min {| P |, | T |}$ .²¹⁵

The result indicates that the number of elementary siphons in a Petri net is no more than the smaller of place and transition counts. Let $Π$ be the siphon set in a net, and $Π_{E}$ (resp. $Π_{D}$ ) be the set of elementary (resp. dependent) ones within the scope of $Π$ . We have $Π = Π_{E} \cup Π_{D}$ .

Example 4

The Petri net shown in the left of Figure 4 has three SMSs: $S_{1} = {p_{3}, p_{6}, p_{9}, p_{13}, p_{14}}$ , $S_{2} = {p_{2}, p_{5}, p_{10}, p_{12}, p_{13}}$ , and $S_{3} = {p_{3}, p_{6}, p_{10}, p_{12}, p_{13}, p_{14}}$ . We have $[λ]$ and $[η]$ as follows

[λ] = (\begin{matrix} 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & 0 \end{matrix})

[η] = (\begin{matrix} 0 & - 1 & 1 & 0 & 0 & - 1 & 1 & 0 & - 1 & 1 & 0 & 0 \\ - 2 & 2 & 0 & 0 & 0 & 2 & 0 & 0 & 0 & - 1 & 1 & 0 \\ - 2 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & - 1 & 0 & 1 & 0 \end{matrix})

Figure 4.

A generalized Petri net $(N, M_{0})$ and its two monitors.

It can be verified that $Rank [η] = | Π_{E} | = 2$ , that is, there are two elementary siphons. If $S_{1}$ and $S_{2}$ are selected as elementary siphons, $S_{3}$ is strongly dependent with $η_{S_{3}} = η_{S_{1}} + η_{S_{2}}$ . If $S_{1}$ and $S_{3}$ are selected as elementary ones, $S_{2}$ becomes weakly dependent, and $η_{S_{2}} = η_{S_{3}} - η_{S_{1}}$ . If $S_{2}$ and $S_{3}$ are selected as elementary ones, $S_{1}$ is weakly dependent.

Controllability of dependent siphons

Li and Zhou²¹⁵ provide the conditions under which a dependent siphon can be always marked if their elementary ones are properly controlled. The following results are useful in designing of structurally simple liveness-enforcing supervisors for a Petri net model. In the following theorems and corollaries, let $M_{\min} (S) = \min {M (S) | M \in R (N, M_{0})}$ and $M_{\max} (S) = \max {M (S) | M \in R (N, M_{0})}$ .

Theorem 9

A weakly dependent siphon S is controlled if²¹⁵

\begin{array}{l} M_{0} (S) > \sum_{i = 1}^{n} a_{i} (M_{0} (S_{i}) - M_{m i n} (S_{i})) \\ - \sum_{j = n + 1}^{m} a_{j} (M_{0} (S_{j}) - M_{m a x} (S_{j})) \end{array}

Corollary 4

A strongly dependent siphon S is controlled if²¹⁵

M_{0} (S) > \sum_{i = 1}^{n} a_{i} (M_{0} (S_{i}) - M_{\min} (S_{i}))

Lemma 1

Let S be a siphon in net $(N, M_{0})$ and $M \in R (N, M_{0})$ be a marking. S is max-marked at M if $M (S) > ω (S)$ , where $ω (S) = \sum_{p \in S} (ma x_{p^{•}} - 1)$ .

Theorem 10

A strongly dependent siphon S is max-controlled if

M_{0} (S) > \sum_{i = 1}^{n} a_{i} M_{0} (S_{i}) - \sum_{i = 1}^{n} a_{i} M_{\min} (S_{i}) + ω (S)

Theorem 11

A weakly dependent siphon S is max-controlled if

\begin{array}{l} M_{0} (S) > \sum_{i = 1}^{n} a_{i} (M_{0} (S_{i}) - M_{m i n} (S_{i})) \\ - \sum_{j = n + 1}^{m} a_{j} (M_{0} (S_{j}) - M_{m a x} (S_{j})) + ω (S) \end{array}

From Definition 7, a well-initially-marked Petri net indicates that at the initial marking, a siphon has the maximal number of tokens. The controllability conditions of strongly and dependent siphons can be unified to one condition shown as follows.

Corollary 5

A dependent siphon S in a well-initially-marked net $(N, M_{0})$ is max-controlled if

M_{0} (S) > \sum_{i = 1}^{n} a_{i} (M_{0} (S_{i}) - M_{\min} (S_{i})) + ω (S)

Example 5

From Example 1, $S_{3}$ is a strongly dependent siphon with $η_{S_{3}} = η_{S_{1}} + η_{S_{2}}$ of the net in Figure 4. By considering monitors $V_{S_{1}}$ and $V_{S_{2}}$ , we have $M_{\min} (S_{1}) = M_{\min} (S_{2}) = 2$ . In addition, $M_{1} (S_{1}) = 5$ , $M_{1} (S_{2}) = 4$ , $M_{1} (S_{3}) = 7$ , and $ω (S_{3}) = 1$ and then $M_{1} (S_{3}) > \sum_{i = 1}^{2} (M_{1} (S_{i}) - M_{\min} (S_{i})) + ω (S_{3})$ holds. As a result, $S_{3}$ is max-controlled due to the control by $V_{S_{1}}$ and $V_{S_{2}}$ .

Augmented elementary siphons in generalized Petri nets

Based on the elementary siphons, a variety of deadlock control policies^{216,229–231,243–246} are developed for synthesizing liveness-enforcement supervisors. However, in generalized Petri nets, multiple resource requirements should be considered sufficiently in identifying a set of elementary siphons. Elementary siphons are further developed for generalized Petri nets.^{222–224,226}

Augmented elementary siphons in WS³PR

Augmented elementary siphons

The augmented siphon and augmented complementary set of a siphon are defined in the work by Hou et al.²²⁴ for WS³PR and then elementary siphons are redefined. The relationship between augmented siphons and their augmented complementary sets is also investigated by fully considering the weights information.

Definition 18

Let S be a siphon in a WS³PR $N = (P_{0} \cup P_{A} \cup P_{R}, T, F, W)$ with $S = S^{P} \cup S^{R}$ , $S^{R} = S \cap P_{R}$ , and $S^{P} = S \ S^{R}$ .²²⁴ A multiset $\tilde{S}$ is the augmented version of siphon S such that (1) $| | \tilde{S} | | = S$ ; (2) $\forall r \in S^{R}$ , $\tilde{S} (r) = 1$ and $\forall p \in S^{P}$ , $\tilde{S} (p) = I_{S} (p)$ , where $I_{S} (p) = \sum_{r \in S^{R}} I_{r} (p)$ and $I_{r}$ is the minimal P-semiflow associated with the resource r.

Definition 18 indicates that a siphon S and its augmented version $\tilde{S}$ are in one-to-one correspondence. $| | \tilde{S} | |$ denotes the support of the multiset $\tilde{S}$ , and $| | \tilde{S} | | = S$ means that a siphon S and its augmented version $\tilde{S}$ have same elements. $\tilde{S}$ introduces the weighted relationship of an operation place p utilizing a resource r in S, where $p, r \in S$ .

Definition 19

Let S be a siphon in a WS³PR $N = (P, T, F, W)$ . P-vector $λ_{\tilde{S}}$ is called the augmented characteristic P-vector of $\tilde{S}$ if $\forall p \in S$ , $λ_{\tilde{S}} (p) = \tilde{S} (p)$ ; otherwise $λ_{\tilde{S}} (p) = 0$ . $η_{\tilde{S}} = [N]^{T} λ_{\tilde{S}}$ is called the augmented characteristic T-vector of $\tilde{S}$ , where $[N]^{T}$ is the transpose of incidence matrices $[N]$ .

Definition 20

Let $[\tilde{λ}]_{k \times m} = [λ_{{\tilde{S}}_{1}} | λ_{{\tilde{S}}_{2}} | \dots | λ_{{\tilde{S}}_{k}}]^{T}$ and $[\tilde{η}]_{k \times n} = [\tilde{λ}]_{k \times m} \times [N]_{m \times n} = [η_{{\tilde{S}}_{1}} | η_{{\tilde{S}}_{2}} | \dots | η_{{\tilde{S}}_{k}}]^{T}$ be augmented characteristic P- and T-vector matrices of the siphons in a WS³PR $N = (P, T, F, W)$ , respectively.

$Π_{E_{A}} = {S_{α}, S_{β}, \dots, S_{γ}}$ is called a set of augmented elementary siphons in N if $η_{{\tilde{S}}_{α}}$ , $η_{{\tilde{S}}_{β}}$ , …, $η_{{\tilde{S}}_{γ}}$ form a linearly independent maximal set of matrix $[\tilde{η}]$ , where ${α, β, \dots, γ} \subseteq N_{k}$ ;

$S \notin Π_{E_{A}}$ is called a strongly augmented dependent siphon if $η_{\tilde{S}} = \sum_{S_{i} \in Π_{E_{A}}} a_{i} η_{{\tilde{S}}_{i}}$ , where $a_{i} \geq 0$ ; $S \notin Π_{E_{A}}$ is called a weakly augmented dependent siphon if $\exists A, B \subset Π_{E_{A}}$ such that $A \neq \emptyset$ , $B \neq \emptyset$ , $A \cap B = \emptyset$ , and $η_{\tilde{S}} = \sum_{S_{i} \in A} a_{i} η_{{\tilde{S}}_{i}} - \sum_{S_{j} \in B} a_{j} η_{{\tilde{S}}_{j}}$ , where $a_{i}, a_{j} \geq 0$ .

Let $Π$ (resp. $Π_{D_{A}}$ ) be the set of SMSs (resp. dependent augmented siphons). We have $Π = Π_{E_{A}} \cup Π_{D_{A}}$ .

Example 6

A WS³PR is shown in Figure 5. It has three SMSs: $S_{1} = {p_{3}, p_{8}, p_{9}, p_{10}}$ , $S_{2} = {p_{4}, p_{7}, p_{10}, p_{11}}$ , and $S_{3} = {p_{4}, p_{8}, p_{9}, p_{10}, p_{11}}$ . Their augmented versions are ${\tilde{S}}_{1} = {p_{3}, p_{8}, p_{9}, p_{10}}$ , ${\tilde{S}}_{2} = {2 p_{4}, 2 p_{7}, p_{10}, p_{11}}$ , and ${\tilde{S}}_{3} = {2 p_{4}, p_{8}, p_{9}, p_{10}, p_{11}}$ . One can obtain $λ_{{\tilde{S}}_{1}} = p_{3} + p_{8} + p_{9} + p_{10}$ , $λ_{{\tilde{S}}_{2}} = 2 p_{4} + 2 p_{7} + p_{10} + p_{11}$ , and $λ_{{\tilde{S}}_{3}} = 2 p_{4} + p_{8} + p_{9} + p_{10} + p_{11}$ . Hence, $η_{{\tilde{S}}_{1}} = - t_{1} + t_{2} - 2 t_{6} + 2 t_{7}$ , $η_{{\tilde{S}}_{2}} = - t_{2} + t_{3} - t_{5} + t_{6}$ , and $η_{{\tilde{S}}_{3}} = - t_{1} + t_{3} - t_{5} - t_{6} + 2 t_{7}$ .

Figure 5.

A WS³PR N.

We have $rank ([\tilde{η}]) = 2$ and $η_{{\tilde{S}}_{3}} = η_{{\tilde{S}}_{1}} + η_{{\tilde{S}}_{2}}$ . It means that $S_{3}$ is a strongly augmented dependent siphon, and $S_{1}$ and $S_{2}$ are the corresponding augmented elementary ones, that is, $Π_{E_{A}} = {S_{1}, S_{2}}$ and $Π_{D_{A}} = {S_{3}}$ . When the method in the work by Li and Zhou²¹⁵ is used, $rank ([η]) = 3$ can be obtained, implying that all SMSs are elementary. A compact elementary siphon set can be obtained by the improved method compared with the work by Li and Zhou.²¹⁵

Definition 21

Let $S = S^{R} \cup S^{P}$ be a siphon in a WS³PR N, and $\tilde{S}$ be its augmented version. $[\tilde{S}] = I_{S} - \tilde{S}$ is called the augmented complementary set of S.

Lemma 2

Let $\tilde{S}$ and $[\tilde{S}]$ be the augmented siphon and augmented complementary set of a siphon S in a WS³PR N, respectively. We have $λ_{\tilde{S}} + λ_{[\tilde{S}]} = I_{S}$ .

In Figure 5, $[{\tilde{S}}_{1}] = p_{2} + 2 p_{7}$ , $[{\tilde{S}}_{2}] = p_{3} + p_{6}$ , and $[{\tilde{S}}_{3}] = p_{2} + p_{3} + p_{6} + 2 p_{7}$ . It is known that for a siphon in an S³PR, $λ_{S} + λ_{[S]} = I_{S}$ ,³¹ where $[S] = I_{S} \ S$ . However, it is not always true for generalized nets. The introduction of $\tilde{S}$ and $λ_{[\tilde{S}]}$ ensures that $λ_{\tilde{S}} + λ_{[\tilde{S}]} = I_{S}$ always holds in a WS³PR. Lemma 2 indicates the relationship between $λ_{\tilde{S}}$ and $λ_{[\tilde{S}]}$ . From Definition 19, we have $[\tilde{η}] = [N]^{T} λ_{\tilde{S}}$ . Hence, the relationships between characteristic T-vectors of dependent and elementary siphons and their augmented complementary sets are consistent.

Theorem 12

Let S be a dependent siphon in N. $η_{\tilde{S}} = \sum_{i = 1}^{m} a_{i} η_{{\tilde{S}}_{i}} - \sum_{j = m + 1}^{n} a_{j} η_{{\tilde{S}}_{j}}$ if

[\tilde{S}] = \sum_{i = 1}^{m} a_{i} [{\tilde{S}}_{i}] - \sum_{j = m + 1}^{n} a_{j} [{\tilde{S}}_{j}]

Controllability of augmented dependent siphons

In a WS³PR, all SMSs are divided into the sets of augmented elementary and augmented dependent ones. The condition in Corollary 5 is still valid, under which an augmented dependent siphon can be always max-marked if their augmented elementary ones are properly controlled.

Augmented elementary siphons in GLS³PR

Elementary siphon theory is further improved by Hou et al.²²³ for a class of generalized Petri nets, namely, GLS³PR that is more general than WS³PR. The following results are from the work by Hou et al.²²³

Augmented elementary siphons

By fully investigating the net structure, especially weights information, the set of elementary siphons obtained by the improved method is more compact and well suits for GLS³PR.

Definition 22

Let $N = (P_{A} \cup P_{0} \cup P_{R}, T, F, W)$ be a GLS³PR. $\forall r \in P_{R}$ , $t \in^{•} r$ , $t' \in r^{•}$ , if $∄ t ″ \in^{•} r \cup r^{•}$ such that $t' < {{}_{N}t}^{″}$ and $t ″ < {}_{t}N$ , then $t'$ and t are called a transition-pair (t-pair for short) of r, denoted as $〈 t', t 〉$ .

Definition 23

Let $N = (P_{A} \cup P_{0} \cup P_{R}, T, F, W)$ be a GLS³PR. $\forall r \in P_{R}$ , $H (r) = | | I_{r} | | \ {r}$ , the operation places that use r, is called the set of holders of r. Its multiset version is $H_{r} = I_{r} - r$ . Let $〈 t', t 〉$ be a t-pair of r. $h^{t} (r) = {p | t' < {}_{N}p, p < {}_{t}N, p \in H (r)}$ , the operation places that use r between $t'$ and t, is called the set of holders of r with respect to t-pair $〈 t', t 〉$ . Its multiset version is $h_{r}^{t} = \sum_{p \in h^{t} (r)} I_{r} (p) p$ .

Definition 24

Let S be a siphon in a GLS³PR $N = (P_{A} \cup P_{0} \cup P_{R}, T, F, W)$ with $S = S^{P} \cup S^{R}$ , $S^{R} = S \cap P_{R}$ , and $S^{P} = S \ S^{R}$ . A multiset $\tilde{S}$ is the augmented version of S such that (1) $| | \tilde{S} | | = S$ and (2) $\forall p \in S$ , $\tilde{S} (p) = k$ , $k \in N^{+}$ : (a) $\forall p \in S^{P}$ , $\forall r \in S^{R}$ , $\tilde{S} (r) = 1$ and if $p \in h^{t} (r)$ and ${}^{•}t \cap S^{P} \neq \emptyset$ , then ${\tilde{S}}_{r} (p) = I_{r} (p)$ , else ${\tilde{S}}_{r} (p) = 0$ and (b) $\tilde{S} (p) = \sum_{r \in S^{R}} {\tilde{S}}_{r} (p)$ .

Definition 25

Let S be a siphon in a GLS³PR N. P-vector $λ_{\tilde{S}}$ is called the augmented characteristic P-vector of $\tilde{S}$ if $\forall p \in S$ , $λ_{\tilde{S}} (p) = \tilde{S} (p)$ ; otherwise $λ_{\tilde{S}} (p) = 0$ . $η_{\tilde{S}} = [N]^{T} λ_{\tilde{S}}$ is called the augmented characteristic T-vector of $\tilde{S}$ .

Definition 26

$Π_{E_{A}} = {S_{α}, S_{β}, \dots, S_{γ}}$ is called a set of augmented elementary siphons in N if $η_{{\tilde{S}}_{α}}, η_{{\tilde{S}}_{β}}, \dots, η_{{\tilde{S}}_{γ}} ({α, β, \dots, γ} \subseteq N_{k})$ constitute a linearly independent maximal set of matrix $[\tilde{η}]$ ;

Let $Π$ (resp. $Π_{D_{A}}$ ) be the set of SMSs (resp. augmented dependent siphons) in N. We have $Π = Π_{E_{A}} \cup Π_{D_{A}}$ .

Elementary and dependent siphons defined in Definition 17 are originally proposed and further clarified in the work by Li and Zhou.^215,216 In order to differentiate from the augmented elementary ones, elementary (resp. dependent) siphons obtained by Definition 17 are called the original elementary siphons, denoted as $Π_{E_{O}}$ (resp. $Π_{D_{O}}$ ).

Definition 27

Let $Π_{E_{O}}$ (resp. $Π_{D_{O}}$ ) be a set of original elementary (resp. dependent) siphons and $Π_{E_{A}}$ (resp. $Π_{D_{A}}$ ) be a set of augmented elementary (resp. dependent) siphons in a GLS³PR N. $Π_{E} = Π_{E_{O}} \cap Π_{E_{A}}$ (resp. $Π_{D} = Π_{D_{O}} \cup Π_{D_{A}}$ ) is called a set of elementary (resp. dependent) siphons of N.

Property 6

Let $Π$ be a set of SMSs in a GLS³PR. Then, $Π = Π_{E} \cup Π_{D}$ and $Π_{E} \cap Π_{D} = \emptyset$ , where $Π_{E} = Π_{E_{O}} \cap Π_{E_{A}}$ and $Π_{D} = Π_{D_{O}} \cup Π_{D_{A}}$ .

Theorem 13

Let $N'_{ES}$ (resp. $N_{E S_{O}}$ ) denote the number of elementary siphons defined in Definition 27 (resp. Definition 17). Then $N'_{ES} = | Π_{E} | \leq N_{E S_{O}}$ .

Definition 28

Let $S = S^{R} \cup S^{P}$ be a siphon in a GLS³PR N, $\tilde{S}$ be its augmented version, and $I_{S} = \sum_{r \in S^{R}} I_{r}$ . $[\tilde{S}] = I_{S} - \tilde{S}$ is called the augmented complementary set of siphon S.

Lemma 3

Let $\tilde{S}$ and $[\tilde{S}]$ be the augmented version and augmented complementary set of a siphon S in a net N, respectively. We have $λ_{\tilde{S}} + λ_{[\tilde{S}]} = I_{S}$ .

Theorem 14

Let S be an augmented dependent siphon in N. $η_{\tilde{S}} = \sum_{i = 1}^{m} a_{i} η_{{\tilde{S}}_{i}} - \sum_{j = m + 1}^{n} a_{j} η_{{\tilde{S}}_{j}}$ if

[\tilde{S}] = \sum_{i = 1}^{m} a_{i} [{\tilde{S}}_{i}] - \sum_{j = m + 1}^{n} a_{j} [{\tilde{S}}_{j}]

Example 7

The net in Figure 6 is a GLS³PR with three SMSs $S_{1}$ , $S_{2}$ , and $S_{3}$ , where $S_{1} = {p_{3}, p_{4}, p_{5}, p_{10}, p_{11}, p_{12}}$ , $S_{2} = {p_{4}, p_{5}, p_{8}, p_{9}, p_{12}, p_{13}}$ , and $S_{3} = {p_{4}, p_{5}, p_{8}, p_{10}, p_{11}, p_{12}, p_{13}}$ . The corresponding augmented siphons are ${\tilde{S}}_{1} = {p_{3}, p_{4}, p_{5}, p_{10}, p_{11}, p_{12}}$ , ${\tilde{S}}_{2} = {2 p_{4}, p_{5}, 3 p_{8}, 2 p_{9}, p_{12}, p_{13}}$ , and ${\tilde{S}}_{3} = {2 p_{4}, p_{5}, p_{8}, p_{10}, p_{11}, p_{12}, p_{13}}$ .

Figure 6.

A GLS³PR $(N, M_{0})$ .

One can obtain

\begin{matrix} λ_{{\tilde{S}}_{1}} = p_{3} + p_{4} + p_{5} + p_{10} + p_{11} + p_{12} \\ λ_{{\tilde{S}}_{2}} = 2 p_{4} + p_{5} + 3 p_{8} + 2 p_{9} + p_{12} + p_{13} \\ λ_{{\tilde{S}}_{3}} = 2 p_{4} + p_{5} + p_{8} + p_{10} + p_{11} + p_{12} + p_{13} \end{matrix}

Hence, we have

\begin{matrix} η_{{\tilde{S}}_{1}} = - t_{1} + t_{2} - 2 t_{7} + 2 t_{9} \\ η_{{\tilde{S}}_{2}} = - t_{2} + t_{3} - t_{6} + t_{7} \\ η_{{\tilde{S}}_{3}} = - t_{1} + t_{3} - t_{6} - t_{7} + 2 t_{9} \end{matrix}

It can be verified that $rank [\tilde{η}] = 2$ with $η_{{\tilde{S}}_{3}} = η_{{\tilde{S}}_{1}} + η_{{\tilde{S}}_{2}}$ , leading to $Π_{E_{A}} = {S_{1}, S_{2}}$ and $Π_{D_{A}} = {S_{3}}$ .

By Definitions 17, we have

\begin{matrix} λ_{S_{1}} = p_{3} + p_{4} + p_{5} + p_{10} + p_{11} + p_{12} \\ λ_{S_{2}} = p_{4} + p_{5} + p_{8} + p_{9} + p_{12} + p_{13} \\ λ_{S_{3}} = p_{4} + p_{5} + p_{8} + p_{10} + p_{11} + p_{12} + p_{13} \end{matrix}

Hence

\begin{matrix} η_{S_{1}} = - t_{1} + t_{2} - 2 t_{7} + 2 t_{9} \\ η_{S_{2}} = - t_{2} + t_{4} - t_{6} - t_{7} + t_{8} + t_{9} \\ η_{S_{3}} = - t_{1} + t_{4} - t_{6} - t_{7} + 2 t_{9} \end{matrix}

Then, $rank [\tilde{η}] = 3$ , implying that all SMSs are original elementary. In this example, the improved elementary siphon method can lead to a compact set of elementary siphons. According to Definition 27, we have $Π_{E} = Π_{E_{O}} \cap Π_{E_{A}} = {S_{1}, S_{2}}$ and $Π_{D} = Π_{D_{O}} \cup Π_{D_{A}} = {S_{3}}$ .

By Definition 28, $[{\tilde{S}}_{1}] = p_{2} + 2 p_{8} + 2 p_{9}$ , $[{\tilde{S}}_{2}] = p_{3} + p_{7}$ , and $[{\tilde{S}}_{3}] = p_{2} + p_{3} + p_{7} + 2 p_{8} + 2 p_{9}$ . It is found that $[{\tilde{S}}_{3}] = [{\tilde{S}}_{1}] + [{\tilde{S}}_{2}]$ , corresponding to $η_{{\tilde{S}}_{3}} = η_{{\tilde{S}}_{1}} + η_{{\tilde{S}}_{2}}$ .

Controllability of dependent siphons

In the work by Hou et al.,²²³ the elementary (resp. dependent) siphons consist of original and augmented parts. Obviously, the condition in Corollary 5 holds for all original dependent siphons. Moreover, it is proved that the condition in Corollary 5 is also applicable to augmented dependent siphons. The controllability of improved dependent siphons obtained by Definition 27 can be ensured by properly supervising their elementary siphons in GLS³PR nets.

Augmented elementary siphons in S⁴PR

Motivated by the purpose of improving the concept of elementary siphons for finding a set of more compact and suitable elementary siphons in an S⁴PR, the augmented siphons in an S⁴PR are further studied in the work by Hou et al.²²² by fully investigating the topological structure and arc weights. The improved elementary and dependent siphons are given subsequently. The following results are from the work by Hou et al.²²²

Augmented elementary siphons

Definition 29

Let $N = (P_{A} \cup P_{0} \cup P_{R}, T, F, W)$ be an S⁴PR. For $r \in P_{R}$ , $H (r) = {p | p \in | | I_{r} | | \cap P_{A}}$ , the operation places that use r, is called the set of holders of r. Let place set $h_{i} (r) \subseteq H (r)$ be a subset of holders of r and $⋃ h_{i} (r) = H (r)$ . If $\forall p \in h_{i} (r)$ , $\exists t \in (h_{i} (r))^{•}$ and $p' \in h_{i} (r)$ , such that $p^{•} \cap^{•} (p' \cup r) = {t} \neq \emptyset$ $(i \in N^{+})$ , then $h (r)$ is called a subset of sequential holders of r, denoted as $h_{i}^{s} (r)$ .

Definition 30

Let S be a siphon in an S⁴PR $N = (P_{A} \cup P_{0} \cup P_{R}, T, F, W)$ with $S = S^{P} \cup S^{R}$ , where $S^{R} = S \cap P_{R}$ and $S^{P} = S \ S^{R}$ . A multiset $\tilde{S} = \sum_{p \in S} l (p) p$ is called an augmented version of S if (1) $\forall p \in S^{R}$ , $l (p) = 1$ and (2) $\forall p \in S^{P}$ : (a) $p \in h^{s} (r)$ , if $p^{•} = {t}$ , $t \in^{•} r$ , then $\exists A = {p_{i} | p_{i} ≺_{N} p, p_{i} \in h^{s} (r), p_{i} \in S^{P}} \cup {p}$ , $\forall p \in A$ , $l_{r}^{t} (p) = W (t, r)$ and (b) $l_{r} (p) = \sum_{t \in^{•} r} l_{r}^{t} (p)$ , $l (p) = \sum_{r \in S_{R}} l_{r} (p)$ .

Definition 31

Let $S = S^{R} \cup S^{P}$ be a siphon in an S⁴PR N and $\tilde{S}$ be its augmented version. $[\tilde{S}] = I_{S} - \tilde{S}$ is called the augmented complementary set of siphon S, where $I_{S} = \sum_{r \in S^{R}} I_{r}$ .

Definition 32

Let $S \subseteq P$ be a subset of places in an S⁴PR $N = (P, T, F, W)$ . P-vector $λ_{\tilde{S}}$ is called the augmented characteristic P-vector of $\tilde{S}$ if $\forall p \in S$ , $λ_{\tilde{S}} (p) = l (p)$ ; otherwise $λ_{\tilde{S}} (p) = 0$ . $η_{\tilde{S}} = [N]^{T} λ_{\tilde{S}}$ is called the augmented characteristic T-vector of $\tilde{S}$ .

Definition 33

Let $N = (P, T, F, W)$ be an S⁴PR with $| P | = m$ and $| T | = n$ , and $Π = {S_{1}, S_{2}, \dots, S_{k}}$ be a set of siphons of N, where $m, n, k \in N^{+}$ . Let $λ_{{\tilde{S}}_{i}} (η_{{\tilde{S}}_{i}})$ be the augmented characteristic P(T)-vector of siphon $S_{i}$ , $i \in N_{k}$ . $[\tilde{λ}]_{k \times m} = [λ_{{\tilde{S}}_{1}} | λ_{{\tilde{S}}_{2}} | \dots | λ_{{\tilde{S}}_{k}}]^{T}$ and $[\tilde{η}]_{k \times n} = [\tilde{λ}]_{k \times m} \times [N]_{m \times n} = [η_{{\tilde{S}}_{1}} | η_{{\tilde{S}}_{2}} | \dots | η_{{\tilde{S}}_{k}}]^{T}$ are called the augmented characteristic P- and T-vector matrices of the siphons in N, respectively.

Definition 34

Let $[\tilde{η}]$ be the augmented characteristic T-vector matrix of the set of siphons $Π = {S_{1}, S_{2}, \dots, S_{k}}$ in an S⁴PR $N = (P, T, F, W)$ .

$Π_{E_{A}} = {S_{α}, S_{β}, \dots, S_{γ}}$ is called a set of augmented elementary siphons in N if $η_{{\tilde{S}}_{α}}$ , $η_{{\tilde{S}}_{β}}$ , …, $η_{{\tilde{S}}_{γ}}$ $({α, β, \dots, γ} \subseteq N_{k})$ are a linearly independent maximal set of matrix $[\tilde{η}]$ ;

Let $Π$ (resp. $Π_{D_{A}})$ be the set of SMSs (resp. augmented dependent siphons), we have $Π = Π_{E_{A}} \cup Π_{D_{A}}$ .

Definition 35

$Π_{E} = Π_{E_{O}} \cap Π_{E_{A}}$ (resp. $Π_{D} = Π_{D_{O}} \cup Π_{D_{A}}$ ) is called the set of elementary (resp. dependent) siphons of N.

Lemma 4

Let $Π$ be a set of SMSs in an S⁴PR. Then, $Π = Π_{E} \cup Π_{D}$ and $Π_{E} \cap Π_{D} = \emptyset$ , where $Π_{E} = Π_{E_{O}} \cap Π_{E_{A}}$ and $Π_{D} = Π_{D_{O}} \cup Π_{D_{A}}$ .

Theorem 15

Let $N'_{ES}$ (resp. $N_{E S_{O}}$ ) denote the number of elementary siphons defined in Definition 35 (resp. Definition 17). Then, $N'_{ES} = | Π_{E} | \leq N_{E S_{O}}$ .

Example 8

The net in Figure 7 is an S⁴PR. It has seven SMSs: $S_{1} = {p_{3}, p_{4}, p_{12}, p_{13}, p_{14}}$ , $S_{2} = {p_{5}, p_{11}, p_{14}, p_{15}}$ , $S_{3} = {p_{5}, p_{9}, p_{10}, p_{15}}$ , $S_{4} = {p_{6}, p_{9}, p_{10}, p_{15}, p_{16}}$ , $S_{5} = {p_{5}, p_{12}, p_{13},$ $p_{14}, p_{15}}$ , $S_{6} = {p_{6}, p_{9}, p_{11}, p_{14}, p_{15}, p_{16}}$ , and $S_{7} = {p_{6}, p_{9}, p_{12}, p_{13}, p_{14}, p_{15}, p_{16}}$ . By utilizing the concept of elementary siphons in the work by Li and Zhou²¹⁵ presented in Definition 17, one obtains

[λ] = [\begin{matrix} 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \end{matrix}]

[η] = [\begin{matrix} - 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & - 1 & 0 & 1 \\ 0 & - 1 & - 2 & 1 & 2 & 0 & 0 & - 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & - 2 & 0 & 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & - 2 & - 1 & 3 & 0 & - 2 & 0 & 2 & 0 & 0 & 0 \\ - 1 & - 1 & - 1 & 1 & 2 & 0 & 0 & - 1 & 0 & 0 & 0 & 1 \\ 0 & - 1 & - 2 & 0 & 3 & 0 & - 2 & 0 & 1 & 1 & 0 & 0 \\ - 1 & - 1 & - 1 & 0 & 3 & 0 & - 2 & 0 & 1 & 0 & 0 & 1 \end{matrix}]

Figure 7.

An S⁴PR model $(N, M_{0})$ .

We have $Rank ([η]) = 5$ , $η_{S_{5}} = η_{S_{1}} + η_{S_{2}}$ , and $η_{S_{7}} = η_{S_{1}} + η_{S_{6}}$ . It can be concluded that $Π_{E_{O}} = {S_{1} - S_{4}, S_{6}}$ and $Π_{D_{O}} = {S_{5}, S_{7}}$ .

Accordingly, the corresponding $[\tilde{λ}]$ and $[\tilde{η}]$ are shown as follows

[\tilde{λ}] = [\begin{matrix} 0 & 0 & 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 3 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 3 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 3 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 3 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 2 & 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 2 & 0 & 0 & 2 & 1 & 1 & 1 & 1 \end{matrix}]

[\tilde{η}] = [\begin{matrix} - 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & - 1 & 1 & 0 \\ 0 & - 1 & - 2 & 3 & 0 & 0 & 0 & - 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & - 2 & 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & - 2 & - 1 & 3 & 0 & - 2 & 2 & 0 & 0 & 0 & 0 \\ - 1 & - 1 & - 1 & 3 & 0 & 0 & 0 & - 1 & 0 & 0 & 1 & 0 \\ 0 & - 1 & - 2 & 0 & 3 & 0 & - 2 & 1 & 0 & 1 & 0 & 0 \\ - 1 & - 1 & - 1 & 0 & 3 & 0 & - 2 & 1 & 0 & 0 & 1 & 0 \end{matrix}]

It is verified that $Rank ([\tilde{η}]) = 5$ , $η_{{\tilde{S}}_{6}} = η_{{\tilde{S}}_{2}} + η_{{\tilde{S}}_{4}} - η_{{\tilde{S}}_{3}}$ , and $η_{{\tilde{S}}_{7}} = η_{{\tilde{S}}_{4}} + η_{{\tilde{S}}_{5}} - η_{{\tilde{S}}_{3}}$ . $Π_{E_{A}} = {S_{1} - S_{5}}$ and $Π_{D_{A}} = {S_{6}, S_{7}}$ can be obtained by Definition 34. By Definition 35, $Π_{E} = Π_{E_{O}} \cap Π_{E_{A}} = {S_{1} - S_{4}}$ and $Π_{D} = Π_{D_{O}} \cup Π_{D_{A}} = {S_{5} - S_{7}}$ can be obtained.

Controllability of dependent siphons

In order to improve the behavioral permissiveness of a liveness-enforcing supervisor, the max′-controlled siphon condition^222,238 is introduced. The controllability conditions of dependent siphons are developed by Hou et al.,²²² under which a dependent siphon can be max′-controlled if their elementary ones are max′-controlled.

Lemma 5

Let S be a siphon in an S⁴PR $(N, M_{0})$ and $M \in R (N, M_{0})$ be a marking. S is max′-marked at M if $M (S) > ϖ (S)$ , where $ϖ (S) = \sum_{p \in S^{R}} (ma x_{t \in (p^{•} \cap {([S] \cap P_{S}^{in})}^{•})} {W (p, t)} - 1)$ .

Theorem 16

An augmented dependent siphon S in an S⁴PR is max′-controlled if $M_{0} (S) > \sum_{i = 1}^{n} a_{i} (M_{0} (S_{i}) - M_{\min} (S_{i})) - \sum_{j = n + 1}^{m} a_{j} (M_{0} (S_{j}) - M_{\max} (S_{j})) + ϖ (S)$ .

Corollary 6

A dependent siphon S in a well-initially-marked S⁴PR $(N, M_{0})$ is max′-controlled if $M_{0} (S) > \sum_{i = 1}^{n} a_{i} (M_{0} (S_{i}) - M_{\min} (S_{i})) + ϖ (S)$ .

Corollary 7

Let $S_{1} \in Π_{D_{O}}$ and $S_{3} \in Π_{D_{A}}$ be dependent siphons in a net $(N, M_{0})$ with $η_{S_{1}} = η_{S_{2}} + η_{S_{3}}$ and $η_{{\tilde{S}}_{3}} = η_{{\tilde{S}}_{4}} + η_{{\tilde{S}}_{5}}$ , where $S_{2}, S_{3} \in Π_{E_{O}}$ and $S_{4}, S_{5} \in Π_{E_{A}}$ . $S_{1}$ is max′-controlled if $M_{0} (S_{1}) > \sum_{i = 2, 4, 5} (M_{0} (S_{i}) - M_{\min} (S_{i})) + ϖ (S_{1})$ .

Example 9

For the net shown in Figure 7, take $S_{4} = {p_{6}, p_{9}, p_{10}, p_{15}, p_{16}}$ as an example. Note that $[S_{4}]^{•} = {t_{4}, t_{5}, t_{8}}$ , we have $p_{15}^{•} \cap ([S_{4}] \cap P_{S_{4}}^{in})^{•} = {t_{8}}$ and $p_{16}^{•} \cap ([S_{4}] \cap P_{S_{4}}^{in})^{•} = {t_{5}}$ . Thus, $ϖ (S_{4}) = \sum_{p \in S_{4}^{R}} (ma x_{t \in (p^{•} \cap {([S] \cap P_{S}^{in})}^{•})} {W (p, t)} - 1) = 0$ , that is, $S_{4}$ is max′-controlled if $\forall M \in R (N, M_{0})$ , $M (S_{4}) > 0$ . Meanwhile, according to Definition 5, $S_{4}$ is max-controlled if $M (S_{4}) \geq 2$ . It is obvious that the max-controlled condition is more conservative than the max′-controlled condition.

For dependant siphon $S_{5}$ , $η_{S_{5}} = η_{S_{1}} + η_{S_{2}}$ . Considering that $ϖ (S_{5}) = 2$ , $S_{5}$ is max′-controlled if $M_{0} (S_{5}) > M_{0} (S_{1}) + M_{0} (S_{2}) - M_{\min} (S_{1}) - M_{\min} (S_{2}) + ϖ (S_{5})$ , that is, $M_{\min} (S_{1}) + M_{\min} (S_{2}) > 4$ .

Computation of siphons and elementary siphons

Siphons computation

Siphons can be used to characterize deadlock states and solve deadlock problems in Petri nets. Siphon-based deadlock prevention control policies need the set of minimal siphons to be computed. Hence, a lot of studies have been devoted to siphons extraction, especially SMSs.

The work by Abdallah et al.²⁴⁷ is usually considered as an earlier and seminal research to compute minimal siphons in an ordinary Petri net. For an S³PR, an efficient algorithm for finding minimal siphons based on a logic programming approach is established. Suffering from the fact that the number of siphons grows quickly with the size of a net, the computation is usually time-consuming. To address the minimal siphon enumeration problem, an iterative method is proposed by Cordone et al.²⁴⁸ based on a partitioning strategy, with additional place constraints. The method is claimed to be rather efficient, which can find $2 \times 10^{7}$ siphons within 1 h.

Chu and Xie²⁴⁹ present a deadlock detection method by solving a mixed integer programming (MIP) problem, which can effectively avoid a complete siphon enumeration. It opens a new avenue for improving the computational efficiency of siphon-based deadlock prevention policies in large-scale systems. Huang et al.²⁵⁰ and Li et al. investigate methods for extracting minimal siphons from a maximal unmarked siphon that can be derived by an MIP method. A software package that can achieve the method is developed by Liu et al.¹⁹⁷ Similar works on minimal siphon extraction based on the MIP method are reported by Li et al.²⁵¹ and Li and Li.²²⁸ To eliminate the minimal siphon extraction step, the work by Chao²⁵² proposes a revised MIP method to directly compute unmarked siphons with a minimal number of places.

An algorithm with polynomial complexity is proposed by Barkaoui and Lemaire¹⁸⁴ to decide whether a set of places is a minimal siphon. A series of classic and typical siphon computation methods are presented in the works by Barkaoui et al.,²⁵³ Ezpeleta et al.,²⁵⁴ Lautenbach,²⁵⁵ Wang et al.,²⁵⁶ and Yamauchi and Watanabe.²⁵⁷

Binary decision diagrams (BDD) have the capability of representing large sets of data with small shared data structures. Chen and Liu²⁵⁸ present a symbolic approach to find minimal siphons of Petri nets using BDD. Formally representing all siphons by a Boolean function, minimal siphons are identified from all the siphons using BDD. The authors concluded that the computation of finding all siphons is efficient; however, identifying minimal siphons is time-consuming.

Tricas and Ezpeleta²⁵⁹ show how the special syntactical constraints of S⁴PR can help in developing specific implementations to compute siphons in a very efficient way. A parallel solution to compute siphons is established by Tricas and Ezpeleta.²⁶⁰ Boer and Murata²⁶¹ introduced a sign incidence matrix which can be used as a new approach to structural analysis of Petri nets. The presented algorithm can find basis siphons. The place-minimal siphons play a central role in the algorithm.

Resource-transition circuits can be used to characterize deadlocks.²⁶² The relationship between siphons and maximal perfect resource-transition circuits is explored by Xing et al.¹³⁶ An algorithm for computing all SMSs is proposed by Wang et al.²⁶³ based on resource circuits in S³PR. In this work, the concepts of loop resource subsets and their characteristic resource subnets are proposed, and sufficient and necessary conditions for loop resource subsets to generate SMS are established. However, the method needs to generate all the characteristic resource subnets and strong connectivity of each characteristic resource subnet, which makes the method tedious. The work by Liu et al.²⁶⁴ improves the method in the work by Wang et al.²⁶³ by introducing critical resource places and their related multi-way holder places, from which whether a loop resource subset can derive an SMS can be decided directly.

Chao made much work in the computation of minimal and elementary siphons in resources allocation systems (RASs). By the concept of handles and bridges,²⁶⁵ Chao²⁶⁶ proposed a computational approach of minimal siphons. The work by Chao²⁵² develops an MIP-based siphon computation method. For an RAS that can be decomposed into a number of synchronized choice nets interconnected by resource places, an efficient approach of extracting SMSs in an incremental fashion rather than the traditional global is investigated by Chao.²⁶⁷

Elementary siphons computation

Computation of elementary siphons proposed by Li et al.²⁶⁸ is essential for deadlock control; however, it is expensive since a complete siphon enumeration is needed. They assume that the siphon constructed from each resource circuit is elementary and proposed a polynomial algorithm to compute elementary siphons. The work by Chao²¹⁹ develops a polynomial algorithm to find elementary siphons, which also constructs all SMSs on the way. The reason is that in the method proposed by Li and Zhou,²⁶⁹ a linear algebraic expression must be established for each dependent siphon, which implies that all SMSs must be located. However, all elementary siphons with polynomial complexity can be located.

Chao²¹⁷ presents the T-characteristic vector $ζ$ to compute SMSs for S³PR in an algebraic fashion. Elementary siphons can be constructed from elementary circuits. Thus, the set of elementary siphons can be computed without the knowledge of all SMSs. Based on the concept of handles and bridges,²⁶⁵ another elementary siphon computation method is developed by Chao.²¹⁸

Based on graph theory, Wang et al.²³³ propose a polynomial complexity algorithm to find a set of elementary siphons for a linear system of simple sequential processes with resources (LS³PR). The algorithm is established through the use of a resource directed graph and complementary sets of SMSs. The upper bound of the SMSs is identified. By considering the arc weights information and multiple resources utilization, Hou et al. further investigate the graph theory–based elementary siphon computation method for generalized Petri nets, WS³PR and GLS³PR. Initial resource weighted digraphs and restricted subgraphs are proposed for WS³PR and GLS³PR, respectively, from which all SMSs and elementary siphons can be derived. The related works can be found in the studies by Hou et al.^223,224

Li et al.²⁷⁰ propose an iterative algorithm to extract a set of elementary siphons in S³PR. By an MIP method, the algorithm finds a maximal unmarked siphon at each iteration, classifies the places in it, extracts an elementary siphon from the classified places, and adds a new constraint in order to extract the next elementary siphon. The algorithm iteratively executes until no new unmarked siphons can be found. A unique set of elementary siphons is obtained finally, and a complete siphon enumeration is avoided.

The work by Liu et al.²⁷¹ establishes a polynomial-time complexity algorithm for enumerating elementary siphons in a subclass of Petri nets, basic systems of simple sequential processes with resources (BS³PR), with polynomial-time complexity. By combining a graph-based technique, elementary RTCs are computed initially, from which MPCs can be derived. Then, a subset of SMSs is obtained from a subset of MPCs by the one-to-one relationship between MPCs and SMSs. A maximal set of linear independent rows of the characteristic T-vector matrix of the obtained subset of SMSs is computed by the Gauss elimination method, which corresponds to a set of elementary siphons. Some similar works can be found in the study by Wang et al.²⁷² for a linear simple sequential process with resources.

Siphon-based deadlock control policies

As a significant structural object, siphons are extensively employed to implement a large number of deadlock control methods for AMS modeled by Petri nets. This section mainly reviews siphon-based deadlock control methods in terms of siphon enumeration, elementary siphon theory, and other combined analysis techniques.

Complete siphon enumeration

As for the structural analysis techniques of Petri nets to prevent deadlocks in AMS, the seminal work conducted by Ezpeleta et al.²³⁵ is usually considered to be a classical contribution to develop the monitor-based liveness-enforcing supervisors for Petri nets. By considering a class of ordinary Petri nets, namely, S³PR nets, the relationship between SMSs and the liveness is revealed. For each unmarked SMS, a monitor is added such that it can be controlled, while all output arcs of additional monitors should point to the source transitions of the net model. After all siphons are controlled, it can be verified that the net system is live. The major advantage of this approach is that a plant net model and its supervisor are successfully separated. However, it also suffers from the issues of structural complexity, behavioral permissiveness, and computational complexity. As is well known, the number of SMSs grows exponentially with respect to the size of a net model in the worst case. From this method, the number of additional monitors is equal to that of all SMSs since every unmarked SMS needs a monitor to prevent from being emptied, resulting in high structural complexity. Second, the permissive behavior of the controlled system is overly restricted since all output arcs are directed to the source transitions. The computational complexity stems from the complete siphon enumeration. The following years after 1995 have seen that a great deal of attention is focused on the aforementioned problems.

As is gradually recognized, the limited behavioral permissiveness flaws the notable deadlock prevention policy in the work by Ezpeleta et al.²³⁵ Based on the concepts of perfect-resource-transition circuits (PRT-circuits) and their saturated states, Xing and Hu²⁶² successfully develop a liveness-enforcing Petri net supervisor for S³PR with maximally permissive behavior and a minimized number of additional monitors. Since a saturated PRT-circuit of the S³PR net implies the existence of circular wait that is tied to deadlock states, the liveness condition in the work by Xing and Hu²⁶² is characterized by the fact that no PRT-circuit can reach a saturated state at any reachable marking of the system.

Starting from PRT-circuits, elementary maximal PRT-circuits are defined by Xing et al.²⁷³ Accordingly, all elementary RTCs and their maximal PRT-circuits are recursively constructed using the graph theory. It is worth noting that the RTC and siphons are two different structural objects of Petri nets. The work by Xing et al.²⁷³ establishes two kinds of deadlock control methods by computing all maximal PRT-circuits and SMSs. Furthermore, a one-to-one correspondence between SMS and maximal PRT-circuits and equivalence relation between two deadlock control methods are presented.

Siphon-based deadlock control often suffers from reaching fewer states than the maximally permissive one. Chao and Liu²⁷⁴ report an alternative control to reach the same good states as that based on the theory of regions, but with fewer monitors, by refining some monitors into several monitors with smaller controller regions. More states can be reached since the controller region is less disturbed by covering only a place in a subregion where only one place is marked at any reachable marking. Subsequently, Chao et al.^275,276 propose a new approach that recovers the system from empty-siphon states to its former live states. The significance of this approach lies in the fact that the same number of states as the original uncontrolled model can be reached and yet using fewer monitors. Unfortunately, those methods suffer from material loss by aborting some operations.

A monitor-based liveness-enforcing Petri net supervisor derived from siphons has suffered from high structural complexity when the number of siphons is large. To obtain a small-sized Petri net controller, Liu et al.,²⁷⁷ pioneer in the concept of a controllable siphon basis, proposed a new criterion for selecting a proper subset of siphons for control. By utilizing a controllable siphon basis, a novel deadlock prevention policy is developed such that a liveness-enforcing supervisor is derived after adding a monitor to each SMS in a controllable siphon basis. It is shown that the number of additional monitors is the same as that of SMSs in the controllable siphon basis, while the latter is no more than that of the operation places in an original Petri net. In the work by Liu et al.,²⁷⁷ it proves that there is no relationship between a controllable siphon basis and a set of elementary siphons. That is to say, the controllable siphon basis and a set of elementary siphons are totally different subsets of SMS in an S³PR.

Partial siphon enumeration

Due to the inherent characteristics of Petri nets, the computational complexity has been a major problem when siphon-based deadlock prevention policies are developed. An efficient way of improving the computational efficiency of a siphon-based deadlock prevention policy is the introduction of the MIP-based deadlock detection method pioneered by Chu and Xie,²⁴⁹ which can successfully avoid the explicit enumeration of all SMSs and open a new research avenue.

Based on this method, Huang et al.²⁵⁰ first propose an iterative two-stage deadlock prevention policy for an S³PR. The first stage is called siphon control, where a maximal unmarked siphon is obtained by solving an MIP problem at each iteration, from which an SMS can be derived. A monitor is added for each SMS to ensure its controllability using the invariant-controlled method as done by Ezpeleta et al.²³⁵ The aforementioned steps are iteratively executed until all siphons in the net are controlled. Then, the first stage terminates, whose termination leads to an augmented net system. At the second stage, namely, control-induced siphon control, the MIP-based deadlock detection method is further applied to the augmented net. After solving an MIP problem, a minimal siphon that contains at least one monitor is found. Then, additional monitors can ensure the controllability of siphons. Note that any output arc of the monitors added in the second stage should point to the source transition of the net model. Similarly, the step is repeated until no unmarked siphon can be found, implying that liveness is achieved. To some extent, this approach enjoys high computational efficiency compared with the existing ones in the literature at that time.

The two-stage method²⁵⁰ is further improved by Hong et al.²⁷⁸ by introducing an additional algorithm for removing the redundant constraints. The policy improves the behavioral permissiveness and greatly enhances the structural simplicity of a supervisor. Later, the MIP-based idea is applied to S⁴PR²⁷⁹ and G-system²⁸⁰ that are more general classes of Petri nets than S³PR.

The MIP-based deadlock detection method is then used by Huang et al.^141,281 Huang et al.²⁸¹ further extend the MIP method to propose an iterative siphon-based control policy for S³PMR nets. Two kinds of control places, called ordinary control (OC) places and weighted control (WC) places, are added to the original system to prevent siphons from becoming unmarked.²⁸¹ Note that the presence of WC places renders that the net is a generalized one, which is harder to analyze, and it is unclear how the traditional MIP is modified. Furthermore, the major technical problem in the work by Huang et al.²⁸¹ is the existence of redundant siphons. As a matter of fact, the work by Shih and Chao²⁸² can be considered as an improvement in the iterative MIP method, which presents a theory to determine the sequence of adding monitors to avoid redundant monitors and the conditions where WC places are redundant.

Li et al.^251,283 propose the iterative siphon-based control policies by utilizing the MIP and the new concept of necessary siphons (NSs). Since those deadlock prevention policies make each NS that contains the minimal number of resource places explicitly controlled in the iteration, while other siphons that have more resource places are implicitly controlled, the liveness-enforcing supervisors with a simple structure can be usually obtained.

To avoid the addition of the corresponding monitors, the redundant test of NSs is further carried out under a certain condition.²⁸³ Based on MIP and the concept of implicit places (IPs), Li and Li²⁸⁴ develop a novel iterative algorithm for simplifying the structural complexity for a live Petri net. Under the condition that liveness is preserved, necessary and redundant monitors can be identified stepwise when computing a feasible solution of an MIP at each iteration. The former and the latter are then kept in or removed from the live controlled system, respectively. As a result, a live Petri net with a simpler structure is obtained.

Li and Li²²⁸ proposed a revised mixed integer programming (RMIP) method to directly solve siphons with the minimal cardinality as well as the minimal number of resource places, called smart siphons. Based on this, an iterative siphon-based control method adopting the proposed RMIP is designed to eliminate deadlocks in Petri net models. Since the solved smart siphons contain the minimal number of resource places, this approach may reduce the possibility of adding redundant monitors to some degree, leading to a liveness-enforcing supervisor with a simple structure. Later, Li et al.²⁸⁵ extend the RMIP method to directly solve new smart siphons (NSSs) associated with deadlocks and livelocks in Petri net models. Consequently, deadlocks and livelocks can be eliminated when all NSSs are max′-controlled and no smart siphons can be found.

Elementary siphon–based approaches

As mentioned previously, the policy in the work by Ezpeleta et al.²³⁵ suffers from the issue of structural complexity since the method needs to design additional monitors for all SMSs. When considering a large-scale net system, too many monitors are added such that the resulting supervisor is structurally complex in theory. If any difference or relationship among SMSs can be deeply revealed, the structural complexity may be effectively alleviated. This problem has remained open for many years until the elementary siphon theory came into being.

The concept of elementary and redundant siphons is first proposed by Li and Zhou,²¹⁵ while the latter are subsequently renamed as dependent siphons.²¹⁶ From the deadlock control policy by Li and Zhou,²¹⁵ all problematic siphons in an S³PR are classified into elementary and dependent siphons. The latter are further separated into weakly and strongly dependent ones by identifying whether the coefficients of linear combination are all positive or not. It is shown that the number of the elementary siphons in a net is no greater than the smaller of place and transition counts. Moreover, a dependent siphon can be controlled by properly supervising its related elementary siphons. For deadlock prevention, strategies that control requirements are achieved by adding monitors; it is of significance that dependent siphons can be implicitly controlled via explicit controlling their elementary siphons by adding monitors and properly arranging the tokens in the monitors. In general cases, the policy by Li and Zhou²¹⁵ can lead to a structurally simple liveness-enforcing supervisor.

From the policy by Li and Zhou,²¹⁵ the controllability of a dependent siphon is investigated according to the elementary siphons that are invariantly controlled. In the work by Li and Zhou,²³⁰ a dependent siphon controllability condition is developed, which is more general than that in the work by Li and Zhou.²¹⁵ Li and Zhao extend such a result to a class of generalized nets in the work by Li and Zhao²⁴³ on the basis of the max-controlled condition of siphons.²³⁴ However, it suffers from the computational complexity and behavioral permissiveness issues as in this²⁴³ policy since the computation of elementary siphons relies on a complete siphon enumeration.

The work by Li et al.²⁸⁶ aims to tackle the issues on the computational complexity and restricted behavior in the work by Li and Zhou.²¹⁵ The MIP-based deadlock detection method is first applied to derive a maximal unmarked siphon on condition that the plant model itself is not live, from which an SMS is computed. If it is an elementary siphon, then a monitor is added such that it is controlled. If it is dependent with respect to the elementary siphons that are already found, its controllability is ensured by properly setting the control depth variables of its elementary siphons. In the work by Li et al.,²⁸⁶ monitors are added for elementary siphons only based on the elementary siphon theory. In addition, it can be concluded that this approach improves the computational complexity by comparing with that in the work by Li and Zhou²¹⁵ due to the partial siphon enumeration.

Unfortunately, the behavioral permissiveness of the resulting supervisors designed by the policies in the works by Li and Zhou²¹⁵ and Li et al.²⁸⁶ is quite restricted since the output arcs of the additional monitors point to the source transitions that represent the entry of raw parts of the system. To ameliorate the aforementioned problem, Li and Zhou²⁸⁷ propose an algorithm for rearranging the output arcs of the additional monitors. From the viewpoint of structural complexity, computational complexity, and behavioral permissiveness, this policy seems to simultaneously address these issues in a reasonable way.

An MIP-based two-stage iterative policy is proposed by Huang et al.,²⁵⁰ which makes a number of improvements compared with the work by Ezpeleta et al.²³⁵ However, the structural complexity problem of a liveness-enforcing supervisor has not significantly improved. By utilizing the concept of elementary siphons, Huang¹⁴¹ proposes an improved two-stage control policy for S³PR nets. The major difference in the policy by Huang et al.²⁵⁰ is in first stage. The first stage in the work by Huang¹⁴¹ finds the set of elementary siphons in an S³PR net model provided that all SMSs are known. Then, a monitor is added for each elementary siphon. Compared with the policy by Huang et al.,²⁵⁰ it is shown that fewer monitors are needed. Later, Zhao et al.²⁴⁶ further extend the iterative method to a more general class, called S⁴PR nets.

In order to achieve a better method that can precisely and immediately decide the controllability of dependent SMSs via their elementary siphons’ control without using the time-consuming MIP tests, the work by Liu et al.²⁸⁸ proposes a more precise sufficient condition for the controllability of dependent SMSs and proves that it is better than the condition in the work by Li and Zhou.²¹⁵ Moreover, a relationship between the complementary set of a weakly dependent SMS and that of its corresponding elementary ones is presented and proven. Accordingly, a new deadlock prevention policy is developed by taking the advantages of the methods by Ezpeleta et al.²³⁵ and Li and Zhou.²¹⁵

Generally, the concept of elementary siphons can clearly and completely indicate the relationship between elementary and dependent siphons in an ordinary net. For an S³PR net, the studies by Hou et al.^289,290 explore the controllability conditions of a siphon composed of two and three elementary siphons, respectively, which are considered as further applications of elementary siphons of Petri nets. Under these sufficient conditions, a maximally permissive liveness-enforcing supervisor expressed by a set of monitors can be always decided by an algorithm with polynomial complexity for an S³PR. It can be concluded that for any S³PR, there exist initial markings such that a maximally permissive liveness-enforcing supervisor can be always found. These developments are based on the computation of elementary siphons and siphons composition operations, which has been shown to be of polynomial complexity with respect to the size of a considered Petri net model.

Since the weight of an arc can be greater than one and an operation place can use multiple resource types in a generalized net, the selection of elementary siphons and their controllability still need improvements in generalized Petri nets. Consequently, the augmented elementary siphon theory is established by sufficiently considering the requirement of multiple resource types by an operation and its weight information. In the work by Hou et al.,²²⁴ the concept of augmented siphons is first proposed for extending the elementary siphon’s application to a class of generalized Petri nets, WS³PR. An augmented siphon is a multiset that reflects the weights information of resource places contained by its original siphon. Among augmented siphons, the elementary siphons are also redefined, from which an elementary siphon set that strongly connects the system structure can be found for WS³PR nets. Moreover, on the basis of graph theory, initial resource weighted digraphs are presented for WS³PR, and the concept of isomorphic structures of Petri nets is also introduced. It is shown that the same set of elementary siphons can be admitted by all different WS³PR systems with isomorphic structures. Later, the work by Hou and Zhao²²⁵ further updates the method proposed by Hou et al.²²⁴ in a more general class of Petri nets, GLS³PR.

Motivated by finding a set of more proper and compact elementary siphons, the concept of augmented siphons is further proposed by Hou et al.²²³ within a class of generalized Petri nets, called GLS³PR nets. The key contributions by Hou et al.²²³ are twofold. First, the supremum of the number of augmented elementary siphons is found according to the relationship between siphons and their restrictive induced subgraphs, which is not greater than that of strongly connected restrictive induced digraphs that cannot be composed. Second, the number of elementary siphons obtained by this method is less than or equal to that obtained in the work by Li and Zhou.²¹⁵

For better improving both the structural complexity and behavioral permissiveness, Hou et al.²²² propose the augmented siphons and redefined elementary siphons in S⁴PR nets. The max′-controlled property is exposed such that the siphon controllability condition is relaxed. Furthermore, more permissive behavior is obtained through the rearrangement of the output arcs of monitors. Hou et al.²²² develop a deadlock control method by combining the deadlock avoidance policy with elementary siphon theory such that all siphons are max′-controlled after adding a monitor for each elementary siphon.

Abdul-Hussin²⁹¹ develops an elementary siphon–based deadlock control policy to ensure that all siphons are controlled and no emptiable control-induced siphons can be introduced. The work by Qin et al.²³² develops an elementary siphon–based policy to design a liveness-enforcing supervisor for an S³PR with uncontrollable and unobservable transitions. For all the elementary siphons, their complementary sets are successively expanded by considering the unobservability and uncontrollability of transitions. Monitors are added for the expanded complementary sets. This approach permits that there are arcs from monitors to a set of special uncontrollable transitions.

Combined techniques

Although the elementary siphon–based approaches play an important role in deadlock control for AMS, it also has several explicit drawbacks. First, elementary siphons merely reflect the topological structure of a net without carrying any dynamical evolution information. Second, the liveness-enforcing supervisors derived by elementary siphon–based methods are usually not optimal. Finally, the approaches on the basis of elementary siphon theory can only be applied to some special classes of Petri nets. Thus, much more attention has been paid to the combination of the state space and structural analysis.

Piroddi et al.²⁹² develop a selective siphon control policy that can obtain a small-sized supervisor with highly permissive behavior. Siphons are divided into essential and dominated ones. The controllability of an essential siphon implies that of its dominated siphons. At each iterative step, the complete enumeration of all siphons and dominated markings are required. Moreover, an essential siphon is distinguished by solving a set covering problem. Unfortunately, the computational complexity in theory is still exponential with respect to the size of a Petri net. In addition, in general, the policy in the work by Piroddi et al.²⁹² cannot lead to an optimal liveness-enforcing supervisor.

After the computational complexity problem is recognized, Piroddi et al.²⁹³ improve the method shortly by utilizing the MIP-based deadlock detection method. Benefiting from the MIP method, a complete minimal siphon enumeration is avoided. They claim that the improved policy is computationally competitive. Later, Wang et al.²⁹⁴ outline the iterative method proposed by Piroddi et al.²⁹³ in detail. By contrast, the methods by Chao and colleagues^138,295,296 can avoid both enumerating all minimal siphons and computing the reachability graph. Also, no iterations are required and there is no need to remove redundant monitors. It lists all such lost states and computes the lost states without reachability analysis but based only on the knowledge of which siphon is responsible for the lost states and some place invariants (PIs).

As known, the theory of regions can usually lead to a maximally permissive supervisor if it exists. However, it often faces the state explosion problem with an increase in the initial markings. Wei and Li²⁴⁵ propose a new methodology by combining the theory of regions and elementary siphons. First, using the theory of regions, a maximally permissive liveness-enforcing supervisor for a net model is designed at a small initial marking. After that, all SMSs are computed and separated into elementary siphons and dependent ones. Then, the algebraic expressions among the markings of the monitors and the resource places are explored on the premise that the supervisor is live and maximally permissive, that is, all SMSs are controlled by the monitors. When the initial markings of the plant change, a new supervisor with the same structure can be determined by reallocating the initial tokens in monitors via the obtained expressions. That is to say, the theory of regions is in fact used to derive the net structure of a supervisor by arranging small initial markings. The contributions by Wei and Li²⁴⁵ are twofold. One is that the state explosion problem may not occur after the theory of regions has once been applied to a plant with fixed net structure. The other is that the permissive behavior of the liveness-enforcing supervisor is near-optimal.

To lower the computational cost of utilizing the theory of regions, Li et al.²⁴⁴ develop a two-stage deadlock prevention policy by integrating siphon control and the theory of regions. The first stage, called siphons control, is to add monitors for all SMSs identified through resource circuits such that it is optimally invariant controlled. Note that siphon identification and control is of polynomial complexity. In the second stage, the theory of regions is utilized to derive a supervisor for the augmented Petri net. Since the siphon control stage is optimal from the view of deadlock prevention point, the final supervisor will be still optimal if such a supervisor exists. The combined approach can produce a maximally permissive liveness-enforcing supervisor for an S³PR model and is more efficient than using the theory of regions alone.

Later, a new definition of the marking/transition-separation instances (MTSIs) is proposed by Huang and Pan,²⁹⁷ called crucial marking/transition-separation instances (CMTSIs), which is the foundation of MTSI. The most attractive advantage of this approach is that the computation cost can be alleviated due to the involvement of few MTSIs. Experimental results show that a maximally permissive liveness-enforcing supervisor with efficient computation can be implemented by the proposed control policy. Further research on CMTSIs is reported by Chao.²⁹⁸

The work by Chao and Wu²⁹⁹ contributes an integrated approach that combines the elementary siphon–based controlled policy in the work by Li et al.²⁴⁴ with the seminal recovery methods reported by Chao and colleagues.^274–276 It is claimed that the method reaches more states and uses fewer monitors. The first stage is the same as the methods by Li et al.²⁴⁴ and Huang and Pan,²⁹⁷ that is, a partially controlled model is obtained by adding monitors to all emptiable resource siphons. The second stage adapts a deadlock detection and recovery method in the work by Chao et al.²⁷⁵ to add only one monitor, taking much less time compared with those in the works by Li et al.²⁴⁴ and Huang and Pan.²⁹⁷ Without solving a large number of inequalities in MTSIs as required by the method in the work by Li et al.²⁴⁴ to reduce the number of MTSIs and the CMTSIs method in the work by Huang and Pan,²⁹⁷ the proposed method is more efficient. The resulting controller is maximally permissive as some methods in the works by Li and colleagues.^244,300,301 Further work about the combination of the selective siphons and CMTSIs can be found in the work by Pan et al.,³⁰² which improves the computational efficiency and reduces the number of CMTSIs.

The previous work by Chao and colleagues^282,303 avoids reachability analysis by classifying siphons and adding monitors to critical siphons only. However, some live states may lose and the number of monitors required is as many as that of critical siphons. Based on these results, a novel method is developed to merge several monitors into a single one while not losing the live states by Liu et al.³⁰⁴ It achieves the same best results in the existing literature while avoiding the time-consuming reachability analysis which does not scale well with the large size of the nets. For a well-known benchmark, the siphon-based merging method in the work by Liu et al.³⁰⁴ may not achieve minimal configuration. Although we could reduce one monitor, which monitor to choose to merge seems to be ad hoc. It is unclear how to select a monitor to reduce for large nets. The work by Chao³⁰⁵ further tackles such an issue successfully using the concept of basic siphons.

The work by Wang et al.²⁹⁴ reviews the existing iterative control policies of discrete event system (DES) modeled with Petri nets and reveals a few technical problems among them. Experimental results indicate that the suitability, effectiveness, and efficiency of an iterative deadlock control approach are sensitive to specific examples, and no general algorithm is found in the literature, which works well for all cases.

Afterward, the simulation with respect to existing deadlock prevention policies and different Petri net models is implemented by Nasr et al.,¹⁴² which explores whether a liveness-enforcing Petri net supervisor can provide better time performance. Abouel Nasr et al. claim that, compared with the siphon-based methods, the iterative methods always lead to structurally and computationally complex liveness-enforcing supervisors. In addition, iterative methods can provide better behavioral permissiveness than siphon-based methods for small-scale systems. For large systems, an SMS-based method can obtain better behavioral permissiveness than the other methods.

For a dozen of years, we have witnessed that the results are much enriched in the area of siphon control and other iterative methods. However, it could not be denied that many interesting problems remain unsolved in terms of application scope, behavioral permissiveness, computational efficiency, and supervisor’s structural complexity. Moreover, there are several survey papers and books that investigate the supervisory control problems of DES using Petri nets.^306,307

Concluding remarks

In most cases, the deadlock prevention policies characterize the deadlock behavior of a system in terms of siphons in its Petri net model and utilize this characterization to control the net. Siphon control provides an effective way to prevent the occurrence of deadlocks. A basic task with respect to siphon-based deadlock control is to design a liveness-enforcing supervisor by considering three performance indicators: structural complexity, computational efficiency, and behavioral permissiveness. Nowadays, the concept of elementary siphons either in ordinary or generalized Petri nets plays a key role in the development of structurally simple liveness-enforcing Petri net supervisors. This article focuses on investigating the state-of-the-art elementary siphon theory of Petri nets including basic concepts, siphons and elementary siphons computation, controllability conditions, and deadlock control applications. The survey is expected to be a reference to guide the researchers and practitioners for choosing suitable methods for their research works and industrial application cases.

Footnotes

Appendix 1

Appendix 2

Academic Editor: Tatsushi Nishi

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the National Natural Science Foundation of China under Grant No. 61403296.

References

Chao

DY.

Automated manufacturing system: virtual-nets or non-virtual-nets?

IET Control Theory A 2009; 3: 671–680.

Desrochers

(ed.). Modeling and control of automated manufacturing systems. Piscataway, NJ: IEEE Press, 1989.

D’Souza

Khator

SK.

A survey of Petri net applications in modeling controls for automated manufacturing systems. Comput Ind 1994; 24: 5–16.

Fanti

Maione

Turchiano

Distributed event-control for deadlock avoidance in automated manufacturing systems. Int J Prod Res 2001; 39: 1993–2021.

Fanti

Zhou

MC.

Deadlock control methods in automated manufacturing systems. IEEE T Syst Man Cy A 2004; 34: 5–22.

ZW.

Efficient deadlock prevention policy in automated manufacturing systems using exhausted resources. Int J Adv Manuf Tech 2009; 40: 566–571.

ZW.

Synthesis of liveness enforcing supervisor for automated manufacturing systems using insufficiently marked siphons. J Intell Manuf 2010; 21: 555–567.

Zhou

ZW.

Supervisor design to enforce production ratio and absence of deadlock in automated manufacturing systems. IEEE T Syst Man Cy A 2011; 41: 201–212.

Jeng

DiCesare

A review of synthesis techniques for Petri nets with applications to automated manufacturing systems. IEEE T Syst Man Cyb 1993; 23: 301–312.

10.

Kim

SS.

An efficient real-time deadlock-free control algorithm for automated manufacturing systems. Int J Prod Res 1997; 35: 1545–1560.

11.

Lawley

MA.

Integrating flexible routing and algebraic deadlock avoidance policies in automated manufacturing systems. Int J Prod Res 2000; 38: 2931–2950.

12.

Reveliotis

Ferreira

PM.

Deadlock avoidance policies for automated manufacturing cells. IEEE T Robotic Autom 1996; 12: 845–857.

13.

Viswanadham

Narahari

Performance modeling of automated manufacturing systems. Englewood Cliffs, NJ: Prentice Hall, 1992.

14.

Zhou

MC.

Avoiding deadlock and reducing starvation and blocking in automated manufacturing systems. IEEE T Robotic Autom 2001; 17: 658–669.

15.

Zhou

MC.

Modeling and deadlock avoidance of automated manufacturing systems with multiple automated guided vehicles. IEEE T Syst Man Cy B 2005; 35: 1193–1202.

16.

Zhou

MC.

Deadlock resolution in automated manufacturing systems with robots. IEEE T Autom Sci Eng 2007; 4: 474–480.

17.

Yeh

WC.

Real-time deadlock detection and recovery for automated manufacturing systems. Int J Adv Manuf Tech 2002; 20: 780–786.

18.

Cho

Kumaran

Wysk

RA.

Graph-theoretic deadlock detection and resolution for flexible manufacturing systems. IEEE T Robotic Autom 1995; 11: 413–421.

19.

Coffman

Elphick

Shoshani

System deadlocks. ACM Comput Surv 1971; 3: 66–78.

20.

Gold

EM.

Deadlock prediction: easy and difficult cases. SIAM J Comput 1978; 7: 320–336.

21.

Isloor

Marsland

TA.

The deadlock problem: an overview. Computer 1980; 13: 58–77.

22.

Castelnuovo

Ferrarini

Piroddi

An incremental Petri net-based approach to the modeling of production sequences in manufacturing systems. IEEE T Autom Sci Eng 2007; 4: 424–434.

23.

Chen

Petri nets applications in automated manufacturing systems (special issue). Int J Adv Manuf Tech 1998; 14.

24.

David

Alla

Petri nets and Grafcet. London: Prentice Hall, 1992.

25.

Desrochers

Al-Jaar

RY.

Applications of Petri nets in manufacturing systems: modeling, control, and performance analysis. New York: IEEE Press, 1994.

26.

DiCesare

Harhalakis

Porth

. Practice of Petri nets in manufacturing. London: Chapman & Hall, 1993.

27.

Hruz

Zhou

MC.

Modeling and control of discrete-event dynamic systems: with Petri nets and other tools. London: Springer-Verlag, 2007.

28.

Iordache

Antsaklis

PJ.

Supervisory control of concurrent systems: a Petri net structural approach. Berlin: Springer-Verlag, 2006.

29.

Jeng

MD.

A Petri net synthesis theory for modeling flexible manufacturing systems. IEEE T Syst Man Cy B 1997; 27: 169–183.

30.

Jensen

Colored Petri nets: basic concepts, analysis methods and practical use. New York: Springer-Verlag, 1994.

31.

Zhou

MC.

Deadlock resolution in automated manufacturing systems: a novel Petri net approach. New York: Springer-Verlag, 2009.

32.

Marsan

Balbo

Conte

. Modelling with generalized stochastic Petri nets. New York: Wiley, 1995.

33.

Moore

Guptats

SM.

Petri net models of flexible and automated manufacturing systems: a survey. Int J Prod Res 1996; 34: 3001–3035.

34.

Murata

Petri nets: properties, analysis and applications. P IEEE 1989; 77: 541–580.

35.

Peterson

JL.

Petri nets. ACM Comput Surv 1977; 9: 223–252.

36.

Peterson

JL.

Petri net theory and the modeling of systems. Englewood Cliffs, NJ: Prentice Hall, 1981.

37.

Proth

Xie

XL.

Petri nets: a tool for design and management of manufacturing systems. New York: Wiley, 1996.

38.

Reisig

Petri nets: an introduction. New York: Springer-Verlag, 1985.

39.

Silva

Teruel

Valette

. Petri nets and production systems. In: Reisig

Rozenberg

(eds) Lectures on Petri nets II: applications, vol. 1492 (Lecture notes in computer science). Berlin: Springer, 1998, pp.85–124.

40.

Zhou

. On Petri net modeling of automated manufacturing systems. In: Proceedings of the IEEE international conference on networking, sensing and control, London, 15–17 April 2007, pp.228–233. New York: IEEE.

41.

Zhou

MC.

Process vs resource-oriented Petri net modeling of automated manufacturing systems. Asian J Control 2010; 12: 267–280.

42.

Zhou

MC.

System modeling and control with resource-oriented Petri nets. New York: CRC Press, 2010.

43.

Zhou

DiCesare

Petri net synthesis for discrete event control of manufacturing systems. Boston, MA: Kluwer Academic Publishers, 1993.

44.

Zhou

(ed.). Petri nets in flexible and agile automation. Norwell, MA: Kluwer Academic Publishers, 1995.

45.

Zhou

Venkatesh

Modeling, simulation, and control of flexible manufacturing systems: a Petri net approach. Singapore: World Scientific, 1998.

46.

Zurawski

Zhou

MC.

Petri nets and industrial applications: a tutorial. IEEE T Ind Electron 1994; 41: 567–583.

47.

Zurawski

Zhou

MC.

Petri nets and industrial applications: a tutorial. IEEE T Ind Electron 1994; 41: 567–583.

48.

Banaszak

Krogh

BH.

Deadlock avoidance in flexible manufacturing systems with concurrently competing process flows. IEEE T Robotic Autom 1990; 6: 724–734.

49.

Barkaoui

Abdallah

. A deadlock prevention method for a class of FMS. In: Proceedings of the IEEE international conference on systems, man and cybernetics, Vancouver, BC, Canada, 22–25 October 1995, pp.4119–4124. New York: IEEE.

50.

Basile

Chiacchio

Giua

. Deadlock recovery of Petri net models controlled using observers. In: Proceedings of the IEEE international conference on emerging technologies and factory automation, Juan-les-Pins, 15–18 October 2001, vol. 2, pp.441–449. New York: IEEE.

51.

Chao

DY.

Weighted characteristic P-vector and deadlock control of WS³PR. J Inf Sci Eng 2010; 26: 1121–1136.

52.

Chao

DY.

Fewer monitors and more efficient controllability for deadlock control in S³PGR² (systems of simple sequential processes with general resource requirements). Comput J 2010; 53: 1783–1798.

53.

Ezpeleta

Tricas

Garcia-Valles

. A banker’s solution for deadlock avoidance in FMS with flexible routing and multiresource states. IEEE T Robotic Autom 2002; 18: 621–625.

54.

Ezpeleta

Recalde

A deadlock avoidance approach for nonsequential resource allocation systems. IEEE T Syst Man Cy A 2004; 34: 93–101.

55.

Fanti

Maione

Turchiano

Deadlock detection and recovery in flexible production systems with multiple capacity resources. In: Proceedings of the 8th Mediterranean electrotechnical conference, Bari, 13–16 May 1996, pp.237–241. New York: IEEE.

56.

Fanti

Maione

Mascolo

. Performance of deadlock avoidance algorithms in flexible manufacturing systems. J Manuf Syst 1996; 15: 164–178.

57.

Fanti

Maione

Mascolo

. Event-based feedback control for deadlock avoidance in flexible production systems. IEEE T Robotic Autom 1997; 13: 347–363.

58.

Fanti

Giua

Seatzu

Monitor design for colored Petri nets: an application to deadlock prevention in railway networks. Control Eng Pract 2006; 14: 1231–1247.

59.

Lemmon

. On the transformation of maximally permissive marking-based liveness enforcing supervisors into monitor supervisors. In: Proceedings of the 39th IEEE conference on decision and control, Sydney, NSW, Australia, 12–15 December 2002, vol. 3, pp.2657–2662. New York: IEEE.

60.

Lemmon

MD.

Liveness verification of discrete-event systems modeled by n-safe ordinary Petri nets. In: Proceedings of the 21st international conference on application and theory of Petri nets, vol. 1825 (Lecture notes in computer science), Aarhus, 26–30 June 2000, pp.227–243. Berlin: Springer.

61.

Lemmon

MD.

Liveness-enforcing supervision of bounded ordinary Petri nets using partial order methods. IEEE T Automat Contr 2002; 47: 1042–1055.

62.

Holloway

Krogh

Giua

A survey of Petri net methods for controlled discrete event systems. Discrete Event Dyn S 1997; 7: 151–190.

63.

Hou

Zhao

Liu

Deadlock control for a class of generalized Petri nets based on proper resource allocation. Asian J Control 2016; 18: 206–223.

64.

ZW.

Clarification on the computation of liveness-enforcing supervisor for resource allocation systems with uncontrollable behavior. IEEE T Autom Sci Eng 2009; 6: 557–559.

65.

Zhou

ZW.

Algebraic synthesis of timed supervisor for automated manufacturing systems using Petri nets. IEEE T Autom Sci Eng 2010; 7: 549–557.

66.

Zhou

ZW.

Low-cost and high-performance supervision in ratio-enforced automated manufacturing systems using timed Petri nets. IEEE T Autom Sci Eng 2010; 7: 933–944.

67.

Zhou

ZW.

Supervisor optimization for deadlock resolution in automated manufacturing systems with Petri nets. IEEE T Autom Sci Eng 2011; 8: 794–804.

68.

Zhou

ZW.

Liveness and ratio-enforcing supervision of automated manufacturing systems using Petri nets. IEEE T Syst Man Cy A 2012; 42: 392–403.

69.

Zhou

. An optimization approach to improved Petri net controller design for automated manufacturing systems. IEEE T Autom Sci Eng 2013; 10: 772–782.

70.

Zhou

ZW.

Deadlock-free control of automated manufacturing systems with flexible routes and assembly operations using Petri nets. IEEE T Ind Inform 2013; 9: 109–121.

71.

Iordache

Antsaklis

. Generalized conditions for liveness enforcement and deadlock prevention in Petri nets. In: Proceedings of the 22nd international conference on applications and theory of Petri nets, vol. 2075 (Lecture notes in computer science), Newcastle upon Tyne, 25–29 June 2001, pp.184–203. Berlin: Springer.

72.

Iordache

Moody

Antsaklis

PJ.

Synthesis of deadlock prevention supervisors using Petri nets. IEEE T Robotic Autom 2002; 18: 59–68.

73.

Lautenbach

Ridder

. The linear algebra of deadlock avoidance: a Petri net approach. Technical report no. 25-96, 1996. Koblenz: Institute for Software Technology, University of Koblenz-Landau.

74.

Zhou

MC.

Comparison of two deadlock prevention methods for different-size flexible manufacturing systems. Int J Intell Contr Syst 2005; 10: 235–243.

75.

Zhu

Zhou

MC.

A divide-and-conquer strategy to deadlock prevention in flexible manufacturing systems. IEEE T Syst Man Cy C 2009; 39: 156–169.

76.

HS.

On systematic methods to remove redundant monitors from liveness-enforcing net supervisors. Comput Ind Eng 2009; 56: 53–62.

77.

Shpitalni

Smart deadlock prevention policy for flexible manufacturing systems using Petri nets. IET Control Theory A 2009; 3: 362–374.

78.

Zhou

MC.

Synthesis of structurally simple supervisors enforcing generalized mutual exclusion constraints in Petri nets. IEEE T Syst Man Cy C 2010; 40: 330–340.

79.

Qin

Zhu

Identification of controllable transitions to decide the existence of an optimal liveness-enforcing supervisor for a class of Petri nets. T I Meas Control 2011; 33: 406–421.

80.

Liu

Hanisch

. Deadlock prevention based on structure reuse of Petri net supervisors for flexible manufacturing systems. IEEE T Syst Man Cy A 2012; 42: 178–191.

81.

ZW.

Deadlock analysis and control in resource allocation systems. Inform Sciences 2016; 363: 174–177.

82.

Liu

Jiang

Zhou

MC.

Two simple deadlock prevention policies for S³PR based on key-resource/operation-place pairs. IEEE T Autom Sci Eng 2010; 7: 945–957.

83.

Liu

ZW.

General mixed integer programming-based liveness test for system of sequential systems with shared resources nets. IET Control Theory A 2010; 4: 2867–2878.

84.

Liu

Barkaoui

. Robustness of deadlock control for a class of Petri nets with unreliable resources. Inform Sciences 2013; 235: 259–279.

85.

Maione

DiCesare

Hybrid Petri net and digraph approach for deadlock prevention in automated manufacturing systems. Int J Prod Res 2005; 43: 5131–5159.

86.

Giua

Design of optimal Petri net controllers for disjunctive generalized mutual exclusion constraints. IEEE T Automat Contr 2015; 60: 1774–1785.

87.

Giua

Petri net controllers for generalized mutual exclusion constraints with floor operators. Automatica 2016; 74: 238–246.

88.

Moody

Antsaklis

. Supervisory control of Petri nets with uncontrollable/unobservable transitions. In: Proceedings of the 35th IEEE conference on decision and control, Kobe, Japan, 13 December 1996, vol. 4, pp.4433–4438. New York: IEEE.

89.

Moody

Antsaklis

PJ.

Petri net supervisors for DES with uncontrollable and unobservable transitions. IEEE T Automat Contr 2000; 45: 462–476.

90.

Park

Reveliotis

SA.

Deadlock avoidance in sequential resource allocation systems with multiple resource acquisitions and flexible routings. IEEE T Automat Contr 2001; 46: 1572–1583.

91.

Qin

Khalgui

. On applicability of deadlock prevention policies with uncontrollable and unobservable transitions. Int J Innov Comput I 2011; 7: 4115–4127.

92.

Reveliotis

Lawley

Ferreira

PM.

Polynomial-complexity deadlock avoidance policies for sequential resource allocation systems. IEEE T Automat Contr 1997; 42: 1344–1357.

93.

Sreenivas

RS.

On the existence of supervisory policies that enforce liveness in discrete-event dynamic systems modeled by controlled Petri nets. IEEE T Automat Contr 1997; 42: 928–945.

94.

Sreenivas

RS.

On supervisory policies that enforce liveness in completely controlled Petri nets with directed cut-places and cut-transitions. IEEE T Automat Contr 1999; 44: 1221–1225.

95.

Taubin

Kondratyev

Kishinevsky

Deadlock prevention using Petri nets and their unfoldings. Int J Adv Manuf Tech 1998; 14: 750–759.

96.

Tricas

Garca-Vallés

Colom

. Using linear programming and the Petri net structure for deadlock prevention in sequential resource allocation systems. In: Proceedings of the XIII Jornadas de Concurrencia y Sistemas Distribuidos, Granada, 13–16 September 2005, pp.65–77. Madrid: Thomson Paraninfo.

97.

Uzam

The use of the Petri net reduction approach for an optimal deadlock prevention policy for flexible manufacturing systems. Int J Adv Manuf Tech 2004; 23: 204–219.

98.

Uzam

Zhou

MC.

An iterative synthesis approach to Petri net-based deadlock prevention policy for flexible manufacturing systems. IEEE T Syst Man Cy A 2007; 37: 362–371.

99.

Uzam

Zhou

MC.

Identification and elimination of redundant control places in Petri net based liveness enforcing supervisors of FMS. Int J Adv Manuf Tech 2007; 35: 150–168.

100.

Uzam

Gelen

. A divide-and-conquer-method for the synthesis of liveness enforcing supervisors for flexible manufacturing systems. J Intell Manuf 2016; 27: 1111–1129.

101.

Uzam

Abubakara

US.

Think globally act locally approach for the synthesis of a liveness-enforcing supervisor of FMSs based on Petri nets. Int J Prod Res 2016; 54: 4634–4657.

102.

Varpaaniemi

Efficient detection of deadlocks in Petri nets. Research report A26, October 1993. Espoo: Digital Systems Laboratory, Helsinki University of Technology.

103.

Viswanadham

Narahari

Johnson

Deadlock prevention and deadlock avoidance in flexible manufacturing systems using Petri net models. IEEE T Robotic Autom 1991; 6: 713–723.

104.

Wang

. A versatile supervisor with one monitor based on macro-tokens. IMA J Math Control I 2014; 31: 245–256.

105.

NQ.

Necessary and sufficient conditions for deadlock-free operation in flexible manufacturing systems using a colored Petri net model. IEEE T Syst Man Cy C 1999; 29: 192–204.

106.

NQ.

Deadlock avoidance in an automated guidance vehicle system using a coloured Petri net model. Int J Prod Res 2002; 40: 223–238.

107.

Zhou

ZW.

Resource-oriented Petri net for deadlock avoidance in flexible assembly systems. IEEE T Syst Man Cy A 2008; 38: 56–69.

108.

Zhou

MC.

Petri net modeling and one-step look-ahead maximally permissive deadlock control of AMS. ACM T Embed Comput S 2013; 12: 1–22.

109.

Xing

Chen

HX.

Deadlock avoidance policy for Petri-net modeling of flexible manufacturing systems with shared resources. IEEE T Automat Contr 1996; 41: 289–295.

110.

Yamalidou

Kantor

Modeling and optimal control of discrete-event chemical processes using Petri nets. Comput Chem Eng 1991; 15: 503–519.

111.

Yan

Wei

. A deadlock prevention policy for a class of Petri nets S³PMR. J Inf Sci Eng 2009; 25: 167–183.

112.

Chen

XL.

An algorithm for the minimum initial marking problem of a structurally live Petri net with inhibitor arcs. IEEJ T Electr Electr 2016; 11: 586–592.

113.

Zhao

ZW.

On deadlock control for a class of generalised Petri net models of flexible manufacturing systems. Int J Prod Res 2009; 47: 6085–6107.

114.

Zhong

Chen

. On nonexistence of a maximally permissive liveness-enforcing pure net supervisor. IEEE T Syst Man Cy A 2013; 43: 29–37.

115.

Zhou

DiCeasre

Parallel and sequential mutual exclusions for Petri net modeling of manufacturing systems with shared resources. IEEE T Robotic Autom 1991; 7: 515–527.

116.

Zhou

DiCesare

A hybrid methodology for synthesis of Petri net models for manufacturing systems. IEEE T Robotic Autom 1992; 8: 350–361.

117.

Zhou

DiCesare

Rudolph

Design and implementation of a Petri net based supervisor for a flexible manufacturing system. Automatica 1992; 28: 1199–1208.

118.

Chen

Al-Ahmari

. Deadlock recovery for flexible manufacturing systems modeled with Petri nets. Inform Sciences 2017; 381: 290–303.

119.

Fanti

Giua

Sanna

. Control and error recovery of Petri net models with event observers. In: Proceedings of the 2nd international work manufacturing Petri nets, Toulouse, France, 23–27 June 1997, pp.53–68.

120.

Fanti

Maione

Turchiano

Digraph-theoretic approach for deadlock detection and recovery in flexible production systems. Stud Inform Control 1996; 5: 373–383.

121.

Tricas

Deadlock analysis, prevention and avoidance in sequential resource allocation systems. PhD Dissertation, University of Zaragoza, Zaragoza, 2003.

122.

Chao

. Comments on “Deadlock prevention and avoidance in FMS: a Petri net based approach.”Int J Adv Manuf Tech 2008; 39: 317–318.

123.

Chen

. Confusion avoidance for discrete event systems by P/E constraints and supervisory control. IMA J Math Control I 2016; 33: 309–332.

124.

Chen

. Confusion diagnosis and avoidance of discrete event systems using supervisory control. IEEJ T Electr Electr 2016; 11: 49–62.

125.

Fanti

Maione

Turchiano

Event control for deadlock avoidance in production systems with multiple capacity resources. Stud Inform Control 1998; 7: 343–364.

126.

Hsieh

Chang

SC.

Dispatching-driven deadlock avoidance controller synthesis for flexible manufacturing systems. IEEE T Robotic Autom 1994; 10: 196–209.

127.

Hsieh

FS.

Fault-tolerant deadlock avoidance algorithm for assembly processes. IEEE T Syst Man Cy A 2004; 34: 65–79.

128.

Lawley

Reveliotis

Ferreira

PM.

A correct and scalable deadlock avoidance policy for flexible manufacturing systems. IEEE T Robotic Autom 1998; 14: 796–809.

129.

Lawley

MA.

Deadlock avoidance for production systems with flexible routing. IEEE T Robotic Autom 1999; 15: 497–509.

130.

Lawley

Reveliotis

SA.

Deadlock avoidance for sequential resource allocation systems: hard and easy cases. Int J Flex Manuf Sys 2001; 13: 385–404.

131.

Park

Structural analysis and control of resource allocation systems using Petri nets. PhD Dissertation, Georgia Institute of Technology, Atlanta, GA, 2000.

132.

Park

Reveliotis

SA.

Algebraic synthesis of efficient deadlock avoidance policies for sequential resource allocation systems. IEEE T Robotic Autom 2000; 16: 190–195.

133.

Reveliotis

. Algebraic deadlock avoidance policies for sequential resource allocation systems. In: Lahmar

(ed.) Facility logistics: approaches and solutions to next generation challenges. New York: Taylor & Francis, 2007, pp.235–289.

134.

Roszkowska

Jentink

Minimal restrictive deadlock avoidance in FMSs. In: Proceedings of the European control conference, Groningen, 28 June–1 July 1993, vol. 2, pp.530–534.

135.

Wysk

Yang

Joshi

Resolution of deadlocks in flexible manufacturing systems: avoidance and recovery approaches. J Manuf Syst 1994; 13: 128–138.

136.

Xing

Zhou

Liu

. Optimal Petri-net-based polynomial-complexity deadlock-avoidance policies for automated manufacturing systems. IEEE T Syst Man Cy A 2009; 39: 188–199.

137.

Chao

DY.

Reducing MIP iterations for deadlock prevention of flexible manufacturing systems. Int J Adv Manuf Tech 2009; 41: 343–346.

138.

Chao

DY.

Formal theory of state loss of Siphon-based deadlock prevention. IET Control Theory A 2011; 5: 1013–1021.

139.

Guo

ZW.

A deadlock prevention approach for a class of timed Petri nets using elementary siphons. Asian J Control 2010; 12: 347–363.

140.

Huang

Jeng

Xie

. A deadlock prevention policy for flexible manufacturing systems using siphons. In: Proceedings of the IEEE international conference on robotics and automation, Seoul, Korea, 21–26 May 2001, pp.541–546. New York: IEEE.

141.

Huang

YS.

Design of deadlock prevention supervisors for FMS using Petri nets. Int J Adv Manuf Tech 2007; 35: 349–362.

142.

Nasr

El-Tamimi

Al-Ahmari

. Comparison and evaluation of deadlock prevention methods for different size automated manufacturing systems. Math Probl Eng 2015; 2015; 537893-1–537893-19.

143.

Qin

Zhou

. Deadlock prevention for a class of Petri nets with uncontrollable and unobservable transitions. IEEE T Syst Man Cy A 2012; 42: 727–738.

144.

Tricas

Garca-Vallés

Colom

. An iterative method for deadlock prevention in FMSs. In: Proceedings of the 5th workshop on discrete event systems (eds Boel

Stremersch

), Ghent, 21–23 August 2000, pp.139–148. USA: Springer.

145.

Uzam

On an iterative deadlock prevention approach for automated manufacturing systems. Int J Adv Manuf Tech 2014; 74: 503–507.

146.

Zhang

WM.

Sequence control of essential siphons for deadlock prevention in Petri nets. ACM T Embed Comput S 2013; 12: 176–179.

147.

Bai

. Optimal one-wafer cyclic scheduling and buffer space configuration for single-arm multicluster tools with linear topology. IEEE T Syst Man Cy A 2016; 46: 1456–1467.

148.

Wang

Wonham

WM.

Dynamic multiple-period reconfiguration of real-time scheduling based on timed des supervisory control. IEEE T Ind Inform 2016; 12: 101–111.

149.

Zhou

MC.

Schedulability analysis and optimal scheduling of dual-arm cluster tools with residency time constraint and activity time variation. IEEE T Autom Sci Eng 2012; 9: 203–209.

150.

Yang

Qiao

. Scheduling of single-arm cluster tools for an atomic layer deposition process with residency time constraints. IEEE T Syst Man Cy A. Epub ahead of print 29 January 2016. DOI: 10.1109/TSMC.2015.2507140.

151.

Zhang

Khalgui

. R-TNCES: a novel formalism for reconfigurable discrete event control systems. IEEE T Syst Man Cy A 2013; 43: 757–772.

152.

Zhang

Khalgui

. Reconfigurable coordination of distributed discrete event control systems. IEEE T Contr Syst T 2015; 23: 323–330.

153.

Chen

. Coevolution of aspirations and cooperation in spatial prisoner’s dilemma game. J Stat Mech: Theory E 2015; 2015: P01032.

154.

Giua

Seatzu

. Liveness enforcing supervisors for railway networks using ES²PR Petri nets. In: Proceedings of the 6th international workshop on discrete event systems (WODES 02), Zaragoza, 4 October 2002, pp.55–60. New York: IEEE.

155.

Giua

Seatzu

Modeling and supervisory control of railway networks using Petri nets. IEEE T Autom Sci Eng 2008; 5: 431–445.

156.

Hou

A genetic algorithm approach to short-term scheduling of crude oil operations in refinery. IEEJ T Electr Electr 2016; 11: 593–603.

157.

Zhou

ZW.

Liveness enforcing supervision of video streaming systems using nonsequential Petri nets. IEEE T Multimedia 2009; 11: 1457–1465.

158.

ZW.

Liveness enforcing supervision in video streaming systems using siphons. J Inf Sci Eng 2009; 25: 1863–1864.

159.

ZW.

Modeling and scheduling for manufacturing grid workflows using timed Petri nets. Int J Adv Manuf Tech 2009; 42: 553–568.

160.

Al-Ahmari

Reversed fuzzy Petri nets and their application for fault diagnosis. Comput Ind Eng 2011; 60: 505–510.

161.

Jeng

Zhou

MC.

Engineering applications of Petri nets (special issue). IEEE T Syst Man Cy C 2007; 37: 442–443.

162.

Odrey

Mejía

A reconfigurable multi-agent system architecture for error recovery in production systems. Robot Cim: Int Manuf 2003; 19: 35–43.

163.

Tong

Seatzu

. Verification of state-based opacity using Petri nets. IEEE T Automat Contr. Epub ahead of print 24 October 2016. DOI: 10.1109/TAC.2016.2620429.

164.

Zhou

MC.

Shortest routing of bidirectional automated guided vehicles avoiding deadlock and blocking. IEEE/ASME T Mech 2007; 12: 63–72.

165.

Chu

. Short-term schedulability analysis of multiple distiller crude oil operations in refinery with oil residency time constraint. IEEE T Syst Man Cy C 2009; 39: 1–16.

166.

Chu

. Hybrid Petri net modeling and schedulability analysis of high fusion point oil transportation under tank grouping strategy for crude oil operations in refinery. IEEE T Syst Man Cy C 2010; 40: 159–175.

167.

Zhou

MC.

Modeling, analysis and control of dual-arm cluster tools with residency time constraint and activity time variation based on Petri nets. IEEE T Autom Sci Eng 2012; 9: 446–454.

168.

Chu

. Petri net modeling and cycle-time analysis of dual-arm cluster tools with wafer revisiting. IEEE T Syst Man Cy A 2013; 43: 196–207.

169.

Zhou

ZW.

Short-term scheduling of crude-oil operations: enhancement of crude-oil operations scheduling using a Petri net-based control-theoretic approach. IEEE Robot Autom Mag 2015; 22: 64–76.

170.

Zhou

Bai

. Short-term scheduling of crude oil operations in refinery with high-fusion-point oil and two transportation pipelines. Enterp Inform Syst 2016; 10: 581–610.

171.

Giua

Decentralized supervision of Petri nets with a coordinator. IEEE T Syst Man Cy A 2015; 45: 955–966.

172.

Badouel

Darondeau

Theory of regions. In: Reisig

Rozenberg

(eds) Lectures on Petri nets I: basic models, vol. 1491 (Lecture notes in computer science). Berlin: Springer, 1998, pp.529–586.

173.

Chen

ZW.

Most permissive liveness-enforcing Petri net supervisors for flexible manufacturing systems. Int J Prod Res 2012; 50: 6357–6371.

174.

Chen

Zhou

MC.

Behaviorally optimal and structurally simple liveness-enforcing supervisors of flexible manufacturing systems. IEEE T Syst Man Cy A 2012; 42: 615–629.

175.

Ciardo

Reachability set generation for Petri nets: can brute force be smart? In: Proceedings of the 25th international conference on applications and theory of Petri nets, vol. 3099 (Lecture notes in computer science), Bologna, 21–25 June 2004, pp.17–34. Berlin: Springer.

176.

Darondeau

. Region based synthesis of P/T-nets and its potential applications. In: Proceedings of the 21st international conference on application and theory of Petri nets, vol. 1825 (Lecture notes in computer science), Aarhus, 26–30 June 2000, pp.16–23. Berlin: Springer.

177.

Ghaffari

Nidhal

Xie

XL.

Design of a live and maximally permissive Petri net controller using the theory of regions. IEEE T Robotic Autom 2003; 19: 137–141.

178.

ZW.

Local and global deadlock prevention policies for resource allocation systems using partially generated reachability graphs. Comput Ind Eng 2009; 57: 1168–1181.

179.

McMillan

Using unfoldings to avoid the state explosion problem in the verification of asynchronous circuits. In: Bochmann

Probst

(eds) Computer aided verification, vol. 663 (Lecture notes in computer science). Berlin: Springer, 1992, pp.164–177.

180.

Miner

Ciardo

Efficient reachability set generation and storage using decision diagrams. In: Donatelli

Kleijn

HCM

(eds) Application and theory of Petri nets: proceedings of the 20th international conference, vol. 1639 (Lecture notes in computer science). Berlin: Springer-Verlag, 1999, pp.6–25.

181.

Uzam

An optimal deadlock prevention policy for flexible manufacturing systems using Petri net models with resources and the theory of regions. Int J Adv Manuf Tech 2002; 19: 192–208.

182.

Wang

Zhou

. A new modified reachability tree approach and its applications to unbounded Petri nets. IEEE T Syst Man Cy A 2013; 43: 932–940.

183.

Zhang

Zhong

. Reachability analysis of a class of Petri nets using place invariants and siphons. Maejo Int J Sci Tech 2013; 7: 278–290.

184.

Barkaoui

Lemaire

. An effective characterization of minimal deadlocks and traps in Petri nets based on graph theory. In: Proceedings of the 10th international conference application theory Petri nets, Bonn, Germany, June 1989, pp.1–21. Berlin: Springer.

185.

Barkaoui

Chaoui

Zouari

. Supervisory control of discrete event systems based on structure theory of Petri nets. In: Proceedings of the IEEE international conference on systems, man, and cybernetics, 1997: computational cybernetics and simulation, Orlando, FL, 12–15 October 1997, pp.3750–3755. New York: IEEE.

186.

Barkaoui

Petrucci

. Structural analysis of workflow nets with shared resources. In: Proceedings of the workshop workflow management: net-based concepts, models, technology tools, Lisbon, Portugal, 22 June 1998, vol. 9807, pp.82–95. Eindhoven: Technische Universiteit Eindhoven.

187.

Barkaoui

Peyre

JF.

Verification in concurrent programming with Petri nets structural techniques. In: Proceedings of the 3rd IEEE international high-assurance systems engineering symposium (HASE ’98), Washington, DC, 13–14 November 1998, pp.124–133. New York: IEEE.

188.

Barkaoui

Peyre

JF.

Uniform verification of workflow soundness. T I Meas Control 2011; 33: 133–148.

189.

Chao

DY.

Maximal class of weakly live nets with nonempty siphons. IEEE T Syst Man Cy B 2006; 36: 1332–1341.

190.

Craig

Zuberek

. Efficient siphon-based deadlock detection in Petri nets. In: Presented at the 3rd international conference on computer science and information technology, Athens, 23–26 July 2007.

191.

Iordache

Antsaklis

PJ.

Supervision based on place invariants: a survey. Discrete Event Dyn S 2006; 16: 451–492.

192.

Jeng

Xie

XL.

Analysis of modularly composed nets by siphons. IEEE T Syst Man Cy A 1999; 29: 399–406.

193.

Jeng

Xie

XL.

Modeling and analysis of semiconductor manufacturing systems with degraded behavior using Petri nets and siphons. IEEE T Robotic Autom 2001; 17: 576–588.

194.

Jeng

Xie

XL.

Deadlock detection and prevention of automated manufacturing systems using Petri nets and siphons. In: Zhou

Fanti

(eds) Deadlock resolution in computer-integrated systems. New York: Marcel Dekker, 2005, pp.233–281.

195.

Lautenbach

Ridder

Liveness in bounded Petri nets which are covered by T-invariants. In: Proceedings of the 13th international conference application theory Petri nets, vol. 815 (Lecture notes in computer science), Zaragoza, 20–24 June 1994, pp.358–375. Berlin: Springer.

196.

Zhou

Uzam

Deadlock control policy for a class of Petri nets without complete siphon enumeration. IET Control Theory A 2007; 1: 1594–1605.

197.

Liu

ZW.

FANM: extraction of a minimal siphon from a maxmial one, 2009, https://drive.google.com/open?id=0B0EMOSvVN2msQ1hBZHR4RGo2MkE

198.

Liu

Zhou

MC.

Liveness of an extended S³PR. Automatica 2010; 46: 1008–1018.

199.

Liu

Zhou

MC.

A parameterized liveness and ratio-enforcing supervisor for a class of generalized Petri nets. Automatica 2013; 49: 3167–3179.

200.

Liu

Zhou

MC.

Hybrid liveness-enforcing policy for generalized Petri net models of flexible manufacturing systems. IEEE T Syst Man Cy A 2013; 43: 85–97.

201.

Liu

Zhong

CF.

New controllability condition for siphons in a class of generalised Petri nets. IET Control Theory A 2010; 4: 854–864.

202.

Reveliotis

SA.

On the siphon-based characterization of liveness in sequential resource allocation systems. In: Van der Aalst

WMP

Best

(eds) Applications and theory of Petri nets: proceedings of the 24th international conference, vol. 2679 (Lecture notes in computer science). Berlin: Springer-Verlag, 2003, pp.241–255.

203.

Xie

Jeng

MD.

ERCN-merged nets and their analysis using siphons. IEEE T Robotic Autom 1999; 15: 692–703.

204.

Yamalidou

Moody

Antsaklis

PJ.

Feedback control of Petri nets based on place invariants. Automatica 1996; 32: 15–28.

205.

Zhong

ZW.

A deadlock prevention approach for flexible manufacturing systems without complete siphon enumeration of their Petri net models. Eng Comput 2009; 25: 269–278.

206.

Chen

ZW.

On structural minimality of optimal supervisors for flexible manufacturing systems. Automatica 2012; 48: 2647–2656.

207.

Chen

Al-Ahmari

AM.

Nonpure Petri net supervisors for optimal deadlock control of flexible manufacturing systems. IEEE T Syst Man Cy A 2013; 43: 252–265.

208.

Chen

Barkaoui

New Petri net structure and its application to optimal supervisory control: interval inhibitor arcs. IEEE T Syst Man Cy A 2014; 44: 1384–1400.

209.

Chen

Zhou

MC.

Optimal supervisory control of flexible manufacturing systems by Petri nets: a set classification approach. IEEE T Autom Sci Eng 2014; 11: 549–563.

210.

Chen

Barkaoui

Maximally permissive liveness-enforcing supervisor with lowest implementation cost for flexible manufacturing systems. Inform Sciences 2014; 256: 74–90.

211.

Chen

Barkaoui

. On the enforcement of a class of nonlinear constraints on Petri nets. Automatica 2015; 55: 116–124.

212.

Chen

Barkaoui

. Compact supervisory control of discrete event systems by Petri nets with data inhibitor arcs. IEEE T Syst Man Cy A 2017; 47: 364–379.

213.

Chen

Barkaoui

Monitor design with multiple self-loops for maximally permissive supervisors. ISA T 2016; 61: 129–140.

214.

Uzam

Zhou

MC.

An improved iterative synthesis method for liveness enforcing supervisors of flexible manufacturing systems. Int J Prod Res 2006; 44: 1987–2030.

215.

Zhou

MC.

Elementary siphons of Petri nets and their application to deadlock prevention in flexible manufacturing systems. IEEE T Syst Man Cy A 2004; 34: 38–51.

216.

Zhou

MC.

Clarifications on the definitions of elementary siphons in Petri nets. IEEE T Syst Man Cy A 2006; 36: 1277–1279.

217.

Chao

DY.

Computation of elementary siphons for deadlock control. Comput J 2006; 49: 470–479.

218.

Chao

DY.

Technical note—a graphic-algebraic computation of elementary siphons of BS³PR. J Inf Sci Eng 2007; 23: 1817–1831.

219.

Chao

DY.

Incremental approach to computation of elementary siphons for arbitrary simple sequential processes with resources. IET Control Theory A 2008; 2: 168–179.

220.

Chao

ZW.

Structural conditions of systems of simple sequential processes with resources nets without weakly dependent siphons. IET Control Theory A 2009; 3: 391–403.

221.

Hong

Chao

DY.

Controllability of control and mixture weakly dependent siphons in S³PR. Int J Syst Sci 2013; 44: 1377–1385.

222.

Hou

Zhao

. Extended elementary siphon-based deadlock prevention policy for a class of generalised Petri nets. Int J Comp Integ M 2014; 27: 85–102.

223.

Hou

Al-Ahmari

. Extended elementary siphons and their application to liveness-enforcement of generalized Petri nets. Asian J Control 2014; 16: 1789–1810.

224.

Hou

Zhao

. Extraction of elementary siphons in a class of generalized Petri nets using graph theory. Eng Computation 2014; 31: 331–352.

225.

Hou

Zhao

. Update to “Extraction of elementary siphons in a class of generalized Petri nets using graph theory.”Eng Computation 2016; 33: 331–352.

226.

Hou

Zhao

Liu

. An efficient siphon-based deadlock prevention policy for a class of generalized Petri nets. Discrete Dyn Nat Soc 2016; 2016: 8219424-1–8219424-12.

227.

ZW.

An optimal-elementary-siphons-based iterative deadlock prevention policy for flexible manufacturing systems. Int J Adv Manuf Tech 2008; 38: 309–320.

228.

ZW.

Solving siphons with the minimal cardinality in Petri nets and its applications to deadlock control. Int J Prod Res 2012; 50: 6203–6218.

229.

Wei

Deadlock control of flexible manufacturing systems via invariant–controlled elementary siphons of Petri nets. Int J Adv Manuf Tech 2007; 33: 24–35.

230.

Zhou

MC.

Control of elementary and dependent siphons in Petri nets and their application. IEEE T Syst Man Cy A 2008; 38: 133–148.

231.

Zhou

. A polynomial-complexity approach to decide the existence of a maximally permissive Petri net supervisor using elementary siphons. In: Proceedings of the IEEE international conference on networking, sensing and control, Okayama, Japan, 26–29 March 2009, pp.608–613. New York: IEEE.

232.

Qin

Al-Ahmari

AM.

Elementary-siphon-based control policy for flexible manufacturing systems with partial observability and controllability of transitions. Asian J Control 2015; 17: 327–342.

233.

Wang

Jian

. An effective algorithm to find elementary siphons in a class of Petri nets. IEEE T Syst Man Cy A 2009; 39: 912–923.

234.

Barkaoui

Pradat-Peyre

. On liveness and controlled siphons in Petri nets. In: Proceedings of the 17th international conference on application and theory of Petri nets, vol. 1091 (Lecture notes in computer science), Osaka, Japan, 24–28 June 1996, pp.57–72. Berlin: Springer.

235.

Ezpeleta

Colom

Martinez

A Petri net based deadlock prevention policy for flexible manufacturing systems. IEEE T Robotic Autom 1995; 11: 173–184.

236.

Barkaoui

Ben Abdallah

. Analysis of a resource allocation problem in FMS using structure theory of Petri nets. In: Proceedings of the 1st international workshop on manufacturing and Petri nets, Osaka, Japan, 24–28 June 1996.

237.

Barkaoui

Couvreur

Klai

On the equivalence between liveness and deadlock-freeness in Petri nets. In: Ciardo

Darondeau

(eds) Applications and theory of Petri nets 2005, vol. 3536 (Lecture notes in computer science). Berlin; Heidelberg: Springer-Verlag, 2005, pp.90–107.

238.

Chao

DY.

Max′-controlled siphons for liveness of S³PGR³. IET Control Theory A 2007; 1: 933–936.

239.

Teruel

Silva

Structure theory of equal conflict systems. Theor Comput Sci 1996; 153: 271–300.

240.

Zhong

ZW.

Self-liveness of a class of Petri net models for flexible manufacturing systems. IET Control Theory A 2010; 4: 403–410.

241.

Liu

Barkaoui

Necessary and sufficient liveness condition of GS³PR Petri nets. Int J Syst Sci 2015; 46: 1147–1160.

242.

Guan

Wang

SG.

New controllability condition for siphons in WS³PR nets. Asian J Control 2015; 17: 908–916.

243.

Zhao

On controllability of dependent siphons for deadlock prevention in generalized Petri nets. IEEE T Syst Man Cy A 2008; 38: 369–384.

244.

Zhou

Jeng

MD.

A maximally permissive deadlock prevention policy for FMS based on Petri net siphon control and the theory of regions. IEEE T Autom Sci Eng 2008; 5: 182–188.

245.

Wei

ZW.

On the suboptimal liveness-enforcing supervisors based on Petri net structural analysis and the theory of regions. Int J Adv Manuf Tech 2008; 38: 195–204.

246.

Zhao

HS.

Suboptimal liveness-enforcing supervisor design for a class of generalised Petri nets using partial siphon enumeration and mathematical programming. Int J Syst Sci 2010; 41: 1013–1026.

247.

Abdallah

ElMaraghy

ElMekkawy

. A logic programming approach for finding minimal siphons in S³PR nets applied to manufacturing systems. In: Proceedings of the IEEE international conference on systems, man, and cybernetics, Orlando, FL, 12–15 October 1997, pp.1710–1715. New York: IEEE.

248.

Cordone

Ferrarini

Piroddi

Enumeration algorithms for minimal siphons in Petri nets based on place constraints. IEEE T Syst Man Cy A 2005; 35: 844–854.

249.

Chu

Xie

XL.

Deadlock analysis of Petri nets using siphons and mathematical programming. IEEE T Robotic Autom 1997; 13: 793–804.

250.

Huang

Jeng

Xie

. Deadlock prevention policy based on Petri nets and siphons. Int J Prod Res 2001; 39: 283–305.

251.

HS.

Siphon extraction for deadlock control in flexible manufacturing systems by using Petri nets. Int J Comp Integ M 2011; 24: 710–725.

252.

Chao

DY.

Direct minimal empty siphon computation using MIP. Int J Adv Manuf Tech 2009; 45: 397–405.

253.

Barkaoui

Dutheillet

Haddad

. An efficient algorithm for finding structural deadlocks in colored Petri nets. In: Marsan

(ed.) Application and theory of Petri nets. Berlin; Heidelberg: Springer, 1993, pp.69–88.

254.

Ezpeleta

Couvreur

Silva

. A new technique for finding a generating family of siphons, traps and st-components: application to colored Petri nets. In: Rozenberg

(ed.) Advances in Petri nets, vol. 674 (Lecture notes in computer science). New York: Springer-Verlag, 1993, pp.126–147.

255.

Lautenbach

Linear algebraic calculation of deadlocks and traps. In: Voss

Genrich

Rozenberg

(eds) Concurrency and nets. New York: Springer-Verlag, 1987, pp.315–336.

256.

Wang

Jia

JY.

Efficient computation of strict minimal siphons for a class of Petri nets models of automated manufacturing systems. T I Meas Control 2011; 32: 182–201.

257.

Yamauchi

Watanabe

Algorithms for extracting minimal siphons containing specified places in a general Petri net. IEICE T Fund Electr 1999; 82: 2566–2575.

258.

Chen

Liu

GY.

Computation of minimal siphons in Petri nets by using binary decision diagrams. ACM T Embed Comput S 2013; 12: 1–3.

259.

Tricas

Ezpeleta

. Some results on siphon computation for deadlock prevention in resource allocation systems modeled with Petri nets. In: Proceedings of the IEEE conference on emerging technologies and factory automation (ETFA), Lisbon, 16–19 September 2003, pp.322–329. New York: IEEE.

260.

Tricas

Ezpeleta

Computing minimal siphons in Petri net models of resource allocation systems: a parallel solution. IEEE T Syst Man Cy A 2006; 36: 532–539.

261.

Boer

Murata

Generating basis siphons and traps of Petri nets using the sign incidence matrix. IEEE T Circuits: I 1994; 41: 266–271.

262.

Xing

. Optimal liveness Petri net controllers with minimal structures for automated manufacturing systems. In: Proceedings of the IEEE international conference on systems, man and cybernetics, Waikoloa, HI, 12 October 2005, pp.282–287. New York: IEEE.

263.

Wang

Zhou

. A method to compute strict minimal siphons in a class of Petri nets based on loop resource subsets. IEEE T Syst Man Cy A 2012; 42: 226–237.

264.

Liu

Wang

ZW.

Sufficient conditions for loop resource subsets to derive strict minimal siphons in class of Petri nets. Electron Lett 2014; 50: 25–27.

265.

Esparza

Silva

Circuits, handles, bridges and nets. In: Rozenberg

(ed.) Advances in Petri nets 1990, vol. 483 (Lecture notes in computer science). Berlin: Springer-Verlag, 1990, pp.210–242.

266.

Chao

DY.

An incremental approach to extracting minimal bad siphons. J Inf Sci Eng 2007; 23: 203–214.

267.

Chao

DY.

Searching strict minimal siphons for SNC-based resource allocation systems. J Inf Sci Eng 2007; 23: 853–867.

268.

Zhou

NQ.

A survey and comparison of Petri net-based deadlock prevention policies for flexible manufacturing systems. IEEE T Syst Man Cy C 2008; 38: 172–188.

269.

Zhou

MC.

On siphon computation for deadlock control in a class of Petri nets. IEEE T Syst Man Cy A 2008; 38: 667–679.

270.

. An extraction algorithm for a set of elementary siphons based on mixed-integer programming. J Syst Sci Syst Eng 2012; 21: 106–125.

271.

Liu

Xing

Wang

. A polynomial algorithm for computing elementary siphons in a class of Petri nets. Asian J Control 2012; 14: 1141–1149.

272.

Wang

Xing

. Research on finding elementary siphon in a class of Petri nets. In: Zhao

Sha

(eds) Communications in computer and information science, vol. 289. Berlin: Springer, 2012, pp.435–442.

273.

Xing

Zhou

Wang

. Resource-transition circuits and siphons for deadlock control of automated manufacturing systems. IEEE T Syst Man Cy A 2011; 41: 74–84.

274.

Chao

Liu

GJ.

A simple suboptimal siphon-based control model of a well-known S³PR. Asian J Control 2012; 14: 163–172.

275.

Chao

Chen

. A best deadlock control for S³PMR to reach all states. Asian J Control 2012; 14: 278–283.

276.

Chao

DY.

A new optimal control policy for a well-known S³PR (systems of simple sequential processes with resources). Int J Prod Res 2012; 50: 6259–6271.

277.

Liu

Xing

. Deadlock prevention for flexible manufacturing systems via controllable siphon basis of Petri nets. IEEE T Syst Man Cy A 2015; 45: 519–529.

278.

Hong

Hou

Jing

. Deadlock prevention policy with behavioral optimality or suboptimality achieved by the redundancy identification of constraints and the rearrangement of monitors. Discrete Dyn Nat Soc 2015; 2015: 579623-1–579623-15.

279.

Zhao

Hou

Liu

Liveness-enforcing supervisors synthesis for a class of generalised Petri nets based on two-stage deadlock control and mathematical programming. Int J Control 2010; 83: 2053–2066.

280.

Zhao

Hou

YF.

An iterative method for synthesizing non-blocking supervisors for a class of generalized Petri nets using mathematical programming. Discrete Event Dyn S 2013; 23: 3–26.

281.

Huang

Jeng

Xie

. Siphon-based deadlock prevention policy for flexible manufacturing systems. IEEE T Syst Man Cy A 2006; 36: 1248–1256.

282.

Shih

Chao

DY.

Sequence of control in S³PMR. Comput J 2010; 53: 1691–1703.

283.

Wang

. Design of liveness-enforcing supervisors with simpler structures for deadlock-free operations in flexible manufacturing systems using necessary siphons. J Intell Manuf 2013; 24: 1157–1173.

284.

ZW.

Structure reduction of liveness-enforcing Petri nets using mixed integer programming. Asian J Control 2012; 14: 384–399.

285.

. Policy to cope with deadlocks and livelocks for flexible manufacturing systems using the max′-controlled new smart siphons. IET Control Theory A 2014; 8: 1607–1616.

286.

Wang

AR.

Design of liveness-enforcing supervisors for flexible manufacturing systems using Petri nets. IEEE T Syst Man Cy C 2007; 37: 517–526.

287.

Zhou

MC.

Two-stage method for synthesizing liveness-enforcing supervisors for flexible manufacturing systems using Petri nets. IEEE T Ind Inform 2006; 2: 313–325.

288.

Liu

Jiang

Zhou

MC.

Improved sufficient condition for the controllability of dependent siphons in system of simple sequential processes with resources. IET Control Theory A 2011; 5: 1059–1068.

289.

Hou

Al-Ahmari

AM.

Optimal controllability of 2-composed siphons in a class of Petri nets. Electron Lett 2012; 48: 1535–1537.

290.

Hou

Hong

. Optimal controllability of 3-composed siphons in a class of Petri nets. Electron Lett 2013; 49: 697–699.

291.

Abdul-Hussin

. Design of a Petri net based deadlock prevention policy supervisor for S³PR. In: Proceedings of the 6th international conference on intelligent systems, modelling and simulation, Kuala Lumpur, Malaysia, 9–12 February 2015, pp.46–52. New York: IEEE.

292.

Piroddi

Cordone

Fumagalli

Selective siphon control for deadlock prevention in Petri nets. IEEE T Syst Man Cy A 2008; 38: 1337–1348.

293.

Piroddi

Cordone

Fumagalli

Combined siphon and marking generation for deadlock prevention in Petri nets. IEEE T Syst Man Cy A 2009; 39: 650–661.

294.

Wang

Zhou

MC.

Iterative deadlock control by using Petri nets. IEEE T Syst Man Cy C 2012; 42: 1204–1218.

295.

Chao

DY.

Enumeration of lost states of a suboptimal control model of a well-known S³PR. IET Control Theory A 2011; 5: 1277–1286.

296.

Chao

Chen

Uzam

Reaching most states via refining controller regions for supervisors of two well-known S³PRs. Int J Prod Res 2013; 51: 4421–4430.

297.

Huang

Pan

YL.

Enhancement of an efficient liveness-enforcing supervisor for flexible manufacture systems. Int J Adv Manuf Tech 2010; 48: 725–737.

298.

Chao

. Comments on “enhancement of an efficient liveness-enforcing supervisor for flexible manufacture systems.”Int J Adv Manuf Tech 2012; 60: 625–629.

299.

Chao

KC.

An integrated approach for supervisory control of a subclass of Petri nets. T I Meas Control 2013; 35: 117–130.

300.

Chen

ZW.

Design of a maximally permissive liveness-enforcing supervisor with a compressed supervisory structure for flexible manufacturing systems. Automatica 2011; 47: 1028–1034.

301.

Chen

Khalgui

. Design of a maximally permissive liveness-enforcing Petri net supervisor for flexible manufacturing systems. IEEE T Autom Sci Eng 2011; 8: 374–393.

302.

Pan

Huang

Jeng

. Enhancement of an efficient control policy for FMSs using the theory of regions and selective siphon method. Int J Adv Manuf Tech 2013; 66: 1805–1815.

303.

Chao

DY.

Improvement of suboptimal siphon- and FBM-based control model of a well-known S³PR. IEEE T Autom Sci Eng 2011; 8: 404–411.

304.

Liu

Chao

Uzam

A merging method for the siphon-based FMS maximally permissive controllers with simpler structures. IMA J Math Control I 2014; 31: 551–573.

305.

Chao

. Improvement on “A merging method for the siphon-based flexible manufacturing systems maximally permissive controllers with simpler structures.”IMA J Math Control I 2016; 33: 163–171.

306.

Liu

Barkaoui

A survey of siphons in Petri nets. Inform Sciences 2016; 363: 198–220.

307.

Zhou

MC.

Deadlock control of automated manufacturing systems based on Petri nets—a literature review. IEEE T Syst Man Cy C 2012; 42: 437–462.

308.

Giua

DiCesare

Silva

. Generalized mutual exclusion constraints on nets with uncontrollable transitions. In: Proceedings of the IEEE international conference on system, man, cybernetics, Chicago, IL, 18–21 October 1992, pp.974–979. New York: IEEE.

309.

Giua

DiCesare

. On the existence of Petri net supervisors. In: Proceedings of the IEEE 31st conference on decision and control, Tucson, AZ, 16–18 December 1992, pp.3380–3385. New York: IEEE.

310.

Giua

DiCesare

Silva

. Petri net supervisor for generalized mutual exclusion constraints. In: Proceedings of the 12th triennial world congress of the international-federation-of-automatic-control, Sydney, NSW, Australia, 18–23 July 1993, vol. 1, pp.267–270. Elsevier Science Ltd.

311.

Giua

Seatzu

Observability of place/transition nets. IEEE T Automat Contr 2002; 47: 1424–1437.

312.

Giua

Xie

XL.

Control of safe ordinary Petri nets using unfolding. Discrete Event Dyn S 2005; 15: 349–373.

313.

Giua

Seatzu

. A systems theory view of Petri nets. In: Bonivento

Isidori

Marconi

. (eds) Advances in control theory and applications, vol. 353 (Lecture notes in control and information sciences). Berlin: Springer-Verlag, 2007, pp.99–127.

314.

Lawley

Reveliotis

Ferreira

PM.

Flexible manufacturing system structural control and the neighborhood policy, part 2: generalization, optimization, and efficiency. IIE Trans 1997; 29: 889–899.

315.

Lawley

Sulistyono

Robust supervisory control policies for manufacturing systems with unreliable resources. IEEE T Robotic Autom 2002; 18: 346–359.

316.

Liu

A correct minimal siphons extraction algorithm from a maximal unmarked siphon of a Petri net. Int J Prod Res 2007; 45: 2161–2165.

317.

Odrey

Mejía

An augmented Petri net approach for error recovery in manufacturing systems control. Robot Cim: Int Manuf 2005; 21: 346–354.

318.

Reveliotis

. Liveness enforcing supervision for sequential resource allocation systems: state of the art and open issues. In: Caillaud

Darondeau

Lavagno

. (eds) Synthesis and control of discrete event systems. Dordrecht: Kluwer Academic Publishers, 2002, pp.203–212.

319.

Roszkowska

Wojcik

. Problems of process flow feasibility in FAS. In: CIM in process and manufacturing industries. Oxford: Pergamon Press, 1993, pp.115–120.

320.

Singhal

Deadlock detection in distributed systems. Computer 1989; 22: 37–48.

321.

Silva

Valette

Petri nets and flexible manufacturing. In: Rozenberg

(ed.) Advances in Petri nets, vol. 424 (Lecture notes in computer science). Heidelberg: Springer-Verlag, 1989, pp.374–417.

322.

Silva

Teruel

. A systems theory perspective of discrete event dynamic systems: the Petri net paradigm. In: Proceedings of the symposium discrete events manufacturing systems, Lille, 1996, pp.1–12.

323.

Tong

Giua

On the equivalence of observation structures for Petri net generators. IEEE T Automat Contr 2016; 61: 2448–2462.

324.

Trappey

AJC

Hsiao

Maintenance chain integration using Petri-net enabled multiagent system modeling and implementation approach. IEEE T Syst Man Cy C 2011; 41: 306–315.

325.

Tricas

Martinez

. An extension of the liveness theory for concurrent sequential processes competing for shared resources. In: Proceedings of the IEEE international conference on systems, Vancouver, BC, Canada, 22–25 October 1995, pp.3035–3040. New York: IEEE.

326.

Wonham

WM.

Supervisory control of discrete event systems, 2009, http://www.control.toronto.edu/people/profs/wonham/wonham.html

327.

Wysk

Yang

Joshi

Detection of deadlocks in flexible manufacturing cells. IEEE T Robotic Autom 1991; 7: 853–859.

328.

Zhou

Fanti

(eds). Deadlock resolution in computer-integrated systems. New York: Marcel Dekker, 2005.

329.

Zhou

. Special issue on “Petri nets for system control and automation.”Asian J Control 2010; 12: 237–239.

Deadlock analysis and control based on Petri nets: A siphon approach review

Abstract

Keywords

Introduction

Siphons and controllability conditions

Siphons and traps

Definition 1

Property 1

Corollary 1

Example 1

Property 2

Property 3

Controllability conditions of siphons

Ordinary Petri nets

Theorem 1

Theorem 2

Corollary 2

Definition 2

Definition 3

Generalized Petri nets

Corollary 3

Max-controlled conditions

Definition 4

Definition 5

Definition 6

Property 4

Property 5

Proposition 1

Example 2

Theorem 3

Max′-controlled conditions

Definition 7

Definition 8

Definition 9

Theorem 4

Example 3

Max″-controlled conditions

Definition 10

Definition 11

Theorem 5

Max ★ -controlled conditions

Definition 12

Theorem 6

W-controlled conditions

Definition 13

Definition 14

Theorem 7

Elementary siphon theory

Elementary siphons

Elementary and dependent siphons

Definition 15

Definition 16

Definition 17

Theorem 8

Example 4

Controllability of dependent siphons

Theorem 9

Corollary 4

Lemma 1

Theorem 10

Theorem 11

Corollary 5

Example 5

Augmented elementary siphons in generalized Petri nets

Augmented elementary siphons in WS3PR

Augmented elementary siphons

Definition 18

Definition 19

Definition 20

Example 6

Definition 21

Lemma 2

Theorem 12

Controllability of augmented dependent siphons

Augmented elementary siphons in GLS3PR

Augmented elementary siphons

Definition 22

Definition 23

Definition 24

Definition 25

${Max}^{★}$ -controlled conditions

Augmented elementary siphons in WS³PR

Augmented elementary siphons in GLS³PR

Augmented elementary siphons in S⁴PR