文献

J-GLOBAL ID：201102266526862651   整理番号：11A1937766

構造的に弱く永続的なネットについて確かめるのはCo-Np完全である

Verifying Structurally Weakly Persistent Net Is Co-NP Complete

著者 (2件)： OHTA Atsushi (Fac. of Information Sci. and Technol., Aichi Prefectural Univ.) ,  TSUJI Kohkichi (Fac. 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))
巻： E94-A  号： 12  ページ： 2832-2835 (J-STAGE)  発行年： 2011年 
JST資料番号： F0699C  ISSN： 0916-8508  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： Petriネットは並行システムのための強力なモデリングツールである。Petriネットのサブクラスは,より少ない計算コストで,ある現実的なアプリケーションをモデル化するために示される。構造的に弱く永続的なネット(SWPN)は,活性が決定性多項式時間において確かめられるようなサブクラスの1つである。この報告書は。与えられたネットがSWPNであるかどうか確かめるための計算量を検討する。3UNSAT問題は,ネットがSWPNでないかどうか確かめるための問題に減少する。これはSWPNの検認問題のco-NPの完全性を含意する。(翻訳著者抄録)

シソーラス用語： *Petriネット ,  モデリング ,  NP完全問題 ,  計算理論 ,  時間 ,  原価 ,  計算コスト
準シソーラス用語： *多項式時間

分類 (1件)： 計算機利用技術一般  (JE01000C)

引用文献 (10件)：

• MURATA, T. Petri nets : Properties, analysis and applications. Proc. IEEE. 1989, 77, 4, 541-580
• JONES, N. D. Complexity of some problems in Petri nets. Theor. Comput. Sci. 1977, 4, 277-299
• OHTA, A. POC net, a subclass of Petri nets, and its application to timed Petri nets. Int. J. Syst. Sci. 1993, 24, 3, 539-552
• HOWELL, R. R. Normal and sinkless petri nets. J. Comput. Syst. Sci. 1993, 46, 1-26
• OHTA, A. Computational complexity of liveness problem of normal Petri net. IEICE Trans. Fundamentals, A. 2009, E92, 11, 2717-2722

タイトルに関連する用語 (1件)： ネット