| 講演名 | 2001/7/17 ACネットの有界活性問題のNP困難性 太田 淳, 辻 孝吉, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | ペトリネットはコンカレントシステムのモデルの一つである。活性問題はペトリネットの最も重要な解析問題の一つである。一般のペトリネットの活性問題の計算量は、決定性指数領域困難であることが知られている。ペトリネットのサブクラスの活性問題の計算量については、有界な自由選択(EFC)ネットの活性問題が決定性多項式時間で解けること、非有界EFCネットの活性問題がNP完全であることが知られている。EFCを包含するクラスである非対称選択(AC)ネットについては非有界ACネットの活性問題はNP困難であるが、有界なACネットについては著者らの知る限り、未解決である。本報告は、論理式の充足可能性問題が有界なACネットの活性問題に多項式時間で帰着可能であることから、この問題はNP困難であることが示される。 |
| 抄録(英) | Petri net is a mathematical model for concurrent systems. Liveness is one of important properties of Petri net. Liveness problem of general Petri net is of exponential space complexity and subclasses are suggested with less computational complexity. It is well known that liveness problem of bounded free choice(EFC)net is solved in deterministic polynomial time. It is also known that liveness problem of general(unbounded)EFC net is NP-complete. This paper treats leveness problem of asymmetric choice(AC)nets. This class properly includes the class of free choice nets, so that liveness problem of general AC net is NP-hard. However, as far as the authors know, computational complexity of liveness problem of bounded AC net has been open problem. It is shown that satisfiability problem of boolean expressions is polynomial time reducible to liveness problem of bounded AC nets. This implies that the problem is NP-hard. |
| キーワード(和) | コンカレントシステム / ペトリネット / 活性 / 計算量 |
| キーワード(英) | concurrent system / Petri net / liveness / computational complexity |
| 資料番号 | CST2001-14 |
| 発行日 |
| 研究会情報 | |
| 研究会 | CST |
|---|---|
| 開催期間 | 2001/7/17(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Concurrent System Technology (CST) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | ACネットの有界活性問題のNP困難性 |
| サブタイトル（和） | |
| タイトル（英） | NP-Hardness of Liveness Problem of Bounded Asymmetric Choice Nets |
| サブタイトル（和） | |
| キーワード(1)（和/英） | コンカレントシステム / concurrent system |
| キーワード(2)（和/英） | ペトリネット / Petri net |
| キーワード(3)（和/英） | 活性 / liveness |
| キーワード(4)（和/英） | 計算量 / computational complexity |
| 第 1 著者 氏名（和/英） | 太田 淳 / Atsushi OHTA |
| 第 1 著者 所属（和/英） | 愛知県立大学情報科学部 Faculty of Information Science and Technology, Aichi Prefectural University |
| 第 2 著者 氏名（和/英） | 辻 孝吉 / Kohkichi TSUJI |
| 第 2 著者 所属（和/英） | 愛知県立大学情報科学部 Faculty of Information Science and Technology, Aichi Prefectural University |
| 発表年月日 | 2001/7/17 |
| 資料番号 | CST2001-14 |
| 巻番号（vol） | vol.101 |
| 号番号（no） | 212 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |