文献

J-GLOBAL ID：201302277142553542   整理番号：13A1574657

WS³PRの活性:複雑性および決定

The Liveness of WS³PR: Complexity and Decision

著者 (4件)： LIU Guanjun (ISTD, Singapore Univ. of Technol. and Design) ,  JIANG Changjun (Key Lab. of the Ministry of Education for Embedded System and Serv. Computing, Tongji Univ.) ,  ZHOU Mengchu (Dep. of Electrical and Computer Engineering, New Jersey Inst. of Technol.) ,  OHTA Atsushi (School of Information Sci. and Technol., Aichi Prefectural Univ.)
資料名： IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (Institute of Electronics, Information and Communication Engineers)  (IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (Institute of Electronics, Information and Communication Engineers))
巻： E96-A  号： 8  ページ： 1783-1793 (J-STAGE)  発行年： 2013年 
JST資料番号： F0699C  ISSN： 0916-8508  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： Petriネットは,デッドロックにおける資源割付および高精度特性評価における自然記述能力により資源割付に関連する同時進行システムに広く応用されている公式言語の一つである。WS³PR(資源による単純逐次プロセスの重みづけシステム)は,多くの資源割付システムをモデル化することができる重要なサブクラスPetriネットである。そこでは,1)多重プロセスを並列実行可能であり,2)各プロセスの各実行ステップは単一資源タイプからの多重ユニットを用いるが,多重資源タイプを用いることはできない。本論文では,最初にWS³PRの活性問題が分割問題に基づき共NP困難であることを報告した。さらに,SCW(構造的円形ウェイト)およびBM(ブロッキングマーキング)と呼ぶ二つの新しい概念に基づくWS³PR活性のための必要十分条件を示した。ここで各SCWがBMをもっていない場合,WS³PRは活性である。これに加え,他のサイフォンベース方式との比較でデッドロック問題を解析するためSCW使用の複数利点を示した。これらの結果は,WS³PRのためのデッドロック防止あるいは回避に関するさらなる研究にとって貴重である。(翻訳著者抄録)

シソーラス用語： シーケンシャル処理 ,  *重みづけ ,  資源割付 ,  *活性 ,  計算量 ,  NP困難 ,  十分条件 ,  必要条件 ,  サイフォン ,  デッドロック ,  *Petriネット
準シソーラス用語： 必要十分条件

分類 (1件)： 数理言語学  (JB05000V)

引用文献 (32件)：

• [1] W.M.P. van der Aalst, K. van Hee, A. ter Hofstede, N. Sidorova, H. Verbeek, M. Voorhoeve, and M. Wynn, “Soundness of workflow nets: Classification, decidability, and analysis,” Formal Aspects Computing, vol.23, pp.333-363, 2011.
• [2] K. Barkaoui, A. Chaoui, and B. Zouari, “Supervisory control of discrete event systems based on structure theory of Petri nets,” Proc. IEEE Int. Conf. Syst. Man Cybern., pp.3750-3755, 1997.
• [3] K. Barkaoui and J. Pradat-Peyre, “On liveness and controlled siphons in Petri nets,” Lect. Notes Comput. Sci., vol.1091, pp.57-72, 1996.
• [4] R.R. Brooks, M. Zhu, J. Lamb, and S.S. Iyengar, “Aspect-orienteddesign of sensor networks,” J. Parallel Distrib. Comput., vol.64, pp.853-865, 2004.
• [5] A. Cheng, J. Esparza, and J. Palsberg, “Complexity results for 1-safe nets,” Theor. Comput. Sci., vol.147, pp.117-136, 1995.

タイトルに関連する用語 (2件)： 活性 ,  複雑性