Title :
Legal firing sequence and related problems of Petri nets
Author :
Watanabe, Toshimasa ; Mizobata, Yutaka ; Onaga, Kenji
Author_Institution :
Fac. of Eng., Hiroshima Univ., Japan
Abstract :
Development of computational tools and techniques dealing with large-scale Petri nets will provide a firm foundation of Petri net theory. A discussion is presented of the computational complexity aspect of the legal firing sequence problem (LFS) and some related problems of Petri nets, each having applications to practical problems. Their NP-completeness and polynomial-time solvability are presented
Keywords :
Petri nets; computational complexity; NP-completeness; Petri nets; computational complexity; computational tools; legal firing sequence; polynomial-time solvability; Computational complexity; Concurrent computing; Fires; Large-scale systems; Law; Legal factors; Petri nets; Polynomials; Search problems;
Conference_Titel :
Petri Nets and Performance Models, 1989. PNPM89., Proceedings of the Third International Workshop on
Conference_Location :
Kyoto
DOI :
10.1109/PNPM.1989.68561
