Enumeration algorithms for maximal perfect-resource-transition circuits and strict minimal siphons i

Keyi Xing, Meng Chu Zhou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 17th World Congress, International Federation of Automatic Control, IFAC
Edition1 PART 1
DOIs
StatePublished - Dec 1 2008
Event17th World Congress, International Federation of Automatic Control, IFAC - Seoul, Korea, Republic of
Duration: Jul 6 2008Jul 11 2008

Publication series

NameIFAC Proceedings Volumes (IFAC-PapersOnline)
Number1 PART 1
Volume17
ISSN (Print)1474-6670

Other

Other17th World Congress, International Federation of Automatic Control, IFAC
CountryKorea, Republic of
CitySeoul
Period7/6/087/11/08

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering

Keywords

  • Automata, Petri Nets and other tools
  • Discrete event systems modeling and control

Fingerprint Dive into the research topics of 'Enumeration algorithms for maximal perfect-resource-transition circuits and strict minimal siphons i'. Together they form a unique fingerprint.

Cite this