© The Institution of Engineering and Technology
Computation of elementary siphons proposed by Li et al. is essential for deadlock control and expensive since complete siphon enumeration of the Petri net is needed, and the number of strict minimal siphons (SMS) grows quickly and exponentially with the size of the net. They assumed that the siphon constructed from each resource circuit is an elementary one and proposed a polynomial algorithm to compute elementary siphons. However, the author demonstrates a counter example where there may be an exponential number of resource circuits. Hence, constructing elementary siphons from resource circuits will result in an exponential number of elementary siphons, which is wrong. The author then develops a polynomial algorithm to find elementary siphons, which also constructs all SMS on the way. This is because, in the method proposed by Li et al., a linear algebraic expression must be established for each dependent siphon, which implies, all SMS must be located. However, all elementary siphons with polynomial complexity can be located.
References
-
-
1)
-
D.Y. Chao
.
A graphic-algebraic computation of elementary siphons of BS3PR.
J. Inf. Sci.
,
6 ,
1817 -
1831
-
2)
-
Z. Li ,
M. Zhou
.
Two-stage method for synthesizing liveness-enforcing supervisors for flexible manufacturing systems using Petri nets.
IEEE Trans. Ind. Inf.
,
4 ,
313 -
325
-
3)
-
D.Y. Chao ,
D.T. Wang
.
Two theoretical and practical aspects of knitting technique – invariants and a new class of Petri net.
IEEE Trans. Syst. Man Cybern.
,
962 -
977
-
4)
-
Z.W. Li ,
J. Zhang ,
M. Zhao
.
Liveness-enforcing supervisor design for a class of generalized Petri net models of flexible manufacturing systems.
IET Control Theory Applic.
,
4 ,
955 -
967
-
5)
-
P. Kemper ,
M.A. Marsan
.
(1993)
Linear time algorithm to find a minimal deadlock in a strongly connected free-choice net, ‘Application and Theory of Petri Nets’, 691, Lecture Notes in Computer Science.
-
6)
-
Li, Z., Hu, H., Zhou, M.: `A polynomial algorithm to find a set of elementary siphons in a class of Petri nets', Proc. IEEE Int. Conf. Syst., Man, Cybern, October 2004, The Hague, The Netherlands, p. 4861–4866.
-
7)
-
D.Y. Chao ,
Z. Li
.
On structural conditions of S3PR nets without weakly dependent siphons.
IEEE Trans. Syst. Man Cybern. A.
-
8)
-
D.Y. Chao
.
Computation of elementary siphons in Petri nets for deadlock control.
Comp. J.
,
4 ,
470 -
479
-
9)
-
Z. Li ,
M. Zhou
.
Clarifications on the definitions of elementary siphons in Petri nets.
IEEE Trans. Syst. Man Cybern. A.
,
1227 -
1229
-
10)
-
Li, Z., Hu, H., Zhou, M.: `An algorithm for an optimal set of elementary siphons in Petri nets for deadlock control', Proc. IEEE Int. Conf. Syst., Man, Cybern, October 2004, The Hague, The Netherlands, p. 4849–4854.
-
11)
-
D.Y. Chao
.
Petri net synthesis and synchronization using knitting technique.
J. Inf. Sci. Eng.
,
543 -
568
-
12)
-
Iordache, M.V., Moody, J.O., Antsaklis, P.J.: `A method for the synthesis liveness enforcing supervisors in Petri nets', Proc. American Control Conf., 2001, p. 4943–4948.
-
13)
-
D.Y. Chao
.
An incremental approach to extract minimal bad siphons.
J. Inf. Sci.
,
1 ,
203 -
214
-
14)
-
Z.W. Li ,
M.C. Zhou
.
Elementary siphons of Petri nets and their application to deadlock prevention in flexible manufacturing systems.
IEEE Trans. Syst. Man, Cybern. A.
,
1 ,
38 -
51
-
15)
-
J. Ezpeleta ,
J.M. Colom ,
J. Martinez
.
A Petri net based deadlock prevention policy for flexible manufacturing systems.
IEEE Trans. Robot. Automat.
,
173 -
184
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cta_20070130
Related content
content/journals/10.1049/iet-cta_20070130
pub_keyword,iet_inspecKeyword,pub_concept
6
6