Intelligent Control and Automation, 2011, 2, 310-319
doi:10.4236/ica.2011.24036 Published Online November 2011 (http://www.SciRP.org/journal/ica)
Controllability of Strongly and Weakly Dependent Siphons
under Disturbanceless Control*
Daniel Yuh Chao1, Kuo-Chiang Wu2, Jiun-Ting Chen1, Mike Y. J. Lee1,3
1Department of Management and Information Systems, National Chengchi University, Taipei, Chinese Taipei
2Department of Computer Science & Engineering, Tatung University, Taipei, Chinese Taipei
3Department of Business Administration, China University of Technology, Taipei, Chinese Taipei
Received April 1, 2011; revised June 28, 2011; accepted July 5, 2011
Abstract
Li and Zhou propose to add monitors Vs to elementary siphons S only while controlling the rest of dependent
siphons—important for large systems but far from being maximally permissive. The control policy for
weakly dependent siphons (WDS) is rather conservative due to some negative terms in the controllability.
We show that this is no longer true as can be shown that it has the same controllability as that for strongly
dependent siphons.
Keywords: Petri Nets, Siphons, Controllability, FMS, S3PR
1. Introduction
A flexible manufacturing systems (FMS) consists of
several concurrent processes competing for resources
such as machines, robotics, etc. to produce different
kinds of parts. Each process performs a sequence of
operations to manufacture a part of a product. Mutual
waiting for resources can bring the system into a
deadlock where no process can proceed.
An FMS can be modeled by a Petri net (PN). System
properties such as boundedness, liveness and reversi-
bility are fundamental for an FMS to operate in a sTable,
deadlock-free, and periodic fashion.
Deadlock prevention approaches [1-23] create the con-
trol policy in a static way by building a Petri net model
first and then adding necessary control to it such that the
controlled model is deadlock-free. Control places and rel-
ated arcs are often used to attain such purpose resulting in
less states reached, but the system runs quicker as a result
of no online computation.
A siphon (trap, respectively) is a set of places [where
tokens can leak out (inject in, respectively)] of a PN
modeling an FMS. Once the siphon has lost all its tokens,
output transitions of places in the siphon can never be
executed and the net is not live.
Control places and related arcs are often added upon
emptiable siphons to disallow them to become unmarked
(no tokens). This disturbs the original model and loses
some reachable good states; i.e., less permissive, impact-
ing the performance of the supervisor.
Ezpeleta et al. [11] propose adding a monitor upon
each problematic siphon for an S3PR which stands for
systems of simple sequential processes with resources.
This method generally requires adding too many moni-
tors due to the fact that there are too many emptiable
siphons. The iterative control method in [12] reduces the
number of monitors by finding all emptiable siphons in
each iteration step. The method becomes very difficult
and remains complex even for a moderate-size model.
Furthermore, Ezpeleta et al. [11] move all output
(called Type-2, or source) arcs of each monitor S to
the output (called source) transition of the entry (called
idle place) of input raw materials to limit their rate into
the system to avoid generaing new emptiable siphons,
called SMSless approach. This may overly constrain the
system to reach much fewer reachable states (6287, the
same as that by Li et al. [13,14] but with a lot more
control elements) than the maximal permissive one using
the region method by Uzam and Zhou [15].
V
It is impractical to add a monitor to each emptiable
siphon for large systems since the number of emptiable
siphons or control elements grows quickly with respect
to the size of a Petri net. Li and Zhou [13,14,16,17]
tackle this problem by classifying siphons into elemen-
tary and dependent ones.
*This work was supported by the National Science Council under Gant
N
SC 99-2221-E-004-002.

D. Y. CHAO ET AL.311
By adding monitors to only elementary siphons, Li
and Zhou [13] greatly reduce the number of control
nodes and arcs, essential for large systems. Some of the
rest of emptiable (called dependent) siphons may already
be controlled depending on the controllability.
Otherwise, the control depth variable may need to be
increased to avoid the siphon unmarked and reach fewer
states. The control policy for weakly dependent siphons
is rather conservative [13] (such that fewer states are
reached) by ignoring some negative terms in the
controllability.
The control place and arcs for siphon , similar to
resource places, form a number of elementary circuits.
Hence, there is an elementary circuit containing adjacent
control places, from which we can synthesize new
problematic siphons. To avoid such, output arcs of a
control place are moved from sink transitions of the
siphon to source transitions of the processes. As a
result, the region
S
S
A
(called controller region) covered
by control arcs is larger than the region (called the
complementary set of ) to trap tokens from . The
disturbed region becomes larger after the movement of
output arcs. This loses more states due to the presence of
control places and arcs, which disturbs the markings of
the original model.
B
S S
We [1-4,6,7] show that elementary (resp. strongly
dependent) siphons in an S3PR (systems of simple
sequential processes with resources) may be synthesized
from elementary (resp. compound) resource circuits.
There is no need to compute the basis for the set of
elementary siphons from the vector space containing all
characteristic T-vectors. Furthermore, we add monitors
for different types of siphons in some sequence to avoid
redundant monitors and losing live states.
It is unclear whether the same advantage can be
extended to weakly dependent siphons. We don’t know
from what circuits can we synthesize a weakly dependent
siphon , and the condition that is controlled. This
paper shows that weakly dependent siphons have a
similar controllability to that for strongly dependent
siphons under the disturbanceless control policy even
though Li et al. prove that the policy for weakly
dependent siphon is more conservative than strongly
dependent siphons.
S S
The rest of the paper is organized as follows: Section 2
and 3 presents the basis to understand the paper. Section
4 reviews the theory on controllability of strongly
dependent siphons in Li and Zhou [13,14]. Section 5
develops the theory to weakly dependent siphons based
on Proposition 1. It is interesting to observe that weakly
and strongly dependent siphons have the same controll-
ability for compound siphons. Section 6 concludes the
paper.
2. Preliminaries
Please refer to [1] for terms related to Petri nets. We now
define characteristic T-vectors, elementary and depend-
ent siphons.
Definition 1. [13,14]: Let be a subset of
places of N. P-vector
P


is called the characteristic
P-vector of

iff

, 1pp 


 ; otherwise


0p 


.

is called the characteristic T-vector of

, if , where [N] is the incidence matrix.
=
TT

[N]
Physically, the firing of a transition t where


0,t  


=0t  , and


0t 

increases, maintains and de-
creases the number of tokens in , respectively S
Definition 2. [13,14]: Let N = (P, T, F) be a net with
|P| = m, which has k siphons 1, , ···, , , S2
Sk Smk

IN,
where IN = {0, 1, 2, ···}. Define

12
T
 

k
km
and
 

12 .
T

k
km









(resp.



) is called
the characteristic P(resp. T)-vector matrix



(resp.



)
of the siphons in N. Let S


, S


, ···, and S


(

,

,

 1, 2, ···, k) be a linear independent maximal set of
matrix



. Then


,
ES,,SS


is called a set of
elementary siphons.
 
E
S

 is called a strongly depen-
dent siphon if Si
SiE
aiS





where . 0
i
a
E
S


is called a weakly dependent siphon if non-empty A,
B

E
 , such that AB

 and
=
SiSi
i
SA SB
ii
aa
S
i



 

 where . 0
i
a
In [13,14], a strongly dependent siphon is also called a
strict redundant one. Li and Zhou propose to find
elementary siphons by constructing the characteristic
P-vector (resp. T-vector)-vector matrix [λ] (resp. [η]) of
the siphons in N followed by finding linearly inde-
pendent vectors in [λ] (resp. [η]) The siphons corre-
sponding to these independent vectors are the elementary
siphons in the net system.
Note that Def. 2 and the above calculation of linearly
independent vectors do not assume N to be an S3PR and
are applicable to arbitrary nets.
Figure 1(a) shows an example of weakly dependent
siphon. Table 1 below lists the four strict minimal
siphons and their η, where 412
=3

 .
3. Types of SMS
In [2,3,6], 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 alternate disjoint path

D. Y. CHAO ET AL. 312
Table 1. Four SMS in Figure 1(a) and their  , where 
4 =

1 +

2 −

3.
S η Set of places [S]
S1 t2 – t4 + t8 – t9 p4, p12, p13, p14, p15 p2, p3, p8, p9, p10, p11
S2 t1 – t3+t7 – t10 p5, p11, p14, p15, p16 p3, p4, p7, p8, p9, p10
S3 t2 – t3 – t4 + t7 p4, p11, p14, p15 p3, p8, p9, p10
S4 t1 + t8 – t9 – t10 p5, p12, p13, p14, p15, p16 p2, p3, p4, p7, p8, p9, p10, p11
(a)
(b)
Figure 1. (a) Example weakly dependent siphon [14]. ra =
p16, rb = p15, rc = p14, rd = p13, ta = t1, tb = t2, tc = t3, td = t8,

c
t =
t4; (b) controlled model of that in Figure 1(a).
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
resource places, form a number of elementary circuits.
Hence, there is an elementary circuit containing adjacent
control places, from which we can synthesize new
problematic siphons.
Definition 3. An elementary resource circuit is called
a basic circuit, denoted by . The siphon constructed
from is called a basic siphon. A compound circuit
12 1nn
b
c
b
c
cccc c


  is a circuit consisting of multi-
ply interconnected elementary circuits , , ···,
1
c2 cn c


,
pp
ii
r rR such that 1ii cc


 (i.e., and 1i c

in-
i
c
tersects at a resource place i). The SMS synthesized
from compound circuit c using the Handle-Construction
Procedure in [9] is called an n-compound (resp. control,
mixture) siphon S, denoted by .
r
12 1
SS S

nn SS
4. Controllability for Strongly Dependent
Siphons
We review the controllability for strongly dependent
siphons to compare with that for weakly ones to be
derived in Section 5. We first present the theory below to
decide whether a monitor to a compound siphon is
redundant.
To disturb the controller region the least, we should
allow M([S1]) to reach its maximum; thus setting



001
=
S
MVM S1

1; S is said to be limit controlled. In
general,


0
=MV M

01
S
11
SS

, where 1
S is the
control depth variable. 1
S
1 

is adjusted to be greater than
1 if some dependent siphons are not controlled. As a
result, max M([S1]) is less than and the
controller region is more disturbed causing more states
lost.

01 1MS
Definition 4. Let

 
00
=MV MS
SS

 where
1
S


S
is called the control depth variable. S is said to
reach its limit state when M(S) = 1; it is limit-controlled
iff it is able to reach its limit state but not able to reach
unmarked state; i.e., 1

or minM(S) = 1.

Theorem 1. [21]: Let (N0, M0) be a net system and 0
be a strongly dependent SMS w.r.t. elementary siphons
S
1
S2 Sn S

=1
n

i
i


, , ···, and such that where , and
0=

1, 2,,in

SS, ij  iff

1
i
ij. is ex-
tended by n control places 1
S, 2 S, ···, and S such
that 1, 2, ···, and are limit-controlled. can
never be emptied iff ,
0
N
V V
n
bM
V
01
S


n
S SS0 S
1

==S
ii


1, 2,,1in

.
Note that for strongly dependent siphon 01ii
,SS S


is a single resource , 01
implies that
there is only one token in the initial marking of .

ii
MS S



=1
r
r

D. Y. CHAO ET AL.313
5. Controllability for Weakly Dependent
Siphons
This section shows that if 0 S weakly depends on 1
and 2, then there exists a third siphon 3—syn-
thesized from core circuits 1 and 2, respectively,
such that 0123
S
S S
c c
=

 . Other properties will also be
derived, from which we will derive the controllability of
a weakly 2-compound siphon.
Chao [2,3,6], show that in an S3PR, an SMS can be
synthesized from a strongly connected resource subnet
and any strongly dependent siphon corresponds to a
compound circuit where the intersection between any
two elementary circuits is at most a resource place.
Let be a strongly dependent siphon, , , ···,
and be elementary siphons, with
012
S S
n
0
S
n
SS
1
S2 S
S
=

  . It is shown in Chao [2,3,6]
that 0 (the core circuit from which to synthesize )
is a compound resource circuit containing 12 ,
and the intersection between any two i and
c0 S
,
n
c,,cc
c
j
c
c
, i = j −
1 > 0, is exactly a resource place, where i (i =0, 1,
2, ···, n) is the core circuit from which to synthesize i.
Thus, if S0 is a WDS (weakly dependent siphon), the
intersection between any two ci and cj, i = j − 1 > 0,
must contain more than one resource place.
S
Let and be the SMS synthesized from basic
circuits 1 and 2, respectively, where 12 .
One can synthesize a third SMS, denoted by 0, from
the strongly connected resource subnet 12
. For S0 to
be a WDS, must contain more than one resource
place.
1
S
c
2
S
c
1
c
cc 
S
cc
2
c
To simplify the presentation, 12
is assumed
to be
cc 


bbc
rt r

,,r r r
on Process 1, where b, are two
re-source places, and
r

c
r
c
r
 
,,
ab
Rcrr

1
2bcd as shown in Figure 1(a). The more
complicated case can be treated similarly as in [9]. For

Rc
instance, in Figure 2,

 
114151
,,Rcp p p6 and




1415
,pp
21 (one more place than the
above one).
213
,,Rc pp
It is assumed, that a core circuit spans between process
1 (WP1) and process 2 (WP2) and () denotes
path
12 k
rr r


11 2 211kkk
rtr trtr

. Let


1trtr aab
crtrbcca
and


2bbccd d b
crtrtrtr

 span between process 1 and
process 2 [see Figure 1(a), where ,
16a
rp15b rp

,
14
p
c
r

, 13d rp

, 1a tt

, 2b, 3, 8d tttt
c
tt

,
4c
tt


]. Note that a, b, c, c and d t may not be
in the same process; some are in process 1 and the rest
are in process 2. Consider the resource path on process 1.
There are only 2 possible cases satisfying the above
conditions are as follows: 1) 2)

.
Case 2 is equivalent to Case 1 by relabeling by
and by , respectively.
t t
r r
t t
abc
rdbca rrrr
a d
r
r rrr

d
r
r
rrr r
rr
d a
Note that it is possible that

abcbcbcd ,
which can be treated similarly as in Chao [10]. For Case
1, 1 can be broken two paths: one, c


aabbc
rt rt r, in
process 1, denoted by


1
bc
r
aab
rt rt; another,


cca
rtr ,
in process 2, denoted by


2; i.e.,
cc
rt a r




1aabbc Similarly, c2 can be broken
two paths: one,
12
.
ca
rtr
c
trtrcr


bb c cd
rtrrt

, in process 1, denoted by


1
ccd
rtr

bb
rt ; another,


dd
rt b r, in process 2, denoted
by


2; i.e.,
ddb
rtr




212 bbcdd d b. In the
sequel, i
crtrtrtr


refers to the T-characteristic vector of siphon
Si synthesized from ci.
Theorem 2. [9]: Let . Then
1
=SSS2
012
=3



.
On the Process 2 side in Figure 1(a), there should be
no PP'-path of the form [c
] (resp. []) to form
basic circuit 4 (resp. 4
c) consisting of only two
resource places of d and c (resp. a and b
r), since
0 is no longer a weakly dependent siphon as derived
below. First, and . This leads to
d
rtr

r
3
*
ba
rt
3
c
c
=
r
14
cc
r

S
c25
=cc
Figure 2. Example a 3-dependent weakly dependent siphon. S0 = S6 = S1  S2  S3, S4 = S1,2, S5 = S2,3 and 
0 =

1 +

2 +

3 −
4 −

5.


D. Y. CHAO ET AL. 314
13
=4

 , 23 =5

 
==
, and
233401 5

 
S S
  
5
S
 
0
S
; 0 strongly depends on
3, 4, and and is no longer a weakly
dependent siphon.
S
Lemma 1. [9]: Let (0,0 N
M
) be a net system and 0
be a weakly dependent SMS w.r.t. elementary siphons
, , and where
S
1
S2 S3 S01 =23

 . Then
1)
 


3b
A
BS

PHr, where

12
=
A
SS

,

21
=BS Sb


, .
3
rS
2)

3c
H
rS


and

0c
H
rS.
3)



 
rMS r


30 0
==
cb
MminM S.
Consider the S3PR in Figure 1(a),



124
==
A
SS p

15
=
b
, ,

21 11
=[]=BS Sp

3.
A
BHr p

Sc

Furthermore, 14, =rp



3810
()=, ,
c3 38910
, , ,
H
r ppp
 
S pppp and


8910
,,,,,
0 237c
H
r Spp pppp .
Define S12 = S3 and S0 = S1

S
2 since
. 12
is similar to 12 S in
that can never be emptied if for both cases.
12
is different than 12 in that
 
12 3
RS SRS
0
S
SS
SS
S 
S
1b
S


12
SRS
for the former contains more than one resource place
while the latter contains only one resource place.
Consider the S3PR in Figure 2. Table 2 lists eight
SMS , and core circuits in Figure 2. Note that S


12

15214
cc ptp
SSS

is not a single resource place and
hence 712 cannot be a strongly dependent
siphon and is a weakly dependent siphon. Similarly,

213 1812
cc ptp
SS S
3
 is not a single resource place and
hence 82 3 cannot be a strongly dependent
siphon and is a weakly dependent siphon. Note that c2
contains 4 rather than 3 resource places assumed above.
Yet, all relevant theory remains true.
Theorem 3. Let be a net system and 0
be a weakly dependent SMS w.r.t. elementary siphons
1, 2, and 3 where

00
,NM
=

S
S SS0123

 
VV
. 0 is ex-
tended by control places 1
S, 2 S, and , such that
, , and are limit-controlled. Let
N
3
VS
1
S2 S3 S


10
=
A
SS,


20
BS S

=, and
3

=
A
BSP Hr, (by Proposition 1) 3 rS

,
0 can never be emptied iff ; 2) is
limit controlled iff .
S

0
==bMr
1
S
1
0
S

0
==bMr
Proof. 1) () Assume 0 is unmarked (hence
, ), while each of 1, 2, and is
marked; i.e., ,


=0Mr 0 S

r
1
MS
S S3 S
0


2
MS 0, and


30MS .
By Proposition 1, it holds that
 
3
=
A
BS

P Hr . Let

 


2
=S


10 since 1 and
are marked.
0
S1
S
MS SM 2
S



==r

H
0
Mr since 1M


=0Mr
and . Now

0
Mr


=1



=2B
3
MS
M 
MHr
1= MH
P

3
S
M
2
A
 
r

. However,
, which is impossible. Thus,
it is impossible that








10
S2 S
0
=1MS MS.
This leads to that either


0MS S
10 or


20
0MSS



, which implies that S0 can never be
emptied. () Assume contrary and


0
=0bMr.
Then it is possible that


0MA and


0MB
such that each of , , and 3 is marked, while
1
S2 S S




=0SS
S
1020 or 0 is unmarked
against the assumption that 0 is marked. 2) (
=SMS SM

) If


0
==bMr 1, then there is a reachable marking such
that


=1MA,


=0

MBMB or , =1


=1MA

.
Either one implies that . () Assume
contrary and

0=1MS


1r
S
0. The proof of part 1 of this
theorem indicates that 0 is unmarked. Hence
cannot be limit controlled against the assumption.
=bM
0
S

Thus, it is similar to a strongly dependent siphon
synthesized from a compound circuit where
is also controlled if 1
b and both 1 and 2 are
limit controlled. For the S3PR in Figure 2 where each
elementary siphon is limit-controlled and 04
is
controlled as well. Assume otherwise and 4 is empty.
Then
S
12
ccS
S S
=SS
S
=1








10
MS 20 ==MS S1S. Let




410
==
A
SSp
,



20
==BS S

11
p,




311
==
A
BSP Hrp. If


0
Mr=1=b

, then
it is impossible that







10 .
Thus, can never be emptied.
20
==S S1MS SM

0
The condition (i.e.,
S


3
=
A
BS PHr,
3
rS

) in Theorem 3 is generally true for vertically
stacked S3PR (in most literatures); that is sink transitions
of 1 and 2 are in the same processes. The condition
may not hold for horizontally stacked S3PR; that is, sink
transitions of and are in different processes. In
this case,
S S
1
S2 S



110
=
A
SS Hr and




r
2, 1. However, it remains
true that
0
=BS S22 rrH


3
=
A
BSP0 S. can become unmarked
when






0
=0M r
10
S1 MS

,






=0
20 02
MSSM r



MS

, .

0MA B
3
Define S12 = S3 and S0 = S1 S
2 since




12 3
. 12 =RS SRSSS

is similar to 12 in
that can never be emptied if for both cases.
12
SS
0
S
SS
=1b

is different than 12 in that SS


RS S
12
for the former contains more than one resource place
while the latter contains only one resource place.
Theorem 4. Let


00
,NM be a net system and
be a weakly dependent SMS such that
0
S
012
=SSS n S


1, 2,,in
denoting the fact that

, ij SS

holds iff 1ij. Let


0
=
ii
A
SS,


10
S=
ii
BS
,




,1 i
=
ii ii
A
BSPHr
, where ,1iii
rS

0 N
2V3
S
V
S S3 S
0
S
1
. is
extended by control places 1
S
V, , 12
S, ,
, ···, and , such that 1 S, 2, 12, ,
23 , ···, and n, 1,n are limit-controlled, 1)
can never be emptied iff 0ii ,
S
V

==bMr
32
S
VSn V
SS 1,n
n
S
V
Sn


1, 2,,1in

; 2) is limit controlled iff
0
S

D. Y. CHAO ET AL.315
Table 2. Eight SMS S, and core circuits in Figure 2.
S Set of places c
S1 p516 = c1 [p14 t4 p16 t1 p15 t2 p14] + HPP' p15 t5 p14], [p14 t6 p15] and [p15 t7 p14].
, p17, p14, p15, p1
e
c [
S2 p c = c 2 [p15 t2 p [p15 t7 p14]
p
PP
p
5, p27, p15, p16
4, p26, p12, p13, p14, p15 2
e
14 t3 p13 t18 p12 t8 p15]+ HPP' [p13 t11 p12], [p12 t12 p13 ], [p15 t5 p14], [p14 t6 p15] and
S3 2, p27, p11, p12, p13 3
e
c = c
3 [p13 t18 p12 t17 p11 t14 p13] + HPP' [p13 t11 p12], [p12 t12 p13], and [p13 t13 p12]
S4 p
4, p17, p14, p15 4
c = c
4[p15 t2 p14 t6 p15] + HPP' [p15 t5 p14] + H [p15 t7 p14]
e
S5 p
2, p26, p12, p13 5
e
c = c
5 [p13 t18 p12 t12 p13]+HPP' [p13 t11 p12], and [p13 t13 p12]
S6 11, p12, p13, p14, p6123
eeee
cc c c
S7 p
5, p26, p12, p13, p14, p15, p16 71 2
ee e
ccc


S8 p
4, p27, p11, p12, p13, p14, p15 82 3
ee e
ccc



By Theorem 3, the
theorem holds f Assume ilds for

0ii
bM
Proof. 1) Prov

=1r,

1, 2,,in =1.
e by induction.
or t ho =2n.=1kn

.
We need to prove that it also holds for =kn . Let
*
1
=nn SS S
, 12 1un
SSS S

,

=

0
=u
A
SS, **
1
=n
A
SS





 and


0
=B S.
n
S
By Theorem 3.2,
that *=
u
S is limit controlled. It is easy to see
A
A and



*
1, 1 nn n
=
A
BSP

.
Hence

Hr


1,nn 1n
A
BSP Hr

 and

,1unn
A
BSH
3. 2. (
never be em
r
Theorem ntrolled
art 1 of this theorem,

0
==1
ii
bMr ,

2, ,in. () If
0
=()=1
ii
bMr,

1, 2,,in . Consider * S, u S,
. 
) If 0 S
ed. By
1,
0
S can never
 is limit co
ti p
be em
,
ptied by
then it can
p
A
, *
A
and B
theorem. Prov
knn
that it als
==SS S

trolled. 
ro pa
e Assume it hs
=1. Theu S is limit controlled since

0
==1
ii
bMr ,

1, 2,,2in. We need to prove
o holdsr =kn . By Theorem 3, it
0un
Su n S are limit con-
trolled and 01 ==1
nn
bM

. Thus, 0 S is limit con-
This theoif the cdition in the
theorem
defined
by in
fo
since both

1
in the pof of
duction.
S and

r
rt 1 of this
old for
holds for
rem implies that on
is satisfied, then the compound siphon is already
co
c
nd
ntrolled. Thus, Theorem 4 shows that the control-
lability for 01 2
=n SSS S for a weakly depen-
dent siphon 0
S is similar to that for a strongly depen-
dent siphon. Aol for WDS needs no
longer be thatonservative as by Li and Zhou.
Table 3 lists eight SMS S and their [S].
0
==SS SSS, 4 =SS, =SS a
s a result, the contr
612 31,252,3
=
0 12345

 . It can be verified that

=[]=
11 217
A
SS p,

12 14
p,

=[]=SBS

1 1151,2
A
BHpS .


22326
==
A
SSp,


23 22
==Sp, BS

2 2132,3
A
BHpS 
By Theorem 3, S
.
6can never be emptied iff




10 1520 13
==bMpb Mp.
firmed using the INA (Integrated
resulting controlled net (see
sta
model, where
==1 This has been con-
Net Analyzer). The
Table 4) reaches 32298
trolled tes out of the total 45135 states of the uncon






016 014012011
====2Mp MpMpMp and




01 06
==2Mp Mp. Note that even though some
new siphons (such as control siphons) are generated by
the presence of
Why this
research.
Physically, for 6 S to become empty under
monitor places
without adding monitors for these n
is so is a subject for future
, the controlled
ew siphons.
net is live
M
,


=0Mr , for every resource place in 6 S. Thus, all
tokens in


0
M
r must stay in

H
r. If


013 1Mp,
it is possible that both p and p
226
plies both 2 S an3 S are marked. Even if
are marked, which
im d


Mp
015 1

, this token may go to p such that 1 S is
also mark6 may becomark
tokens in 16 p and pgo to 7 and 20 p, respec-
tively. Thus, en though each of 1 S, 2 S, an
adding a monitor, 6 Say still become
unmarked and nes a monitor.
On the othand, if
17
unmed w
p
m
ed. Se
11
ev
marked by
ed
her
hen
d
all
3
S is




10 1520 13
====1bMpb Mp, we sh that i6
S
becomes unmarked, at least one o1 S, 2 S, and 3 S is
also unmarked contradicting th
ow
f
fact that each
ding a monitor.
f
1
S,
6
S
to
e
2
S by ad
to become unmarked, all tokens
of
For , and 3 S is controlled
in 16 p and 11 p go
7
p and 20 p, respectively.
Hence, for 1 S and 3 S to be marked, 17 p and 2
must be both marked since

p


16 17
=SS p and




362
=SS p. Now, both 4 p an26 p are marked
e
d un
sinc




5
pp Hp,
417 1
,


13
Hp

, and
226
,pp




015 013
==1p MpBut then S isnmark
contradicting the fact that
M.
each o
adding a monitor. Thus, the assum
ked is incorrect and we pr
2 u
f S
6
ove that S
ed
is controlled by
2
ption that S becomes
unmar 0 is con-

D. Y. CHAO ET AL. 316
Ta , [Sble 3. Eight SMS S] and  in Figure 2.
S [S]

p3, p4, p7, p8, p9, p10 S1 t1 – t3 + t7 – t10
S2 p2, p3, p8, p9, p10 21, p23, p24, p25 , p17, pt2 – t4 + – t17 t13
S3 p
20, p21, p23, p24, p25, p26 – t8 + t14 – t16 + t18
S4 p3, p8, p9, p10 t2 – t3 – t4 + t7
S5 p21, p23, p24, p25 –t8 + t13 – t17 + t18
S6 p2, p3, p4, p7, p8, p921, p23 , p24, p25, p26 , p10, p17, p20, pt1 – t10 + t14 – t16
S7 p2, p3, p4, p7, , p23, p24, p25 p8, p9, p10, p17, p21 t1 – t10 + t13 – t17
S8 p2, p3, p8, p9, p10, p17, p20, p21, p23 , p24, p25, p26 t2 – t4 + t14 – t16
Table 4. Disturbancess control model of the net in Figure 2.
S Monitor
le
S
V

S V
 M0
S1 + c − 1 V1 t
3, t10 t 1, t7 a + b
S2 V
2 t 4, t2, t13 b + c + d + e − 1
a + b +− 1
a + b− 1
17 t
S3 V
3 t 8, t16 t 14, t18 d + e + f − 1
S4 V
4 t 3, t4 t 2, t7 b + c − 1
S5 V
5 t 8, t17 t 13, t18 d + e − 1
S6 V
6 t 10, t16 t 1, t14 c + d + e + f
S7 V
7 t 10, t17 t 1, t13 + c + d + e
S8 V
8 t 4, t16 t 2, t14 b + c + d + e + f − 1
trolled.
Alternatively, we will prove based on the following
bservations from Table 3 that: o












6 12345
=SSSSSS,








7124
=SSSS,
and








823
=SSSS.
5
In general, ifj , then
e
following theorem.
Theorem 5. Let

be
be a dependent S elementary siphons
d where


0=1 =1
=
nm
SiSnjS
in
ij
ab  



nm
nj nj
bS



or

=1 n
nm
inj
S
j
b 



 shown in th


S
 

0=1
=i
SS
i
a 

 
0
=1 =1
=ii
ij
aS 

j


as
a net system and

00
NM,
MS w.r.t.
2n
S, ···, an
0
S
1
S,
2
S, ···, S, S,
n1nnm


0=1
==
nm
SiSnjSab
ab
S
=1 in
j
ij




 ,

=1
=
n
ai
i
a

S
i

 , and =
b


=1
n j
m
S
j
j
b 

 .
Then
1)


0121 2
,,,,, ,,,
nn nnm
SSSS SSSS
 
 
[]SS
,
=


(characteristic T-vector of the com
tary set of siphon S equals the negative of that of
pen-
).
2)
lem
S


0=1 =1
=
nm
inj
SS S
inj
ij
ab  



 






, where ,

i a
j
bR(set of real numbers), a

1, 2,,in

nd


1, 2j,,m (characteristic P-vectors of the comple-
mentary sets of siphon S, 1 S, 2 S, ···, n S, n S,
1

2n
S

, ···, nm S

follow th
3) The Marking Equality (ME) holds:,
of siphon
e sam
eristic T-vect
e equation as that
ors).
of the
corresponding charact



0
=1
=,
,
j
MS
MRNM

 



=1
0
nm
iinj nj
i
aMSbM S





(1)
(total tokens in the complementary sets
, S, ···, S, S
S,
1
S2n1n

, S2n

, ···, S follow t
nmhe sa
equation as that rresponding character
me
istic of the co

D. Y. CHAO ET AL.317
T-vectors).
Proof. 1)




RrS
R
SSS Hr


variant
is the sup-
port of a P-in
I
based on Property 1 and


SS. Note that
R
R
SSP

.


pS S
s
,

1Ip (valid for OPN); otherwise,

=0Ip. Thu,

=SS I

 .







==0
TTT
SS
IN N (By the
definition of P-invariant), where 0 is a vector with all
components b
controlled, we have






00
max
M
SMS or
 

0
=1 =1
max m
nm
iinj nj
ij
MSaM SbMS





in










(2)
To be conseve, the term associated with the
negative terms is set to zero0
N   rvati
. That is, if
eing 0.

=
SS


on equation 0b
.
2) Based =
Sa

 , the factt tha

=
SS

  and


=
TT
N  , we have

0=1
=
nm
i
SS
i
ab  
 
 


SS
 



=1
=1
0=1 =1
=
=0
n j
Snj
ij
nm
TT T
j
inj
SS S
inj
ij
Na N bN
abN
 
 
 
 



 
 





0=1
in
SS S
inj
ij
  
 


T
nm










 




If , then
0=1 =1
=0
nm
inj
SS S
inj
ij
ab  

 
 





is
a P-invariant. However, all places in


0
S,


1
S,


2
S, ···, and


nm
S
and he
are not ma
g ofnce the union of
rked in the i

nitial
markin N

0
S,


1
S,


2
S, ···, and


nm
S
m
cannot be the
P-invariant. This i
support of a
plies that 0



0=
nm
inj
SSS
inj
ab  

 
 


 .
=1 =1ij

3 Multiplyingoth sides of the equation in Equation
(1) by T
) b
M
, w have
0=1
=
nm
TT T
i
SS
in
MaM 
 
 
e
   

=1
0
=1 =1
=.
n j
Sj
ij
nm
i injnj
ij
b M
MSaMSbMS

 













This theorem holds for FMS modeled by OPN [not
Genera (GPN)] sl PNuch as an S3PMR since we have
assumed


pS S,


1Yp
odeled by GP
. However, it can be
extendedN such as S4PR and
S3PGR2
to FMS m
by replacing
M
with W((M(A))), the weighted
sum of tokens in
A
S or [S].
This ME says that the total number of tokens trapped
in [0 S] and [i S], follow the same linear algebraic
relationship between 0
S

and Si

, i = 1, 2, ···, n, n +
1, ···, n +ically, m. This is becase puhys


St
  is the
number of tokens removed from S by firing t once.
Now, max




=1
ii
tM SS
0
M

(i S is said to be limit
controlled) for i Sve tokens. In order for to be to ha0 S

M
S
than max (


=1
n
ii
i
aM S

holds.
not hold that
s large i
enough to be greater), then Equa-
tion (2) necessarily
However it may








0101202
11
n
MSa MSaMS 


0
11
nn i
aMS S


0
=1
=i
i
n
aM
0=1i
=aMi a





y not be controlled when
After lowering

That isma each is
limit controlled.
0 S i S



i
M
S to


0
MS
iS
i


, 1
Si

 where Si

is the c
in Li and Zhou [13], fo

ontropth
r each , it
may hold that
l de
i
S variable mentioned




01202
=
n
i
Sa MS
aM


01 SS
MSa M 



12
00
=1
0
=.
nn S i
ni
i
aM
aMS S

S






This is exa


the MLI (marking lin
In the sequel, we do not
negative terms to zero; t
controllability.
d 5
S (resp. 6 S, 7 S, and
d) siphons; they are lim

ctlyear inequality
mentioned in [13]). set the term
associated with theherefore
achieving a better
, , ···, an) are
. compound
1
S
basic (re
by setting
2
S
sp
8 S
it-controlle


01 S=1
M
Vabc

,


02=1 S
M
Vbcde

,

03=1 S
M
Vdef ,


04=1 S
M
Vbc

, and

05=1 S
M
Vde.


06
=
M
S abcde

 ,

=
07
M
Sbcdef ,
and


08
=
M
Sabcde f

 . Table 4 shows the
disturbaf thnceless control model oe net in Figure 2.





iS
i
max 0
=
M
SMV, i =, 2, ···, 5, and 1















max 7maxn 4
=1max 2mi
M
SMS SMSM
part 3 oemma 1)
1 1
bcde c
(by Theorem 4 and f L
=
abc

 
=2abcdeb

 .
Thus, is limfor control
7
Sit-c ontrolled (no need

D. Y. CHAO ET AL. 318
elements) iff





07max 7
M
SM S
7
S to be limit-cont
==3b, of whichone toke
12 21
ps
2
S are marked (
oth S andS are
one
ontrol e
ntr ility
, which implies
d control
elemrolled. For instance,
n goes to
since
Simila
co
that
b < 2 or

013
==1bMp .
On the other hand, if b > 1, we need to ad
ents for
3
ns to
b
rly,
an

01
Mp
two toke
p
, 4 p
d)
d
17
p, also a tokens in 16 p to 5 p and
e tokens in p to . Thi makes 7 S emptied and
yet both 1 S and consistent with the
fact that
1 2
17 1
S and 42 pS and both 4 p and 17 p are
marked.
can argue that 8 S is limit-controlled
(no need for c elemnts) iff 013 =1Mp Now
nsider the coollab of 6 S.

controlle

.

















max 61max2max 3
4 min
=

max
min

5
M
SMS SMS
SM


M
M




1
=
def ce
abcde f


S
(b


1
3
y Part 3 of Theorem 4)

=1abcbcd

e
bd


(by Part 3 of Lemma 1).
where



min4=
M
Sc and



5= min
M
Sd
ntrol ele
. Thus,
is liments)
6
S
mit-co

ntrolled (no need for co

iff



06max 6
M
SM

3=
S , which imp
 
013 015
===pdMp
1 and

lies that
=1 . If bd

30 
n
bd
==1, theor
bd
bM




06
MS M

max 6
S

=1, other-
wise, 3bd and



06max 6
M
SM
s
rived the controllability fo
eapendent siph
at they he the same co
proves the conservativ
ao, “A Graphic-Algebr
Siphons of BS3PR,” Jour
ineering, Vol. 23, No. 6
.
S; 6 S is
emptie
6. Csion
We hstrongly
(SDS) akly deS It is
surprisedavus,
his paper im
d.
on
avr both
ons (WD).
ntrollability. Th
e control policy for
aic Computation of Ele-
mentar nal of Information Sci-
, 2007, pp. 1817-
, Vol. 2, No. 2, 2007,
1080/00207540701747210
clu
e de
nd w
th
y
pp. 168-179
t
WDS in [8].
7. References
[1] D. Y. Chao, “Computation of Elementary Siphons in
Petri Nets for Deadlock Control,” The Computer Journal,
Vol. 49, No. 4, 2006, pp. 470-479.
[2] D. Y. Ch
ence and Eng
1831.
[3] D. Y. Chao, “Incremental Approach to Computation of
Elementary Siphons for Arbitrary S3PR,” IEE Proceed-
ings Control Theory & Applications
[4] D. Y. Chao, “Technical Note-Reaching More States for
Control of FMS,” International Journal of Production
Research, Vol. 48, No. 4, 2008, pp. 1217-1220.
doi:10.
9, No. 3-4, 2008, pp. 317-318.
[5] D. Y. Chao, “Comments on Deadlock Prevention and
Avoidance in FMS: A Petri Net Based Approach,” The
International Journal of Advanced Manufacturing Tech-
nology, Vol. 3
doi:10.1007/s00170-007-1190-x
[6] D. Y. Chao, “An Incremental Approach to Extract Mini-
mal Bad Siphons,” Journal of Information Scien
Engineering, Vol. 23, No. 1, 2007,
ce and
pp. 203-214.
[7] D. Y. Chao, “Revised Dependent Siphons,” The Interna-
tional Journal of Advanced Manufacturing Technology,
Vol. 43, No. 1, 2009, pp. 182-188,
doi:10.1007/s00170-008-1684-1
[8] D. Y. Chao, “Conservative Control Policy for Weakly
ptimal Siphon- and
a Well-Known S3PR,”
Dependent Siphons in S3PR Based on Elementary Si-
phons,” IET Control Theory & Applications, Vol. 4, No.
7, 2010, pp. 1298-1302.
[9] D. Y. Chao, “Structure of Weakly Dependent Siphons,”
Unpublished Manuscript.
[10] D. Y. Chao, “Improvement of Subo
FBM-Based Control Model of
IEEE Transactions on Automation Science and Engi-
neering, Vol. 8, No. 2, 2011, pp. 404-411.
doi:10.1109/TASE.2010.2088120
[11] J. Ezpeleta, J. M. Colom and J. Martinez, “A Petri Net
Transactions on Robotics and
Based Deadlock Prevention Policy for Flexible Manu-
facturing Systems,” IEEE
Automation, Vol. 11, No. 2, 1995, pp. 173-184.
doi:10.1109/70.370500
[12] M. V. Iordache, J. O. Moody and P. J. Antsaklis, “A
Method for the Synthesis of Liveness Enfo
visors in Petri Nets,” Proceedings
rcing Super-
of the 2001 American
ntion in
Systems,” IEEE Transactions on
ystems, Man, and Cybernetics Part A: Sys-
Systems and Hu-
Control Conference, Arlington, 25-27 June 2001, pp.
4943-4948.
[13] Z. W. Li and M. C. Zhou, “Elementary Siphons of Petri
Nets and Their Application to Deadlock Preve
Flexible Manufacturing
Systems, Man, and Cybernetics Part A: Systems and Hu-
mans, Vol. 34, No. 1, 2004, pp. 38-51.
[14] Z. W. Li and M. C. Zhou, “Clarifications on the Defini-
tions of Elementary Siphons in Petri Nets,” IEEE Trans-
actions on S
tems and Humans, Vol. 35, No. 6, 2006, pp. 1227-1229.
[15] 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 Part A:
mans, Vol. 37, No. 3, 2007, pp. 362-371.
[16] Z. W. Li and M. C. Zhou, “Control of Elementary and
Dependent Siphons in Petri Nets and Their Application,”
IEEE Transactions on Systems, Man, and Cybernetics
Part A: Systems and Humans, Vol. 38, No. 1, 2008, pp.
133-148.
[17] Z. W. Li and M. C. Zhou, “On Controllability of De-

D. Y. CHAO ET AL. 319
ems, Man
pendent Siphons for Deadlock Prevention in Generalized
Petri Nets,” IEEE Transactions on Syst, and
Cybernetics Part A: Systems and Humans, Vol. 38, No. 2,
2008, pp. 369-384. doi:10.1109/TSMCA.2007.914741
[18] Z. W. Li and M. C. Zhou, “On Siphon Computation for
Deadlock Control in a Class of Petri Net,” IEEE Transac-
tions on Systems, Man, and Cybernetics Part A: Sy
p.
an
Part A: Systems and Humans, Vol. 39, No. 3,
stems
and Humans, Vol. 38, No. 3, 2008, pp. 667-679.
[19] L. Piroddi, R. Cordone and I. Fumagalli, “Selective Si-
phon Control for Deadlock Prevention in Petri Nets,”
IEEE Transactions on Systems, Man, and Cybernetics
Part A: Systems and Humans, Vol. 38, No. 6, 2008, p
1337-1348.
[20] L. Piroddi, R. Cordone and I. Fumagalli, “Combined
Siphon and Marking Generation for Deadlock Prevention
in Petri Nets,” IEEE Transactions on Systems, M, and
Cybernetics
2009, pp. 650-661.
[21] Y. Y. Shih and D. Y. Chao, “Sequence of Control in
S3PMR,” Computer Journal, Vol. 53, No. 10, 2010, pp.
1691-1703. doi:10.1093/comjnl/bxp081
[22] M. Uzam, Z. W. Li and M. C. Zhou, “Identification and
facturing Tech-
Elimination of Redundant Control Places in Petri Net
Based Liveness Enforcing Supervisors of FMS,” The In-
ternational Journal of Advanced Manu
nology, Vol. 35, No. 1-2, 2007, pp. 150-168.
doi:10.1007/s00170-006-0701-5
[23] 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 Is
“Control of Discrete Event System
sue on the
s”, Vol. 6, No. 2, 2010,
pp. 270-280.