TY - JOUR
T1 - Some results and open problems concerning elementary siphons of petri nets
AU - Li, ZhiWu
AU - Zhou, Mengchu
PY - 2004/12/1
Y1 - 2004/12/1
N2 - Siphons are related to the liveness property of Petri net models of concurrent systems. Elementary siphons, an important concept proposed in our previous work, has been proved to be an effective way to characterize, analyze, and control deadlocks in these systems. This paper first surveys the existing results on elementary siphons of Petri nets. It is proved that the number of elementary siphons in a Petri net is bounded by the smaller of place count and transition count. We investigate the conditions under which there is no weakly dependent siphon in a Petri net. A polynomial algorithm is developed to decide the set of elementary siphons for the deadlock control purpose. Some interesting and open problems on elementary siphons are finally discussed.
AB - Siphons are related to the liveness property of Petri net models of concurrent systems. Elementary siphons, an important concept proposed in our previous work, has been proved to be an effective way to characterize, analyze, and control deadlocks in these systems. This paper first surveys the existing results on elementary siphons of Petri nets. It is proved that the number of elementary siphons in a Petri net is bounded by the smaller of place count and transition count. We investigate the conditions under which there is no weakly dependent siphon in a Petri net. A polynomial algorithm is developed to decide the set of elementary siphons for the deadlock control purpose. Some interesting and open problems on elementary siphons are finally discussed.
UR - http://www.scopus.com/inward/record.url?scp=15744368025&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=15744368025&partnerID=8YFLogxK
M3 - Article
AN - SCOPUS:15744368025
SN - 1062-922X
VL - 2
SP - 1717
EP - 1722
JO - Conference Proceedings - IEEE International Conference on Systems, Man and Cybernetics
JF - Conference Proceedings - IEEE International Conference on Systems, Man and Cybernetics
ER -