| 講演名 | 1994/1/26 マークグラフにおけるトランジションの潜在的同時発火可能性判定アルゴリズム 高橋 正毅, 荒木 俊郎, 柏原 敏伸, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | ペトリネットにおける潜在的同時発火可能性判定問題とは,初期マーキングを持つペトリネットとペトリネット中の複数個のトランジションの集合Aが指定されたとき,初期マーキングから到達可能なマーキングの集合の要素で,Aのすべてのトランジションが発火可能であるようなマーキングが存在するか否かを判定する問題である.一般にペトリネットについてのこの問題はNP因難であるが,部分クラスであるマークグラフに限定した場合について,|A|=2のときは,時間計算量Ο(|F|)のアルゴリズムが知られている.本論文では,この結果を拡張し,マークグラフに対して,|F|をアークの総数とすると,Ο(|A||F|+|A|)の時間計算量で判定するアルゴリズムを示す. |
| 抄録(英) | Concurrent firability problem for a Petri net is defined as follows:given a transition set A,decide whether or not there exists a reachable marking from initial marking at which all transitions in A are enabled. It is known that there exists an Ο( F )time algorithm for concur rent firabihtv problem when the given Petri net is in a subclass of Petri net called marked graph and number of all arcs in the marked graph. In this paper,we extend the above result and present an Ο( A )time decision algorithm for marked graphs. |
| キーワード(和) | ペトリネット / マークグラフ / 潜在的同時発火可能性 |
| キーワード(英) | Petri net / marked graph / concument firability |
| 資料番号 | COMP93-76 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1994/1/26(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | マークグラフにおけるトランジションの潜在的同時発火可能性判定アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | An algorithm to decide concurrent firability for a marked qraph |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ペトリネット / Petri net |
| キーワード(2)（和/英） | マークグラフ / marked graph |
| キーワード(3)（和/英） | 潜在的同時発火可能性 / concument firability |
| 第 1 著者 氏名（和/英） | 高橋 正毅 / Masaki Takahashi |
| 第 1 著者 所属（和/英） | 大阪大学基礎工学部情報工学科 Department of information and computer scicnce,faculty of engineering science,Osaka University |
| 第 2 著者 氏名（和/英） | 荒木 俊郎 / Toshiro Araki |
| 第 2 著者 所属（和/英） | 大阪大学基礎工学部情報工学科 Department of information and computer scicnce,faculty of engineering science,Osaka University |
| 第 3 著者 氏名（和/英） | 柏原 敏伸 / Toshinobu Kashiwabara |
| 第 3 著者 所属（和/英） | 大阪大学基礎工学部情報工学科 Department of information and computer scicnce,faculty of engineering science,Osaka University |
| 発表年月日 | 1994/1/26 |
| 資料番号 | COMP93-76 |
| 巻番号（vol） | vol.93 |
| 号番号（no） | 438 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |