In: PNPM89. Proceedings of the Third International Workshop On Petri Nets and Performance Models, 1989, Kyoto, Japan, pages 277-286. Los Alamitos, CA, USA: IEEE Computer Society Press, 1990.
Abstract: Development of computational tools and techniques dealing with large Petri nets will certainly contribute to providing a firm foundation of Petri net theory. From this motivation, the authors discuss computational complexity aspect of the legal firing sequence problem and some related problems, each having applications to practical problems. Their NP-completeness and polynomial-time solvability are presented.
Keywords: complexity (of) legal firing sequence problem.