# An Efficient Siphon-Based Deadlock Prevention Policy for a Class of Generalized Petri Nets

Authors: YiFan Hou; Mi Zhao; Ding Liu; Liang Hong
Journal: Discrete Dynamics in Nature and Society
 (2016)

---

## Abstract

We propose a new deadlock prevention policy for an important class of resource allocation systems (RASs) that appear in the modeling of flexible manufacturing systems (FMSs). The model of this class in terms of generalized Petri nets is, namely, S4PR. On the basis of recent structural analysis results related to the elementary siphons in generalized Petri nets on one hand and an efficient deadlock avoidance policy proposed for the class of conjunctive/disjunctive (C/D) RASs on the other hand, we show how one can generate monitors to be added to a net system such that all its strict minimal siphons are max′-controlled and no insufficiently marked siphon is generated. Thereby, a new, simple, and more permissive liveness-enforcing supervisor synthesis method for S4PR is established.


---

## Body

## 1. Introduction

A flexible manufacturing system (FMS) is characterized by flexibility, concurrent operations, and mainly automated elements, such as production controllers, machines, automated guided vehicles, and conveyors. In an FMS, raw parts are processed in a preestablished sequence to compete for a limited number of system resources. Deadlocks may occur when some processes keep waiting indefinitely for other processes to release resources, which can lead to catastrophic results in highly automated systems. One way of dealing with deadlock problems is to model an FMS with Petri nets [1]. Deadlock prevention is considered to be one of the most effective methods in deadlock control [2–9], which is usually achieved by either designing an effective system or using an off-line mechanism to control the requests for resources to ensure that deadlocks never occur in a system. To achieve this purpose, monitors and related arcs are added to the net system. One of the most interesting past developments is the use of structural objects to design liveness-enforcing Petri net supervisors [10–16]. Above all, the concept of elementary siphons provides an efficient and effective avenue for designing structurally simple supervisors [17, 18]. Elementary siphons have been maturely applied for a class of ordinary Petri nets such as S3PR [19], as well as some classes of generalized ones [16]. Since a siphon is a set of places that does not carry the weight information and the complex allocations of shared resources in a generalized Petri net, elementary siphons in [17] are not well suitable for generalized Petri nets. By fully investigating the topological structure and the requirements of multiple resource types of S4PR [20–22], the concept of augmented siphons is recently proposed in [23, 24]. Indeed, since the role of weight of arcs in determining the liveness of generalized Petri nets cannot be neglected, the notion of elementary siphons is redefined by considering augmented siphons, from which a compact and suitable set of elementary siphons can be obtained.For automated operation of modern technological systems that involve resource sharing, deadlock avoidance is also an essential control requirement. Broadly speaking, a deadlock avoidance policy tries to restrict the operation of an FMS to its reachable and safe sub-state-space. It is worth noting that we can translate the enforcement of liveness into a forbidden state problem in essence. Mutual exclusion constraints are a natural way of expressing the concurrent use of a finite number of resources, shared among different processes. In the framework of Petri nets formalisms, the work in [25] defines a generalized mutual exclusion constraint (GMEC) as a condition that limits a weighted sum of tokens contained in a subset of places. Based on this concept, the problem of forbidden state specification can be represented by GMECs. Many constraints that deal with exclusions between states and events can be transformed into the form of GMECs.The work in [26] generalizes the deadlock avoidance policy (DAP) of conjunctive/disjunctive resource upstream neighbourhood (C/D RUN) for resource allocation systems with multiple resource acquisitions and flexible routings, namely, S4PR, and this policy is of polynomial complexity. Motivated by the DAP of C/D RUN policy, a deadlock prevention policy is developed in this work by combining this method with the concept of augmented and elementary siphons in S4PR net. First, the concept of augmented siphons is proposed. Among augmented siphons, a set of improved elementary siphons can be derived. After that, we obtain a set of linear inequality constraints expressed by state vectors from elementary siphons. After modifying them by the proposed policy, we find a set of GMECs expressed by marking vectors. Then monitors are added to the plant model such that the elementary siphons in S4PR are all max′-controlled and no insufficiently marked siphon is generated due to the addition of the monitors. Finally, it can usually lead to a highly permissive liveness-enforcing supervisor by using the elementary siphon-based deadlock control policy.The rest of the paper is organized as follows. Section2 introduces the definition of S4PR. Section 3 elaborates the concept of augmented siphons and the method of deriving a set of elementary siphons in S4PR. The deadlock control policy for S4PR is proposed in Section 4, and a typical example is introduced to show the applicability and efficiency of the proposed method, while Section 5 concludes the paper. Some basics of Petri nets and elementary siphons used throughout this paper are listed in the Appendix.


## 2. S4PR

This section gives the definition of a class of generalized Petri nets, namely, S4PR [13, 26, 27]. Note that, in [26], an S4PR is called S3PGR2: the definition of these two subclasses of nets are in fact identical. S4PR nets include some well known classes of Petri nets such as S3PR, ES3PR, and WS3PR. Indeed, an S4PR concerns the modeling of concurrently cyclic sequential processes sharing common resources where an operation place can use simultaneously multiple resources of different types. Also sequential processes (state machines) mean that an operation place can be shared (flexible routings) but assembly and disassembly operations, for which synchronization is required, cannot be considered.Definition 1.
An S4PR net is a generalized and self-loop free net N=◯i=1nNi=(P,T,F,W), where(1)
Ni=(PAi∪{pi0}∪PRi,Ti,Wi), i∈Nn={1,…,n};(2)
P=PA∪P0∪PR is a partition such that (i) PA=⋃i=1n‍PAi is called the set of operation places, where PAi≠∅ and PAi∩PAj=∅, ∀i≠j (i,j∈Nn); (ii) PR={r1,r2,…,rm∣m∈N+} is called the set of resource places; (iii) P0=⋃i=1n‍{pi0} is called the set of idle places; and (iv) the output transitions of idle places are called source transitions;(3)
T=⋃i=1nTi is called the set of transitions, where ∀i,j∈Nn, i≠j, Ti≠∅, and Ti∩Tj=∅;(4)
W=WA∪WR, where WA:((PA∪P0)×T)∪(T×(PA∪P0))→{0,1} such that ∀i,j∈Nn, j≠i, ((PAj∪{pj0})×Ti)∪(Ti×(PAj∪{pj0}))→{0}, and WR:(PR×T)∪(T×PR)→N;(5)
∀i∈Nn, the subset N¯i generated by PAi∪{pi0}∪Ti is a strongly connected state machine such that every cycle contains pi0;(6)
∀r∈PR, there exists a unique minimal P-invariant Ir∈NP such that r=Ir∩PR, P0∩Ir=∅, PA∩Ir≠∅, and Ir(r)=1, where N|P| is a set of P-dimensional nonnegative integer vectors. Furthermore, PA=⋃r∈PR(Ir∖{r});(7)
N is strongly connected.In the special case where S4PR net corresponds to an asymmetric-choice (AC) net with non-blockingness (∀p∈P, mint∈p•{W(t,p)}≥mint∈p•{W(p,t)}) and homogeneous valuation (∀p∈P, ∀t,t′∈p•, W(p,t)=W(p,t′)), then it is well known that liveness property is equivalent to controlled-siphon property [2]. In this paper we extend this structural liveness characterization by dealing with S4PR nets in the general case.Definition 2.
LetN=(PA∪P0∪PR,T,F,W) be an S4PR net. An initial marking M0 is acceptable for N if (1)  ∀i∈Nn, M0(pi0)>0, (2)  ∀p∈PA, M0(p)=0, and (3)  ∀r∈PR, M0(r)>maxp∈IrIr(p).Example 3.
The net(N,M0) shown in Figure 1(a) is an S4PR (it is also an AC net but with no homogeneous valuation), where PA={p2–p6,p8–p12} is the set of operation places, P0={p1,p7} is the set of idle places, and PR={p13–p16} is the set of shared resource places. Each operation place in S4PR can simultaneously require multiple units of different resource types. For instance, operation place p2 needs one unit in place p13 and two in place p14 simultaneously for its operation. And the S4PR net model consists of two parallel sequential processes as shown in Figure 1(b), that is, process 1: PA1={P2–P6} and process 2: PA2={P8–P12}. These two parallel sequential processes compete for the limited resources represented by four resource places p13–p16. For example, the operation place p2 in process 1 requests one unit in resource place p13, whereas the resource units may be held by operation place p12 in process 2. The competition of the limited resources may lead to deadlocks of the net model, which is an undesired phenomenon and must be prevented by some effective instruments.
I
p
1
=
p
1
+
p
2
+
p
3
+
p
4
+
p
5
+
p
6 and Ip7=p7+p8+p9+p10+p11+p12 are the minimal P-semiflows associated with idle places p1 and p7. Ip13=p2+p3+2p12+p13, Ip14=p3+p4+p11+p14, Ip15=2p4+3p5+p9+p10+p15, and Ip16=p6+2p8+2p9+p16 are the minimal P-semiflows associated with resources p13, p14, p15, and p16, respectively. Let us consider the following acceptable initial marking M0=50p1+50p7+4p13+3p14+3p15+4p16. The net has seven strict minimal siphons (SMSs): S1={p3,p4,p12,p13,p14}, S2={p5,p11,p14,p15}, S3={p5,p9,p10,p15}, S4={p6,p9,p10,p15,p16}, S5={p5,p12,p13,p14,p15}, S6={p6,p9,p11,p14,p15,p16}, and S7={p6,p9,p12,p13,p14,p15,p16}. The strict minimal siphons are closely related to the deadlocks of a net model. Once an SMS is insufficiently marked in an S4PR, the net model will trap into deadlock.Figure 1
(a) An S4PR model (N,M0); (b) Processes 1 and 2.
(a)
(b)


## 3. Elementary Siphons in Generalized Petri Nets

### 3.1. Augmented and Elementary Siphons in S4PR

The concept of elementary siphons was originally proposed in [17] for a class of ordinary Petri nets, S3PR, and has been widely applied in ordinary Petri nets for designing liveness-enforcing supervisors. For more details, please refer to Appendix B: Elementary siphons. However, it still needs to be improved when a generalized Petri net is considered. In order to differentiate from the improved elementary siphons in this work, in what follows, let ΠEO (resp., ΠDO) denote elementary (resp., dependent) siphons defined in [17], which is called original elementary (resp., dependent) siphons in the rest of this paper.For the S4PR in Figure 1(a), by utilizing the concept of elementary siphons in [17], we have [λ] and [η] shown as follows:(1)λ=0011000000011100000010000010011000001000110000100000010011000011000010000001111000000100101001110000010010011111,(2)η=-101000000-1010-1-21200-1010000-202000000000-2-130-202000-1-1-11200-100010-1-2030-201100-1-1-1030-201001.It is easy to verify thatRank([η])=5, ηS5=ηS1+ηS2, and ηS7=ηS1+ηS6. It means that there are 5 original elementary siphons ΠEO={S1–S4,S6} and 2 original strongly dependent siphons ΠDO={S5,S7}.For an S4PR, the weight of an arc may be greater than one and an operation place can use simultaneously multiple types of resources. In this subsection, augmented siphons and improved elementary ones proposed for S4PR in [23] are introduced. Since the weights information of arcs is vital for the liveness of generalized Petri nets and the permissive behavior of their corresponding liveness-enforcing supervisors, the notion of elementary siphons is redefined for S4PR nets on the basis of augmented siphons. Consequently, the improved elementary siphons are compact and well suitable for S4PR, which can lead to a structurally simple controlled system.Definition 4 (see [23]).
LetN=(PA∪P0∪PR,T,F,W) be an S4PR. For r∈PR, H(r)={p∣p∈Ir∩PA}, the operation places that use r, is called the set of holders of r. Let place set hi(r)⊆H(r) be a subset of holders of r and ⋃‍hi(r)=H(r). If ∀p∈hi(r), ∃t∈(hi(r))• and p′∈hi(r), such that p•∩(p′∪r)•=t≠∅, where i∈N+. Then hi(r) is called a subset of sequential holders of r, denoted as his(r).Definition 5 (see [23]).
LetS be a siphon in an S4PR N=(PA∪P0∪PR,T,F,W) with S=SP∪SR, where SR=S∩PR and SP=S∖SR. A multiset S~=∑p∈S‍l(p)p is called an augmented version of S, where (1)  ∀p∈SR, l(p)=1 and (2)  ∀p∈SP: (a) p∈hs(r), if p•=t, t∈r•, then ∃A={pi∣pi≺Np,pi∈hs(r),pi∈SP}∪{p}, ∀p∈A, lrt(p)=W(t,r); and (b) lr(p)=∑t∈r•‍lrt(p), l(p)=∑r∈SR‍lr(p).Note that a siphonS and its augmented version S~ are in one-to-one correspondence. In an S4PR net, by considering the simultaneous requirements of multiple resources of different types by an operation place p, multiset S~ is introduced to represent the weighted relationship of p of holding and releasing resources in S. From Definition 5, S~=∑p∈S‍l(p)p, ∀p∈S, l(p) denotes the coefficient of the places in an augmented siphon S~, which means that the support set of S~ is S; that is, S~=S. ∀p∈SR, l(p) always equals one; and ∀p∈SP; the coefficient l(p) is determined by the number of resource units held by the operation place p.Example 6.
For the net in Figure1(a), take S2={p5,p11,p14,p15} as an example. For S2, note that H(p14)={p3,p4,p11} with h1s(p14)={p3,p4} and h2s(p14)={p11}; H(p15)={p4,p5,p9,p10} with h1s(p15)={p4,p5} and h2s(p15)={p9,p10}. Thus, we have the following: (1) For p14,p15∈PR, l(p14)=l(p15)=1 and (2) for p5∈PA, p5∈h1s(p15), and p5•=t5∈p15•, then lp15t5(p5)=W(t5,p15)=3. For p11∈PA, p11∈h2s(p14) and p11•=t11∈p14•, then lp14t11(p11)=W(t11,p14)=1. Hence, l(p5)=lp15(p5)=lp15t5(p5)=3 and l(p11)=lp14(p11)=lp14t11(p11)=1. As a result, we obtain S~2={3p5,p11,p14,p15}. Similarly, we have S~1={2p3,p4,2p12,p13,p14}, S~3={3p5,p9,p10,p15}, S~4={p6,3p9,p10,p15,p16}, S~5={3p5,2p12,p13,p14,p15}, S~6={p6,2p9,p11,p14,p15,p16}, and S~7={p6,2p9,2p12,p13,p14,p15,p16}.Definition 7 (see [23]).
LetS=SR∪SP be a siphon in an S4PR N and let S~ be its augmented version. [S]={p∣p∈IS∖S} is called the complementary set of siphon S and [S~]=IS-S~ is called the augmented complementary set of siphon S, where IS=∑r∈SR‍Ir.Example 8.
TakeS2 in the net N in Figure 1(a) as an example. Note that IS2=Ip14+Ip15=p3+3p4+3p5+p9+p10+p11+p14+p15. Thus, [S~2]=IS2-S~2=p3+3p4+p9+p10.Definition 9 (see [23]).
LetS⊆P be a subset of places in an S4PR N=(P,T,F,W). P-vector λS~ is called the augmented characteristic P-vector of S~ if ∀p∈S, λS~(p)=l(p); otherwise λS~(p)=0. ηS~=[N]TλS~  is called the augmented characteristic T-vector of S~.Definition 10 (see [23]).
LetN=(P,T,F,W) be an S4PR with |P|=m and |T|=n, and let Π={S1,S2,…,Sk} be a set of siphons of N, where m,n,k∈N+. Let λS~i(ηS~i) be the augmented characteristic P(T)-vector of siphon Si, i∈Nk. [λ~]k×m=[λS~1∣λS~2∣⋯∣λS~k]T and [η~]k×n=[λ~]k×m×[N]m×n=[ηS~1∣ηS~2∣⋯∣ηS~k]T are called the augmented characteristic P- and T-vector matrices of the siphons in N, respectively.Definition 11 (see [23]).
Let[η~] be augmented characteristic T-vector matrix of the set of siphons Π={S1,S2,…,Sk} in an S4PR N=(P,T,F,W):(1)
ΠEA={Sα,Sβ,…,Sγ} is called a set of augmented elementary siphons in N if ηS~α,ηS~β,…, and ηS~γ({α,β,…,γ}⊆Nk) is a linearly independent maximal set of matrix [η~].(2)
S∉ΠEA is called a strongly augmented dependent siphon if ηS~=∑Si∈ΠEAaiηS~i, where ai≥0; S∉ΠEA is called a weakly augmented dependent siphon if ∃A,B⊂ΠEA such that A≠∅, B≠∅, A∩B=∅, and ηS~=∑Si∈AaiηS~i-∑Sj∈BajηS~j, where ai,aj≥0.(3)
LetΠ (resp., ΠDA) be the set of strict minimal siphons (resp., augmented dependent siphons); we have Π=ΠEA∪ΠDA.Example 12.
The netN in Figure 1(a) has 7 strict minimal siphons; we have obtained augmented versions of all 7 SMS by Definition 5. Accordingly, the corresponding [λ~] and [η~] are shown as follows:(3)λ~=0021000000021100000030000010011000003000110000100000010031000011000030000002111000000100201001110000010020021111,η~=-110000000-1100-1-23000-1010000-220000000000-2-130-220000-1-1-13000-100100-1-2030-210100-1-1-1030-210010.
It is easy to verify thatRank([η~])=5, ηS~6=ηS~2+ηS~4-ηS~3, and ηS~7=ηS~4+ηS~5-ηS~3. It means that 5 augmented elementary siphons ΠEA={S1–S5} and 2 augmented dependent siphons ΠDA={S6,S7} can be obtained based on the concept of augmented siphons.Definition 13 (see [23]).
LetΠEO (resp., ΠDO) be a set of original elementary (resp., dependent) siphons and let ΠEA (resp., ΠDA) be a set of augmented elementary (resp., dependent) siphons in an S4PR N. ΠE=ΠEO∩ΠEA (resp., ΠD=ΠDO∪ΠDA) is called the set of elementary (resp., dependent) siphons of N.Lemma 14 (see [23]).
LetΠ be a set of SMS in an S4PR. Then Π=ΠE∪ΠD and ΠE∩ΠD=∅, where ΠE=ΠEO∩ΠEA and ΠD=ΠDO∪ΠDA.Example 15.
For the net in Figure1(a), we have ΠEO={S1–S4,S6}, ΠDO={S5,S7}, ΠEA={S1–S5}, and ΠDA={S6,S7}. By Definition 13, ΠE=ΠEO∩ΠEA={S1–S4} and ΠD=ΠDO∪ΠDA={S5–S7} can be obtained. It is obvious that ΠE∪ΠD=Π={S1–S7} is true. We have 4 elementary siphons and 3 dependent siphons finally.


### 3.2. Controllability of Siphons

The cs-property [2] is an important concept in liveness-enforcement for a generalized Petri net. The work in [2] provides the max-controlled condition of siphons that may overly restrict the permissive behavior of the supervisor. In order to reduce this restriction, a max′-controlled condition of siphons for generalized Petri net was first proposed in [28]. In this subsection, the formal definitions of max′-controlled siphons and the controllability of siphons are presented.Definition 16 (see [28]).
Let(N1,M01) be a subnet of (N,M0) with N1=(P1,T1,F1,W1) and N=(P,T,F,W). Place p∈P is called an input place of N1 if p∉P1 and ∃t∈T1, p∈t• (i.e., p∈T1•).LetN=(P,T,F,W) be a PN and let S⊆P be a subset of places. The subnet generated by X=S∪S• is denoted by NS, where NS=(S,S•,FX,WX). For convenience, the set of input places of NS is called the set of input places of S, denoted as PSin.For the net in Figure1(a), take S2={p5,p11,p14,p15} as an example. X=S2∪S2•; for the subnet NS2, we have PS2in={p2,p8}.Definition 17 (see [23]).
LetS be a siphon of a well initially marked S4PR (N,M0). S is said to be max′-marked at marking M∈R(N,M0) if (1)  ∃p∈SP such that M(p)≥1 or (2)  ∃p∈SR such that M(p)≥maxt∈(p•∩([S]∩PSin)•){W(p,t)}.Lemma 18 (see [23]).
LetS be a siphon in an S4PR (N,M0) and let M∈R(N,M0) be a marking. S is max′-marked at M if M(S)>ϖ(S), where ϖ(S)=∑p∈SR‍(maxt∈(p•∩([S]∩PSin)•){W(p,t)}-1).Definition 19.
LetS be a siphon of a well initially marked S4PR (N,M0). S is said to be max′-controlled if S is max′-marked at any reachable marking M, ∀M∈R(N,M0).Example 20.
For the net shown in Figure1(a), take S4={p6,p9,p10,p15,p16} as an example. Note that [S4]•={t4,t5,t8}; we have p15•∩([S4]∩PS4in)•={t8} and p16•∩([S4]∩PS4in)•={t5}. Thus ϖ(S4)=∑p∈S4R‍(maxt∈(p•∩([S]∩PSin)•){W(p,t)}-1)=0; that is, S4 is max′-controlled if ∀M∈R(N,M0), M(S4)>0.Theorem 21 (see [28]).
Let(N,M0) be a well initially marked S4PR. N is live if every siphon in N is max′-controlled.


## 3.1. Augmented and Elementary Siphons in S4PR

The concept of elementary siphons was originally proposed in [17] for a class of ordinary Petri nets, S3PR, and has been widely applied in ordinary Petri nets for designing liveness-enforcing supervisors. For more details, please refer to Appendix B: Elementary siphons. However, it still needs to be improved when a generalized Petri net is considered. In order to differentiate from the improved elementary siphons in this work, in what follows, let ΠEO (resp., ΠDO) denote elementary (resp., dependent) siphons defined in [17], which is called original elementary (resp., dependent) siphons in the rest of this paper.For the S4PR in Figure 1(a), by utilizing the concept of elementary siphons in [17], we have [λ] and [η] shown as follows:(1)λ=0011000000011100000010000010011000001000110000100000010011000011000010000001111000000100101001110000010010011111,(2)η=-101000000-1010-1-21200-1010000-202000000000-2-130-202000-1-1-11200-100010-1-2030-201100-1-1-1030-201001.It is easy to verify thatRank([η])=5, ηS5=ηS1+ηS2, and ηS7=ηS1+ηS6. It means that there are 5 original elementary siphons ΠEO={S1–S4,S6} and 2 original strongly dependent siphons ΠDO={S5,S7}.For an S4PR, the weight of an arc may be greater than one and an operation place can use simultaneously multiple types of resources. In this subsection, augmented siphons and improved elementary ones proposed for S4PR in [23] are introduced. Since the weights information of arcs is vital for the liveness of generalized Petri nets and the permissive behavior of their corresponding liveness-enforcing supervisors, the notion of elementary siphons is redefined for S4PR nets on the basis of augmented siphons. Consequently, the improved elementary siphons are compact and well suitable for S4PR, which can lead to a structurally simple controlled system.Definition 4 (see [23]).
LetN=(PA∪P0∪PR,T,F,W) be an S4PR. For r∈PR, H(r)={p∣p∈Ir∩PA}, the operation places that use r, is called the set of holders of r. Let place set hi(r)⊆H(r) be a subset of holders of r and ⋃‍hi(r)=H(r). If ∀p∈hi(r), ∃t∈(hi(r))• and p′∈hi(r), such that p•∩(p′∪r)•=t≠∅, where i∈N+. Then hi(r) is called a subset of sequential holders of r, denoted as his(r).Definition 5 (see [23]).
LetS be a siphon in an S4PR N=(PA∪P0∪PR,T,F,W) with S=SP∪SR, where SR=S∩PR and SP=S∖SR. A multiset S~=∑p∈S‍l(p)p is called an augmented version of S, where (1)  ∀p∈SR, l(p)=1 and (2)  ∀p∈SP: (a) p∈hs(r), if p•=t, t∈r•, then ∃A={pi∣pi≺Np,pi∈hs(r),pi∈SP}∪{p}, ∀p∈A, lrt(p)=W(t,r); and (b) lr(p)=∑t∈r•‍lrt(p), l(p)=∑r∈SR‍lr(p).Note that a siphonS and its augmented version S~ are in one-to-one correspondence. In an S4PR net, by considering the simultaneous requirements of multiple resources of different types by an operation place p, multiset S~ is introduced to represent the weighted relationship of p of holding and releasing resources in S. From Definition 5, S~=∑p∈S‍l(p)p, ∀p∈S, l(p) denotes the coefficient of the places in an augmented siphon S~, which means that the support set of S~ is S; that is, S~=S. ∀p∈SR, l(p) always equals one; and ∀p∈SP; the coefficient l(p) is determined by the number of resource units held by the operation place p.Example 6.
For the net in Figure1(a), take S2={p5,p11,p14,p15} as an example. For S2, note that H(p14)={p3,p4,p11} with h1s(p14)={p3,p4} and h2s(p14)={p11}; H(p15)={p4,p5,p9,p10} with h1s(p15)={p4,p5} and h2s(p15)={p9,p10}. Thus, we have the following: (1) For p14,p15∈PR, l(p14)=l(p15)=1 and (2) for p5∈PA, p5∈h1s(p15), and p5•=t5∈p15•, then lp15t5(p5)=W(t5,p15)=3. For p11∈PA, p11∈h2s(p14) and p11•=t11∈p14•, then lp14t11(p11)=W(t11,p14)=1. Hence, l(p5)=lp15(p5)=lp15t5(p5)=3 and l(p11)=lp14(p11)=lp14t11(p11)=1. As a result, we obtain S~2={3p5,p11,p14,p15}. Similarly, we have S~1={2p3,p4,2p12,p13,p14}, S~3={3p5,p9,p10,p15}, S~4={p6,3p9,p10,p15,p16}, S~5={3p5,2p12,p13,p14,p15}, S~6={p6,2p9,p11,p14,p15,p16}, and S~7={p6,2p9,2p12,p13,p14,p15,p16}.Definition 7 (see [23]).
LetS=SR∪SP be a siphon in an S4PR N and let S~ be its augmented version. [S]={p∣p∈IS∖S} is called the complementary set of siphon S and [S~]=IS-S~ is called the augmented complementary set of siphon S, where IS=∑r∈SR‍Ir.Example 8.
TakeS2 in the net N in Figure 1(a) as an example. Note that IS2=Ip14+Ip15=p3+3p4+3p5+p9+p10+p11+p14+p15. Thus, [S~2]=IS2-S~2=p3+3p4+p9+p10.Definition 9 (see [23]).
LetS⊆P be a subset of places in an S4PR N=(P,T,F,W). P-vector λS~ is called the augmented characteristic P-vector of S~ if ∀p∈S, λS~(p)=l(p); otherwise λS~(p)=0. ηS~=[N]TλS~  is called the augmented characteristic T-vector of S~.Definition 10 (see [23]).
LetN=(P,T,F,W) be an S4PR with |P|=m and |T|=n, and let Π={S1,S2,…,Sk} be a set of siphons of N, where m,n,k∈N+. Let λS~i(ηS~i) be the augmented characteristic P(T)-vector of siphon Si, i∈Nk. [λ~]k×m=[λS~1∣λS~2∣⋯∣λS~k]T and [η~]k×n=[λ~]k×m×[N]m×n=[ηS~1∣ηS~2∣⋯∣ηS~k]T are called the augmented characteristic P- and T-vector matrices of the siphons in N, respectively.Definition 11 (see [23]).
Let[η~] be augmented characteristic T-vector matrix of the set of siphons Π={S1,S2,…,Sk} in an S4PR N=(P,T,F,W):(1)
ΠEA={Sα,Sβ,…,Sγ} is called a set of augmented elementary siphons in N if ηS~α,ηS~β,…, and ηS~γ({α,β,…,γ}⊆Nk) is a linearly independent maximal set of matrix [η~].(2)
S∉ΠEA is called a strongly augmented dependent siphon if ηS~=∑Si∈ΠEAaiηS~i, where ai≥0; S∉ΠEA is called a weakly augmented dependent siphon if ∃A,B⊂ΠEA such that A≠∅, B≠∅, A∩B=∅, and ηS~=∑Si∈AaiηS~i-∑Sj∈BajηS~j, where ai,aj≥0.(3)
LetΠ (resp., ΠDA) be the set of strict minimal siphons (resp., augmented dependent siphons); we have Π=ΠEA∪ΠDA.Example 12.
The netN in Figure 1(a) has 7 strict minimal siphons; we have obtained augmented versions of all 7 SMS by Definition 5. Accordingly, the corresponding [λ~] and [η~] are shown as follows:(3)λ~=0021000000021100000030000010011000003000110000100000010031000011000030000002111000000100201001110000010020021111,η~=-110000000-1100-1-23000-1010000-220000000000-2-130-220000-1-1-13000-100100-1-2030-210100-1-1-1030-210010.
It is easy to verify thatRank([η~])=5, ηS~6=ηS~2+ηS~4-ηS~3, and ηS~7=ηS~4+ηS~5-ηS~3. It means that 5 augmented elementary siphons ΠEA={S1–S5} and 2 augmented dependent siphons ΠDA={S6,S7} can be obtained based on the concept of augmented siphons.Definition 13 (see [23]).
LetΠEO (resp., ΠDO) be a set of original elementary (resp., dependent) siphons and let ΠEA (resp., ΠDA) be a set of augmented elementary (resp., dependent) siphons in an S4PR N. ΠE=ΠEO∩ΠEA (resp., ΠD=ΠDO∪ΠDA) is called the set of elementary (resp., dependent) siphons of N.Lemma 14 (see [23]).
LetΠ be a set of SMS in an S4PR. Then Π=ΠE∪ΠD and ΠE∩ΠD=∅, where ΠE=ΠEO∩ΠEA and ΠD=ΠDO∪ΠDA.Example 15.
For the net in Figure1(a), we have ΠEO={S1–S4,S6}, ΠDO={S5,S7}, ΠEA={S1–S5}, and ΠDA={S6,S7}. By Definition 13, ΠE=ΠEO∩ΠEA={S1–S4} and ΠD=ΠDO∪ΠDA={S5–S7} can be obtained. It is obvious that ΠE∪ΠD=Π={S1–S7} is true. We have 4 elementary siphons and 3 dependent siphons finally.


## 3.2. Controllability of Siphons

The cs-property [2] is an important concept in liveness-enforcement for a generalized Petri net. The work in [2] provides the max-controlled condition of siphons that may overly restrict the permissive behavior of the supervisor. In order to reduce this restriction, a max′-controlled condition of siphons for generalized Petri net was first proposed in [28]. In this subsection, the formal definitions of max′-controlled siphons and the controllability of siphons are presented.Definition 16 (see [28]).
Let(N1,M01) be a subnet of (N,M0) with N1=(P1,T1,F1,W1) and N=(P,T,F,W). Place p∈P is called an input place of N1 if p∉P1 and ∃t∈T1, p∈t• (i.e., p∈T1•).LetN=(P,T,F,W) be a PN and let S⊆P be a subset of places. The subnet generated by X=S∪S• is denoted by NS, where NS=(S,S•,FX,WX). For convenience, the set of input places of NS is called the set of input places of S, denoted as PSin.For the net in Figure1(a), take S2={p5,p11,p14,p15} as an example. X=S2∪S2•; for the subnet NS2, we have PS2in={p2,p8}.Definition 17 (see [23]).
LetS be a siphon of a well initially marked S4PR (N,M0). S is said to be max′-marked at marking M∈R(N,M0) if (1)  ∃p∈SP such that M(p)≥1 or (2)  ∃p∈SR such that M(p)≥maxt∈(p•∩([S]∩PSin)•){W(p,t)}.Lemma 18 (see [23]).
LetS be a siphon in an S4PR (N,M0) and let M∈R(N,M0) be a marking. S is max′-marked at M if M(S)>ϖ(S), where ϖ(S)=∑p∈SR‍(maxt∈(p•∩([S]∩PSin)•){W(p,t)}-1).Definition 19.
LetS be a siphon of a well initially marked S4PR (N,M0). S is said to be max′-controlled if S is max′-marked at any reachable marking M, ∀M∈R(N,M0).Example 20.
For the net shown in Figure1(a), take S4={p6,p9,p10,p15,p16} as an example. Note that [S4]•={t4,t5,t8}; we have p15•∩([S4]∩PS4in)•={t8} and p16•∩([S4]∩PS4in)•={t5}. Thus ϖ(S4)=∑p∈S4R‍(maxt∈(p•∩([S]∩PSin)•){W(p,t)}-1)=0; that is, S4 is max′-controlled if ∀M∈R(N,M0), M(S4)>0.Theorem 21 (see [28]).
Let(N,M0) be a well initially marked S4PR. N is live if every siphon in N is max′-controlled.


## 4. Deadlock Prevention Policy for S4PR

An S4PR is a subclass of sequential resource allocation systems, which can be defined by a set of resource types PR={ri∣i∈Nm} and a set of job processes J={Jj∣j∈Nn}. Each resource ri is characterized by its capacity Cri, a finite positive integer, which stands for the maximum number of parts that can contemporaneously hold in ri. Each job type Jj is defined by a set of operations Jj={pj,k∣k∈Nlj,lj∈N+}, which is partially ordered through a set of precedence constraints. lj is the number of operation places in Jj.An algebraic polynomial deadlock avoidance policy is proposed by Park and Reveliotis [26] for the class of conjunctive/disjunctive RASs, which can be represented as a polynomially sized set of linear inequalities in the state vector:(4)Ap·q≤fp,where Ap is an incidence matrix. Each row of Ap can be associated with a subset of process stages JT(i)={JTjk∣A[i,(j,k)]=1}. A[i,·]·q counts the number of operations in state q, which execute stages in JT(i). An algebraic policy can be expressed by the condition that a state q is admissible if the number of operations in state q in process stage JT(i) does not exceed the policy-defined bound fp[i] for every process stage subset JT(i). Hence, the sequential resource allocation can be managed reasonably to guarantee the absence of deadlock states and processes by considering the RUN policy; that is, it requires that a state is admissible if the number of jobs in the upstream neighbourhood of each resource ri does not exceed its buffering capacity Cri.Definition 22 (see [25]).
Let(N,M0) be a net system with place set P. A GMEC (l,b) defines a set of legal markings: M(l,b)={M∈N|P|∣lTM≤b}, where l:P→N is a weighting vector, N|P| is a set of |P|-dimensional nonnegative integer vectors, and b∈N+={1,2,…} is called the constraint constant.The markings inN|P| that are not in M(l,b) are called forbidden markings with respect to constraint (l,b).Definition 23.
A set of GMEC(L,B) with L=[l1∣l2∣⋯∣lm] and B=(b1,b2,…,bm) defines a set of legal markings M(L,B)={M∈N|P|∣LTM≤B}=⋂i=1mM(li,bi).Definition 24.
Let(N,M0) be an S4PR with N=(P0∪PA∪PR,T,F,W) and let (l,b) be a GMEC; the monitor that enforces this constraint is a new place V to be added to the net system (N,M0). The resulting system is denoted as (Nc,M0c) with additional structure NV=(V,TV,FV,WV). We assume that there are no self-loop containing V in NV, and the initial marking M0 satisfies the constraint (l,b). Then NV will have incidence matrix: [NV]=-lT·[N]. FV can be uniquely determined by NV, and M0V(V)=b-lT.Definition 25.
Letr∈PR be a resource in N. H(r)={p∣p∈Ir∩PA} is the set of holders of r. Then ∀ri∈PR, ∑p∈{ri}∪H(ri)Iri(p)M(p)=M0(ri)≡Cri.Theorem 26.
Let(N,M0) be an S4PR with N=(PA∪P0∪PR,T,F,W) and let S be a strict minimal siphon of N. Siphon S is max′-marked if  ∀M∈R(N,M0), where M(S)≥ξS,  ξS>ϖ(S).Proof.
From Lemma18, S is max′-controlled if ∀M∈R(N,M0), M(S)>ϖ(S). As a result, it is easy to see if ∀M∈R(N,M0), M(S)≥ξS, where ξS>ϖ(S), S is max′-marked.In order to develop a liveness-enforcing supervisor for any given S4PR (N,M0)=(PA∪P0∪PR,T,F,W,M0), we can add a monitor for every elementary siphon S of N, which imposes the linear inequality:(5)λST·M≥ξS,where λS~ is an augmented characteristic vector of S~, M is the marking of net N, and ξS is a control depth variable such that ϖ(S)<ξS<M0(S). Since S~+[S~]=IS is the support of a P-invariant of N, we can conclude that M(S~)+M([S~])=M0(S~). From Definition 5, M0(S)=M0(S~)=M(S~)+M([S~])≥M(S)+M([S~]); that is, M0(S)-M([S~])≥M(S). As a result, the satisfaction of (5) can be ensured by satisfying the following inequality:(6)lpT·MS≤M0S-ξS,where ∀p∈[Sj], lp(p):=[S~j](p); otherwise lp(p):=0.According to Theorem26 and Definition 24, an elementary siphon S of an S4PR cannot be insufficiently marked after the addition of its corresponding monitor based on (6). The controllability of dependent siphons of N can be ensured by changing the control depth variables of its related elementary siphons. That is to say, all strict minimal siphons in N can be controlled. However, this can generate new insufficiently marked control-induced siphons. It is necessary for us to modify (6) to get some new constraints. Consequently, we can find that (6) is of the same type as (4). Hence the RUN policy [26] is considered, and the sequential resource allocation can be managed reasonably to guarantee the absence of deadlock states in the resulting net. In what follows, we utilize the polynomial-complexity DAP, which is an effective modification to C/D-RAS of the RUN DAP. Some notations are defined as follows.Definition 27.
Let(N,M0)=(PA∪P0∪PR,T,F,W,M0) be an S4PR. Suppose that a monitor Ri∗ is added for each elementary siphon Si with M0(Ri∗)=M0(Si)-ξSi; then Ri∗ is called a virtual resource of (N,M0).Definition27 defines the right-hand side of (6) by a virtual resource Ri∗. Each virtual resource relates to the resources included in its corresponding elementary siphon Si but does not exist in net N actually. The number of virtual resources is equal to that of elementary siphons. Virtual resources Ri∗ can serve as the temporary buffer in a system, and a state is admissible if the number of jobs in the upstream neighborhood of virtual resources Ri∗ (denoted as Pun(Ri∗)) does not exceed its buffering capacity M0(Ri∗), where Pun(Ri∗) is defined below.Definition 28.
LetR∗(pj,k) be the virtual resource that support the execution of operation pj,k and let EP(pj,k-q,pj,k) be an elementary path from pj,k-q to pj,k, where j∈Nn, k∈N|Jj|, q={1,2,…,k-1}, and J is the set of job processes in an S4PR. Pun(Ri∗)={pj,k∣Ri∗∈R∗(pj,k)}∪{pj,k-q∣Ri∗∈R∗(pj,k-q+1)∧O[R∗(pj,k-q)]≤O(Ri∗)} is called a set of job operations in the upstream neighborhood of resource place Ri∗, where O(·):R∗→Nm is any partial order defined on R∗, and i∈Nm.Definition 29.
Letoi≡O(Ri∗), O:R∗→Nm, be any partial order imposed on the virtual resource set R∗. Given an operation place p∈PA, let (7)ρpmax=max⁡oi∣api>0,i∈Nmif∃r∈R∗,p∈Hr0,otherwise,ρpmin=min⁡oi∣api>0,i∈Nmif∃r∈R∗,p∈Hr0,otherwise.
Also, letLp={q∣q∈p••∩PA∧ρqmax=minv∈p••∩PAρvmax}. By convention, Lp=∅ if p••∩P0≠∅. Then we have the following:(1)
The neighborhood setNp of p∈PA is defined recursively by the following equation:(8)Np=p∪q∣q∈⋃v∈LpNv∧ρpmin≤ρqmax.(2)
∀p∈PA, the adjusted resource allocation requirement a^p, is a m-dimensional nonnegative vector under partial order O(·) (resource ordering), which is given by the following expression:(9)a^pi=max⁡aqi∣q∈Np,ifoi≥ρpmin,i∈Nm0,otherwise.The policy-imposed constraint on the system operation is expressed by the requirement that no virtual resource is overallocated with respect to the adjusted operation requirements specified by (9). Actually, the set of linear inequality constraints of elementary siphons can be written in the following matrix form:(10)A^p·MP≤fp,where the column vector in A^p corresponding to an operation place p is a^p, vector MP is the restriction of marking M to operation places, and fp is the capacity vector of virtual resources; that is, fp[i]=M0(Ri∗), i∈Nm.Theorem 30.
Let(N,M0) be an S4PR and let (Nc,M0c) be the net resulting from adding monitors for elementary siphons only by Definition 24. (Nc,M0c) is a live controlled system if the following linear programming problem (LPP) has a feasible solution:(11)min∑Si∈ΠEξ^Sis.t.MS~j>M0Sj-ϖSj,∀Sj∈ΠD;A^p·MP≤fp-ξ^p,∀Si∈ΠE;IrTM=IrTM0=M0r,∀r∈PR,where ξ^p[i]+ϖ(Si)+1=ξSi and Ir is the P-invariant of r.Proof.
From Theorem26 and Definition 29, all elementary siphons are max′-controlled and no control-induced siphon is generated due to the addition of monitors. If the LPP has a feasible solution, it means that all dependent siphons are controlled by properly setting the control depth variables of the elementary siphons. As a result, all siphons are max′-controlled, which indicates that the controlled system (Nc,M0c) is live.Based on the discussion above, an algorithm of designing liveness-enforcing supervisor for S4PR based on improved elementary siphons is developed as in Algorithm 1.Algorithm 1:A deadlock prevention policy for S4PR based on improved elementary siphons.
Input: anS4PR (N,M0)=(PA∪P0∪PR,T,F,W,M0)
Output: a live controlled system(Nc,M0c)
(1) begin;
(2) Compute the set of SMS and their corresponding augmented siphons
(3) Find the set of elementary siphons ΠE=S1,S2,…,Sm, dependent siphons ΠD=Sm+1,…,Sn, and the set of virtual
resources R∗=R1∗,R2∗,…,Rm∗.
(4) for (j=1 to m) do
(5)  Compute the augmented complementary set of elementary siphons ΠEc≔[S~1],[S~2],…,[S~m],.
(6) end for
(7) Compute the set of linear inequality constraints expressed by state vectors from ΠEc according to  (4), where Ap is an incidence
an incidence matrix, binary matrix q restricts the PN marking vector to its components corresponding to places p∈PA, and
∀p∈[S~i], ap[i]≔[S~i](p), otherwise ap[i]≔0; fp[i]≔M0(Ri∗)=M0(Si)-ξSi, ξSi≔ϖ(Si)+1.
(8)  According to Definition 29, modify the matrix Ap to be matrix A^p.
(9)  Get the set of GMEC expressed by the marking vector according to  (10), that is, A^p⋅MP≤fp, where vector MP is the restriction
of marking M to operation places.
(10) if (ΠD≠∅) then
(11)  Find a set of ξS1,…,ξSm for elementary siphons by solving the LPP according to Theorem 30, where ξSi=ξ^p[i]+ϖ(Si)+1.
(12)  Get the adjusted GMEC A^p⋅MP≤f^p, where f^p[i]≔M0(Si)-ξSi.
(13) end if
(14) According to Definition 24 and the above set of GMEC, add the set of monitors for the corresponding ΠE to the net N, and the
obtained controlled system is denoted by (Nc,M0c).
(15) output (Nc,M0c)
(16) end.Theorem 31.
Let(N,M0) be a marked S4PR net and let Si be an elementary siphon of N. Si is max′-controlled after adding monitor Vi by Algorithm 1 (line (14)).Proof.
For Algorithm1 (line (14)), the monitor Vi adding for siphon Si is according to the Definition 24. And by Theorem 30, Si is max′-controlled by the control of Si.Theorem 32.
Let(N,M0) be a marked S4PR net and let ΠE be the set of elementary siphons of N. (Nc,M0c) is live if the set of monitors V is added by Algorithm 1.Proof.
This result follows from the fact that all siphons aremax′-controlled and no new non-max′-controlled siphon is generated in (Nc,M0c). By Theorem 21, (Nc,M0c) is live.For Algorithm1, a complete siphon enumeration is needed, and the time complexity of computing all SMSs in the worst case is exponential with the number of nodes of the net system, that is, O(a2n), where a is the number of arcs and n=|P|+|T| is the number of nodes of the nets. Therefore, the temporal complexity of Algorithm 1 is exponential with the scale of the Petri net model in the worst case.Example 33.
For the net in Figure1(a), we have four elementary siphons: S1={p3,p4,p12,p13,p14}, S2={p5,p11,p14,p15}, S3={p5,p9,p10,p15}, and S4={p6,p9,p10,p15,p16}. Their augmented versions are S~1={2p3,p4,2p12,p13,p14}, S~2={3p5,p11,p14,p15}, S~3={3p5,p9,p10,p15}, and S~4={p6,3p9,p10,p15,p16}. Moreover, their augmented complementary sets are as follows: [S~1]=p2+p11, [S~2]=p3+3p4+p9+p10, [S~3]=2p4, and [S~4]=2p4+3p5+2p8.
Then we can find the virtual resources for this system:M0(R1∗)=M0(S1)-2=5, M0(R2∗)=M0(S2)-1=5, M0(R3∗)=M0(S3)-1=2, and M0(R4∗)=M0(S4)-1=6. Therefore we obtain the initial set of linear inequality constraints expressed by state vector q: (12)1000000010013000110000200000000023020000·M≤5526,where M denotes the state vector defined by the operation place set, PA, expressed by the following vector:(13)Mp2Mp3⋯Mp6Mp8⋯Mp12T.
We consider the net in Figure1(a) under the virtual resource orders o1=O(R1∗)=2, o2=O(R2∗)=1, o3=O(R3∗)=1, and o4=O(R4∗)=1. From Definition 29, the neighborhood sets associated with the operation places p∈PA can be computed starting from the terminal operation places according to the partial order mentioned above.
For jobJ1={p2,p3,p4,p5,p6}, we haveρp6max=ρp6min=0, Lp6=∅ by (p6•)•∩P0≠∅, and Np6={p6};ρp5max=ρp5min=1, Lp5={p6}, and Np5={p5};ρp4max=ρp4min=1, Lp4={p5}, and Np4={p4,p5};ρp3max=ρp3min=1, Lp3={p4}, and Np3={p3,p4,p5};ρp2max=ρp2min=2, Lp2={p3}, and Np2={p2}.
For jobJ2={p8,p9,p10,p11,p12}, we haveρp12max=ρp12min=0, Lp12=∅, and Np12={p12};ρp11max=ρp11min=2, Lp11={p12}, and Np11={p11};ρp10max=ρp10min=1, Lp10={p11}, and Np10={p10,p11};ρp9max=ρp9min=1, Lp9={p10}, and Np9={p9,p10,p11};ρp8max=ρp8min=1, Lp8={p9}, and Np8={p8,p9,p10,p11}.
The adjusted virtual resource allocation requirements can be found as follows:a^p2=(1,0,0,0)T, a^p3=(0,3,2,3)T, a^p4=(0,3,2,3)T, a^p5=(0,0,0,3)T, a^p6=(0,0,0,0)T, a^p8=(1,1,0,2)T, a^p9=(1,1,0,0)T, a^p10=(1,1,0,0)T, a^p11=(1,0,0,0)T, and a^p12=(0,0,0,0)T. Thus the modified set of linear inequality constraints expressed by state vector A^p·MP≤fp is shown below:(14)1000011110033001110002200000000333020000·M≤5526.
According to Algorithm1, a feasible solution of the LPP according to Theorem 30, ξ^p[1]=ξ^p[2]=ξ^p[3]=ξ^p[4]=0, can be found and ξSi=ϖ(Si)+1. The adjusted GMEC is consistent with A^p·MP≤fp.
Four constraints need to add four monitorsV1, V2, V3, and V4 to the original net system. It can be indicated that all siphons are max′-controlled. The resulting net system (Nc,M0c) is live after adding four monitors as shown in Table 1.
The example is also studied by applying control polices reported in other papers. Table2 shows their comparison that is done in terms of resultant supervisor’s structural complexity and behavior permissiveness by using policies among [13, 23] and the proposed method.Table 1
MonitorsVi added for the net shown in Figure 1(a).
V
i
∙
V
i
V
i
∙
M
0
c
(
V
i
)
V
1
t
2, t11
t
1, t7
5
V
2
3
t
4, t10
3
t
2, t7
5
V
3
2
t
4
2
t
2
2
V
4
3
t
5, 2t8
3
t
2, 2t7
6Table 2
The performance comparison of supervisors for theS4PR in Figure 1(a) due to different policies.
Parameter
The method in [13]
The method in [23]
The proposed method
Permissive behavior
676
1723
2032
Number of monitors
5
4
4
Number of arcs
19
14
14Next, another S4PR example shown in Figure 2, which is not an AC net and without homogeneous valuation, is used to further illustrate the applicability and efficiency of the proposed method. By using Algorithm 1, the resulting live controlled system (Nc,M0c) with three monitors is shown in Table 3. Similarly, Table 4 shows the comparison of control performances among [13, 23] and the proposed method.Table 3
MonitorsVi added for the net shown in Figure 2.
V
i
∙
V
i
V
i
∙
M
0
c
(
V
i
)
V
1
3
t
3, 3t5,t11
3
t
1, t9
4
V
2
t
6, t11
t
5, t9
4
V
3
2
t
7, t10
2
t
6, t9
3Table 4
The performance comparison of supervisors for theS4PR in Figure 2 due to different policies.
Parameter
The method in [13]
The method in [23]
The proposed method
Permissive behavior
456
1158
1453
Number of monitors
5
3
3
Number of arcs
26
13
13Figure 2
An S4PR net system (N,M0).From this two case studies, it can be concluded that the liveness-enforcing supervisors synthesised by the proposed method are more structurally simple, and the final controlled net system can be obtained with more permissive behavior than some other elementary siphon-based approaches. Tracing to the essential reasons, the advantage of the proposed method is that the number of the elementary siphons explicitly controlled is more smaller by introducing the concept of augmented siphons, which can significantly reduce the structural complexity of the supervisors. Meanwhile, the constraints imposed by the monitors are less restrictive on account of combining the DAP of RUN policy with improved elementary siphons in an S4PR net.


## 5. Conclusion

This paper presents an elementary siphon-based deadlock prevention method for a class of generalized Petri nets, called S4PR that can deal with the modeling of concurrently cyclic sequential processes sharing common resources, where deadlocks are caused by the insufficiently marked siphons in their Petri net models. Generally, all insufficiently marked siphons are divided into elementary siphons and dependent ones by using the concept of augmented siphons in this work. From the former, a set of linear inequality constraints expressed by state vectors is obtained. Then we utilize a deadlock control method that combines the DAP of RUN policy with elementary siphons theory to ensure that all siphons are max′-controlled after adding a monitor for each elementary siphon. Consequently, the resulting net system by using the proposed method is live. The major advantage of this new Petri nets based deadlock prevention method as a liveness-enforcing supervisor synthesis is that a small number of monitors are added leading to a more permissive behavior. Since a complete siphon enumeration is computationally expensive, our future work will be guided to develop an approach without a complete siphon enumeration.



---

*Source: 8219424-2016-02-25.xml*