In: Proceedings of the IEEE International Symposium on Circuits and Systems, 1989, Portland, OR, USA; Vol. 1, pages 323-326. New York, NY, USA: IEEE, 1989.
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.
Keywords: free-choice net; persistent net; legal firing sequence; minimum initial marking.