Title :
Polynomial order decomposition algorithms for free choice systems
Author :
Nishimura, Tadaaki ; Lee, Dong-Ik S. ; Kumagai, Sadatoshi
Author_Institution :
Osaka Gas Co., Japan
Abstract :
An O(m2n2) algorithm to find an S-decomposition of a live and bounded free choice (LSFC) net or (live and safe free choice) (LBFC) net is obtained. A polynomial order algorithm to find a T-decomposition can be constructed easily based on the algorithm. An O(m2n2+mn3) algorithm to find an LSFC net is proposed. Many analysis problems of concurrent systems modeled by free choice net can be solved efficiently based on the proposed algorithms
Keywords :
Petri nets; computational complexity; LSFC net; Petri nets; S-decomposition; concurrent systems; free choice systems; live and bounded free choice net; live and safe free choice; polynomial order decomposition algorithm; Bismuth; Computational complexity; Embedded computing; Polynomials;
Conference_Titel :
Emerging Technologies and Factory Automation, 1993. Design and Operations of Intelligent Factories. Workshop Proceedings., IEEE 2nd International Workshop on
Conference_Location :
Palm Cove-Cairns, Qld.
Print_ISBN :
0-7803-0985-5
DOI :
10.1109/ETFA.1993.396411
