| Previous | [ 1] | [ 2] | [ 3] | [ 4] | [ 5] | [ 6] | [ 7] | [ 8] | [ 9] | [ 10] | [ 11] | [ 12] | [ 13] | [ 14] | [ 15] | [ 16] | [ 17] | [ 18] | [ 19] | [ 20] |
¡@
Daniel Yuh Chao
National Chengchi University
Taipei, 116 Taiwan
E-mail: yaw@mis.nccu.edu.tw
Unlike other techniques, Li et al. add control nodes and arcs for only elementary
siphons, thus reducing the number of control nodes and arcs required for deadlock control
in Petri net supervisors. Their method suffers from the expensive computation of all
SMS (Strict Minimal Siphons). We propose a graphic-algebra approach to compute elementary
siphons without the knowledge of SMS. We show that each SMS corresponds
to a strongly connected resource subnet (sub-SCC) whose characteristic T-vector £a can
be computed as a linear sum of that of all resource places in the subnet. An SMS includes
all resource places in the subnet plus all input operation places of transitions with
positive components in £a. We propose Algorithm 2 to find all sub-SCC. We prove that
any sub-SCC N¡¦, containing an elementary resource circuit c as a proper subset and N¡¦ =
N¡¨ ¡å c, N¡¨ ¡ä c = {r}, corresponds to a dependent siphon. Hence, elementary siphons are
closely related to (and can be constructed from) elementary (called basic) circuits and in
general, combinations of elementary circuits may contribute to elementary siphons. For a
simple basic subclass of S3PR (called BS3PR), the set of elementary siphons is identical
to that synthesized from elementary (basic) circuits. As a result, we simplify Algorithm 2
to find all elementary circuits. It is more efficient than traditional algorithms by terminating
earlier upon detecting that the net is not a BS3PR.
Received October 11, 2005; revised March 6 & May 18, 2006; accepted June 8, 2006.
Received September 23, 2005; revised November 2, 2006; accepted January 9, 2007.
Communicated by Chin-Teng Lin.