文献

J-GLOBAL ID：201402255821805864   整理番号：14A0273844

禁止枝ペトリネットの最大発火系列問題に関する可解性 重みなし/あり無競合ペトリネット

Solvability for The Maximum Legal Firing Sequence Problem of Inhibitor-Arc Petri nets: Unweighted/Weighted Conflict-Free Petri nets

著者 (3件)： TAOKA Satoshi (Hiroshima Univ., Higashi-Hiroshima, JPN) ,  OCHIIWA Satoru (Hiroshima Univ., Higashi-Hiroshima, JPN) ,  WATANABE Toshimasa (Hiroshima Univ., Higashi-Hiroshima, JPN)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 113  号： 422(SS2013 48-71)  ページ： 41-45  発行年： 2014年01月23日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 本論文の主題は,抑止ペトリネットINの最大発火系列問題(MAX-INLFS)である。INが抑止辺を持たない場合のMAX-INLFSをMAX-LFSとする。INの台ペトリネットNとは,INから抑止辺を除いたペトリネットである。抑止ペトリネットのモデル化能力はチューリングマシンと同等であることが知られており,MAX-INLFSは可達問題,最小初期資源配置問題,(Level4の)活性問題,スケジューリング問題などペトリネットの基本的問題に広く応用を持つ。本論文では,INの台ペトリネットが重みありマークグラフで,INが抑止辺が接続するプレース(リベットと呼ぶ)を1つ持つときにMAX-INLFSをO(|P||X|)時間で解くことができることを証明し,そして,INの台ペトリネットが重みあり無競合ペトリネットでINがリベットをただ1つ持つときに,MAX-INLFSがNP-hardであることを示す。(著者抄録)

シソーラス用語： *Petriネット ,  問題 ,  システム ,  可能性 ,  *重みづけ ,  *抑制 ,  競争 ,  Turing機械 ,  モデリング ,  資源割付
準シソーラス用語： *可解性 ,  *発火系列問題

分類 (2件)： ネットワーク法  (KA03040X) ,  オートマトン理論  (JB04000O)

タイトルに関連する用語 (8件)： 禁止 ,  枝 ,  ペトリネット ,  発火 ,  系列 ,  問題 ,  可解性 ,  競合