http://iet.metastore.ingenta.com
1887

Incremental approach to computation of elementary siphons for arbitrary simple sequential processes with resources

Incremental approach to computation of elementary siphons for arbitrary simple sequential processes with resources

For access to this article, please select a purchase option:

Buy article PDF
$19.95
(plus tax if applicable)
Buy Knowledge Pack
10 articles for $120.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IET Control Theory & Applications — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

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. 1)
    2. 2)
      • D.Y. Chao . An incremental approach to extract minimal bad siphons. J. Inf. Sci. , 1 , 203 - 214
    3. 3)
      • 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.
    4. 4)
      • 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.
    5. 5)
    6. 6)
      • 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
    7. 7)
      • 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
    8. 8)
      • 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.
    9. 9)
    10. 10)
      • D.Y. Chao . Petri net synthesis and synchronization using knitting technique. J. Inf. Sci. Eng. , 543 - 568
    11. 11)
      • 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
    12. 12)
    13. 13)
      • D.Y. Chao . A graphic-algebraic computation of elementary siphons of BS3PR. J. Inf. Sci. , 6 , 1817 - 1831
    14. 14)
      • D.Y. Chao , Z. Li . On structural conditions of S3PR nets without weakly dependent siphons. IEEE Trans. Syst. Man Cybern. A.
    15. 15)
      • 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.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cta_20070130
Loading

Related content

content/journals/10.1049/iet-cta_20070130
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
This is a required field
Please enter a valid email address