文献

J-GLOBAL ID：201502244276159076   整理番号：15A0745206

ワークフローネットの状態数計算問題

State Number Calculation Problem of Workflow Nets

著者 (2件)： BIN AHMADON Mohd Anuaruddin (Graduate School of Sci. and Engineering, Yamaguchi Univ.) ,  YAMAGUCHI Shingo (Graduate School of Sci. and Engineering, Yamaguchi Univ.)
資料名： IEICE Transactions on Information and Systems (Web)  (IEICE Transactions on Information and Systems (Web))
巻： E98.D  号： 6  ページ： 1128-1136 (J-STAGE)  発行年： 2015年 
JST資料番号： U0469A  ISSN： 1745-1361  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 状態数はPetriネット解析におけるモデル検査方式の大変重要な問題である。最初に状態数計算問題の形式的定義を付与した:初期状態(マーク)を有するPetriネットに関して,それは幾つの状態を持つか。次に,P≠NPなら,自由選択ワークフローネットとして知られるPetriネットの一般サブクラスに関して,問題を多項式時間で解けないことを示した。その上で,プロセス木と呼ぶ表現バイアスを用いて問題を解く,多項式時間アルゴリズムを提案した。また,適用事例を通してアルゴリズムの有効性を示した。(翻訳著者抄録)

シソーラス用語： *Petriネット ,  フローグラフ ,  定理証明 ,  *状態推定 ,  可能性 ,  *計算量 ,  *モデル検査 ,  状態 ,  木【グラフ】 ,  計算理論 ,  システムモデル
準シソーラス用語： ワークフローネット ,  多項式時間アルゴリズム ,  可解性 ,  計算複雑性 ,  状態空間モデル

分類 (2件)： 計算理論  (JB02000A) ,  ネットワーク法  (KA03040X)

引用文献 (20件)：

• [1] T. Murata, “Petri nets: Properties, analysis and applications,” Proc. IEEE, vol.77, no.4, pp.541-580, 1989.
• [2] G.J. Holzmann, The SPIN Model Checker: Primer and Reference Manual, Addison-Wesley, 2004.
• [3] D.Y. Chao and Y. Fang, “Number of reachable states for simple classes of Petri nets,” Proc. IECON 2011, pp.3788-3791, 2011.
• [4] W.M.P. van der Aalst and K.M. van Hee, Workflow Management: Models, Methods, and Systems, The MIT Press, 2002.
• [5] W.M.P. van der Aalst, J.C.A.M. Buijs, and B.F. van Dongen, “Towards improving the representational bias of process mining,” Lecture Notes in Business Information Processing, vol.116, pp.39-54, 2012.

タイトルに関連する用語 (2件)： ワークフローネット ,  計算