Polynomial order decomposition algorithms for free choice systems
Tadaaki Nishimura, D.-I.S. Lee, Satoshi Kumagai · 2002
An O(m/sup 2/n/sup 2/) 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(m/sup 2/n/sup 2/+mn/sup 3/) 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.>