<figure><img src="image_1.png" /></figure>

HAL
open science

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

Yifan Hou, Kamel Barkaoui

► To cite this version:

Yifan Hou, Kamel Barkaoui. Deadlock analysis and control based on Petri nets: A siphon approach review. Advances in Mechanical Engineering, 2017, 9 (5), pp.168781401769354. 10.1177/1687814017693542. hal-02476563

HAL Id: hal-02476563

https://hal.science/hal-02476563

Submitted on 6 Apr 2020

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_3.png" /></figure>

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

YiFan Hou<fnref n="1" />,<fnref n="2" /> and Kamel Barkaoui<fnref n="3" />

## Abstract

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

## Keywords

Petri net, deadlock prevention, structural analysis, siphon, elementary siphon

Date received: 3 October 2016; accepted: 11 January 2017

Academic Editor: Tatsushi Nishi

## Introduction

An automated manufacturing system (AMS)<fnref n="1" />,<fnref n="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

<footnote n="1">¹School of Electro-Mechanical Engineering, Xidian University, Xi’an, P.R. China</footnote>

<footnote n="2">²Key Laboratory of Electronic Equipment Structure Design, Ministry of Education, Xidian University, Xi’an, P.R. China</footnote>

<footnote n="3">³Cedric Lab and Computer Science Department, Conservatoire National des Arts et Métiers, Paris, France</footnote>

<footnote>**Corresponding author:**
YiFan Hou, School of Electro-Mechanical Engineering, Xidian University, Xi’an 710071, P.R. China.</footnote>

<footnote>Email: yfhou@xidian.edu.cn</footnote>
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 employed 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 sig-
nificant role in the analysis of their behavioral proper-
ties, 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 $\bullet S \subseteq S^*$. $S \subseteq P$ is a trap if $S^* \subseteq \bullet 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 $\bullet 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 emp-
tied 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 $\bullet S_4 = \{t_2, t_3\}$ and $S_4^\bullet = \{t_1, t_2, t_3\}$, we have $\bullet S_4 \subseteq S_4^\bullet$, which means that $S_4$ is an SMS. In Figure 1, $S_1, S_2$, and $S_3$ are both siphons and traps since $\bullet S_1 = S_1^\bullet, \bullet S_2 = S_2^\bullet$, and $\bullet S_3 = S_3^\bullet$.

**Property 2.** Let $M \in R(N, M_0)$ be a marking of net $(N, M_0)$ and $S$ be a siphon. If $M(S) = 0$, then $\forall M' \in R(N, M), M'(S) = 0$.

**Property 3.** Let $M \in R(N, M_0)$ be a marking of net $(N, M_0)$ and $S$ be a trap. If $M(S)>0$, then $\forall M' \in R(N, M), M'(S)>0$.

<figure><img src="image_4.png" /><figcaption>**Figure 1.** A Petri net ($N, M_0$).</figcaption></figure>

These two properties indicate that once a siphon is
emptied, it remains unmarked at any subsequent mark-
ings 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 $\exists t \in S^*$, *t* is enabled. By Definition 1, all transi-
tions 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 tran-
sitions 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.³¹,²³⁵
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₀) be an ordinary net and Π be the set of its siphons.³¹,²³⁴ The net is deadlock-free if ∀S ∈ Π, ∀M ∈ R(N, M₀), M(S)>0.

**Theorem 2.** Let (N, M) be an ordinary net that is in a deadlock state.³¹,²³⁴ Then, {p ∈ P|M(p) = 0} is a siphon.

Theorem 1 means that if no (minimal) siphon even-
tually 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.³¹,²³⁴

**Definition 2.** A siphon *S* is said to be controlled in an ordinary Petri net system (*N*, *M*₀) if ∀*M* ∈ *R*(*N*, *M*₀), *M*(*S*)>0.³¹,²³⁴

**Definition 3.** Siphon *S* in an ordinary net system (*N*, *M*₀) is invariant-controlled by *P*-invariant *I* at *M*₀ if *I*ᵀ*M*₀>0 and ∨*p* ∈ *P*\*S, *I*(*p*) ≤ 0, or equivalently, *I*ᵀ*M*₀>0 and ||*I*||⁺ ⊆ *S*.³¹,²³⁴

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 imple-
mented 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 con-
cerned with the enabling and firing of transitions con-
nected with the considered siphons.

**Max-controlled conditions.** Barkaoui and colleagues²³⁴,²³⁶ 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.³¹,²³⁸

**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 \max_{p^*}$, where $\max_{p^*} = \max\{W(p, t)|t \in p^*\}$.

<figure><img src="image_5.png" /><figcaption>**Figure 2.** (a) A Petri net ($N, M_0$) and (b) the reachability graph of ($N, M_0$).</figcaption></figure>

**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), \max_{p^*} = 1, ||I||^+ \subseteq S$ and $I^T M_0 > \sum_{p \in S} I(p)(\max_{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 \subseteq S^*$, $S$ is an SMS. It can be found that $||I||^+ = S$, $||I||^- \cap S = \emptyset$, and $I^T M_0 = M_0(p_5) + 2M_0(p_3) - M_0(p_6) = 1$. We have $\sum_{p \in S} I(p)(\max_{p^*} - 1) = I(p_3)(\max_{p_3^*} - 1) + I(p_5)(\max_{p_5^*} - 1) = 0$. In consequence, $S$ is max-controlled owing to $I^T M_0 > \sum_{p \in S} I(p)(\max_{p^*} - 1)$. The reachability graph of the net in Figure 2(a) is shown in Figure 2(b).

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 \bullet S$ is denoted by $N_S$, where $N_S = (S, \bullet S, F_X, W_X)$. The set of input places of $N_S$ is called the set of input places of $S$, denoted as $P_S^{in}$.²²²

**Definition 7.** Let $\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 \max_{t \in (p \bullet \cap ([S] \cap P_S^{in}) \bullet)} \{W(p, t)\}$.

**Definition 9.** Let $S$ be a siphon of a well-initially-marked S⁴PR $(N, M_0)$.²²²$S$ is said to be max'-controlled if $S$ is max'-marked at any reachable marking $M \in R(N, M_0)$.

**Theorem 4.** Let $(N, M_0)$ be a well-initially-marked S⁴PR.²³⁸$N$ is live if every siphon in $N$ is max'-controlled.

**Example 3.** In the net shown in Figure 3, $S$ is an SMS with $S^P = S \cap P_A = \{p_3, p_6, p_8\}$ and $S^R = S \cap P_R = \{p_9, p_{10}\}$. Then, we have $[S] = \{p_2, p_5\}$ and $P_S^{in} = \{p_2, p_5\}$. Note that $[S] = \{t_2, t_5\}$, $p_9 \cap [S] = \{t_5\}$, and $p_{10} \cap [S] = \{t_2\}$. For $p_9 \in S^R$, $M'(p_9) = \max_{t \in (p_9 \cap ([S] \cap P_S^{in}) \bullet)} \{W(p_9, t)\} = W(p_9, t_5) = 1$. As a result, $S$ is max'-marked at $M'$.

**Max"-controlled conditions.** Liu et al.²⁰¹ present the max"-controllability condition of siphons to relax the max'-controllability condition.

<figure><img src="image_6.png" /><figcaption>**Figure 3.** An S⁴PR $(N_1, M_0_1)$.</figcaption></figure>

**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'} \alpha(t, r) \cdot W(r, t) + M(r) \ge \max_{t' \in T' \cap [S]^{\bullet}} \{W(r, t')\}$, where $T' = \{t | t \in \bullet r \cap [S]^{\bullet}\}$, $\forall r' \in \bullet t \cap P_R, M(r') \ge W(r', t), M(P_A \cap \bullet t) \ge 1\}$, $\alpha_t$ denotes the times that $t$ is fired from marking $M$, and $\min \sum_{t \in T'} \alpha_t \cdot W(t, r)$ can be solved by the following mixed integer program

$$ \begin{array}{ll} \min & \sum_{t \in T'} \alpha \cdot W(t, r) \\ & p \in \bullet t \cap P_A, M(p) \ge 1, t_x \in p^{\bullet} \cap T' \\ & \sum_{r' \in \bullet t \cap P_R, t_y \in r'^{\bullet} \cap T'} \alpha_{t_x} \le M(p) \\ & \sum_{r' \in \bullet t \cap P_R, t_y \in r'^{\bullet} \cap T'} \alpha_{t_y} \cdot W(r', t_y) \le M(r') \\ & t \in \bullet r \cap [S]^{\bullet} \\ \min & \left\{ \frac{M(r') - \sum \alpha_{t_y} \cdot W(r', t_y)}{W(r', t)}, M(p) - \sum \alpha_{t_x} \right\} < 1 \\ & \alpha_t \in \mathbb{N} \end{array} $$

**Definition 11.** Let $S$ be a siphon in a well-marked S⁴PR $(N, M_0)$.²⁰¹$S$ is said to be max"-controlled if $\forall M \in R(N, M_0)$, $S$ is max"-marked at $M$.

**Theorem 5.** Let $(N, M_0)$ be a well-marked S⁴PR.²⁰¹ The net is live if all its siphons are max"-controlled.

**Max★-controlled conditions.** Liu and Barkaoui²⁴¹ present the max★-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 max★-marked
(non-max★-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 \max_{i \in T_r} W(r, t)$;

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

**Theorem 6.** Let $(N, M_0)$ be a well-marked $GS^3PR$ net and $\Pi \ne \emptyset$ be the set of SMS.²⁴¹ It is live if $\forall S \in \Pi$, $S$ is max★-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^3PR$ can be ensured if all its siphons are W-controlled.

**Definition 13.** Let $S$ be a siphon in a marked $WS^3PR$ $(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 \bullet S^R \cap S^R \circ$, $M' \in R(N, M)$ such that $\exists M'' \in R(N, M')$ satisfies $M''(r) \ge W(r, t)$, where $\{r\} = \bullet t \cap P_R$.

**Definition 14.** Let $S$ be a siphon in a marked $WS^3PR$ $(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^3PR$.²⁴² The net is live if and only if all its siphons are W-controlled.

Note that max-controllability,²³⁴ max'-controllability,²²²,²³⁸ and max"-controllability²⁰¹ can be utilized in $S^4PR$, and all of them are sufficient but not necessary conditions. Max★-controllability and W-controllability are both necessary and sufficient. The former is proposed for $GS^3PR$, and the latter is developed for $WS^3PR$.

## 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^3PR$²³⁵ 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}, \dots, \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 \emptyset, B \ne \emptyset, A \cap B = \emptyset$, 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] = \begin{pmatrix} 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & 0 \end{pmatrix}$$

$$[\eta] = \begin{pmatrix} 0 & -1 & 1 & 0 & 0 & -1 & 1 & 0 & -1 & 1 & 0 & 0 \\ -2 & 2 & 0 & 0 & 0 & 2 & 0 & 0 & 0 & -1 & 1 & 0 \\ -2 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & -1 & 0 & 1 & 0 \end{pmatrix}$$

It can be verified that $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.
<figure><img src="image_7.png" /><figcaption>Figure 4. A generalized Petri net (N, M₀) and its two monitors.</figcaption></figure>

**Controllability of dependent siphons.** Li and Zhou<sup>215</sup> 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<sup>215</sup>

$$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))$$

**Corollary 4.** A strongly dependent siphon S is controlled if<sup>215</sup>

$$M_0(S) > \sum_{i=1}^{n} a_i (M_0(S_i) - M_{min}(S_i))$$

**Lemma 1.** Let S be a siphon in net (N, M₀) and M ∈ R(N, M₀) be a marking. S is max-marked at M if $M(S) > \omega(S)$, where $\omega(S) = \sum_{p \in S} (max_p - 1)$.

**Theorem 10.** A strongly dependent siphon S is max-controlled if

$$M_0(S) > \sum_{i=1}^{n} a_i M_0(S_i) - \sum_{i=1}^{n} a_i M_{min}(S_i) + \omega(S)$$

**Theorem 11.** A weakly dependent siphon S 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)) + \omega(S)$$

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₀) is max-controlled if

$$M_0(S) > \sum_{i=1}^{n} a_i (M_0(S_i) - M_{min}(S_i)) + \omega(S)$$

**Example 5.** From Example 1, S₃ 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₃ 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<sup>216,229–231,243–246</sup> 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.<sup>222–224,226</sup>

### Augmented elementary siphons in WS<sup>3</sup>PR

**Augmented elementary siphons.** The augmented siphon and augmented complementary set of a siphon are defined in the work by Hou et al.<sup>224</sup> for WS<sup>3</sup>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<sup>3</sup>PR N = (P₀ ∪ P<sub>A</sub> ∪ P<sub>R</sub>, T, F, W) with S = S<sup>P</sup> ∪ S<sup>R</sup>, S<sup>R</sup> = S ∩ P<sub>R</sub>, and S<sup>P</sup> = S \ S<sup>R</sup>.<sup>224</sup> 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}, \dots, \eta_{\tilde{S}_\gamma}$ form a linearly independent maximal set of matrix $[\tilde{\eta}]$, where $\{\alpha, \beta, \dots, \gamma\} \subseteq 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 \emptyset, B \ne \emptyset, A \cap B = \emptyset$, 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} + p_{11}$, $\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$.

We have $\text{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$^{215}$ is used, $\text{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.$^{215}$

<figure><img src="image_8.png" /><figcaption>Figure 5. A WS³PR N.</figcaption></figure>

**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 \setminus 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

$$[\tilde{S}] = \sum_{i=1}^{m} a_i [\tilde{S}_i] - \sum_{j=m+1}^{n} a_j [\tilde{S}_j]$$

**Controllability of augmented dependent siphons.** In a WS³PR, all SMSs are divided into the sets of augmented elementary and augmented dependent ones. The condition in Corollary 5 is still valid, under which an augmented dependent siphon can be always 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.$^{223}$ 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.$^{223}$

**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$^3$PR. $\forall r \in P_R$, $t \in \bullet r$, $t' \in r^\bullet$, if $\nexists t'' \in \bullet r \cup r^\bullet$ such that $t' <_N t''$ and $t'' <_N t$, then $t'$ and $t$ are called a transition-pair (t-pair for short) of $r$, denoted as $\langle t', t \rangle$.

**Definition 23.** Let $N = (P_A \cup P_0 \cup P_R, T, F, W)$ be a GLS$^3$PR. $\forall r \in P_R$, $H(r) = ||I_r|| \setminus \{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 $\langle t', t \rangle$ be a t-pair of $r$. $h^t(r) = \{p | t' <_N p, p <_N t, p \in H(r)\}$, the operation places that use $r$ between $t'$ and $t$, is called the set of holders of $r$ with respect to t-pair $\langle t', t \rangle$. 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$^3$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 \setminus S^R$. A multiset $\tilde{S}$ is the augmented version of $S$ such that $(1) \quad ||\tilde{S}|| = S$ and $(2) \quad \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 $\bullet t \cap S^P \neq \emptyset$, then $\tilde{S}_r(p) = I_r(p)$, else $\tilde{S}_r(p) = 0$ and (b) $\tilde{S}(p) = \sum_{r \in S^R} \tilde{S}_r(p)$.

**Definition 25.** Let $S$ be a siphon in a GLS$^3$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$^3$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_j \in \Pi_{E_A}} a_i \eta_{\tilde{S}_j}$, 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 \neq \emptyset, B \neq \emptyset, A \cap B = \emptyset$, 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.²¹⁵,²¹⁶ 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$^3$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$^3$PR. Then, $\Pi = \Pi_E \cup \Pi_D$ and $\Pi_E \cap \Pi_D = \emptyset$, where $\Pi_E = \Pi_{E_O} \cap \Pi_{E_A}$ and $\Pi_D = \Pi_{D_O} \cup \Pi_{D_A}$.

**Theorem 13.** Let $N'_{ES}$ (resp. $N_{ES_O}$) denote the number of elementary siphons defined in Definition 27 (resp. Definition 17). Then $N'_{ES} = |\Pi_E| \le N_{ES_O}$.

**Definition 28.** Let $S = S^R \cup S^P$ be a siphon in a GLS$^3$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

$$[\tilde{S}] = \sum_{i=1}^{m} a_i [\tilde{S}_i] - \sum_{j=m+1}^{n} a_j [\tilde{S}_j]$$

**Example 7.** The net in Figure 6 is a GLS$^3$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}\}$.

One can obtain

$$\lambda_{\tilde{S}_1} = p_3 + p_4 + p_5 + p_{10} + p_{11} + p_{12}$$

$$\lambda_{\tilde{S}_2} = 2p_4 + p_5 + 3p_8 + 2p_9 + p_{12} + p_{13}$$

$$\lambda_{\tilde{S}_3} = 2p_4 + p_5 + p_8 + p_{10} + p_{11} + p_{12} + p_{13}$$

Hence, we have

$$\eta_{\tilde{S}_1} = -t_1 + t_2 - 2t_7 + 2t_9$$

$$\eta_{\tilde{S}_2} = -t_2 + t_3 - t_6 + t_7$$

$$\eta_{\tilde{S}_3} = -t_1 + t_3 - t_6 - t_7 + 2t_9$$
<figure><img src="image_9.png" /><figcaption>Figure 6. A GLS³PR (N, M₀).</figcaption></figure>

It can be verified that $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{aligned}
\lambda_{S_1} &= p_3 + p_4 + p_5 + p_{10} + p_{11} + p_{12} \\
\lambda_{S_2} &= p_4 + p_5 + p_8 + p_9 + p_{12} + p_{13} \\
\lambda_{S_3} &= p_4 + p_5 + p_8 + p_{10} + p_{11} + p_{12} + p_{13}
\end{aligned}
$$

Hence

$$ 
\begin{aligned}
\eta_{S_1} &= -t_1 + t_2 - 2t_7 + 2t_9 \\
\eta_{S_2} &= -t_2 + t_4 - t_6 - t_7 + t_8 + t_9 \\
\eta_{S_3} &= -t_1 + t_4 - t_6 - t_7 + 2t_9
\end{aligned}
$$

Then, $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_0} \cap \Pi_{E_A} = \{S_1, S_2\}$ and $\Pi_D = \Pi_{D_0} \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 \equiv \|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 $\cup h_i(r) = H(r)$. If $\forall p \in h_i(r)$, $\exists t \in (h_i(r))$ and $p' \in h_i(r)$, such that $p' \cap (p' \cup r) = \{t\} \neq \emptyset$ ($i \in \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 \setminus 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^s = \{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^s(p) = W(t, r)$ and (b) $l_r(p) = \sum_{l \in r} l_r^l(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}_{\tilde{S}_1}|\tilde{\eta}_{\tilde{S}_2}|\cdots|\tilde{\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}, \dots, \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_j \in \Pi_{E_A}} a_i \eta_{\tilde{S}_j}$, 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 \emptyset, B \ne \emptyset$, $A \cap B = \emptyset$, and $\eta_{\tilde{S}} \sim = \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_0} \cap \Pi_{E_A}$ (resp. $\Pi_D = \Pi_{D_0} \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^4$PR. Then, $\Pi = \Pi_E \cup \Pi_D$ and $\Pi_E \cap \Pi_D = \emptyset$, where $\Pi_E = \Pi_{E_0} \cap \Pi_{E_A}$ and $\Pi_D = \Pi_{D_0} \cup \Pi_{D_A}$.

**Theorem 15.** Let $N'_{ES}$ (resp. $N_{ES_0}$) denote the number of elementary siphons defined in Definition 35 (resp. Definition 17). Then, $N'_{ES} = |\Pi_E| \le N_{ES_0}$.

**Example 8.** The net in Figure 7 is an $S^4$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$^{215}$ presented in Definition 17, one obtains

<figure><img src="image_10.png" /><figcaption>**Figure 7.** An $S^4$PR model ($N, M_0$).</figcaption></figure>

$$[\lambda] = \begin{bmatrix} 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \end{bmatrix}$$

$$[\eta] = \begin{bmatrix} -1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & 1 \\ 0 & -1 & -2 & 1 & 2 & 0 & 0 & -1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & -2 & 0 & 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & -2 & -1 & 3 & 0 & -2 & 0 & 2 & 0 & 0 & 0 & 0 & 0 & 1 \\ -1 & -1 & -1 & 1 & 2 & 0 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & -1 & -2 & 0 & 3 & 0 & -2 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ -1 & -1 & -1 & 0 & 3 & 0 & -2 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \end{bmatrix}$$

We have $\text{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_0} = \{S_1 - S_4, S_6\}$ and $\Pi_{D_0} = \{S_5, S_7\}$.

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

$$[\tilde{\lambda}] = \begin{bmatrix} 0 & 0 & 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 3 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 3 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 3 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 3 & 0 & 0 & 0 & 0 & 0 & 2 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 2 & 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 2 & 0 & 0 & 2 & 1 & 1 & 1 & 1 \end{bmatrix}$$

$$[\tilde{\eta}] = \begin{bmatrix} -1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 \\ 0 & -1 & -2 & 3 & 0 & 0 & 0 & -1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & -2 & 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & -2 & -1 & 3 & 0 & -2 & 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ -1 & -1 & -1 & 3 & 0 & 0 & 0 & -1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & -1 & -2 & 0 & 3 & 0 & -2 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ -1 & -1 & -1 & 0 & 3 & 0 & -2 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \end{bmatrix}$$

It is verified that $\text{Rank}([\tilde{\eta}]) = 5$, $\eta_{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_0} \cap \Pi_{E_A} = \{S_1 - S_4\}$ and $\Pi_D = \Pi_{D_0} \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.,$^{222}$ 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^4$PR ($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^R} (\max_{t \in (p \cdot \cap([S] \cap P_S^{\omega}))} \{W(p, t)\} - 1)$.

**Theorem 16.** An augmented dependent siphon $S$ in an $S^4$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)) + \omega(S)$.
**Corollary 6.** A dependent siphon *S* in a well-initially-marked S⁴PR (*N*, *M*₀) is max'-controlled if *M*₀(*S*) > Σ<sub>*i*</sub><sup>*n*</sup> *a*<sub>*i*</sub>(*M*₀(*S*<sub>*i*</sub>) − *M*<sub>min</sub>(*S*<sub>*i*</sub>)) + *ω*(*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)) + \omega(S_1)$.

**Example 9.** For the net shown in Figure 7, take $S_4 = \{p_6, p_9, p_{10}, p_{15}, p_{16}\}$ as an example. Note that $[S_4]^* = \{t_4, t_5, t_8\}$, we have $p_{15}^* \cap ([S_4] \cap P_{S_4}^{in})^* = \{t_8\}$ and $p_{16}^* \cap ([S_4] \cap P_{S_4}^{in})^* = \{t_5\}$. Thus, $\omega(S_4) = \sum_{p \in S_4^R} (\max_{t \in (p^* \cap ([S] \cap P_S^{in})^*)} \{W(p, t)\} - 1) = 0$, that is, $S_4$ is max'-controlled if $\forall M \in R(N, M_0)$, $M(S_4) > 0$. Meanwhile, according to Definition 5, $S_4$ is max-controlled if $M(S_4) \ge 2$. It is obvious that the max-controlled condition is more conservative than the max'-controlled condition.

For dependent siphon $S_5$, $\eta_{S_5} = \eta_{S_1} + \eta_{S_2}$. Considering that $\omega(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) + \omega(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<sup>252</sup> 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.<sup>267</sup>

## Elementary siphons computation

Computation of elementary siphons proposed by Li et al.<sup>268</sup> 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<sup>219</sup> 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,<sup>269</sup> 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<sup>217</sup> presents the *T*-characteristic vector $\zeta$ to compute SMSs for $S^3PR$ 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,<sup>265</sup> another elementary siphon computation method is developed by Chao.<sup>218</sup>

Based on graph theory, Wang et al.<sup>233</sup> propose a polynomial complexity algorithm to find a set of elementary siphons for a linear system of simple sequential processes with resources ($LS^3PR$). 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^3PR$ and $GLS^3PR$. Initial resource weighted digraphs and restricted subgraphs are proposed for $WS^3PR$ and $GLS^3PR$, respectively, from which all SMSs and elementary siphons can be derived. The related works can be found in the studies by Hou et al.<sup>223,224</sup>

Li et al.<sup>270</sup> propose an iterative algorithm to extract a set of elementary siphons in $S^3PR$. 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.<sup>271</sup> 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^3PR$), 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.<sup>272</sup> 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.<sup>235</sup> 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^3PR$ 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.²⁷⁵,²⁷⁶ 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<sup>280</sup> that are more general classes of Petri nets than S<sup>3</sup>PR.

The MIP-based deadlock detection method is then used by Huang et al.<sup>141,281</sup> Huang et al.<sup>281</sup> further extend the MIP method to propose an iterative siphon-based control policy for S<sup>3</sup>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.<sup>281</sup> 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.<sup>281</sup> is the existence of redundant siphons. As a matter of fact, the work by Shih and Chao<sup>282</sup> 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.<sup>251,283</sup> 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.<sup>283</sup> Based on MIP and the concept of implicit places (IPs), Li and Li<sup>284</sup> 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<sup>228</sup> 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.<sup>285</sup> 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.<sup>235</sup> 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,<sup>215</sup> while the latter are subsequently renamed as dependent siphons.<sup>216</sup> From the deadlock control policy by Li and Zhou,<sup>215</sup> all problematic siphons in an S<sup>3</sup>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<sup>215</sup> can lead to a structurally simple liveness-enforcing supervisor.

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

The work by Li et al.<sup>286</sup> aims to tackle the issues on the computational complexity and restricted behavior in the work by Li and Zhou.<sup>215</sup> 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.²⁸⁹,²⁹⁰ 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<sup>291</sup> 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.<sup>232</sup> develops an elementary siphon-based policy to design a liveness-enforcing supervisor for an S<sup>3</sup>PR with uncontrollable and unobservable transitions. For all the elementary siphons, their complementary sets are successively expanded by considering the unobservabil- ity 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 opti- mal. 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.<sup>292</sup> 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 sol- ving a set covering problem. Unfortunately, the com- putational 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.<sup>292</sup> cannot lead to an optimal liveness-enforcing supervisor.

After the computational complexity problem is recognized, Piroddi et al.<sup>293</sup> 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.<sup>294</sup> outline the iterative method proposed by Piroddi et al.<sup>293</sup> in detail. By contrast, the methods by Chao and colleagues<sup>138,295,296</sup> can avoid both enumerat- ing 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<sup>245</sup> 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 sepa- rated 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 moni- tors. When the initial markings of the plant change, a new supervisor with the same structure can be deter- mined 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<sup>245</sup> 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 the- ory of regions, Li et al.<sup>244</sup> develop a two-stage deadlock prevention policy by integrating siphon control and the theory of regions. The first stage, called siphons con- trol, is to add monitors for all SMSs identified through resource circuits such that it is optimally invariant con- trolled. 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 aug- mented Petri net. Since the siphon control stage is opti- mal 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 maxi- mally permissive liveness-enforcing supervisor for an S<sup>3</sup>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.²⁷⁴⁻²⁷⁶ 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.²⁴⁴,³⁰⁰,³⁰¹ 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²⁸²,³⁰³ 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.³⁰⁶,³⁰⁷

## 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.

## Declaration of conflicting interests

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

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

## References

1. Chao DY. Automated manufacturing system: virtual-nets or non-virtual-nets? *IET Control Theory A* 2009; 3: 671-680.

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

3. D'Souza KA and Khator SK. A survey of Petri net applications in modeling controls for automated manufacturing systems. *Comput Ind* 1994; 24: 5-16.

4. Fanti MP, Maione G and Turchiano B. Distributed event-control for deadlock avoidance in automated manufacturing systems. *Int J Prod Res* 2001; 39: 1993-2021.

5. Fanti MP and Zhou MC. Deadlock control methods in automated manufacturing systems. *IEEE T Syst Man Cy A* 2004; 34: 5-22.

6. Hu HS and Li ZW. Efficient deadlock prevention policy in automated manufacturing systems using exhausted resources. *Int J Adv Manuf Tech* 2009; 40: 566-571.

7. Hu HS and Li ZW. Synthesis of liveness enforcing supervisor for automated manufacturing systems using insuffciently marked siphons. *J Intell Manuf* 2010; 21: 555-567.

8. Hu HS, Zhou MC and Li ZW. Supervisor design to enforce production ratio and absence of deadlock in automated manufacturing systems. *IEEE T Syst Man Cy A* 2011; 41: 201-212.

9. Jeng MD and DiCesare F. A review of synthesis techniques for Petri nets with applications to automated manufacturing systems. *IEEE T Syst Man Cyb* 1993; 23: 301-312.

10. Kim CO and Kim SS. An efficient real-time deadlock-free control algorithm for automated manufacturing systems. *Int J Prod Res* 1997; 35: 1545-1560.

11. Lawley MA. Integrating flexible routing and algebraic deadlock avoidance policies in automated manufacturing systems. *Int J Prod Res* 2000; 38: 2931-2950.

12. Reveliotis SA and Ferreira PM. Deadlock avoidance policies for automated manufacturing cells. *IEEE T Robotic Autom* 1996; 12: 845-857.

13. Viswanadham N and Narahari Y. *Performance modeling of automated manufacturing systems*. Englewood Cliffs, NJ: Prentice Hall, 1992.

14. Wu NQ and Zhou MC. Avoiding deadlock and reducing starvation and blocking in automated manufacturing systems. *IEEE T Robotic Autom* 2001; 17: 658-669.

15. Wu NQ and Zhou MC. Modeling and deadlock avoidance of automated manufacturing systems with multiple automated guided vehicles. *IEEE T Syst Man Cy B* 2005; 35: 1193-1202.

16. Wu NQ and Zhou MC. Deadlock resolution in automated manufacturing systems with robots. *IEEE T Autom Sci Eng* 2007; 4: 474-480.

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

18. Cho H, Kumaran TK and Wysk RA. Graph-theoretic deadlock detection and resolution for flexible manufacturing systems. *IEEE T Robotic Autom* 1995; 11: 413-421.

19. Coffman EG, Elphick MJ and Shoshani A. System deadlocks. *ACM Comput Surv* 1971; 3: 66-78.

20. Gold EM. Deadlock prediction: easy and difficult cases. *SIAM J Comput* 1978; 7: 320-336.

21. Isloor SS and Marsland TA. The deadlock problem: an overview. *Computer* 1980; 13: 58-77.

22. Castelnuovo A, Ferrarini L and Piroddi L. An incremental Petri net-based approach to the modeling of production sequences in manufacturing systems. *IEEE T Autom Sci Eng* 2007; 4: 424-434.

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

24. David R and Alla H. *Petri nets and Grafcet*. London: Prentice Hall, 1992.

25. Desrochers AA and Al-Jaar RY. *Applications of Petri nets in manufacturing systems: modeling, control, and performance analysis*. New York: IEEE Press, 1994.

26. DiCesare F, Harhalakis G, Porth JM, et al. *Practice of Petri nets in manufacturing*. London: Chapman & Hall, 1993.

27. Hruz B and Zhou MC. *Modeling and control of discrete-event dynamic systems: with Petri nets and other tools*. London: Springer-Verlag, 2007.

28. Iordache MV and Antsaklis PJ. *Supervisory control of concurrent systems: a Petri net structural approach*. Berlin: Springer-Verlag, 2006.

29. Jeng MD. A Petri net synthesis theory for modeling flexible manufacturing systems. *IEEE T Syst Man Cy B* 1997; 27: 169-183.

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

31. Li ZW and Zhou MC. *Deadlock resolution in automated manufacturing systems: a novel Petri net approach*. New York: Springer-Verlag, 2009.

32. Marsan MA, Balbo G, Conte G, et al. *Modelling with generalized stochastic Petri nets*. New York: Wiley, 1995.

33. Moore KE and Guptats SM. Petri net models of flexible and automated manufacturing systems: a survey. *Int J Prod Res* 1996; 34: 3001-3035.

34. Murata T. Petri nets: properties, analysis and applications. *P IEEE* 1989; 77: 541-580.

35. Peterson JL. Petri nets. *ACM Comput Surv* 1977; 9: 223-252.

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

37. Proth JM and Xie XL. *Petri nets: a tool for design and management of manufacturing systems*. New York: Wiley, 1996.

38. Reisig W. *Petri nets: an introduction*. New York: Springer-Verlag, 1985.

39. Silva M, Teruel E, Valette R, et al. Petri nets and production systems. In: Reisig W and Rozenberg G (eds) *Lectures on Petri nets II: applications*, vol. 1492 (Lecture
notes in computer science). Berlin: Springer, 1998, pp.85–124.

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

41. Wu NQ and Zhou MC. Process vs resource-oriented Petri net modeling of automated manufacturing systems. *Asian J Control* 2010; 12: 267–280.

42. Wu NQ and Zhou MC. *System modeling and control with resource-oriented Petri nets*. New York: CRC Press, 2010.

43. Zhou MC and DiCesare F. *Petri net synthesis for discrete event control of manufacturing systems*. Boston, MA: Kluwer Academic Publishers, 1993.

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

45. Zhou MC and Venkatesh K. *Modeling, simulation, and control of flexible manufacturing systems: a Petri net approach*. Singapore: World Scientific, 1998.

46. Zurawski R and Zhou MC. Petri nets and industrial applications: a tutorial. *IEEE T Ind Electron* 1994; 41: 567–583.

47. Zurawski R and Zhou MC. Petri nets and industrial applications: a tutorial. *IEEE T Ind Electron* 1994; 41: 567–583.

48. Banaszak Z and Krogh BH. Deadlock avoidance in flexible manufacturing systems with concurrently competing process flows. *IEEE T Robotic Autom* 1990; 6: 724–734.

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

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

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

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

53. Ezpeleta J, Tricas F, Garcia-Valles F, et al. A banker's solution for deadlock avoidance in FMS with flexible routing and multiresource states. *IEEE T Robotic Autom* 2002; 18: 621–625.

54. Ezpeleta J and Recalde L. A deadlock avoidance approach for nonsequential resource allocation systems. *IEEE T Syst Man Cy A* 2004; 34: 93–101.

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

56. Fanti MP, Maione B, Mascolo S, et al. Performance of deadlock avoidance algorithms in flexible manufacturing systems. *J Manuf Syst* 1996; 15: 164–178.

57. Fanti MP, Maione B, Mascolo S, et al. Event-based feedback control for deadlock avoidance in flexible production systems. *IEEE T Robotic Autom* 1997; 13: 347–363.

58. Fanti MP, Giua A and Seatzu C. Monitor design for colored Petri nets: an application to deadlock prevention in railway networks. *Control Eng Pract* 2006; 14: 1231–1247.

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

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

61. He KX and Lemmon MD. Liveness-enforcing supervision of bounded ordinary Petri nets using partial order methods. *IEEE T Automat Contr* 2002; 47: 1042–1055.

62. Holloway LE, Krogh BH and Giua A. A survey of Petri net methods for controlled discrete event systems. *Discrete Event Dyn S* 1997; 7: 151–190.

63. Hou YF, Zhao M and Liu D. Deadlock control for a class of generalized Petri nets based on proper resource allocation. *Asian J Control* 2016; 18: 206–223.

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

65. Hu HS, Zhou MC and Li ZW. Algebraic synthesis of timed supervisor for automated manufacturing systems using Petri nets. *IEEE T Autom Sci Eng* 2010; 7: 549–557.

66. Hu HS, Zhou MC and Li ZW. Low-cost and high-performance supervision in ratio-enforced automated manufacturing systems using timed Petri nets. *IEEE T Autom Sci Eng* 2010; 7: 933–944.

67. Hu HS, Zhou MC and Li ZW. Supervisor optimization for deadlock resolution in automated manufacturing systems with Petri nets. *IEEE T Autom Sci Eng* 2011; 8: 794–804.

68. Hu HS, Zhou MC and Li ZW. Liveness and ratio-enforcing supervision of automated manufacturing systems using Petri nets. *IEEE T Syst Man Cy A* 2012; 42: 392–403.

69. Hu HS, Zhou MC, Li ZW, et al. An optimization approach to improved Petri net controller design for automated manufacturing systems. *IEEE T Autom Sci Eng* 2013; 10: 772–782.

70. Hu HS, Zhou MC and Li ZW. Deadlock-free control of automated manufacturing systems with flexible routes and assembly operations using Petri nets. *IEEE T Ind Inform* 2013; 9: 109–121.

71. Iordache MV and Antsaklis PJ. Generalized conditions for liveness enforcement and deadlock prevention in Petri nets. In: *Proceedings of the 22nd international conference on applications and theory of Petri nets*, vol. 2075 (Lecture notes in computer science), Newcastle upon Tyne, 25–29 June 2001, pp.184–203. Berlin: Springer.
72. Iordache MV, Moody JO and Antsaklis PJ. Synthesis of deadlock prevention supervisors using Petri nets. *IEEE T Robotic Autom* 2002; 18: 59-68.

73. Lautenbach K and Ridder H. *The linear algebra of deadlock avoidance: a Petri net approach*. Technical report no. 25-96, 1996. Koblenz: Institute for Software Technology, University of Koblenz-Landau.

74. Li ZW and Zhou MC. Comparison of two deadlock prevention methods for different-size flexible manufacturing systems. *Int J Intell Contr Syst* 2005; 10: 235-243.

75. Li ZW, Zhu S and Zhou MC. A divide-and-conquer strategy to deadlock prevention in flexible manufacturing systems. *IEEE T Syst Man Cy C* 2009; 39: 156-169.

76. Li ZW and Hu HS. On systematic methods to remove redundant monitors from liveness-enforcing net supervisors. *Comput Ind Eng* 2009; 56: 53-62.

77. Li ZW and Shpitalni M. Smart deadlock prevention policy for flexible manufacturing systems using Petri nets. *IET Control Theory A* 2009; 3: 362-374.

78. Li ZW and Zhou MC. Synthesis of structurally simple supervisors enforcing generalized mutual exclusion constraints in Petri nets. *IEEE T Syst Man Cy C* 2010; 40: 330-340.

79. Li ZW, Qin M and Zhu S. Identification of controllable transitions to decide the existence of an optimal liveness-enforcing supervisor for a class of Petri nets. *T I Meas Control* 2011; 33: 406-421.

80. Li ZW, Liu GY, Hanisch HM, et al. Deadlock prevention based on structure reuse of Petri net supervisors for flexible manufacturing systems. *IEEE T Syst Man Cy A* 2012; 42: 178-191.

81. Li ZW. Deadlock analysis and control in resource allocation systems. *Inform Sciences* 2016; 363: 174-177.

82. Liu GJ, Jiang CJ and Zhou MC. Two simple deadlock prevention policies for $S^3PR$ based on key-resource/operation-place pairs. *IEEE T Autom Sci Eng* 2010; 7: 945-957.

83. Liu GY and Li ZW. General mixed integer programming-based liveness test for system of sequential systems with shared resources nets. *IET Control Theory A* 2010; 4: 2867-2878.

84. Liu GY, Li ZW, Barkaoui K, et al. Robustness of deadlock control for a class of Petri nets with unreliable resources. *Inform Sciences* 2013; 235: 259-279.

85. Maione G and DiCesare F. Hybrid Petri net and digraph approach for deadlock prevention in automated manufacturing systems. *Int J Prod Res* 2005; 43: 5131-5159.

86. Ma ZY, Li ZW and Giua A. Design of optimal Petri net controllers for disjunctive generalized mutual exclusion constraints. *IEEE T Automat Contr* 2015; 60: 1774-1785.

87. Ma ZY, Li ZW and Giua A. Petri net controllers for generalized mutual exclusion constraints with floor operators. *Automatica* 2016; 74: 238-246.

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

89. Moody JO and Antsaklis PJ. Petri net supervisors for DES with uncontrollable and unobservable transitions. *IEEE T Automat Contr* 2000; 45: 462-476.

90. Park J and Reveliotis SA. Deadlock avoidance in sequential resource allocation systems with multiple resource acquisitions and flexible routings. *IEEE T Automat Contr* 2001; 46: 1572-1583.

91. Qin M, Li ZW, Khalgui M, et al. On applicability of deadlock prevention policies with uncontrollable and unobservable transitions. *Int J Innov Comput I* 2011; 7: 4115-4127.

92. Reveliotis SA, Lawley MA and Ferreira PM. Polynomial-complexity deadlock avoidance policies for sequential resource allocation systems. *IEEE T Automat Contr* 1997; 42: 1344-1357.

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

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

95. Taubin A, Kondratyev A and Kishinevsky M. Deadlock prevention using Petri nets and their unfoldings. *Int J Adv Manuf Tech* 1998; 14: 750-759.

96. Tricas F, Garca-Vallés F, Colom JM, et al. Using linear programming and the Petri net structure for deadlock prevention in sequential resource allocation systems. In: *Proceedings of the XIII Jornadas de Concurrencia y Sistemas Distribuidos*, Granada, 13-16 September 2005, pp.65-77. Madrid: Thomson Paraninfo.

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

98. Uzam M and Zhou MC. An iterative synthesis approach to Petri net-based deadlock prevention policy for flexible manufacturing systems. *IEEE T Syst Man Cy A* 2007; 37: 362-371.

99. Uzam M, Li ZW and Zhou MC. Identification and elimination of redundant control places in Petri net based liveness enforcing supervisors of FMS. *Int J Adv Manuf Tech* 2007; 35: 150-168.

100. Uzam M, Li ZW, Gelen G, et al. A divide-and-conquer-method for the synthesis of liveness enforcing supervisors for flexible manufacturing systems. *J Intell Manuf* 2016; 27: 1111-1129.

101. Uzam M, Li ZW and Abubakara US. Think globally, act locally approach for the synthesis of a liveness-enforcing supervisor of FMSs based on Petri nets. *Int J Prod Res* 2016; 54: 4634-4657.

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

103. Viswanadham N, Narahari Y and Johnson T. Deadlock prevention and deadlock avoidance in flexible manufacturing systems using Petri net models. *IEEE T Robotic Autom* 1991; 6: 713-723.

104. Wang Q, Li ZW, Wang AR, et al. A versatile supervisor with one monitor based on macro-tokens. *IMA J Math Control I* 2014; 31: 245-256.

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

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

107. Wu NQ, Zhou MC and Li ZW. Resource-oriented Petri net for deadlock avoidance in flexible assembly systems. *IEEE T Syst Man Cy A* 2008; 38: 56–69.

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

109. Xing KY, Hu BS and Chen HX. Deadlock avoidance policy for Petri-net modeling of flexible manufacturing systems with shared resources. *IEEE T Automat Contr* 1996; 41: 289–295.

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

111. Yan MM, Li ZW, Wei N, et al. A deadlock prevention policy for a class of Petri nets $S^3$PMR. *J Inf Sci Eng* 2009; 25: 167–183.

112. Ye JH, Li ZW and Chen XL. An algorithm for the minimum initial marking problem of a structurally live Petri net with inhibitor arcs. *IEEJ T Electr Electr* 2016; 11: 586–592.

113. Zhao M and Li ZW. On deadlock control for a class of generalised Petri net models of flexible manufacturing systems. *Int J Prod Res* 2009; 47: 6085–6107.

114. Zhong CF, Li ZW, Chen YF, et al. On nonexistence of a maximally permissive liveness-enforcing pure net supervisor. *IEEE T Syst Man Cy A* 2013; 43: 29–37.

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

116. Zhou MC and DiCeasre F. A hybrid methodology for synthesis of Petri net models for manufacturing systems. *IEEE T Robotic Autom* 1992; 8: 350–361.

117. Zhou MC, DiCeasre F and Rudolph D. Design and implementation of a Petri net based supervisor for a flexible manufacturing system. *Automatica* 1992; 28: 1199–1208.

118. Chen YF, Li ZW, Al-Ahmari A, et al. Deadlock recovery for flexible manufacturing systems modeled with Petri nets. *Inform Sciences* 2017; 381: 290–303.

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

120. Fanti MP, Maione G and Turchiano B. Digraph-theoretic approach for deadlock detection and recovery in flexible production systems. *Stud Inform Control* 1996; 5: 373–383.

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

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

123. Chen XL, Li ZW, Wu NQ, et al. Confusion avoidance for discrete event systems by P/E constraints and

supervisory control. *IMA J Math Control I* 2016; 33: 309–332.

124. Chen XL, Li ZW, Wu NQ, et al. Confusion diagnosis and avoidance of discrete event systems using supervisory control. *IEEJ T Electr Electr* 2016; 11: 49–62.

125. Fanti MP, Maione B and Turchiano B. Event control for deadlock avoidance in production systems with multiple capacity resources. *Stud Inform Control* 1998; 7: 343–364.

126. Hsieh FS and Chang SC. Dispatching-driven deadlock avoidance controller synthesis for flexible manufacturing systems. *IEEE T Robotic Autom* 1994; 10: 196–209.

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

128. Lawley MA, Reveliotis SA and Ferreira PM. A correct and scalable deadlock avoidance policy for flexible manufacturing systems. *IEEE T Robotic Autom* 1998; 14: 796–809.

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

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

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

132. Park J and Reveliotis SA. Algebraic synthesis of efficient deadlock avoidance policies for sequential resource allocation systems. *IEEE T Robotic Autom* 2000; 16: 190–195.

133. Reveliotis SA. Algebraic deadlock avoidance policies for sequential resource allocation systems. In: Lahmar M (ed.) *Facility logistics: approaches and solutions to next generation challenges*. New York: Taylor & Francis, 2007, pp.235–289.

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

135. Wysk RA, Yang NS and Joshi S. Resolution of deadlocks in flexible manufacturing systems: avoidance and recovery approaches. *J Manuf Syst* 1994; 13: 128–138.

136. Xing KY, Zhou MC, Liu HX, et al. Optimal Petri-net-based polynomial-complexity deadlock-avoidance policies for automated manufacturing systems. *IEEE T Syst Man Cy A* 2009; 39: 188–199.

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

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

139. Guo JW and Li ZW. A deadlock prevention approach for a class of timed Petri nets using elementary siphons. *Asian J Control* 2010; 12: 347–363.

140. Huang YS, Jeng MD, Xie XL, et al. A deadlock prevention policy for flexible manufacturing systems using siphons. In: *Proceedings of the IEEE international*
conference on robotics and automation, Seoul, Korea,
21–26 May 2001, pp.541–546. New York: IEEE.

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

142. Nasr EA, El-Tamimi AM, Al-Ahmari A, et al. Comparison and evaluation of deadlock prevention methods for different size automated manufacturing systems. *Math Probl Eng* 2015; 2015: 537893-1-537893-19.

143. Qin M, Li ZW, Zhou MC, et al. Deadlock prevention for a class of Petri nets with uncontrollable and unobservable transitions. *IEEE T Syst Man Cy A* 2012; 42: 727–738.

144. Tricas F, Garca-Vallés F, Colom JM, et al. An iterative method for deadlock prevention in FMSs. In: *Proceedings of the 5th workshop on discrete event systems* (eds R Boel and G Stremersch), Ghent, 21–23 August 2000, pp.139–148. USA: Springer.

145. Uzam M and Li Z. On an iterative deadlock prevention approach for automated manufacturing systems. *Int J Adv Manuf Tech* 2014; 74: 503–507.

146. Zhang ZM and Wu WM. Sequence control of essential siphons for deadlock prevention in Petri nets. *ACM T Embed Comput S* 2013; 12: 176–179.

147. Bai LP, Wu NQ, Li ZW, et al. Optimal one-wafer cyclic scheduling and buffer space configuration for single-arm multicluster tools with linear topology. *IEEE T Syst Man Cy A* 2016; 46: 1456–1467.

148. Wang X, Li Z and Wonham WM. Dynamic multiple-period reconfiguration of real-time scheduling based on timed des supervisory control. *IEEE T Ind Inform* 2016; 12: 101–111.

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

150. Yang F, Wu NQ, Qiao Y, et al. Scheduling of single-arm cluster tools for an atomic layer deposition process with residency time constraints. *IEEE T Syst Man Cy A*. Epub ahead of print 29 January 2016. DOI: 10.1109/TSMC.2015.2507140.

151. Zhang JF, Khalgui M, Li ZW, et al. R-TNCES: a novel formalism for reconfigurable discrete event control systems. *IEEE T Syst Man Cy A* 2013; 43: 757–772.

152. Zhang JF, Khalgui M, Li ZW, et al. Reconfigurable coordination of distributed discrete event control systems. *IEEE T Contr Syst T* 2015; 23: 323–330.

153. Chen W, Wu T, Li ZW, et al. Coevolution of aspirations and cooperation in spatial prisoner's dilemma game. *J Stat Mech: Theory E* 2015; 2015: P01032.

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

155. Giua A and Seatzu C. Modeling and supervisory control of railway networks using Petri nets. *IEEE T Autom Sci Eng* 2008; 5: 431–445.

156. Hou Y, Wu NQ and Li Z. A genetic algorithm approach to short-term scheduling of crude oil operations in refinery. *IEEJ T Electr Electr* 2016; 11: 593–603.

157. Hu HS, Zhou MC and Li ZW. Liveness enforcing supervision of video streaming systems using nonsequential Petri nets. *IEEE T Multimedia* 2009; 11: 1457–1465.

158. Hu HS and Li ZW. Liveness enforcing supervision in video streaming systems using siphons. *J Inf Sci Eng* 2009; 25: 1863–1864.

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

160. Hu HS, Li ZW and Al-Ahmari A. Reversed fuzzy Petri nets and their application for fault diagnosis. *Comput Ind Eng* 2011; 60: 505–510.

161. Jeng MD and Zhou MC. Engineering applications of Petri nets (special issue). *IEEE T Syst Man Cy C* 2007; 37: 442–443.

162. Odrey NG and Mejia G. A reconfigurable multi-agent system architecture for error recovery in production systems. *Robot Cim: Int Manuf* 2003; 19: 35–43.

163. Tong Y, Li ZW, Seatzu C, et al. Verification of state-based opacity using Petri nets. *IEEE T Automat Contr. Epub ahead of print* 24 October 2016. DOI: 10.1109/TAC.2016.2620429.

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

165. Wu NQ, Chu F, Chu CB, et al. Short-term schedulability analysis of multiple distiller crude oil operations in refinery with oil residency time constraint. *IEEE T Syst Man Cy C* 2009; 39: 1–16.

166. Wu NQ, Chu F, Chu CB, et al. Hybrid Petri net modeling and schedulability analysis of high fusion point oil transportation under tank grouping strategy for crude oil operations in refinery. *IEEE T Syst Man Cy C* 2010; 40: 159–175.

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

168. Wu NQ, Chu F, Chu CB, et al. Petri net modeling and cycle-time analysis of dual-arm cluster tools with wafer revisiting. *IEEE T Syst Man Cy A* 2013; 43: 196–207.

169. Wu NQ, Zhou MC and Li ZW. Short-term scheduling of crude-oil operations: enhancement of crude-oil operations scheduling using a Petri net-based control-theoretic approach. *IEEE Robot Autom Mag* 2015; 22: 64–76.

170. Wu NQ, Zhou MC, Bai LP, et al. Short-term scheduling of crude oil operations in refinery with high-fusion-point oil and two transportation pipelines. *Enterp Inform Syst* 2016; 10: 581–610.

171. Ye JH, Li ZW and Giua A. Decentralized supervision of Petri nets with a coordinator. *IEEE T Syst Man Cy A* 2015; 45: 955–966.

172. Badouel E and Darondeau P. Theory of regions. In: Reisig W and Rozenberg G (eds) *Lectures on Petri nets I: basic models*, vol. 1491 (Lecture notes in computer science). Berlin: Springer, 1998, pp.529–586.

173. Chen YF and Li ZW. Most permissive liveness-enforcing Petri net supervisors for flexible manufacturing systems. *Int J Prod Res* 2012; 50: 6357–6371.

174. Chen YF, Li ZW and Zhou MC. Behaviorally optimal and structurally simple liveness-enforcing supervisors of
flexible manufacturing systems. *IEEE T Syst Man Cy A* 2012; 42: 615–629.

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

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

177. Ghaffari A, Nidhal N and Xie XL. Design of a live and maximally permissive Petri net controller using the theory of regions. *IEEE T Robotic Autom* 2003; 19: 137–141.

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

179. McMillan K. Using unfoldings to avoid the state explosion problem in the verification of asynchronous circuits. In: Bochmann BV and Probst DK (eds) *Computer aided verification*, vol. 663 (Lecture notes in computer science). Berlin: Springer, 1992, pp.164–177.

180. Miner AS and Ciardo G. Efficient reachability set generation and storage using decision diagrams. In: Donatelli S and Kleijn HCM (eds) *Application and theory of Petri nets: proceedings of the 20th international conference*, vol. 1639 (Lecture notes in computer science). Berlin: Springer-Verlag, 1999, pp.6–25.

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

182. Wang SG, Zhou MC, Li ZW, et al. A new modified reachability tree approach and its applications to unbounded Petri nets. *IEEE T Syst Man Cy A* 2013; 43: 932–940.

183. Zhang XY, Li ZW, Zhong CF, et al. Reachability analysis of a class of Petri nets using place invariants and siphons. *Maejo Int J Sci Tech* 2013; 7: 278–290.

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

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

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

187. Barkaoui K and Peyre JF. Verification in concurrent programming with Petri nets structural techniques. In:

*Proceedings of the 3rd IEEE international high-assurance systems engineering symposium (HASE '98)*, Washington, DC, 13–14 November 1998, pp.124–133. New York: IEEE.

188. Barkaoui K and Peyre JF. Uniform verification of workflow soundness. *T I Meas Control* 2011; 33: 133–148.

189. Chao DY. Maximal class of weakly live nets with noneempty siphons. *IEEE T Syst Man Cy B* 2006; 36: 1332–1341.

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

191. Iordache MV and Antsaklis PJ. Supervision based on place invariants: a survey. *Discrete Event Dyn S* 2006; 16: 451–492.

192. Jeng MD and Xie XL. Analysis of modularly composed nets by siphons. *IEEE T Syst Man Cy A* 1999; 29: 399–406.

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

194. Jeng MD and Xie XL. Deadlock detection and prevention of automated manufacturing systems using Petri nets and siphons. In: Zhou MC and Fanti MP (eds) *Deadlock resolution in computer-integrated systems*. New York: Marcel Dekker, 2005, pp.233–281.

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

196. Li ZW, Zhou MC and Uzam M. Deadlock control policy for a class of Petri nets without complete siphon enumeration. *IET Control Theory A* 2007; 1: 1594–1605.

197. Liu D, Li X and Li ZW. FANM: extraction of a minimal siphon from a maxmal one, 2009, https://drive.google.com/open?id=0B0EMOSvVN2msQ1hBZHR4RGo2MkE

198. Liu D, Li ZW and Zhou MC. Liveness of an extended $S^3PR$. *Automatica* 2010; 46: 1008–1018.

199. Liu D, Li ZW and Zhou MC. A parameterized liveness and ratio-enforcing supervisor for a class of generalized Petri nets. *Automatica* 2013; 49: 3167–3179.

200. Liu D, Li ZW and Zhou MC. Hybrid liveness-enforcing policy for generalized Petri net models of flexible manufacturing systems. *IEEE T Syst Man Cy A* 2013; 43: 85–97.

201. Liu GY, Li ZW and Zhong CF. New controllability condition for siphons in a class of generalised Petri nets. *IET Control Theory A* 2010; 4: 854–864.

202. Reveliotis SA. On the siphon-based characterization of liveness in sequential resource allocation systems. In: Van der Aalst WMP and Best E (eds) *Applications and theory of Petri nets: proceedings of the 24th international conference*, vol. 2679 (Lecture notes in computer science). Berlin: Springer-Verlag, 2003, pp.241–255.
203. Xie XL and Jeng MD. ERCN-merged nets and their analysis using siphons. *IEEE T Robotic Autom* 1999; 15: 692–703.

204. Yamalidou E, Moody JO and Antsaklis PJ. Feedback control of Petri nets based on place invariants. *Automatica* 1996; 32: 15–28.

205. Zhong CF and Li ZW. A deadlock prevention approach for flexible manufacturing systems without complete siphon enumeration of their Petri net models. *Eng Comput* 2009; 25: 269–278.

206. Chen YF and Li ZW. On structural minimality of optimal supervisors for flexible manufacturing systems. *Automatica* 2012; 48: 2647–2656.

207. Chen YF, Li ZW and Al-Ahmari AM. Nonpure Petri net supervisors for optimal deadlock control of flexible manufacturing systems. *IEEE T Syst Man Cy A* 2013; 43: 252–265.

208. Chen YF, Li ZW and Barkaoui K. New Petri net structure and its application to optimal supervisory control: interval inhibitor arcs. *IEEE T Syst Man Cy A* 2014; 44: 1384–1400.

209. Chen YF, Li ZW and Zhou MC. Optimal supervisory control of flexible manufacturing systems by Petri nets: a set classification approach. *IEEE T Autom Sci Eng* 2014; 11: 549–563.

210. Chen YF, Li ZW and Barkaoui K. Maximally permissive liveness-enforcing supervisor with lowest implementation cost for flexible manufacturing systems. *Inform Sciences* 2014; 256: 74–90.

211. Chen YF, Li ZW, Barkaoui K, et al. On the enforcement of a class of nonlinear constraints on Petri nets. *Automatica* 2015; 55: 116–124.

212. Chen YF, Li ZW, Barkaoui K, et al. Compact supervisory control of discrete event systems by Petri nets with data inhibitor arcs. *IEEE T Syst Man Cy A* 2017; 47: 364–379.

213. Chen YF, Li ZW and Barkaoui K. Monitor design with multiple self-loops for maximally permissive supervisors. *ISA T* 2016; 61: 129–140.

214. Uzam M and Zhou MC. An improved iterative synthesis method for liveness enforcing supervisors of flexible manufacturing systems. *Int J Prod Res* 2006; 44: 1987–2030.

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

216. Li ZW and Zhou MC. Clarifications on the definitions of elementary siphons in Petri nets. *IEEE T Syst Man Cy A* 2006; 36: 1277–1279.

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

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

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

220. Chao DY and Li ZW. Structural conditions of systems of simple sequential processes with resources nets

without weakly dependent siphons. *IET Control Theory A* 2009; 3: 391–403.

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

222. Hou YF, Li ZW, Zhao M, et al. Extended elementary siphon-based deadlock prevention policy for a class of generalised Petri nets. *Int J Comp Integ M* 2014; 27: 85–102.

223. Hou YF, Li ZW, Al-Ahmari AM, et al. Extended elementary siphons and their application to liveness-enforcement of generalized Petri nets. *Asian J Control* 2014; 16: 1789–1810.

224. Hou YF, Li ZW, Zhao M, et al. Extraction of elementary siphons in a class of generalized Petri nets using graph theory. *Eng Computation* 2014; 31: 331–352.

225. Hou YF and Zhao M. Update to “Extraction of elementary siphons in a class of generalized Petri nets using graph theory.” *Eng Computation* 2016; 33: 331–352.

226. Hou YF, Zhao M, Liu D, et al. An efficient siphon-based deadlock prevention policy for a class of generalized Petri nets. *Discrete Dyn Nat Soc* 2016; 2016: 8219424-1-8219424-12.

227. Hu HS and Li ZW. An optimal-elementary-siphons-based iterative deadlock prevention policy for flexible manufacturing systems. *Int J Adv Manuf Tech* 2008; 38: 309–320.

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

229. Li ZW and Wei N. Deadlock control of flexible manufacturing systems via invariant-controlled elementary siphons of Petri nets. *Int J Adv Manuf Tech* 2007; 33: 24–35.

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

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

232. Qin M, Li ZW and Al-Ahmari AM. Elementary-siphon-based control policy for flexible manufacturing systems with partial observability and controllability of transitions. *Asian J Control* 2015; 17: 327–342.

233. Wang AR, Li ZW, Jian JY, et al. An effective algorithm to find elementary siphons in a class of Petri nets. *IEEE T Syst Man Cy A* 2009; 39: 912–923.

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

235. Ezpeleta J, Colom JM and Martinez J. A Petri net based deadlock prevention policy for flexible manufacturing systems. *IEEE T Robotic Autom* 1995; 11: 173–184.

236. Barkaoui K and Ben Abdallah I. Analysis of a resource allocation problem in FMS using structure theory of Petri nets. In: *Proceedings of the 1st international*
workshop on manufacturing and Petri nets, Osaka, Japan, 24-28 June 1996.

237. Barkaoui K, Couvreur JM and Klai K. On the equiva-
lence between liveness and deadlock-freeness in Petri
nets. In: Ciardo G and Darondeau P (eds) *Applications
and theory of Petri nets 2005*, vol. 3536 (Lecture notes in
computer science). Berlin; Heidelberg: Springer-Verlag,
2005, pp.90-107.

238. Chao DY. Max'-controlled siphons for liveness of S³PGR³. *IET Control Theory A* 2007; 1: 933-936.

239. Teruel E and Silva M. Structure theory of equal conflict systems. *Theor Comput Sci* 1996; 153: 271-300.

240. Zhong CF and Li ZW. Self-liveness of a class of Petri net models for flexible manufacturing systems. *IET Control Theory A* 2010; 4: 403–410.

241. Liu GY and Barkaoui K. Necessary and sufficient liveness condition of GS³PR Petri nets. *Int J Syst Sci* 2015; 46: 1147–1160.

242. Guan XX, Wu WH and Wang SG. New controllability condition for siphons in WS³PR nets. *Asian J Control* 2015; 17: 908–916.

243. Li ZW and Zhao M. On controllability of dependent siphons for deadlock prevention in generalized Petri nets. *IEEE T Syst Man Cy A* 2008; 38: 369–384.

244. Li ZW, Zhou MC and Jeng MD. A maximally permis-
sive deadlock prevention policy for FMS based on Petri
net siphon control and the theory of regions. *IEEE T
Autom Sci Eng* 2008; 5: 182–188.

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

246. Zhao M, Li ZW and Hu HS. Suboptimal liveness-
enforcing supervisor design for a class of generalised Petri
nets using partial siphon enumeration and mathematical
programming. *Int J Syst Sci* 2010; 41: 1013–1026.

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

248. Cordone R, Ferrarini L and Piroddi L. Enumeration algorithms for minimal siphons in Petri nets based on place constraints. *IEEE T Syst Man Cy A* 2005; 35: 844–854.

249. Chu F and Xie XL. Deadlock analysis of Petri nets using siphons and mathematical programming. *IEEE T Robotic Autom* 1997; 13: 793–804.

250. Huang YS, Jeng MD, Xie XL, et al. Deadlock prevention policy based on Petri nets and siphons. *Int J Prod Res* 2001; 39: 283–305.

251. Li SY, Li ZW and Hu HS. Siphon extraction for dead-
lock control in flexible manufacturing systems by using
Petri nets. *Int J Comp Integ M* 2011; 24: 710–725.

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

253. Barkaoui K, Dutheillet C, Haddad S, et al. An efficient algorithm for finding structural deadlocks in colored Petri nets. In: Marsan MA (ed.) *Application and theory of Petri nets*. Berlin; Heidelberg: Springer, 1993, pp.69–88.

254. Ezpeleta J, Couvreur JM and Silva M. A new technique for finding a generating family of siphons, traps and st-components: application to colored Petri nets. In: Rozenberg G (ed.) *Advances in Petri nets*, vol. 674 (Lecture notes in computer science). New York: Springer-Verlag, 1993, pp.126–147.

255. Lautenbach K. Linear algebraic calculation of deadlocks and traps. In: Voss K, Genrich HJ and Rozenberg G (eds) *Concurrency and nets*. New York: Springer-Verlag, 1987, pp.315–336.

256. Wang AR, Li ZW and Jia JY. Efficient computation of strict minimal siphons for a class of Petri nets models of automated manufacturing systems. *T I Meas Control* 2011; 32: 182-201.

257. Yamauchi M and Watanabe T. Algorithms for extract-
ing minimal siphons containing specified places in a gen-
eral Petri net. *IEICE T Fund Electr* 1999; 82: 2566-2575.

258. Chen YF and Liu GY. Computation of minimal siphons in Petri nets by using binary decision diagrams. *ACM T Embed Comput S* 2013; 12: 1-3.

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

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

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

262. Xing KY and Hu BS. Optimal liveness Petri net control-
lers with minimal structures for automated manufactur-
ing systems. In: *Proceedings of the IEEE international
conference on systems, man and cybernetics*, Waikoloa,
HI, 12 October 2005, pp.282–287. New York: IEEE.

263. Wang SG, Wang CY, Zhou MC, et al. A method to compute strict minimal siphons in a class of Petri nets based on loop resource subsets. *IEEE T Syst Man Cy A* 2012; 42: 226-237.

264. Liu M, Wang SG and Li ZW. Sufficient conditions for loop resource subsets to derive strict minimal siphons in class of Petri nets. *Electron Lett* 2014; 50: 25-27.

265. Esparza J and Silva M. Circuits, handles, bridges and nets. In: Rozenberg G (ed.) *Advances in Petri nets 1990*, vol. 483 (Lecture notes in computer science). Berlin: Springer-Verlag, 1990, pp.210-242.

266. Chao DY. An incremental approach to extracting minimal bad siphons. *J Inf Sci Eng* 2007; 23: 203-214.

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

268. Li ZW, Zhou MC and Wu NQ. A survey and comparison of Petri net-based deadlock prevention policies for flexible manufacturing systems. *IEEE T Syst Man Cy C* 2008; 38: 172–188.

269. Li ZW and Zhou MC. On siphon computation for dead-lock control in a class of Petri nets. *IEEE T Syst Man Cy A* 2008; 38: 667–679.
270. Li SY, Li ZW, Hu HS, et al. An extraction algorithm for a set of elementary siphons based on mixed-integer programming. *J Syst Sci Syst Eng* 2012; 21: 106-125.

271. Liu HX, Xing KY, Wang F, et al. A polynomial algorithm for computing elementary siphons in a class of Petri nets. *Asian J Control* 2012; 14: 1141-1149.

272. Wang F, Xing KY, Xu XP, et al. Research on finding elementary siphon in a class of Petri nets. In: Zhao M and Sha J (eds) *Communications in computer and information science*, vol. 289. Berlin: Springer, 2012, pp.435-442.

273. Xing KY, Zhou MC, Wang F, et al. Resource-transition circuits and siphons for deadlock control of automated manufacturing systems. *IEEE T Syst Man Cy A* 2011; 41: 74-84.

274. Chao DY and Liu GJ. A simple suboptimal siphon-based control model of a well-known S³PR. *Asian J Control* 2012; 14: 163-172.

275. Chao DY, Chen TY, Chen JT, et al. A best deadlock control for S³PMR to reach all states. *Asian J Control* 2012; 14: 278-283.

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

277. Liu HX, Xing KY, Wu WM, et al. Deadlock prevention for flexible manufacturing systems via controllable siphon basis of Petri nets. *IEEE T Syst Man Cy A* 2015; 45: 519-529.

278. Hong L, Hou YF, Jing JF, et al. Deadlock prevention policy with behavioral optimality or suboptimality achieved by the redundancy identification of constraints and the rearrangement of monitors. *Discrete Dyn Nat Soc* 2015; 2015: 579623-1-579623-15.

279. Zhao M, Hou YF and Liu D. Liveness-enforcing supervisors synthesis for a class of generalised Petri nets based on two-stage deadlock control and mathematical programming. *Int J Control* 2010; 83: 2053-2066.

280. Zhao M and Hou YF. An iterative method for synthesizing non-blocking supervisors for a class of generalized Petri nets using mathematical programming. *Discrete Event Dyn S* 2013; 23: 3-26.

281. Huang YS, Jeng MD, Xie XL, et al. Siphon-based deadlock prevention policy for flexible manufacturing systems. *IEEE T Syst Man Cy A* 2006; 36: 1248-1256.

282. Shih YY and Chao DY. Sequence of control in S³PMR. *Comput J* 2010; 53: 1691-1703.

283. Li SY, An A, Wang Y, et al. Design of liveness-enforcing supervisors with simpler structures for deadlock-free operations in flexible manufacturing systems using necessary siphons. *J Intell Manuf* 2013; 24: 1157-1173.

284. Li SY and Li ZW. Structure reduction of liveness-enforcing Petri nets using mixed integer programming. *Asian J Control* 2012; 14: 384-399.

285. Li SY, An AM, Wu HM, et al. Policy to cope with deadlocks and livelocks for flexible manufacturing systems using the max'-controlled new smart siphons. *IET Control Theory A* 2014; 8: 1607-1616.

286. Li ZW, Hu HS and Wang AR. Design of liveness-enforcing supervisors for flexible manufacturing systems using Petri nets. *IEEE T Syst Man Cy C* 2007; 37: 517-526.

287. Li ZW and Zhou MC. Two-stage method for synthesizing liveness-enforcing supervisors for flexible manufacturing systems using Petri nets. *IEEE T Ind Inform* 2006; 2: 313-325.

288. Liu GJ, Jiang CJ and Zhou MC. Improved sufficient condition for the controllability of dependent siphons in system of simple sequential processes with resources. *IET Control Theory A* 2011; 5: 1059-1068.

289. Hou YF, Li ZW and Al-Ahmari AM. Optimal controllability of 2-composed siphons in a class of Petri nets. *Electron Lett* 2012; 48: 1535-1537.

290. Hou YF, Li ZW, Hong L, et al. Optimal controllability of 3-composed siphons in a class of Petri nets. *Electron Lett* 2013; 49: 697-699.

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

292. Piroddi L, Cordone R and Fumagalli I. Selective siphon control for deadlock prevention in Petri nets. *IEEE T Syst Man Cy A* 2008; 38: 1337-1348.

293. Piroddi L, Cordone R and Fumagalli I. Combined siphon and marking generation for deadlock prevention in Petri nets. *IEEE T Syst Man Cy A* 2009; 39: 650-661.

294. Wang AR, Li ZW and Zhou MC. Iterative deadlock control by using Petri nets. *IEEE T Syst Man Cy C* 2012; 42: 1204-1218.

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

296. Chao DY, Chen JT and Uzam M. Reaching most states via refining controller regions for supervisors of two well-known S³PRs. *Int J Prod Res* 2013; 51: 4421-4430.

297. Huang YS and Pan YL. Enhancement of an efficient liveness-enforcing supervisor for flexible manufacture systems. *Int J Adv Manuf Tech* 2010; 48: 725-737.

298. Chao DY. Comments on "enhancement of an efficient liveness-enforcing supervisor for flexible manufacture systems." *Int J Adv Manuf Tech* 2012; 60: 625-629.

299. Chao DY and Wu KC. An integrated approach for supervisory control of a subclass of Petri nets. *T I Meas Control* 2013; 35: 117-130.

300. Chen YF and Li ZW. Design of a maximally permissive liveness-enforcing supervisor with a compressed supervisory structure for flexible manufacturing systems. *Automatica* 2011; 47: 1028-1034.

301. Chen YF, Li ZW, Khalgui M, et al. Design of a maximally permissive liveness-enforcing Petri net supervisor for flexible manufacturing systems. *IEEE T Autom Sci Eng* 2011; 8: 374-393.

302. Pan YL, Huang YS, Jeng MD, et al. Enhancement of an efficient control policy for FMSs using the theory of
regions and selective siphon method. *Int J Adv Manuf Tech* 2013; 66: 1805-1815.

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

304. Liu GY, Chao DY and Uzam M. A merging method for the siphon-based FMS maximally permissive controllers with simpler structures. *IMA J Math Control I* 2014; 31: 551–573.

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

306. Liu GY and Barkaoui K. A survey of siphons in Petri nets. *Inform Sciences* 2016; 363: 198–220.

307. Li ZW, Wu NQ and Zhou MC. Deadlock control of automated manufacturing systems based on Petri nets—a literature review. *IEEE T Syst Man Cy C* 2012; 42: 437–462.

308. Giua A, DiCesare F and Silva M. Generalized mutual exclusion constraints on nets with uncontrollable transitions. In: *Proceedings of the IEEE international conference on system, man, cybernetics*, Chicago, IL, 18–21 October 1992, pp.974–979. New York: IEEE.

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

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

311. Giua A and Seatzu C. Observability of place/transition nets. *IEEE T Automat Contr* 2002; 47: 1424–1437.

312. Giua A and Xie XL. Control of safe ordinary Petri nets using unfolding. *Discrete Event Dyn S* 2005; 15: 349–373.

313. Giua A and Seatzu C. A systems theory view of Petri nets. In: Bonivento C, Isidori A, Marconi L, et al. (eds) *Advances in control theory and applications*, vol. 353 (Lecture notes in control and information sciences). Berlin: Springer-Verlag, 2007, pp.99–127.

314. Lawley MA, Reveliotis SA and Ferreira PM. Flexible manufacturing system structural control and the neighborhood policy, part 2: generalization, optimization, and efficiency. *IIE Trans* 1997; 29: 889–899.

315. Lawley MA and Sulistyono W. Robust supervisory control policies for manufacturing systems with unreliable resources. *IEEE T Robotic Autom* 2002; 18: 346–359.

316. Li ZW and Liu D. A correct minimal siphons extraction algorithm from a maximal unmarked siphon of a Petri net. *Int J Prod Res* 2007; 45: 2161–2165.

317. Odrey NG and Mejía G. An augmented Petri net approach for error recovery in manufacturing systems control. *Robot Cim: Int Manuf* 2005; 21: 346–354.

318. Reveliotis SA. Liveness enforcing supervision for sequential resource allocation systems: state of the art and open issues. In: Caillaud B, Darondeau P, Lavagno L, et al. (eds) *Synthesis and control of discrete event systems*. Dordrecht: Kluwer Academic Publishers, 2002, pp.203–212.

319. Roszkowska E and Wojcik R. Problems of process flow feasibility in FAS. In: *CIM in process and manufacturing industries*. Oxford: Pergamon Press, 1993, pp.115–120.

320. Singhal M. Deadlock detection in distributed systems. *Computer* 1989; 22: 37–48.

321. Silva M and Valette R. Petri nets and flexible manufacturing. In: Rozenberg G (ed.) *Advances in Petri nets*, vol. 424 (Lecture notes in computer science). Heidelberg: Springer-Verlag, 1989, pp.374–417.

322. Silva M and Teruel E. A systems theory perspective of discrete event dynamic systems: the Petri net paradigm. In: *Proceedings of the symposium discrete events manufacturing systems*, Lille, 1996, pp.1–12.

323. Tong Y, Li ZW and Giua A. On the equivalence of observation structures for Petri net generators. *IEEE T Automat Contr* 2016; 61: 2448–2462.

324. Trappey AJC, Hsiao DW and Ma L. Maintenance chain integration using Petri-net enabled multiagent system modeling and implementation approach. *IEEE T Syst Man Cy C* 2011; 41: 306–315.

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

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

327. Wysk RA, Yang NS and Joshi S. Detection of deadlocks in flexible manufacturing cells. *IEEE T Robotic Autom* 1991; 7: 853–859.

328. Zhou MC and Fanti MP (eds). *Deadlock resolution in computer-integrated systems*. New York: Marcel Dekker, 2005.

329. Zhou MC and Li ZW. Special issue on “Petri nets for system control and automation.” *Asian J Control* 2010; 12: 237–239.

# Appendix I

## Basics of Petri nets

A generalized Petri net (structure) $N$ is a four-tuple $(P, T, F, W)$, where $P$ and $T$ are finite and nonempty sets, respectively. $P$ is a set of places and $T$ is a set of transitions with $P \cap T = \emptyset$. $F \subseteq (P \times T) \cup (T \times P)$ is called a flow relation of the net, represented by arcs with arrows from places to transitions or from transitions to places. $W: (P \times T) \cup (T \times P) \to \mathbb{N}$ is a mapping that assigns a weight to an arc: $W(x,y)>0$ if $(x,y) \in F$, and $W(x,y) = 0$ otherwise, where $x,y \in P \cup T$, and $\mathbb{N} = \{0, 1, 2, \dots\}$ is a set of non-negative integers. If $\forall(x,y) \in F$, $W(x,y) = 1$, $N$ is said to be ordinary. If $\forall x, y \in P \cup T$, $W(x,y)>0$ implies $W(y,x) = 0$, $N$ is called a pure (self-loop free) net.

A pure net $N = (P, T, F, W)$ can be alternatively represented by its incidence matrix $[N]$, that is, a $|P| \times |T|$
integer matrix with $[N](p, t) = W(t, p) - W(p, t)$. For a
place *p* (transition *t*), its incidence vector, a row (col-
umn) in $[N]$, is denoted by $[N](p, \cdot)$ ($[N](\cdot, t)$).

Let $x \in P \cup T$ be a node of net $N = (P, T, F, W)$. The
preset of $x$ is defined as $\bullet x = \{y \in P \cup T | (y, x) \in F\}$.
While the postset of $x$ is defined as
$x^\bullet = \{y \in P \cup T|(x,y) \in F\}$. This notation can be
extended to a set of nodes as follows: given $X \subseteq P \cup T$,
$\bullet X = \cup_{x \in X} \bullet x$ and $X^\bullet = \cup_{x \in X} x^\bullet$. A Petri net
$N = (P, T, F)$ is said to be a state machine if $\forall t \in T$,
$|\bullet t| = |t^\bullet| = 1$. $N = (P, T, F)$ is said to be a marked
graph if $\forall p \in P$, $|\bullet p| = |p^\bullet| = 1$. Given a place $p$,
$\max\{W(p, t)|t \in p^\bullet\}$ is denoted by $\max_{p^\bullet}$. A string $x_1, x_2,$
..., $x_n$ ($x_i \in P \cup T$) is called a path of $N$ if
$\forall i \in \{1, 2, \dots, n-1\}$, $x_i + 1 \in x_i^\bullet$. An elementary path
from $x_1$ to $x_n$ is a path whose nodes are all different
(except, perhaps, $x_1 = x_n$), which is denoted by
$EP(x_1, x_n)$. A path $x_1, x_2, \dots, x_n$ is called a circuit if it is
an elementary path with $x_1 = x_n$.

A marking *M* of a net *N* is a mapping from *P* to *N*.
*M*(*p*) denotes the number of tokens in place *p*. A place
*p* is marked at a marking *M* if *M*(*p*)>0. A subset *S* ⊆ *P*
is marked at *M* if at least one place in *S* is marked at
*M*. The sum of tokens in all places in *S* is denoted by
*M*(*S*), that is, *M*(*S*) = Σ*p*∈*S* *M*(*p*). (*N*, *M*₀) is called a
net system or marked net and *M*₀ is called an initial
marking of *N*. One usually describes markings and vec-
tors using a multiset or formal sum notation for econ-
omy of space.

A transition $t \in T$ is enabled at marking $M$ if $\forall p \in \bullet t$, $M(p) \ge W(p, t)$. This fact is denoted by $M[t]$. Firing $t$ yields a new marking $M'$ such that $\forall p \in P$, $M'(p) = M(p) - W(p, t) + W(t, p)$, denoted as $M[t]M'$. If there exist a sequence of transitions $\sigma = t_0t_1...t_n$ and markings $M_1, M_2, ..., $ and $M_n$ such that $M[t_0]M_1[t_1]M_2...M_n[t_n]M''$ holds, and marking $M''$ is said to be reachable from $M$. $R(N, M)$ denotes a set of all markings reachable from $M$ in $N$, called the reachability set of Petri net $N$ at initial marking $M$.

A transition $t \in T$ is live at $M_0$ if $\forall M \in R(N, M_0)$,
$\exists M' \in R(N, M)$, $M'[t]$. $N$ is dead at $M_0$ if $\exists t \in T$, $M_0[t]$ holds. ($N, M_0$) is deadlock-free if $\forall M \in R(N, M_0)$,
$\exists t \in T$, $M[t]$ holds. ($N, M_0$) is quasi-live if $\forall t \in T$,
$\exists M \in R(N, M_0)$, $M[t]$ holds. ($N, M_0$) is live if $\forall t \in T$, $t$ is live at $M_0$.

A P-vector is a column vector *I* : *P* → ℤ indexed by
*P* and a *T*-vector is a column vector *J* : *T* → ℤ indexed
by *T*, where *Z* is the set of integers. *P*-vector *I* is called
a *P*-invariant if *I* ≠ **0** and *I*<sup>*T*</sup>[*N*] = **0**<sup>*T*</sup>. *T*-vector *J* is
called a *T*-invariant if *J* ≠ **0** and [*N*] *J* = **0**. *P*-invariant
*I* is a *P*-semiflow if every element of *I* is non-negative.
||*I*|| = {*p*|*I*(*p*) ≠ **0**} is called the support of *I*. The fol-
lowing properties of *P*-invariant are known: any linear
combination of *P*-invariants of a net is still a *P*-invar-
iant. Furthermore, if *I* is a *P*-invariant of net *N* with an
initial marking *M*₀, then $\forall M \in R(N, M_0)$, $I^T M = I^T M_0$.

**Appendix 2**

Subclass of Petri nets

S<sup>3</sup>PR

**Definition 36.** A simple sequential process (S<sup>2</sup>P) is a Petri net $N = (P_A \cup \{p^0\}, T, F)$ where (1) $P_A \neq \emptyset$ is called a set of operation places; (2) $p^0 \notin P_A$ is called an idle process place; (3) *N* is a strongly connected state machine; and (4) every circuit of *N* contains place $p^0$.<sup>235</sup>

**Definition 37.** A simple sequential process with resources (S<sup>2</sup>PR) is a Petri net $N = (\{p^0\} \cup P_A \cup P_R, T, F)$ such that<sup>235</sup>

1. The subnet $\bar{N}$ generated by $X = \{p^0\} \cup P_A \cup T$ is an S<sup>2</sup>P;

2. $P_R \neq \emptyset$ is called a set of resource places with $(\{p^0\} \cup P_A) \cap P_R = \emptyset$;

3. $\forall p \in P_A, \quad \forall t \in \bullet p, \quad \forall t' \in p^*, \quad \exists r_p \in P_R, \bullet t \cap P_R = t^* \cap P_R = \{r_p\}$;

4. The following statements are verified: (1)

$\forall r \in P_R, \bullet \bullet r \cap P_A = r^{\bullet\bullet} \cap P_A \neq \emptyset$ and (2)

$\forall r \in P_R, \bullet r \cap r^\bullet = \emptyset$;

5. $^{\bullet\bullet}(p^0) \cap P_R = (p^0)^{\bullet\bullet} \cap P_R = \emptyset$.

**Definition 38.** A system of S<sup>2</sup>PR, called S<sup>3</sup>PR for short, is defined recursively as follows:<sup>235</sup>

1. An S<sup>2</sup>PR is an S<sup>3</sup>PR;

2. Let $N_i = (P_{A_i} \cup \{p_i^0\} \cup P_R, T_i, F_i)$, $i \in \{1, 2\}$, be two S<sup>3</sup>PR such that $(P_{A_1} \cup \{p_1^0\}) \cap (P_{A_2} \cup \{p_2^0\}) = \emptyset$, $P_{R_1} \cap P_{R_2} = P_C \neq \emptyset$, and $T_1 \cap T_2 = \emptyset$. Then, the net $N = (P_A \cup P_0 \cup P_R, T, F)$ resulting from the composition of $N_1$ and $N_2$ via $P_C$ defined as follows: (1) $P_A = P_{A_1} \cup P_{A_2}$, (2) $P_0 = \{p_1^0\} \cup \{p_2^0\}$, (3) $P_R = P_{R_1} \cup P_{R_2}$, (4) $T = T_1 \cup T_2$, and (5) $F = F_1 \cup F_2$ is also an S<sup>3</sup>PR.

WS³PR.

**Definition 39.** A simple sequential process with weighted resources allocation (WS<sup>2</sup>PR) is a generalized Petri net $N = (\{p^0\} \cup P_A \cup P_R, T, F, W)$ such that<sup>198</sup>

1. The subnet $\bar{N}$ generated by $X = P_A \cup \{p^0\} \cup T$ is an S<sup>2</sup>P;

2. $P_R \neq \emptyset$ and $(P_A \cup \{p^0\}) \cap P_R = \emptyset$;

3. $\forall p \in P_A, \forall t \in \bullet p, \forall t' \in p^*, \exists r_p \in P_R, \bullet t \cap P_R = t^* \cap P_R = \{r_p\}$;

4. The two following statements are verified: (1)

$\forall r \in P_R, \bullet \bullet r \cap P_A = r^{\bullet\bullet} \cap P_A \neq \emptyset$ and (2)

$\forall r \in P_R, \bullet r \cap r^\bullet = \emptyset$;

5. $^{\bullet\bullet}(p^0) \cap P_R = (p^0)^{\bullet\bullet} \cap P_R = \emptyset$;
6. The three following statements are verified: (1) $W(p, t) = 1$ and $W(t, p) = 1$, $\forall p \in P_A \cup \{p^0\}$, $\forall t \in T$, (2) $W(r, t) \ge 1$ and $W(t, r) \ge 1$, $\forall r \in P_R$, $\forall t \in T$, and (3) two arcs of any arc pair have the same weight.

**Definition 40.** Let $N = (\{p^0\} \cup P_A \cup P_R, T, F, W)$ be a WS$^2$PR.$^{198}$ An initial marking $M_0$ is called an acceptable initial marking for $N$ if (1) $M_0(p^0) \ge 1$; (2) $M_0(p) = 0$, $\forall p \in P_A$; and (3) $M_0(r) \ge W(r, t)$, $\forall r \in P_R$, $t \in r^\bullet$.

**Definition 41.** A system of WS$^2$PR, called WS$^3$PR for short, is defined recursively as follows:$^{198}$

1. A WS$^2$PR is a WS$^3$PR;

2. Let $N_i = (\{p_i^0\} \cup P_{A_i} \cup P_{R_i}, T_i, F_i, W_i)$, $i \in \{1, 2\}$, be two WS$^3$PR such that $(P_{A_1} \cup \{p_1^0\}) \cap (P_{A_2} \cup \{p_2^0\}) = \emptyset$, $P_{R_1} \cap P_{R_2} = P_C \ne \emptyset$, and $T_1 \cap T_2 = \emptyset$. Then, the net $N = (P_A \cup P_0 \cup P_R, T, F, W)$ resulting from the composition of $N_1$ and $N_2$ via $P_C$ (denoted $N_1 \circled{N_2}$) such that (1) $P = P_{A_1} \cup P_{A_2}$, (2) $P_0 = \{p_1^0\} \cup \{p_2^0\}$, (3) $P_R = P_{R_1} \cup P_{R_2}$, (4) $T = T_1 \cup T_2$, (5) $F = F_1 \cup F_2$, and (6) $W = W_1 \cup W_2$ is also a WS$^3$PR.

## GLS$^3$PR.

**Definition 42.** An S$^2$P $N = (P_A \cup \{p^0\}, T, F)$ is a linear simple sequential process (LS$^2$P) if $\forall p \in P_A$, $|p^\bullet| = 1$.

**Definition 43.** A generalized linear simple sequential process with resources (GLS$^2$PR) is a generalized Petri net $N = (P_A \cup \{p^0\} \cup P_R, T, F, W)$ such that

1. The subnet $\bar{N}$ generated by $X = P_A \cup \{p^0\} \cup T$ is an LS$^2$P;

2. $P_R \ne \emptyset$, $r \in P_R$ is called a resource place, and $(P_A \cup \{p^0\}) \cap P_R = \emptyset$;

3. $W = W_A \cup W_R$, where $W_A = ((P_A \cup \{p^0\}) \times T) \cup (T \times (P_A \cup \{p^0\})) \to \{0, 1\}$ and $W_R = (P_R \times T) \cup (T \times P_R) \to \mathbb{N}$;

4. $\forall r \in P_R$, there exists a unique minimal P-semi-flow $I_r \in \mathbb{N}^{|P|}$ such that $||I_r|| \cap P_R = \{r\}$, $\{p^0\} \cap ||I_r|| = \emptyset$, and $P_A \cap ||I_r|| \ne \emptyset$. Furthermore, (1) $I_r(r) = 1$; (2) $\forall p \in ||I_r|| \cap P_A$, $I_r(p) \ge 1$; if $\exists p' \in ||I_r|| \cap P_A$ such that $p^\bullet \cap \bullet p' \ne \emptyset$, then $I_r(p') = I_r(p)$;

5. Let $H(r) = ||I_r||||\{r\}$ and $P_A = \cup_{r \in P_R} H(r)$;

6. $\forall p \in H(r)$, $\forall t \in \bullet p$, if $\bullet t \cap H(r) = \emptyset$, then $W(r, t) \ge 1$. $\forall p \in H(r)$, $\forall t \in p^\bullet$, if $t^\bullet \cap H(r) = \emptyset$, then $W(r, t) \ge 1$.

**Definition 44.** A system of GLS$^2$PR, GLS$^3$PR for short, is recursively defined as follows:

1. A GLS$^2$PR is a GLS$^3$PR;

2. Let $N_i = (P_{A_i} \cup \{p_i^0\} \cup P_{R_i}, T_i, F_i, W_i)$, $i \in \{1, 2\}$, be two GLS$^3$PR with $(P_{A_1} \cup \{p_1^0\}) \cap (P_{A_2} \cup \{p_2^0\}) = \emptyset$, $P_{R_1} \cap P_{R_2} = P_C \ne \emptyset$, and $T_1 \cap T_2 = \emptyset$. Then, the net $N = (P_A \cup P_0 \cup P_R, T, F, W)$ resulting from the composition of $N_1$ and $N_2$ via $P_C$ such that (1) $P_A = P_{A_1} \cup P_{A_2}$, $P_0 = \{p_1^0\} \cup \{p_2^0\}$, and $P_R = P_{R_1} \cup P_{R_2}$, (2) $T = T_1 \cup T_2$, (3) $F = F_1 \cup F_2$, and (4) $W(x, y) = W_i(x, y)$ if $(x, y) \in F_i$, $i = 1, 2$ is also a GLS$^3$PR.

**Definition 45.** Let $N = (P_A \cup P_0 \cup P_R, T, F, W)$ be a GLS$^3$PR. $\forall r \in P_R$, $t \in \bullet r$, $t' \in r^\bullet$, if $\nexists t''$ such that $t' <_N t''$ and $t'' <_N t$, then $t'$ and $t$ are called a transition-pair (t-pair for short) of $r$, denoted as $\langle t', t \rangle$.

## S$^4$PR net

**Definition 46.** An S$^4$PR net is a generalized and self-loop free net $N = \bigcap_{i=1}^n N_i = (P, T, F, W)$, where

1. $N_i = (P_{A_i} \cup \{p_i^0\} \cup P_{R_i}, T_i, W_i)$, $i \in \mathbb{N}_n = \{1, \dots, n\}$.

2. $P = P_A \cup P_0 \cup P_R$ is a partition such that (1) $P_A = \bigcup_{i=1}^n P_{A_i}$ is called the set of operation places, where $P_{A_i} \ne \emptyset$ and $P_{A_i} \cap P_{A_j} = \emptyset$, $\forall i \ne j$ $(i, j \in \mathbb{N}_n)$; (2) $P_R = \{r_1, r_2, \dots, r_m | m \in \mathbb{N}^+\}$ is called the set of resource places; (3) $P_0 = \bigcup_{i=1}^n \{p_i^0\}$ is called the set of idle places; and (4) the output transitions of idle places are called source transitions.

3. $T = \bigcup_{i=1}^n T_i$ is called the set of transitions, where $\forall i, j \in \mathbb{N}_n$, $i \ne j$, $T_i \ne \emptyset$, and $T_i \cap T_j = \emptyset$.

4. $W = W_A \cup W_R$, where $W_A : ((P_A \cup P_0) \times T) \cup (T \times (P_A \cup P_0)) \to \{0, 1\}$ such that $\forall i, j \in \mathbb{N}_n$, $j \ne i$, $((P_{A_j} \cup \{p_j^0\}) \times T_i) \cup (T_i \times (P_{A_j} \cup \{p_j^0\})) \to \{0\}$, and $W_R : (P_R \times T) \cup (T \times P_R) \to \mathbb{N}$.

5. $\forall i \in \mathbb{N}_n$, the subset $\bar{N}_i$ generated by $P_{A_i} \cup \{p_i^0\} \cup T_i$ is a strongly connected state machine such that every cycle contains $p_i^0$.

6. P-invariant $I_r \in \mathbb{N}^{|P|}$ such that $\{r\} = ||I_r|| \cap P_R$, $P_0 \cap ||I_r|| = \emptyset$, $P_A \cap ||I_r|| \ne \emptyset$, and $I_r(r) = 1$, where $\mathbb{N}^{|P|}$ is a set of P-dimensional non-negative integer vectors. Furthermore, $P_A = \cup_{r \in P_R} (||I_r||||\{r\})$.

7. N is strongly connected.