文献

J-GLOBAL ID：201802210848485182   整理番号：18A1365214

ワークフローネットにおける応答特性問題の計算複雑性と多項式時間手順

Computational Complexity and Polynomial Time Procedure of Response Property Problem in Workflow Nets

著者 (3件)： BIN AB MALEK Muhammad Syafiq (Graduate School of Science and Technology for Innovation, Yamaguchi University) ,  BIN AHMADON Mohd Anuaruddin (Graduate School of Science and Technology for Innovation, Yamaguchi University) ,  YAMAGUCHI Shingo (Graduate School of Science and Technology for Innovation, Yamaguchi University)
資料名： IEICE Transactions on Information and Systems (Web)  (IEICE Transactions on Information and Systems (Web))
巻： E101.D  号： 6  ページ： 1503-1510(J-STAGE)  発行年： 2018年 
JST資料番号： U0469A  ISSN： 1745-1361  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 応答特性は一種の活性特性である。応答特性問題を,2つの活性αとβを与えると,αが実行される時は常にβはいつもその後に実行されるか?と定義した。本論文では,ワークフローPetriネット(略してWFネット)に関する問題に取り組んだ。著者らの結果は,(i)非環式WFネットに対する応答特性問題は決定可能であり,(ii)非環式非対称選択(AC)WFネットに関する問題は取扱困難であり,(iii)非環式ブリッジなしの良く構造化されたWFネットに対する問題は多項式時間で解けることだった。応用例による手順の有用性を示した。(翻訳著者抄録)

シソーラス用語： *Petriネット ,  *計算量 ,  計算理論 ,  時間 ,  *応答特性 ,  非対称性 ,  活性 ,  構造形成
準シソーラス用語： *ワークフローネット ,  *計算複雑性 ,  構造化 ,  多項式時間

著者キーワード (5件)： 応答特性 ,  Petriネット ,  プロセスツリー ,  計算の複雑さ ,  多項式時間アルゴリズム

分類 (3件)： その他の計算機利用技術  (JE14000C) ,  計算理論  (JB02000A) ,  グラフ理論基礎  (IA02020S)

引用文献 (11件)：

• [1] T. Murata, “Petri nets: Properties, analysis and applications,” Proc. IEEE, vol.77, no.4, pp.541-580, 1989. 10.1109/5.24143
• [2] O.E. Hichami, M.A. Achhab, I. Berrada, R. Oucheikh, B.E.E. Mohajir, “An approach of optimization and formal verification of workflow Petri nets,” Journal of Theoretical and Applied Information Technology, vol.61, no.3, pp.486-495, 2014.
• [3] S. Yamaguchi, “Polynomial time verification of reachability in sound extended free-choice workflow net,” IEICE Trans. Fundamentals, vol.E97-A, no.2, pp.468-475, Feb. 2014. 10.1587/transfun.e97.a.468
• [4] W.M.P. van der Aalst and K.M. van Hee, Workflow Management: Models, Methods, and Systems, The MIT Press, 2002.
• [5] W. van der Aalst, J. Buijs, and B. van Dongen, “Towards improving the representational bias of process mining,” Data-Driven Process Discovery and Analysis, Lecture Notes in Business Information Processing, vol.116, pp.39-54, Springer-Verlag, Berlin, 2012. 10.1007/978-3-642-34044-4_3

タイトルに関連する用語 (6件)： ワークフローネット ,  応答特性 ,  問題 ,  計算複雑性 ,  多項式時間 ,  手順