DocumentCode
2641258
Title
Polynomial order decomposition algorithms for free choice systems
Author
Nishimura, Tadaaki ; Lee, Dong-Ik S. ; Kumagai, Sadatoshi
Author_Institution
Osaka Gas Co., Japan
fYear
1993
fDate
27-29 Sep 1993
Firstpage
197
Lastpage
203
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;
fLanguage
English
Publisher
ieee
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
Type
conf
DOI
10.1109/ETFA.1993.396411
Filename
396411
Link To Document