| 講演名 | 2014/1/23 禁止枝ペトリネットの最大発火系列問題に関する可解性 : 重みなし/あり無競合ペトリネット 田岡 智志, 落岩 諭, 渡邉 敏正, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本論文の主題は,抑止ペトリネットINの最大発火系列問題(MAX-INLFS)である.INが抑止辺を持たない場合のMAX-INLFSをMAX-LFSとする.INの台ペトリネットNとは,INから抑止辺を除いたペトリネットである.抑止ペトリネットのモデル化能力はチューリングマシンと同等であることが知られており,MAX-INLFSは可達問題,最小初期資源配置問題,(Level 4の)活性問題、スケジューリング問題などペトリネットの基本的問題に広く応用を持つ.本論文では、INの台ペトリネットが重みありマークグラフで、INが抑止辺が接続するプレース(リベットと呼ぶ)を1つ持つときにMAX-INLFSをO(|P||X|)時間で解くことができることを証明し、そして、INの台ペトリネットが重みあり無競合ペトリネットでINがリベットをただ1つ持つときに、MAX-INLFSがNP-hardであることを示す. |
| 抄録(英) | The subject of this paper is the maximum legal firing sequence problem (MAX-INLFS) for inhibitor-arc Petri nets IN. Let MAX-LFS denote MAX-INLFS in which IN has no inhibitor arcs. The underlying Petri net TV of /TV is a Petri net with all inhibitor arcs removed from IN. It is well-known that modeling capability of inhibitor-arc Petri nets is equivalent to that of Turing machines, and MAX-INLFS has wide applications to fundamental problems of Petri net such as the marking reachability problem, the minimum initial resource allocation problem, the liveness (of level 4) problem, the scheduling problem, and so on. This paper proves that MAX-INLFS can be solved in O(|P||X|) time when the underlying Petri net TV of IN is a weighted marked graph and IN has only one place (called a rivet) to which at least one inhibitor-arc is incident, and shows that MAX-INLFS is NP-hard when the underlying Petri net TV of IN is a weighted conflict-free Petri net and /TV has only one rivet. |
| キーワード(和) | ペトリネット / 発火系列問題 / 可達問題 / 抑止辺 / 抑止ペトリネット |
| キーワード(英) | Petri nets / legal firing sequence problems reachability problems / inhibitor arcs / inhibitor Petri nets |
| 資料番号 | SS2013-55,MSS2013-58 |
| 発行日 |
| 研究会情報 | |
| 研究会 | SS |
|---|---|
| 開催期間 | 2014/1/23(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Software Science (SS) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 禁止枝ペトリネットの最大発火系列問題に関する可解性 : 重みなし/あり無競合ペトリネット |
| サブタイトル（和） | |
| タイトル（英） | Solvability for The Maximum Legal Firing Sequence Problem of Inhibitor-Arc Petri nets : Unweighted/Weighted Conflict-Free Petri nets |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ペトリネット / Petri nets |
| キーワード(2)（和/英） | 発火系列問題 / legal firing sequence problems reachability problems |
| キーワード(3)（和/英） | 可達問題 / inhibitor arcs |
| キーワード(4)（和/英） | 抑止辺 / inhibitor Petri nets |
| キーワード(5)（和/英） | 抑止ペトリネット |
| 第 1 著者 氏名（和/英） | 田岡 智志 / Satoshi TAOKA |
| 第 1 著者 所属（和/英） | 広島大学 Hiroshima University |
| 第 2 著者 氏名（和/英） | 落岩 諭 / Satoru OCHIIWA |
| 第 2 著者 所属（和/英） | 広島大学大学院工学研究科情報工学専攻 Hiroshima University |
| 第 3 著者 氏名（和/英） | 渡邉 敏正 / Toshimasa WATANABE |
| 第 3 著者 所属（和/英） | 広島大学 Hiroshima University |
| 発表年月日 | 2014/1/23 |
| 資料番号 | SS2013-55,MSS2013-58 |
| 巻番号（vol） | vol.113 |
| 号番号（no） | 422 |
| ページ範囲 | pp.- |
| ページ数 | 5 |
| 発行日 | |