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
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;
Conference_Titel :
Circuits and Systems, 1989., IEEE International Symposium on
Conference_Location :
Portland, OR
DOI :
10.1109/ISCAS.1989.100356
