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.

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\prime \in R(N,M)$ , $M\prime (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\prime \in R(N,M)$ , $M\prime (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 $\nexists 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 $\Pi$ be the set of its siphons.^31,234 The net is deadlock-free if $\forall S\in \Pi$ , $\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\backslash S$ , $I(p)\le 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)\ge \mathrm{ma}{x}_{p^{•}}$ , where $\mathrm{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)$ , $\mathrm{ma}{x}_{p^{•}}=1$ , $||I|{|}^{+}\subseteq S$ and $I^T{M}_0>\sum _{p\in S}I(p)(\mathrm{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+2p_3+p_5$ . Trivially, $I=I_2-I_1=2p_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=\varnothing$ , and $I^T{M}_0=M_0(p_5)+2M_0(p_3)-M_0(p_6)=1$ . We have $\sum _{p\in S}I(p)(\mathrm{ma}{x}_{p^{•}}-1)=I(p_3)(\mathrm{ma}{x}_{p_3^{•}}-1)+I(p_5)(\mathrm{ma}{x}_{p_5^{•}}-1)=0$ . In consequence, S is max-controlled owing to $I^T{M}_0>\sum _{p\in S}I(p)(\mathrm{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^{\mathrm{in}}$ . ²²²

Definition 7

Let $\Pi$ be the set of minimal siphons in a net $(N,M_0)$ . ³¹ It is said to be well-initially-marked if $\forall S\in \Pi$ , $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)\ge 1$ , or (2) $\exists p\in S^R$ such that $M(p)\ge \mathrm{ma}{x}_{t\in (p^{•}\cap {([S]\cap P_S^{\mathrm{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^{\mathrm{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\prime (p_9)=\mathrm{ma}{x}_{t\in (p_9^{•}\cap {([S]\cap P_S^{\mathrm{in}})}^{•})}\{W(p_9,t)\}=W(p_9,t_5)=1$ . As a result, S is max′-marked at $M\prime$ .

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:

1. M is an initial marking;

2. $\exists p\in S^P$ such that $M(p)\ge 1$ ;

3. $\exists r\in S^R$ , $\min \sum _{t\in T\prime }\alpha (t,r)·W(t,r)+M(r)\ge \mathrm{ma}{x}_{t\prime \in r^{•}\cap [S^{•}]}\{W(r,t\prime )\}$ , where $T\prime =\{t|t\in {}^{•}r\cap [S{]}^{•},\forall r\prime \in {}^{•}t\cap P_R,M(r\prime )\ge W(r\prime ,t),M(P_A\cap {}^{•}t)\ge 1\}$ , ${\alpha }_t$ denotes the times that t is fired from marking M, and $\min \sum _{t\in T\prime }{\alpha }_t·W(t,r)$ can be solved by the following mixed integer program

$$min{\displaystyle \sum _{t\in T^{\prime }}\alpha ·W(t,r)}$$

$$p{\in }^{•}t\cap P_A,M(p)\ge 1,t_x\in p^{•}\cap T^{\prime }$$

$${\displaystyle \sum {\alpha }_{t_x}}\le M(p)$$

$$r^{\prime }{\in }^{•}t\cap P_R,t_y\in {r^{\prime }}^{•}\cap T^{\prime }$$

$$\sum {\alpha }_{t_y}·W(r\prime ,t_y)\le M(r\prime )$$

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

$$\min \{\frac{M(r\prime )-\sum {\alpha }_{t_y}·W(r\prime ,t_y)}{W(r\prime ,t)},M(p)-\sum {\alpha }_{t_x}\}<1$$

$${\alpha }_t\in \mathbb{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.

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

Liu and Barkaoui ²⁴¹ present the $\mathrm{ma}{\mathrm{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 $\mathrm{ma}{\mathrm{x}}^{★}$ -marked (non- $\mathrm{ma}{\mathrm{x}}^{★}$ -marked) at $M\in R(N,M_0)$ if at least one (none) of the following conditions hold:

1. $\exists p\in S^P$ , $M(p)\ge 1$ ;

2. $\exists r\in S^R$ , $M(r)\ge \mathrm{ma}{x}_{t\in T_r^c}W(r,t)$ ;

3. $\exists t\in T_S^c$ , $e_{\mathrm{pt}}=1$ , and $e_{rt}=1$ (t is enabled at M).

Theorem 6

Let $(N,M_0)$ be a well-marked GS³PR net and $\Pi \ne \varnothing$ be the set of SMS. ²⁴¹ It is live if $\forall S\in \Pi$ , S is $\mathrm{ma}{\mathrm{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\prime \in R(N,M)$ such that $\exists M″\in R(N,M\prime )$ satisfies $M″(r)\ge 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. $\mathrm{Ma}{\mathrm{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 ${\lambda }_S$ is called the characteristic P-vector of S if $\forall p\in S$ , ${\lambda }_S(p)=1$ ; otherwise, ${\lambda }_S(p)=0$ . ${\eta }_S=[N{]}^T{\lambda }_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 $\Pi =\{S_1,S_2,\dots ,S_k\}$ be a set of siphons of N, $m,n,k\in {\mathbb{N}}^{+}$ . ²¹⁵ Let ${\lambda }_{S_i}$ ( ${\eta }_{S_i}$ ) be the characteristic P(T)-vector of siphon $S_i$ , $i\in {\mathbb{N}}_k=\{1,\dots ,k\}$ . $[\lambda {]}_{k\times m}=[{\lambda }_{S_1}|{\lambda }_{S_2}|\cdots |{\lambda }_{S_k}{]}^T$ and $[\eta {]}_{k\times n}=[\lambda {]}_{k\times m}\times [N{]}_{m\times n}=[{\eta }_{S_1}|{\eta }_{S_2}|\cdots |{\eta }_{S_k}{]}^T$ are called the characteristic P- and T-vector matrices of the siphons in N, respectively.

Definition 17

Let ${\eta }_{S_{\alpha }}$ , ${\eta }_{S_{\beta }}$ , …, ${\eta }_{S_{\gamma }}$ be a linearly independent maximal set of matrix $[\eta ]$ . ²¹⁵ Then, ${\Pi }_E=\{S_{\alpha },S_{\beta },\dots ,S_{\gamma }\}$ is called a set of elementary siphons in N. $S\notin {\Pi }_E$ is called a strongly dependent siphon if ${\eta }_S=\sum _{S_i\in {\Pi }_E}{a}_i{\eta }_{S_i}$ , where $a_i\ge 0$ . $S\notin {\Pi }_E$ is called a weakly dependent siphon if $\exists A,B\subset {\Pi }_E$ such that $A\ne \varnothing$ , $B\ne \varnothing$ , $A\cap B=\varnothing$ , and ${\eta }_S=\sum _{S_i\in A}{a}_i{\eta }_{S_i}-\sum _{S_i\in B}{a}_i{\eta }_{S_i}$ , where $a_i>0$ .

Theorem 8

$|{\Pi }_E|\le \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 $\Pi$ be the siphon set in a net, and ${\Pi }_E$ (resp. ${\Pi }_D$ ) be the set of elementary (resp. dependent) ones within the scope of $\Pi$ . We have $\Pi ={\Pi }_E\cup {\Pi }_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 $[\lambda ]$ and $[\eta ]$ as follows

$$[\lambda ]=\left(\begin{array}{ccccccccccccccc}0\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 1\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& 1\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 1\hfill & 1\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & 1\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 1\hfill & 1\hfill & 1\hfill & 0\hfill \end{array}\right)$$

$$[\eta ]=\left(\begin{array}{cccccccccccc}0\hfill & -1\hfill & 1\hfill & 0\hfill & 0\hfill & -1\hfill & 1\hfill & 0\hfill & -1\hfill & 1\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{-2}& 2\hfill & 0\hfill & 0\hfill & 0\hfill & 2\hfill & 0\hfill & 0\hfill & 0\hfill & -1\hfill & 1\hfill & 0\hfill \\ \multicolumn{1}{c}{-2}& 1\hfill & 1\hfill & 0\hfill & 0\hfill & 1\hfill & 1\hfill & 0\hfill & -1\hfill & 0\hfill & 1\hfill & 0\hfill \end{array}\right)$$

Figure 4.

A generalized Petri net $(N,M_0)$ and its two monitors.

It can be verified that $\mathrm{Rank}[\eta ]=|{\Pi }_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 ${\eta }_{S_3}={\eta }_{S_1}+{\eta }_{S_2}$ . If $S_1$ and $S_3$ are selected as elementary ones, $S_2$ becomes weakly dependent, and ${\eta }_{S_2}={\eta }_{S_3}-{\eta }_{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)>{\displaystyle \sum _{i=1}^n{a}_i}\left(M_0\left(S_i\right)-M_{min}\left(S_i\right)\right)\\ -{\displaystyle \sum _{j=n+1}^m{a}_j}\left(M_0\left(S_j\right)-M_{max}\left(S_j\right)\right)\end{array}$$

Corollary 4

A strongly dependent siphon S is controlled if ²¹⁵

$$M_0(S)>\sum _{i=1}^n{a}_i(M_0\left(S_i\right)-M_{\min }\left(S_i\right))$$

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)>\omega (S)$ , where $\omega (S)=\sum _{p\in S}(\mathrm{ma}{x}_{p^{•}}-1)$ .

Theorem 10

A strongly dependent siphon S is max-controlled if

$$M_0\left(S\right)>\sum _{i=1}^n{a}_i{M}_0\left(S_i\right)-\sum _{i=1}^n{a}_i{M}_{\min }\left(S_i\right)+\omega \left(S\right)$$

Theorem 11

A weakly dependent siphon S is max-controlled if

$$\begin{array}{l}{M}_0(S)\mathrm{>}{\displaystyle \sum _{i=1}^n{a}_i(M_0(S_i)-M_{min}(S_i))}\\ -{\displaystyle \sum _{j=n+1}^m{a}_j\left(M_0\left(S_j\right)-M_{max}\left(S_j\right)\right)}+\omega (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\left(S_i\right)-M_{\min }\left(S_i\right))+\omega (S)$$

Example 5

From Example 1, $S_3$ is a strongly dependent siphon with ${\eta }_{S_3}={\eta }_{S_1}+{\eta }_{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 $\omega (S_3)=1$ and then $M_1(S_3)>\sum _{i=1}^2(M_1(S_i)-M_{\min }(S_i))+\omega (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\backslash 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 ${\lambda }_{\tilde{S}}$ is called the augmented characteristic P-vector of $\tilde{S}$ if $\forall p\in S$ , ${\lambda }_{\tilde{S}}(p)=\tilde{S}(p)$ ; otherwise ${\lambda }_{\tilde{S}}(p)=0$ . ${\eta }_{\tilde{S}}=[N{]}^T{\lambda }_{\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{\lambda }{]}_{k\times m}=[{\lambda }_{{\tilde{S}}_1}|{\lambda }_{{\tilde{S}}_2}|\cdots |{\lambda }_{{\tilde{S}}_k}{]}^T$ and $[\tilde{\eta }{]}_{k\times n}=[\tilde{\lambda }{]}_{k\times m}\times [N{]}_{m\times n}=[{\eta }_{{\tilde{S}}_1}|{\eta }_{{\tilde{S}}_2}|\cdots |{\eta }_{{\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.

1. ${\Pi }_{E_A}=\{S_{\alpha },S_{\beta },\dots ,S_{\gamma }\}$ is called a set of augmented elementary siphons in N if ${\eta }_{{\tilde{S}}_{\alpha }}$ , ${\eta }_{{\tilde{S}}_{\beta }}$ , …, ${\eta }_{{\tilde{S}}_{\gamma }}$ form a linearly independent maximal set of matrix $[\tilde{\eta }]$ , where $\{\alpha ,\beta ,\dots ,\gamma \}\subseteq {\mathbb{N}}_k$ ;

2. $S\notin {\Pi }_{E_A}$ is called a strongly augmented dependent siphon if ${\eta }_{\tilde{S}}=\sum _{S_i\in {\Pi }_{E_A}}{a}_i{\eta }_{{\tilde{S}}_i}$ , where $a_i\ge 0$ ; $S\notin {\Pi }_{E_A}$ is called a weakly augmented dependent siphon if $\exists A,B\subset {\Pi }_{E_A}$ such that $A\ne \varnothing$ , $B\ne \varnothing$ , $A\cap B=\varnothing$ , and ${\eta }_{\tilde{S}}=\sum _{S_i\in A}{a}_i{\eta }_{{\tilde{S}}_i}-\sum _{S_j\in B}{a}_j{\eta }_{{\tilde{S}}_j}$ , where $a_i,a_j\ge 0$ .

3. Let $\Pi$ (resp. ${\Pi }_{D_A}$ ) be the set of SMSs (resp. dependent augmented siphons). We have $\Pi ={\Pi }_{E_A}\cup {\Pi }_{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=\{2p_4,2p_7,p_{10},p_{11}\}$ , and ${\tilde{S}}_3=\{2p_4,p_8,p_9,p_{10},p_{11}\}$ . One can obtain ${\lambda }_{{\tilde{S}}_1}=p_3+p_8+p_9+p_{10}$ , ${\lambda }_{{\tilde{S}}_2}=2p_4+2p_7+p_{10}+p_{11}$ , and ${\lambda }_{{\tilde{S}}_3}=2p_4+p_8+p_9+p_{10}+p_{11}$ . Hence, ${\eta }_{{\tilde{S}}_1}=-t_1+t_2-2t_6+2t_7$ , ${\eta }_{{\tilde{S}}_2}=-t_2+t_3-t_5+t_6$ , and ${\eta }_{{\tilde{S}}_3}=-t_1+t_3-t_5-t_6+2t_7$ .

Figure 5.

A WS³PR N.

We have $\mathrm{rank}([\tilde{\eta }])=2$ and ${\eta }_{{\tilde{S}}_3}={\eta }_{{\tilde{S}}_1}+{\eta }_{{\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, ${\Pi }_{E_A}=\{S_1,S_2\}$ and ${\Pi }_{D_A}=\{S_3\}$ . When the method in the work by Li and Zhou ²¹⁵ is used, $\mathrm{rank}([\eta ])=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 ${\lambda }_{\tilde{S}}+{\lambda }_{[\tilde{S}]}=I_S$ .

In Figure 5, $[{\tilde{S}}_1]=p_2+2p_7$ , $[{\tilde{S}}_2]=p_3+p_6$ , and $[{\tilde{S}}_3]=p_2+p_3+p_6+2p_7$ . It is known that for a siphon in an S³PR, ${\lambda }_S+{\lambda }_{[S]}=I_S$ , ³¹ where $[S]=I_S\backslash S$ . However, it is not always true for generalized nets. The introduction of $\tilde{S}$ and ${\lambda }_{[\tilde{S}]}$ ensures that ${\lambda }_{\tilde{S}}+{\lambda }_{[\tilde{S}]}=I_S$ always holds in a WS³PR. Lemma 2 indicates the relationship between ${\lambda }_{\tilde{S}}$ and ${\lambda }_{[\tilde{S}]}$ . From Definition 19, we have $[\tilde{\eta }]=[N{]}^T{\lambda }_{\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. ${\eta }_{\tilde{S}}=\sum _{i=1}^m{a}_i{\eta }_{{\tilde{S}}_i}-\sum _{j=m+1}^n{a}_j{\eta }_{{\tilde{S}}_j}$ if

$$\left[\tilde{S}\right]=\sum _{i=1}^m{a}_i\left[{\tilde{S}}_i\right]-\sum _{j=m+1}^n{a}_j\left[{\tilde{S}}_j\right]$$

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\prime \in r^{•}$ , if $\nexists t″\in {}^{•}r\cup r^{•}$ such that $t\prime <{{}_{N}t}^{″}$ and $t″<{}_{t}N$ , then $t\prime$ and t are called a transition-pair (t-pair for short) of r, denoted as $〈t\prime ,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||\backslash \{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\prime ,t〉$ be a t-pair of r. $h^t(r)=\{p|t\prime <{}_{N}p,p<{}_{t}N,p\in H(r)\}$ , the operation places that use r between $t\prime$ and t, is called the set of holders of r with respect to t-pair $〈t\prime ,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\backslash 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 {\mathbb{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\ne \varnothing$ , 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 ${\lambda }_{\tilde{S}}$ is called the augmented characteristic P-vector of $\tilde{S}$ if $\forall p\in S$ , ${\lambda }_{\tilde{S}}(p)=\tilde{S}(p)$ ; otherwise ${\lambda }_{\tilde{S}}(p)=0$ . ${\eta }_{\tilde{S}}=[N{]}^T{\lambda }_{\tilde{S}}$ is called the augmented characteristic T-vector of $\tilde{S}$ .

Definition 26

Let $[\tilde{\lambda }{]}_{k\times m}=[{\lambda }_{{\tilde{S}}_1}|{\lambda }_{{\tilde{S}}_2}|\cdots |{\lambda }_{{\tilde{S}}_k}{]}^T$ and $[\tilde{\eta }{]}_{k\times n}=[\tilde{\lambda }{]}_{k\times m}\times [N{]}_{m\times n}=[{\eta }_{{\tilde{S}}_1}|{\eta }_{{\tilde{S}}_2}|\cdots |{\eta }_{{\tilde{S}}_k}{]}^T$ be augmented characteristic P- and T-vector matrices of the siphons in a GLS³PR N, respectively.

1. ${\Pi }_{E_A}=\{S_{\alpha },S_{\beta },\dots ,S_{\gamma }\}$ is called a set of augmented elementary siphons in N if ${\eta }_{{\tilde{S}}_{\alpha }},{\eta }_{{\tilde{S}}_{\beta }},\dots ,{\eta }_{{\tilde{S}}_{\gamma }}(\{\alpha ,\beta ,\dots ,\gamma \}\subseteq {\mathbb{N}}_k)$ constitute a linearly independent maximal set of matrix $[\tilde{\eta }]$ ;

2. $S\notin {\Pi }_{E_A}$ is called a strongly augmented dependent siphon if ${\eta }_{\tilde{S}}=\sum _{S_i\in {\Pi }_{E_A}}{a}_i{\eta }_{{\tilde{S}}_i}$ , where $a_i\ge 0$ ; $S\notin {\Pi }_{E_A}$ is called a weakly augmented dependent siphon if $\exists A,B\subset {\Pi }_{E_A}$ such that $A\ne \varnothing$ , $B\ne \varnothing$ , $A\cap B=\varnothing$ , and ${\eta }_{\tilde{S}}=\sum _{S_i\in A}{a}_i{\eta }_{{\tilde{S}}_i}-\sum _{S_j\in B}{a}_j{\eta }_{{\tilde{S}}_j}$ , where $a_i,a_j\ge 0$ .

3. Let $\Pi$ (resp. ${\Pi }_{D_A}$ ) be the set of SMSs (resp. augmented dependent siphons) in N. We have $\Pi ={\Pi }_{E_A}\cup {\Pi }_{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 ${\Pi }_{E_O}$ (resp. ${\Pi }_{D_O}$ ).

Definition 27

Let ${\Pi }_{E_O}$ (resp. ${\Pi }_{D_O}$ ) be a set of original elementary (resp. dependent) siphons and ${\Pi }_{E_A}$ (resp. ${\Pi }_{D_A}$ ) be a set of augmented elementary (resp. dependent) siphons in a GLS³PR N. ${\Pi }_E={\Pi }_{E_O}\cap {\Pi }_{E_A}$ (resp. ${\Pi }_D={\Pi }_{D_O}\cup {\Pi }_{D_A}$ ) is called a set of elementary (resp. dependent) siphons of N.

Property 6

Let $\Pi$ be a set of SMSs in a GLS³PR. Then, $\Pi ={\Pi }_E\cup {\Pi }_D$ and ${\Pi }_E\cap {\Pi }_D=\varnothing$ , where ${\Pi }_E={\Pi }_{E_O}\cap {\Pi }_{E_A}$ and ${\Pi }_D={\Pi }_{D_O}\cup {\Pi }_{D_A}$ .

Theorem 13

Let $N{\prime }_{\mathrm{ES}}$ (resp. $N_{E{S}_O}$ ) denote the number of elementary siphons defined in Definition 27 (resp. Definition 17). Then $N{\prime }_{\mathrm{ES}}=|{\Pi }_E|\le 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 ${\lambda }_{\tilde{S}}+{\lambda }_{[\tilde{S}]}=I_S$ .

Theorem 14

Let S be an augmented dependent siphon in N. ${\eta }_{\tilde{S}}=\sum _{i=1}^m{a}_i{\eta }_{{\tilde{S}}_i}-\sum _{j=m+1}^n{a}_j{\eta }_{{\tilde{S}}_j}$ if

$$\left[\tilde{S}\right]=\sum _{i=1}^m{a}_i\left[{\tilde{S}}_i\right]-\sum _{j=m+1}^n{a}_j\left[{\tilde{S}}_j\right]$$

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=\{2p_4,p_5,3p_8,2p_9,p_{12},p_{13}\}$ , and ${\tilde{S}}_3=\{2p_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{array}{c}{\lambda }_{{\tilde{S}}_1}=p_3+p_4+p_5+p_{10}+p_{11}+p_{12}\hfill \\ {\lambda }_{{\tilde{S}}_2}=2p_4+p_5+3p_8+2p_9+p_{12}+p_{13}\hfill \\ {\lambda }_{{\tilde{S}}_3}=2p_4+p_5+p_8+p_{10}+p_{11}+p_{12}+p_{13}\hfill \end{array}$$

Hence, we have

$$\begin{array}{c}{\eta }_{{\tilde{S}}_1}=-t_1+t_2-2t_7+2t_9\hfill \\ {\eta }_{{\tilde{S}}_2}=-t_2+t_3-t_6+t_7\hfill \\ {\eta }_{{\tilde{S}}_3}=-t_1+t_3-t_6-t_7+2t_9\hfill \end{array}$$

It can be verified that $\mathrm{rank}[\tilde{\eta }]=2$ with ${\eta }_{{\tilde{S}}_3}={\eta }_{{\tilde{S}}_1}+{\eta }_{{\tilde{S}}_2}$ , leading to ${\Pi }_{E_A}=\{S_1,S_2\}$ and ${\Pi }_{D_A}=\{S_3\}$ .

By Definitions 17, we have

$$\begin{array}{c}{\lambda }_{S_1}=p_3+p_4+p_5+p_{10}+p_{11}+p_{12}\hfill \\ {\lambda }_{S_2}=p_4+p_5+p_8+p_9+p_{12}+p_{13}\hfill \\ {\lambda }_{S_3}=p_4+p_5+p_8+p_{10}+p_{11}+p_{12}+p_{13}\hfill \end{array}$$

Hence

$$\begin{array}{c}{\eta }_{S_1}=-t_1+t_2-2t_7+2t_9\hfill \\ {\eta }_{S_2}=-t_2+t_4-t_6-t_7+t_8+t_9\hfill \\ {\eta }_{S_3}=-t_1+t_4-t_6-t_7+2t_9\hfill \end{array}$$

Then, $\mathrm{rank}[\tilde{\eta }]=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 ${\Pi }_E={\Pi }_{E_O}\cap {\Pi }_{E_A}=\{S_1,S_2\}$ and ${\Pi }_D={\Pi }_{D_O}\cup {\Pi }_{D_A}=\{S_3\}$ .

By Definition 28, $[{\tilde{S}}_1]=p_2+2p_8+2p_9$ , $[{\tilde{S}}_2]=p_3+p_7$ , and $[{\tilde{S}}_3]=p_2+p_3+p_7+2p_8+2p_9$ . It is found that $[{\tilde{S}}_3]=[{\tilde{S}}_1]+[{\tilde{S}}_2]$ , corresponding to ${\eta }_{{\tilde{S}}_3}={\eta }_{{\tilde{S}}_1}+{\eta }_{{\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 $\bigcup h_i(r)=H(r)$ . If $\forall p\in h_i(r)$ , $\exists t\in (h_i(r){)}^{•}$ and $p\prime \in h_i(r)$ , such that $p^{•}{\cap }^{•}(p\prime \cup r)=\{t\}\ne \varnothing$ $(i\in {\mathbb{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\backslash 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{\prec }_{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 ${\lambda }_{\tilde{S}}$ is called the augmented characteristic P-vector of $\tilde{S}$ if $\forall p\in S$ , ${\lambda }_{\tilde{S}}(p)=l(p)$ ; otherwise ${\lambda }_{\tilde{S}}(p)=0$ . ${\eta }_{\tilde{S}}=[N{]}^T{\lambda }_{\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 $\Pi =\{S_1,S_2,\dots ,S_k\}$ be a set of siphons of N, where $m,n,k\in {\mathbb{N}}^{+}$ . Let ${\lambda }_{{\tilde{S}}_i}({\eta }_{{\tilde{S}}_i})$ be the augmented characteristic P(T)-vector of siphon $S_i$ , $i\in {\mathbb{N}}_k$ . $[\tilde{\lambda }{]}_{k\times m}=[{\lambda }_{{\tilde{S}}_1}|{\lambda }_{{\tilde{S}}_2}|\cdots |{\lambda }_{{\tilde{S}}_k}{]}^T$ and $[\tilde{\eta }{]}_{k\times n}=[\tilde{\lambda }{]}_{k\times m}\times [N{]}_{m\times n}=[{\eta }_{{\tilde{S}}_1}|{\eta }_{{\tilde{S}}_2}|\cdots |{\eta }_{{\tilde{S}}_k}{]}^T$ are called the augmented characteristic P- and T-vector matrices of the siphons in N, respectively.

Definition 34

Let $[\tilde{\eta }]$ be the augmented characteristic T-vector matrix of the set of siphons $\Pi =\{S_1,S_2,\dots ,S_k\}$ in an S⁴PR $N=(P,T,F,W)$ .

1. ${\Pi }_{E_A}=\{S_{\alpha },S_{\beta },\dots ,S_{\gamma }\}$ is called a set of augmented elementary siphons in N if ${\eta }_{{\tilde{S}}_{\alpha }}$ , ${\eta }_{{\tilde{S}}_{\beta }}$ , …, ${\eta }_{{\tilde{S}}_{\gamma }}$ $(\{\alpha ,\beta ,\dots ,\gamma \}\subseteq {\mathbb{N}}_k)$ are a linearly independent maximal set of matrix $[\tilde{\eta }]$ ;

2. $S\notin {\Pi }_{E_A}$ is called a strongly augmented dependent siphon if ${\eta }_{\tilde{S}}=\sum _{S_i\in {\Pi }_{E_A}}{a}_i{\eta }_{{\tilde{S}}_i}$ , where $a_i\ge 0$ ; $S\notin {\Pi }_{E_A}$ is called a weakly augmented dependent siphon if $\exists A,B\subset {\Pi }_{E_A}$ such that $A\ne \varnothing$ , $B\ne \varnothing$ , $A\cap B=\varnothing$ , and ${\eta }_{\tilde{S}}=\sum _{S_i\in A}{a}_i{\eta }_{{\tilde{S}}_i}-\sum _{S_j\in B}{a}_j{\eta }_{{\tilde{S}}_j}$ , where $a_i,a_j\ge 0$ .

3. Let $\Pi$ (resp. ${\Pi }_{D_A})$ be the set of SMSs (resp. augmented dependent siphons), we have $\Pi ={\Pi }_{E_A}\cup {\Pi }_{D_A}$ .

Definition 35

${\Pi }_E={\Pi }_{E_O}\cap {\Pi }_{E_A}$ (resp. ${\Pi }_D={\Pi }_{D_O}\cup {\Pi }_{D_A}$ ) is called the set of elementary (resp. dependent) siphons of N.

Lemma 4

Let $\Pi$ be a set of SMSs in an S⁴PR. Then, $\Pi ={\Pi }_E\cup {\Pi }_D$ and ${\Pi }_E\cap {\Pi }_D=\varnothing$ , where ${\Pi }_E={\Pi }_{E_O}\cap {\Pi }_{E_A}$ and ${\Pi }_D={\Pi }_{D_O}\cup {\Pi }_{D_A}$ .

Theorem 15

Let $N{\prime }_{\mathrm{ES}}$ (resp. $N_{E{S}_O}$ ) denote the number of elementary siphons defined in Definition 35 (resp. Definition 17). Then, $N{\prime }_{\mathrm{ES}}=|{\Pi }_E|\le 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

$$[\lambda ]=\left[\begin{array}{cccccccccccccccc}0\hfill & 0\hfill & 1\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 1\hfill & 1\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 1\hfill & 1\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 1\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 1\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 1\hfill & 1\hfill & 1\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 1\hfill & 1\hfill & 1\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 1\hfill & 1\hfill & 1\hfill & 1\hfill & 1\hfill \end{array}\right]$$

$$[\eta ]=\left[\begin{array}{cccccccccccc}-1\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & -1\hfill & 0\hfill & 1\hfill \\ \multicolumn{1}{c}{0}& -1\hfill & -2\hfill & 1\hfill & 2\hfill & 0\hfill & 0\hfill & -1\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & -2\hfill & 0\hfill & 2\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & -2\hfill & -1\hfill & 3\hfill & 0\hfill & -2\hfill & 0\hfill & 2\hfill & 0\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{-1}& -1\hfill & -1\hfill & 1\hfill & 2\hfill & 0\hfill & 0\hfill & -1\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill \\ \multicolumn{1}{c}{0}& -1\hfill & -2\hfill & 0\hfill & 3\hfill & 0\hfill & -2\hfill & 0\hfill & 1\hfill & 1\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{-1}& -1\hfill & -1\hfill & 0\hfill & 3\hfill & 0\hfill & -2\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 1\hfill \end{array}\right]$$

Figure 7.

An S⁴PR model $(N,M_0)$ .

We have $\mathrm{Rank}([\eta ])=5$ , ${\eta }_{S_5}={\eta }_{S_1}+{\eta }_{S_2}$ , and ${\eta }_{S_7}={\eta }_{S_1}+{\eta }_{S_6}$ . It can be concluded that ${\Pi }_{E_O}=\{S_1-S_4,S_6\}$ and ${\Pi }_{D_O}=\{S_5,S_7\}$ .

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

$$[\tilde{\lambda }]=\left[\begin{array}{cccccccccccccccc}0\hfill & 0\hfill & 2\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 2\hfill & 1\hfill & 1\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & 0\hfill & 0\hfill & 3\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 1\hfill & 1\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & 0\hfill & 0\hfill & 3\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 3\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 1\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & 0\hfill & 0\hfill & 3\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 2\hfill & 1\hfill & 1\hfill & 1\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 2\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 1\hfill & 1\hfill & 1\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 2\hfill & 0\hfill & 0\hfill & 2\hfill & 1\hfill & 1\hfill & 1\hfill & 1\hfill \end{array}\right]$$

$$[\tilde{\eta }]=\left[\begin{array}{cccccccccccc}-1\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & -1\hfill & 1\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& -1\hfill & -2\hfill & 3\hfill & 0\hfill & 0\hfill & 0\hfill & -1\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & -2\hfill & 2\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & -2\hfill & -1\hfill & 3\hfill & 0\hfill & -2\hfill & 2\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{-1}& -1\hfill & -1\hfill & 3\hfill & 0\hfill & 0\hfill & 0\hfill & -1\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& -1\hfill & -2\hfill & 0\hfill & 3\hfill & 0\hfill & -2\hfill & 1\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{-1}& -1\hfill & -1\hfill & 0\hfill & 3\hfill & 0\hfill & -2\hfill & 1\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill \end{array}\right]$$

It is verified that $\mathrm{Rank}([\tilde{\eta }])=5$ , ${\eta }_{{\tilde{S}}_6}={\eta }_{{\tilde{S}}_2}+{\eta }_{{\tilde{S}}_4}-{\eta }_{{\tilde{S}}_3}$ , and ${\eta }_{{\tilde{S}}_7}={\eta }_{{\tilde{S}}_4}+{\eta }_{{\tilde{S}}_5}-{\eta }_{{\tilde{S}}_3}$ . ${\Pi }_{E_A}=\{S_1-S_5\}$ and ${\Pi }_{D_A}=\{S_6,S_7\}$ can be obtained by Definition 34. By Definition 35, ${\Pi }_E={\Pi }_{E_O}\cap {\Pi }_{E_A}=\{S_1-S_4\}$ and ${\Pi }_D={\Pi }_{D_O}\cup {\Pi }_{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)>\varpi (S)$ , where $\varpi (S)=\sum _{p\in S^R}(\mathrm{ma}{x}_{t\in (p^{•}\cap {([S]\cap P_S^{\mathrm{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))+\varpi (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))+\varpi (S)$ .

Corollary 7

Let $S_1\in {\Pi }_{D_O}$ and $S_3\in {\Pi }_{D_A}$ be dependent siphons in a net $(N,M_0)$ with ${\eta }_{S_1}={\eta }_{S_2}+{\eta }_{S_3}$ and ${\eta }_{{\tilde{S}}_3}={\eta }_{{\tilde{S}}_4}+{\eta }_{{\tilde{S}}_5}$ , where $S_2,S_3\in {\Pi }_{E_O}$ and $S_4,S_5\in {\Pi }_{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))+\varpi (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}^{\mathrm{in}}{)}^{•}=\{t_8\}$ and $p_{16}^{•}\cap ([S_4]\cap P_{S_4}^{\mathrm{in}}{)}^{•}=\{t_5\}$ . Thus, $\varpi (S_4)=\sum _{p\in S_4^R}(\mathrm{ma}{x}_{t\in (p^{•}\cap {([S]\cap P_S^{\mathrm{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)\ge 2$ . It is obvious that the max-controlled condition is more conservative than the max′-controlled condition.

For dependant siphon $S_5$ , ${\eta }_{S_5}={\eta }_{S_1}+{\eta }_{S_2}$ . Considering that $\varpi (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)+\varpi (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 $\zeta$ 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.