正規Petriネットの活性問題の計算量

OHTA Atsushi; TSUJI Kohkichi

文献

J-GLOBAL ID：200902219774930977 整理番号：09A1152405

正規Petriネットの活性問題の計算量

Computational Complexity of Liveness Problem of Normal Petri Net

出版者サイト複写サービスで全文入手 {{ this.onShowCLink("http://jdream3.com/copy/?sid=JGLOBAL&noSystem=1&documentNoArray=09A1152405&COPY=1") }}
高度な検索・分析はJDreamⅢで {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=09A1152405&from=J-GLOBAL&jstjournalNo=F0699C") }}

著者 (2件)： ,
資料名：
巻： E92-A 号： 11 ページ： 2717-2722 発行年： 2009年11月01日
JST資料番号： F0699C ISSN： 0916-8508 資料種別：逐次刊行物 (A)
記事区分：原著論文発行国：日本 (JPN) 言語：英語 (EN)

Petriネットは,並行システムの強力なモデル化ツールである。ローカルなデッドロックが存在しないことを検証する問題である活性は,解析するPetriネットの最重要問題の一つである。一般Petriネットの活性の計算量は,決定性指数空間である。活性は,Petriネットのサブクラスに対し研究され,計算量の少なくて済む必要十分条件が求められている。これらは,サイホンと呼ぶプレースの部分集合を使用して主に行われている。各サイホンが各可到達マーキングにトークンを持つことを表すCS特性は,活性解析における鍵となる特性の一つである。その一方で,正規Petriネットは,可到達性が効果的に計算可能なPetriネットのサブクラスである。本論文は,正規Petriネットの活性問題の計算量を研究する。最初に,正規Petriネットの活性はCS特性に等価であることを示す。次にこの問題はco-NP完全であることを,非活性に対する非決定性アルゴリズムを求めることにより示すが,これはHowellらが示唆した活性に対するアルゴリズムと類似している。最後に,活性とCS特性が等価である有界Petriネットの構造的特徴を研究する。この考察から,有界正規Petriネットの活性問題は,決定性多項式時間計算量であることを示す。(翻訳著者抄録)

, , , , , , , , , , , , , , , ,
, ,

システム・制御理論一般 , 計算理論

引用文献 (13件)：

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
ESPARZA, J. A polynomial-time algorithm to decide liveness of bounded free choice nets. Theor. Comput. Sci. 1992, 102, 185-205
BARKAOUI, K. On the equivalence between liveness and deadlock-freeness in Petri nets. Applications and Theory of Petri Nets 2005. 2005, 90-107
MATSUMOTO, T. Necessary and sufficient condition of structural liveness for general Petri nets-Virtual deadlock-trap properties. IEICE Trans. Fundamentals, A. 1995, E78, 12, 1862-1874

, , ,

前のページに戻る