DocumentCode
1621133
Title
Legal firing sequences and minimum initial markings for Petri nets
Author
Watanabe, Toshimasa ; Mizobata, Yutaka ; Onaga, Kenji
Author_Institution
Fac. of Eng., Hiroshima Univ., Japan
fYear
1989
Firstpage
323
Abstract
Computational complexity and approximation algorithms for the legal firing sequence (LFS) and minimum initial marking (MIM) problem for a Petri net PN are discussed. The NP-completeness of LFS for a consistent free-choice net PN with an elementary T-invariant is proved, and an algorithm for LFS with PN restricted to a persistent Petri net is given. It is also shown that MIM is NP-complete even if PN is a weakly connected marked graph with each node having a total in-degree and out-degree of at most three. Some approximation algorithms for MIM are proposed
Keywords
Petri nets; approximation theory; computational complexity; NP-completeness; Petri nets; approximation algorithms; consistent free-choice net; elementary T-invariant; in-degree; legal firing sequence; minimum initial markings; out-degree; weakly connected marked graph; Approximation algorithms; Computational complexity; Graph theory; Law; Legal factors; Petri nets; Terminology;
fLanguage
English
Publisher
ieee
Conference_Titel
Circuits and Systems, 1989., IEEE International Symposium on
Conference_Location
Portland, OR
Type
conf
DOI
10.1109/ISCAS.1989.100356
Filename
100356
Link To Document