Legal firing sequences and minimum initial markings for Petri nets
Takuo Watanabe, Y. Mizobata, Kenji Onaga · 2003
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.>