TY - GEN
T1 - Enumeration algorithms for maximal perfect-resource-transition circuits and strict minimal siphons i
AU - Xing, Keyi
AU - Zhou, Meng Chu
PY - 2008
Y1 - 2008
N2 - Resource-transition circuits (RTCs) and siphons are related to the deadlock problem and liveness control problem in Petri net models of automated manufacturing systems. This paper will concentrate on a particular type of Petri nets called systems of sequential processes with resources (S3PRs) and solves the RTC and siphon enumeration problems. A graph-based technique is first used to find all elementary RTC structures. Any RTC can be expressed as a union of some elementary RTCs. Then, an iterative method is developed to recursively construct all maximal perfect-resource-transition circuits (MPCs), which can lead the system to deadlock, from the elementary RTCs. Finally, by the one-to-one correspondence between strict minimal siphons and MPCs, a new algorithm is obtained to compute strict minimal siphons in S3PRs.
AB - Resource-transition circuits (RTCs) and siphons are related to the deadlock problem and liveness control problem in Petri net models of automated manufacturing systems. This paper will concentrate on a particular type of Petri nets called systems of sequential processes with resources (S3PRs) and solves the RTC and siphon enumeration problems. A graph-based technique is first used to find all elementary RTC structures. Any RTC can be expressed as a union of some elementary RTCs. Then, an iterative method is developed to recursively construct all maximal perfect-resource-transition circuits (MPCs), which can lead the system to deadlock, from the elementary RTCs. Finally, by the one-to-one correspondence between strict minimal siphons and MPCs, a new algorithm is obtained to compute strict minimal siphons in S3PRs.
KW - Automata, Petri Nets and other tools
KW - Discrete event systems modeling and control
UR - http://www.scopus.com/inward/record.url?scp=79961017757&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79961017757&partnerID=8YFLogxK
U2 - 10.3182/20080706-5-KR-1001.4069
DO - 10.3182/20080706-5-KR-1001.4069
M3 - Conference contribution
AN - SCOPUS:79961017757
SN - 9783902661005
T3 - IFAC Proceedings Volumes (IFAC-PapersOnline)
BT - Proceedings of the 17th World Congress, International Federation of Automatic Control, IFAC
T2 - 17th World Congress, International Federation of Automatic Control, IFAC
Y2 - 6 July 2008 through 11 July 2008
ER -