Intelligent Control and Automation, 2011, 2, 24-30
doi:10.4236/ica.2011.21003 Published Online February 2011 (http://www.SciRP.org/journal/ica)
α-Siphons of a Suboptimal Control Model of a
Subclass of Petri Nets*
Daniel Yuh Chao
Department of Management and Information Systems, National ChengChi University, Chinese Taipei
Received October 12, 2010; revised January 9, 2011; accepted January 10, 2011
Abstract
It has been a hot research topic to synthesize maximally permissive controllers with fewest monitors. So far,
all maximally permissive control models for a well-known benchmark are generalized Petri net, which com-
plicates the system. In addition, they all relied on time-consuming reachability analysis. Uzam and Zhou ap-
ply First-met-bad-marking (FBM) method to the benchmark to achieve a near maximal permissive control
policy with the advantage of no weighted control (WC) arcs. To improve the state of the art, it is interesting
to synthesize optimal controller with as few weighted arcs as possible since it is unclear how to optimize the
control for siphon involving WC arcs, This paper explores the condition to achieve optimal controller with-
out WC and defining a new type of siphon, called α-siphon. If the condition is not met, one can apply the
technique by Piroddi et al. to synthesize optimal controllers with WC.
Keywords: Petri Nets, Siphons, Controllability, FMS, S3PR
1. Introduction
Petri nets are a popular and powerful formalism to han-
dle deadlock problems in a resource allocation system
that is a technical abstraction of contemporary technical
systems. Petri nets (PN) have been employed to model
FMS to discover that insufficiently marked sip ho ns cau se
deadlocks [1-4].
Uzam and Zhou [5] propose an iterative approach. At
each iteration, a first-met bad marking (FBM) is singled
out from the reachability graph of a given Petri net
model. The objective is to prevent this marking from
being reached via a place invariant of the Petri net. A
well-established invariant-based control method is used
to derive a control place. This process is carried out until
the net model becomes live. The proposed method is
generally applicable, easy to use, effective and straight-
forward although its off-line computation is of exponen-
tial complexity. Two FMS are used to show its effec-
tiveness and applicab ility.
Although reaching 19 states fewer and 6 more moni-
tors than that the optimal one by Piroddi et al. for a
well-known benchmark, it does not employ weighted
control arcs and runs more efficiently. Piroddi et al. [6,7]
further increase it to the optimal 21581 states using the
set covering approach. However, the computation is ex-
pensive since the set-covering problem involves a large
system of inequalities with numerous (the number of
minimal siphons) variables. Redundant monitors must
be identified based on the method in [8] during each it-
eration, which entails exponential time complexity. Thus ,
the computational burden remains high and the method is
not applicable to large FMS.
Furthermore, unlike that in [5], quite a few control
arcs are weighted rendering the net to be a general Petri
net (GPN), which are much harder to analyze than the
ordinary control net by Uzam and Zhou. The traditional
MIP method cannot be extended to GPN. Hence, Piroddi
et al. transformed weighted arcs into ordinary ones,
which sometimes may cause unnecessary deadlocks as
mentioned in [5].
Our approach [9-11] categorizes SMS into basic,
compound, control and mixture siphons and derives their
controllability. If one carefully selects a sequence of
emptiable siphons to add monitors, the number of moni-
tors requir ed can be reduced. Mixtur e siphons containing
nonsharing resource places may be emptiable.
This method does not need to enumerate all minimal
siphons, nor to compute the reachability graph. Also no
iterations are required and no need to remove redundant
*This work was supported by the National Science Council under Gan
t
N
SC 99-2221-E-004-002.

D. Y. CHAO
25
monitors. Hence, the computation burden is much less
than those by Uzam et al. as well as Piroddi et al. In ad-
dition, no control arcs are weighted.
However, the resulting model of the well-known S3PR
reaches fewer (21363) states than the one (21562) in [5],
but with 11 monitors and 50 control arcs fewer than 19
monitors and 120 control arcs reported in [5].
Without the knowledge of unmarked siphons, Uzam
and Zhou employ a simplified generalized mutual-exclu-
sion constraints (GMECs) equivalently setting the num-
ber of tokens in the complementary set [S] of a siphon S
fewer than the initial number of tokens in S by one. This
excludes some live states where the number of tokens in
[S] may equal the initial number of tokens in S. The
GMEC by Piroddi et al. sets S to be always marked and
does not cause states to be lost.
To avoid WC while not losing live states, we need to
understand why the state loss occurs. An earlier paper
helps this by proposing one way to list all lost states and
estimating the number of lost states without reachability
analysis. Analyzing these state losses, one may find
some enhancements to reach more states.
However, it assumes that the siphon responsible for
the lost states is known a priori. This paper focuses on
developing theory to find the responsible siphon and the
conditions where weighted arcs cannot be avoided.
Without theory, one could waste much time failing to
reach more states. Thus, it is important to find out the
condition where more states can be reached. If no more
states can be reached, one simply stop and satisfy with
the suboptimal model obtained or to employ weighted
control arcs to reach more states following the approach
by Piroddi et al.
The rest of the paper is organized as follows. Section 2
presents the preliminaries about Petri nets and S3PR.
Section 3 presents different types of siphons: basic,
compound, mixture and α-siphons. It shows that only
α-siphons siphons are responsible for state losses. Sec-
tion 4 develops the condition for an α-siphon to incur
state losses. Finally, Section 5 concludes the paper.
2. Preliminaries
A Petri net (or Place/Transition net) is a 3-tuple N =
(P,T,F), where P = {p1, p2, ···, pa} is a set of places, T =
{t1,t2, ··· ,tb} a set of transitions, wi th P  T ≠  and P ∩
T =  and F a mapping from (P × T)  (T × P) to non-
negative integers indicating the weight of directed arcs
between places and transitions. In the special case that
the flow relation F maps onto {0, 1}; the Petri net is said
to be ordinary (otherwise, general). M0 : P → {0,1,2, ···}
denotes an initial marking whose ith component, M0(pi),
represents the number of tokens in place pi. N is strongly
connected iff there is a directed path from any node to
any other node. A nod e x in N = (P, T, F) is either a p 
P or a t  T. The post-set of node x is x● = {y  P  T
|F(x,y) > 0}, and its pre-set ●x = {y  P  T |F(y,x) >
0}.
ti is firable if each place pj in ●ti holds no less tokens
than the weight wj = F(pj,ti). Firing ti under M0 removes
wj tokens from pj and deposits wk = F(ti,pk) tokens into
each place pk in ti●; moving the system state from M0 to
M1. Repeating this process, it reaches M’ by firing a se-
quence
 of transitions. M’ is said to be reachable from
M0; i.e., M0 [
 > M’.
R(N, M0) is the set of markings reachable from M0. A
transition t  T is live under M0 if M  R(N, M0), M’
 R(N, M), t is firable under M’. A transition t  T is
dead under M0 if ∄M  R(N, M0) where t is firable. A
marking M  R(N, M0) is a (total) deadlock if t  T, t is
dead. A PN is live under M0 if t  T, t is live under M0.
For a Petri net (N, M0), a non-empty subset S(  ) of
places is called a siphon (trap) if ●S  S●( 
●  ●
 ), i.e.,
every transition having an output (input) place in S has
an input (output) place in S (
 ). If M0(S) =


0
pS
M
p


= 0,
S is called a empty siphon at M0. A minimal siphon does
not contain a siphon as a proper subset. It is called a
strict minimal siphon (SMS), if it does not contain a trap.
A P-vector (place vector) is a column vector Y : P →
Z indexed by P where Z is the set of integers. For econ-
omy of space, we use p  P L(p)p to denote a P-vector.
The incidence matrix of N is a matrix [N] : P × T → Z
indexed by P and T such th at [N]+ − [N]− where [N] + (p, t)
= F(t, p) and [N]−(p, t) = F(p, t). We denote column vec-
tors where every entry equals 0(1) by 0(1). YT and [N]T
are the transposed versions of a vector Y and a matrix [N],
respectively. Y is a P-invariant (place invariant) if and
only if Y ≠ 0 and YT [N] =0T hold. ||Y|| = {p  P | Y(p) ≠ 0}
is the support of Y. A minimal P-invariant does not con-
tain another P-invariant as a proper subset. If a siphon S
 ||Y||, then [S] = ||Y|| \ S is called the complementary
siphon of S and S  [S] is the support of a P-invariant.
Let YV be the minimal P-invariant associated with control
place V. H(V) = [V] = ||YV|| \ {V} is called the cont roller
(or disturbed) region or the set of holder places of V.
Definition 1 [1]: A simple sequential process (S2P) is a
net N = (P  {p0},T,F) where: 1) P  , p0 P (p0 is
called the process idle or initia l or final opera tion place);
2) N is strongly connected state machine (SM) and 3)
every circuit C of N contains the place p0.
Definition 2 [1]: A simple sequential process with re-
sources (S2PR), also called a working processes (WP), is
a net N = (P{p0}PR,T,F) so that 1) the subnet gener-
ated by X = P  {p0}  T is an S2P; 2) PR   and P 
{p0}  PR = ; 3) p  P, t 

p, t'  p

, rp  PR, ●t
 PR = t'●  PR = {rp}; 4) The two following statements
are verified: r  PR, a)

r  P =r

 P  ; b)

r 

D. Y. CHAO
26
r

= . 5)

(p0)  PR = (p0)

 PR = . p  P, p is
called an operation (or activity) place. r  P
R, r is
called a resource place. H(r) =

r  P denotes the set of
holders of r (operation places that use r).
 (r) = {r} 
H(r) denotes the union of H(r) and {r} and is the support
of a minimal P-invariant Yr that contains r.
Definition 3 [1]: A system of S2PR (S3PR) is defined
recursively as follows: 1) An S2PR is de fined a s an S 3PR;
2) Let Ni = (Pi  Pi0  PRi, Ti, Fi), i  {1,2} be two S3PR
so that (P1  P10)  (P2  P20) = . PR1  PR2 = PC (
) and T1  T2 = . The net N = (P  P0  PR,T,F) re-
sulting from the composition of N1 and N2 via PC (de-
noted by N1 o N2) defined as follows: 1) P = P1  P2; 2)
P0 = P10  P20; 3) PR = PR1  PR2; 4) T = T1  T2 and 5)
F = F1  F2 is also an S3PR. A directed circuit in N is
called a resource circuit, if p   , p  R. An elemen-
tary resource circuit is both a resource and an elemen-
tary circuit.
3. Types of SMS and Siphon Responsible for
Lost States
In [12-14], we show that SMS can be synthesized from
resource or core subnets. New types (such as control
siphons) of SMS can be synthesized from control subnets
formed by control places. If we add monitors to these
different types of siphons in a certain order, then some
siphons may be redundant.
We construct an SMS based on the concept of handles.
Roughly speaking, a “handle” is an alt ernat e di sj oi nt path
between two nodes. A PT-handle starts with a place and
ends with a transition while a TP-handle starts with a
transition and ends with a place. A core subnet can be
obtained from an elementary circuit, called core circuit,
by repeatedly adding handles.
The control place and arcs for siphon S, similar to re-
source places, form a number of elementary circuits.
Hence, there is an elementary circuit containing adjacent
control places, from which we can synthesize new prob-
lematic siphons.
Definition 4: An elementary resource circuit is called
a basic circuit, denoted by cb. The siphon constructed
from cb is called a basic siphon. A compound circuit c =
c1 o c2 o ··· cn-1 o cn is a circuit consisting of multiply
interconnected elementary circuits c1, c2, ···, cn such that
ci  ci+1 = {rpi}, rpi  R (i.e., ci and ci+1 intersects at a
resource place ri). rpi is called an inter-place. The SMS
synthesized from compound circuit c (resp. control, mix-
ture) using the Handle-Construction Procedure in [9] is
called an n-compound (resp. control, mixture) siphon S,
denoted by S = S1 o S2 o ··· Sn-1 o Sn. A siphon is called a
resource siphon if it does not contain any control place.
The set of compound, contro l, an d mixture sip hons fo r an
n-compound siphon is called a family set of siphons of
the n-compound siphon.
Definition 5: A mixture subnet is obtained by adding
non-resourceless TP-handles (containing no operation
places) upon a core circuit. A siphon synthesized from a
mixture subnet is called a mixture siphon. A full mixture
subnet is a mixture subnet upon which we can no longer
add non-resourceless TP-hand les to form a larger subnet
to synthesize a new siphon. Otherwise, it is called a par-
tial mixture (briefed as p-mix) subnet. A siphon synthe-
sized from a full (resp. partial) mixture subnet is called a
full (resp. partial) mixture siphon, briefed as f-mix (resp.
p-mix). RS (resp. CS) the set of resource (resp. control)
places in S. An α-siphon is a mixture one with non-
sharing places.
For the benchmark in Figure 1, S11 is an α-siphon
(where p43 is a non-sharing place.), whose core subnet
can be obtained by adding handles [t3 p40 t2 p30 t22 V11],
[t22 p42 t7 p30], [t20 p43 t19 p32 t5 V16], [V16 t8V11], [p32 t10
p43], [t10 V16], and [t8 p42] to Core circuit c = [V16 t3V11 t20
V16]. c1 = [p31 t3 p40 t2 p30 t22 p42 t21 p31], c2 = [p31 t20 p43
t19 p32 t5 p41 t4 p31], c1 ∩ c2 = {p31}, and M0 {rp = p31} = 1.
Table 1 lists the controlled model by Uzam et al. based
on the FBM approach.
In a mixture siphon, t  (S

/

S), |

t  S| > 1, and
each firing of t may remove multiple (say x) tokens from
S. This is the reason that the arc from VS to t must be
weighted by x if M0(VS) = M0(S) – 1. Thus, Mmax([S]) <
M0(S). In order to avoid empty S, one may set M0(VS) =
Mmax([S]) – 1 with ordinary control arcs.
On the other hand, for a siphon S where all
non-operation places are resource ones, t  (S

/

S), |

t
 S| = 1, each firing of t (called sink transitions of the
siphon) removes one token from VS and S respectively.
Thus, Mmax([S]) = M0(S). The same holds true for a con-
trol siphon.
Based on the above discussion, there will be no live
state losses if M0(VS) = M0(S) – 1 for the resource or con-
trol siphon since state losses occur iff there are live states
M such that M([S]) > M0(VS)(Theorem 1 in [11]). For a
mixture siphon to be emptiable, it must be an α-siphon.
Lemma 1: Let S be a siphon in the family set of a
2-compound siphon involved in some state loss, then S
must be an α-siphon.
Proof: The state loss would not occur if no monitor is
added to S. The thesis holds since there is no state loss if
S is not emptiable and a mixture siphon is emptiable and
needs a monitor iff it is an α-siphon.
Monitor V17 is added to S11 to make 19 live states to be
forbidden and lost via reachability analysis in [2]. In the
sequel, we will develop the condition for state loss for an
α-siphon since other siphons in the family set of a
2-compound do not incur state loss.

D. Y. CHAO
27
Figure 1. A well-known example of S3PR [1].
Table 1. Control model by Uzam et al. for the benchmark in Figur e 1.
i FBM(M0(Vi)) S

Vi V
i

1 p11 + 2p12(2) {p5, p8, p13, p23, p31, p41} t
14 t12
2 p4 + 2p12(2) S
1 t4, t14 t 3, t13
3 2p7 + p23(2) S
2 = {p4, p8, p11, p13, p24, p31, p42}t8, t21 t 7, t20
4 p8 + 2p22(2) S
3 = {p4, p9, p11, p13, p23, p31, p43}t9, t20 t 8, t19
5 2p7 + p22(3) S
4 = {p8, p23, V2, V3} t8, t20 t 7, t19
6 2p9 + p21(2) S
5 = {p6, p22, p32, p43} t10, t19 t 9, t18
7 2p7 + p8 + p21 + p22(4) S
6 = {p6, p23, V3, V8} t 9, t20 t 7, t18
8 p8 + p9 + p21 + p22(3) S
7 = {p6, p23, p31, p32, p43} t 10, t20 t 8, t18
9 2p7 + p9 + p21 + p22(4) S
6 t 8, t10, t20 t7, t9, t18
10 p5 + p11 + p12 + p21 + 2p22(5) S
8 = {p6, p13, p23, p31, p32, p41, p43}t5, t14, t20 t4,t12, t18
11 p2 + 2p3 + p7 + p23 + p24(5) S9 = {p4, p8, p11, p13, p25, p30, p31,
p40, p42} t3, t8, t22 t
1, t20
12 p4 + p5 + p12 + p21 + 2p22(5) S
8 t 5, t14, t20 t3, t13, t18
13 p5 + 2p7 + p11 + p12 + p21 + 2p22(6) S10 = {p6, p23, p31, p32, p41, V2} t
5, t8, t14, t20 t4, t7, t12, t18
14 p5 + p9 + p11 + p12 + p21 + 2p22(5) S8 t5, t10, t14, t20 t4, t9, t12, t18
15 p4 + p5 + 2p7 + p12 + p21 + p22(6) S10 t
5, t8, t14, t20 t3, t7, t13, t18
16 p4 + p5 + p9 + p12 + p21 + p22(5) S
8 t5, t10, t14, t20 t3, t8, t13, t18
17 p2 + 2p3 + p4 + p5 + p7 + p9 + p21 +
p22 + p24(9) S11 = {p6, p11, p13, p25, p30, p32, p40, p42, p43, V8, V11, V16} t5, t8, t10, t20, t22 t1, t9, t18, t21
18 p2 + 2p3 + 2p5 + p7 + p9 + p21 + p22
+ p23(9) S12 = {p6, p11, p13, p25, p30, p32,
p40, p43, V9, V11, V16} t3, t5, t8, t10, t21 t1, t4, t9, t18
19 p2 + p3 + 2p5 + p7 + p8 + p21 + p22
+ p24(9) S13 = {p6, p11, p13, p25, p30, p32, p40, p42, V4, V11, V16, V17} t3, t5, t9, t20, t22 t1, t4, t18, t21

D. Y. CHAO
28
4. Condition for State Loss
To have lost live states, some live states must be forbid-
den by the addition of Monitor VS. For states to be live,
the α-siphon S must be always marked. For states to be
forbidden, the total number of tokens in the complemen-
tary set [S] of S must remain at its maximum, which
cannot occur in the presence of ordinary VS. To turn M(S)
> 0 (live) from M’(S) = 0 while maintaining M([S]) =
M’([S]) = Mmax([S]) (forbidden), a token must be shifted
from one place in [S] to another place in [S]. In the se-
quel, we first deal with liveness of lost states followed by
two different cases where state loss may or may not oc-
cur.
Lemma 2: Let S be a siphon and M0(S) > 0. M(S) > 0
[M  R(N, M0)], if no transitions in S

\

S ever fire.
Proof: Only transitions in S

\

S can fire to move to-
kens from S into [S]. Transitions in S



S fire to move
tokens from S into S itself. Hence, the thesis holds.
Observation 1: Let S be an α-siphon, VS’  S, (S

\

S)
 VS’

 .
For the α-siphon S = S11 in Ta ble 1 , S



S = {t1, t18}.
If t1 and t18 never fire, tokens in S cannot leak out from S.
There are 3 VS’ in S11: V8, V11 and V16. S



S = {t1, t18}
and t1  V11

, t18  V16

.
Lemma 3: Let S be an α-siphon, VS’  S, M(VS’) = 0,
M  R(N, M0). Then no transitions in S

\

S can ever
fire.
Proof: The thesis holds since all transitions in VS’

are
disabled owing to th e fact that M(VS’) = 0 and (S

\

S) 
VS’

  by Observation 1.
The abov e lemmas h elp prov e that mar king s, where an
α-siphon is always marked, are live ones.
Definition 6: Let S be an α-siphon, R C = { r| r  PR, r 
R(cSi), cSi  CS} the set of resource places whose holder
places are also in that of control places of CS and
 = RC
\ {rp}, where rp is an inter-place. p’  H(rp) is called a
skew place.
Theorem 1: Let S be an α-siphon, Ma(p) = 0, Ma(H(p)
 [S]) = M0(p), p 
  CS, Ma  R(N, M0). Then all
transitions in S

are dead.
Proof: It is easy to see that Ma(S) = 0 and all transi-
tions in S

are dead.
For the example, CS = {V11, V16}, R(V16) = {p31, p32,
p41, p43}, RC = {p30, p31, p32, p40, p41, p42, p43}, rp = p31,
and
 = Rc \ {rp} = {p30, p32, p40, p41, p42, p43}, where p30,
p32, p40, p42, p43 are unmarked under FBM17. H(rp) = {p4,
p8, p23} and each place in H(rp) is a skew place. Ma(p2) =
Ma(H(p30)  [S]) = M0(p30) = 1, Ma(p3) = Ma(H(p40) 
[S]) = M0(p40) = 2, M(p21) = Ma(H(p32)  [S]) = M0(p32)
= 1, and Ma(p7) + Ma(p24) = Ma(H(p42)  [S]) = M0(p42) =
2, Ma(p9) + Ma(p22) = Ma(H(p43)  [S]) = M0(p43) = 2.
Note that Ma(p) = 0, p    CS. Thus all output tran-
sitions of p are dead . The rest transitions are outpu t tran-
sitions of p6, p25, p4, p8, p23, which are also dead since
Ma(p6) = Ma(p25) = Ma(p4) = Ma(p8) = Ma(p23) = 0.
We first add Monitor V’, so that H(V’) = . This in-
duces dead submarkings (markings restricted to opera-
tion places or ) FBMa = p2 + 2p3 + p4 + p5 + p7 + p9 +
p21 + p22 + p24, FBMb = p2 + 2p3 + 2p5 + p7 + p9 + p21 +
p22 + p23 and FBMc = p2 + 2p3 + 2p5 + p7 + p8 + p21 +
p22 + p24. Monitors V17, V18, and V
19 (called induced
monitors) are added with M0(V17) = 9, M0(V18) = 9 and
M0(V19) = 9, respectively.
Now Monitor V’ is redundant since its controller re-
gion ’ = {p2, p3, p5, p7, p9, p21, p22, p24} is a subset of
that ( = {p2, p3, p4, p5, p7, p9, p21, p22, p24}) for Monitor
V17 by the following lemma.
Lemma 4 [11]: Let S be an SMS.

1 
  [S]. M, M1
 R(N, M0) such that M(
 ) = M1( 
1) = Mmax([S]), V and
V1 are two monitors added such that M0(V) = M0(V1) =
Mmax([S]) – 1 and [V] =
 , [V1] = 
1. Then V1 is redun-
dant.

1 and
 are the controller regions for Monitors V and
V11, respectively. In the sequel, we will prove that when
the above redundant monitor appears, there are lost states,
and vice versa.
Theorem 2: Let S be an α-siphon,  the set of marked
operation places when S is unmarked under Ma, and VS
is the monitor added to S with M0(VS) = Mmax([S]) – 1
and H(VS) = . Let Mb(p) = Mb(r) = 1, Mb(p') = Ma(p') –
1, Mb(p*) = Ma(p*), p*  P \ ({p, p'}, Mb  R(N, M0),
where p  H(rp), rp an inter-place, r  (

(p

))   , p’ 
p

 H(r) and Ma was defined in Theorem 1. If H(r) 
[S] = {p’} and r  S, then 1) Mb is a nonlive marking. 2)
There are no lost live states iff Mb(p’) = 0 or M0(r) = 1
and a monitor has been added to prevent Mb from being
reached.
Proof: 1) Among all dead transitions under Ma, only
output transitions of r may be enabled under Mb since
Mb(r) = 1. If H(r)  [S] = {p'}, the only possibly enab led
transition is the output transition of both r and p. How-
ever, after t fires, it reaches Ma, which is a dead marking.
Thus, Mb is a nonlive marking. But t is disabled by VS
since t is the output transition of VS and M(VS) = 0
(Mb([S]) = Ma([S]) + Mb(p) – Ma(p) + Mb(p') – Ma(p') =
Ma([S]).
2) First assume a) Mb(p') > 0 (or M0(r) > 1). Let Mc 
R(N, M0) be such that Mc(p') = Mb(p') + 1 (i.e., adding a
token to p'), Mc(p^) = Mb(p^) – 1 (to ensure Mb(V) = 0),
Mc(p*) = Mb(p*), p*  P \ ({p', p^}, where p^  H(r')
 H(V), p'  H(V), V  S, r'  RC.
Then M(H(r')  S) = 1. By Lemma 2, S remains
marked since V is unmarked to disable its output transi-
tion in S

\

S. All markings M’ where S and all other
siphons in the final live controlled net are marked and

D. Y. CHAO
29
M’(p) = Mc(p), p  S  [S]. Such states are live as
proved below. Assume it necessarily evolves to a dead-
lock state M*, then there exist an unmarked sip hon und er
M*, which violates the fact that all siphons have been
controlled.
These states are lost since Mc() = Mb() = Mmax([VS]),
which are not reachable by Monitor VS with M0(VS) =
Mmax([S]) – 1.
Next consider b) M
b(p’) = 0 (or M 0(r) = 1).  now
does not include p'. One can no longer add a token to p'
to induce M(H(r')  S) = 1. Thus, there are no lost states.
a) and b) together prove the thesis.
For the example, p' = p5, r = p41 and H(r)  [S] = {p'}.
r has only one ou tput transition t4 with an input operation
place in . The above theorem indicates that when
M0(p41) = 1 (instead of 2 as in Figure 1), there will be no
loss of good states. VS is not redundant and cannot be
removed for the control.
a) If M0(p41) > 1, then there will be lost live states by
adding a token to p5 so that Mc(p5) = Mb(p5) + 1. These
live states must be such that Mc() = Mmax(), which are
not reachable by adding Monitor VS to make Mc() <
Mmax(). To make Mc() = Mmax (), it must be that
Mc(V) = Mb(V) = Ma(V) = 0, V = V16. This leads to
Mc([V16]) = M0(V16) = 5 or
Mc(p4) + Mc(p5) + Mc(p8) + Mc(p9)
+ Mc(p21) + Mc(p22) = M0(V16) = 5
Mc(p8) = 0, implies that
α = Mc(p4) + Mc(p5) + Mc(p9) + Mc(p21) + Mc(p22) = 5.
Note that the a ddition of Monitor V16 limits α to be
no more than 5. However, setting α to 5 may not
make S unmarked since some resource place (e.g., p43
or p32) in S may be marked (Mc(S) > 0) even though
V16 is unmarked. These states Mc(S) > 0 will stay so
(and are live as proved above) since transitions in S

\

S
are disabled by output control arcs from unmarked V16
and V11. Note that VS is redundant and can be removed.
b) If M0(p41) = 1, then there will be no lost live states
since Mc(p5) = 0 and the set c of marked operation
places under Mc does not include p5. One can no longer
add a token to c to make Mc(S) > 0. Hence, there are no
lost states.
Theorem 3: Let S be an α-siphon,  the set of marked
operation places when S is unmarked under Ma, and VS
is the monitor added to S with M0(VS) = Mma x () – 1 and
H(VS) = . Let Mb(p) = Mb(r) = 1, Mb(p*) = Ma(p*), p*
 P \ ({p, p'}, Mb  R(N, M0), Mb(p’) = 0, where p 
H(rp), r  (

(p

))   , p’  p

 H(r). If r  S and H(r)
 [S]  {p'}, then 1) Mb is a nonlive marking, and 2)
there are no lost live states by adding a monitor to pre-
vent Mb from bei ng rea ched.
Proof: 1) Similar to the proof of Theorem 2, the output
transition of both r and p is an output transition of VS
(Monitor for S) and disabled by unmarked VS. Other
output transitions t' of r are also disabled as explained
here. If H(r)  [S]  {p'}, then μ =
 \ {p'} (  = (H(r) 
[S])  {p}) is the complementary set of another siphon
S’; the output transition set of VS' (control place for S')
contains t'. Mb(p') = 0 implies that Mb(μ) = M0(rp) + M0(r)
– 1 = M0(r) = Mb(p) + Mb(H(r)  [S]) – Mb(p') = M0(S') –
1 = M0(VS’). Thus, VS' is unmarked to disable t' and all
possible enab led transitions are dead and Mb is a nonlive
marking, which needs a monitor V' with H(V') the set of
unmarked operation places in [S].
2) Note th at H(V') does not include p’ since Mb(p') = 0.
Since Mb(μ \ {p}) + Mb(r) = M0(r), there is no way to add
a token (to reach states forbidden by V') to enable some
transition. Hence, such states are nonlive and there are no
lost live states.
For the example, there are two possible pairs of (r p
p’): 1. (p43 p8 p9) and 2. (p42 p23 p24) for the above theo-
rem. For Case 1, H(r)  [S] = {p9, p22}  {p' = p9}. For
Case 2, H(r)  [S] = {p7, p24}  {p' = p24}. r has more
than one output transition (1. t9, t19 and 2. t7, t21) with an
input operation place in .

1 = (H(r)  [S])  {p} = {p8,
p9, p22}, μ1 =

1 \ {p'} = {p8, p22} = [S4],

2 = (H(r)  [S])
 {p} = {p7, p23, p24}, μ2 =

2 \ {p'} = {p7, p23} = [S3].
The corresponding submarkings are FBMb = p2 + 2p3
+ 2p5 + p7 + p9 + p21 + p22 + p23 (Mb(p') = Mb(p24) = 0)
and FBMc = p2 + 2p3 + 2p5 + p7 + p8 + p21 + p22 +
p24(Mb(p') = Mb(p9) = 0),respectively. Thus, the set b of
marked operation places under Mb does not include p'.
One cannot add a token to a skew place inb to make
Mc(S) > 0. Hence, there are no lost states. Combining
Theorem s 2 and 3, we have
Theorem 4: Let S be an α-siphon and all necessary
monitors have been added such that there are no marked
set  (  S) of operation places with dead output tran-
sitions. Then there are no lost live states iff Mb(p’) = 0
for all possible p' (defined in Theorem 3).
Proof: Theorems 2 and 3 consider all cases where H(r)
 [S] = {p'} and H(r)  [S]  {p'}, respectively. Theo-
rem 2 proves that there are no lost live states iff Mb(p') =
0 for all possible p'. Theorem 3 proves that if Mb(p') = 0,
then Mb is a nonliv e marking and there are no lost states.
Similar to the proof for Theorem 2, one can show that if
there are no lost states, then it must be that Mb(p') = 0.
All cases have been considered and the thesis is proved.
In summary, this section develops the condition for a
mixture siphon S to be involved in reaching fewer live
states. After adding a monitor VS to S, new unmarked
siphons may be generated. One new set of unmarked
operation places may cover H(VS) of VS, as a proper sub-
set. This makes VS redundant and some live states lost.
The physics of loss of live states is as follows. Adding
a token to a skew place (e.g., p4 in Figure 1) of S reduces

D. Y. CHAO
30
a token in the holder set (e.g., p21 in Figure 1) of a re-
source place r (e.g., p32 in Figure 1) in S, which in turn
induces a token in r, thus making S marked. Such a state
is live and forbidden since the total number of tokens in
 remains unchanged.
5. Conclusions
This paper enhances an earlier paper (which estimates
the number of lost states without reachability analysis)
and develops theory to identify the siphon responsible
for lost states for a well-known benchmark and explores
the condition to achieve optimal controller without WC.
If the condition is not met, one can apply the technique
by Piroddi et al. to synthesize optimal controllers with
WC. Future work should be addressed to synthesize
suboptimal controller without WC when the condition
cannot be satisfied.
6. References
[1] J. Ezpeleta, J. M. Colom and J. Martinez, “A Petri Net
Based Deadlock Prevention Policy for Flexible Manu-
facturing Systems,” IEEE Transactions on Robotics and
Automation, Vol. 11, No. 2, 1995, pp. 173-184. doi:
10.1109/70.370500
[2] Z. W. Li, J. Zhang and M. Zhao, “Liveness-Enforcing
Supervisor Design for a Class of Generalized Petri Net
Models of Flexible Manufacturing Systems,” IEE Pro-
ceedings Control Theory & Applications, Vol. 1, No. 4,
2007, pp. 955-967. doi:10.1049/iet-cta:20060218
[3] C.-F. Zhong and Z.-W. Li, “Design of Liveness-Enforcing
Supervisors via Transforming Plant Petri Net Models of
FMS,” Asian Journal of Control (Special Issue on the
Control of Discrete Event Systems), Vol. 6, No. 2, 2010,
pp. 270-280.
[4] J. W. Guo and Z. W. Li, “A Deadlock Prevention Ap-
proach for a Class of Timed Petri Nets Using Elementary
Siphons,” Asian Journal of Control, Vol. 12, No. 3, 2010,
pp. 347-363. doi:10.1002/asjc.189
[5] M. Uzam and M. C. Zhou, “An Iterative Synthesis Ap-
proach to Petri Net Based Deadlock Prevention Policy for
Flexible Manufacturing Systems,” IEEE Transactions on
Systems, Man, and Cybernetics A, Vol. 37, No. 3, 2007,
pp. 362-371. doi:10.1109/TSMCA.2007.893484
[6] L. Piroddi, R. Cordone and I. Fumagalli, “Selective Si-
phon Control for Deadlock Prevention in Petri Nets,”
IEEE Transactions on Systems, Man, and Cybernetics A,
Vol. 38, No. 6, 2008, pp. 1337-1348. doi:10.1109/TSM
CA.2008.2003535
[7] L. Piroddi, R. Cordone and I. Fumagalli, “Combined
Siphon and Marking Generation for Deadlock Prevention
in Petri Nets,” IEEE Transactions on Systems, Man, and
Cybernetics A, Vol. 39, No. 3, 2009, pp. 650-661.
doi:10.1109/TSMCA.2009.2013189
[8] M. Uzam, Z. W. Li and M. C. Zhou, “Identification and
Elimination of Redundant Control Places in Petri Net
Based Liveness Enforcing Supervisors of FMS,” Interna-
tional Journal of Advanced Manufacturing Technology,
Vol. 35, No. 1-2, 2007, pp. 150-168. doi:10.1007/s00170-
006-0701-5
[9] D. Y. Chao, “Improvement of Suboptimal Siphon- and
FBM-Based Control Model of a Well-Known S3PR,”
IEEE Transactions on Automation Science and Engi-
neering, Vol. 8, 2011.
[10] Y.-Y. Shih and D. Chao, “Sequence of Control in S3PMR,”
Computer Journal, Vol. 53, No. 10, 2010, pp. 1691-1703.
doi:10.1093/comjnl/bxp081
[11] D. Chao and G. J. Liu, “A Simple Suboptimal Siphon-
Based Control Model of a Well-Known S3PR,” Asian
Journal of Control, December 2010. http://onlinelibrary.
wiley.com/doi/10.1002/asjc.292/full
[12] D. Y. Chao, “Computation of Elementary Siphons in Petri
Nets for Deadlock Control,” Computer Journal, Vol. 49,
No. 4, 2006, pp. 470-479. doi:10.1093/comjnl/bxl019
[13] D. Y. Chao, “A Graphic-Algebraic Computation of Ele-
mentary Siphons of BS3PR,” Journal of Information Sci-
ence and Engineering, Vol. 23, No. 6, 2007, pp. 1817-1831.
[14] D. Y. Chao, “Incremental Approach to Computation of
Elementary Siphons for Arbitrary S3PR,” IEE Proceed-
ings Control Theory & Applications, Vol. 2, No. 2, 2007,
pp. 168-179.