| 講演名 | 2002/7/30 各トランジションの発火が2回以下である辺重み付きカクタスにおける発火系列探索 高原 伸水, 田岡 智志, 渡邉 敏正, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | ペトリネットの発火系列問題(LFS)とは,『ペトリネットN,初期マーキングM,発火回数ベクトルXが与えられたとき,Mから順次発火可能で各トランジションtが丁度X(t)回出現する発火系列σが存在するか否かを判定し,存在するならばそのような発火系列を求めよ.』と定義される.LFSを解くことは容易ではなく,単純な構造を持つペトリネットに対してもNP-困難であることが知られている.しかしながら,ペトリネットが辺重み付きカクタス構造で,かつX=1^^-の場合はO(|P|log|P|)時間で解けることが既に示されている.本稿では,その解法を拡張して,ペトリネットが辺重み付きカクタス構造で,かつ各トランジションtの発火回数X(t)が1または2の場合に,O(|P|log|P|)時間解法を提案する. |
| 抄録(英) | The legal firing sequence problem of Petri nets (LFS for short) is defined as follows. Given a Petri net N, an initial marking M and a firing count vector X, find a firing sequence (a sequence of transitions that can be fired through), starting from M, such that each transition t appears in σ exactly X(t) times as prescribed by X. Solving LFS generally is not easy, and it is NP-hard even if a given Petri net has very simple structure. An O(|P|log|P|) time algorithm for an edge-weighted cactus and X = 1^^- has been shown. In this paper we propose an O(|P|log|P|) time algorithm for an edge-weighted cactus and X with X(t) ≦ 2 for each transition t. |
| キーワード(和) | ペトリネット / 辺重み付きカクタス / 発火系列問題 / 多項式時間アルゴリズム |
| キーワード(英) | Petri nets / edge-weighted cactuses / legal firing sequence problem / polynomial time algorithms |
| 資料番号 | CST2002-15 |
| 発行日 |
| 研究会情報 | |
| 研究会 | CST |
|---|---|
| 開催期間 | 2002/7/30(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Concurrent System Technology (CST) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 各トランジションの発火が2回以下である辺重み付きカクタスにおける発火系列探索 |
| サブタイトル（和） | |
| タイトル（英） | Finding legal firing sequences of edge-weighted cactuses with each transition firing at most twice |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ペトリネット / Petri nets |
| キーワード(2)（和/英） | 辺重み付きカクタス / edge-weighted cactuses |
| キーワード(3)（和/英） | 発火系列問題 / legal firing sequence problem |
| キーワード(4)（和/英） | 多項式時間アルゴリズム / polynomial time algorithms |
| 第 1 著者 氏名（和/英） | 高原 伸水 / Shinsui TAKAHARA |
| 第 1 著者 所属（和/英） | 広島大学大学院 工学研究科 情報工学専攻 Graduate School of Engineering, Hiroshima University |
| 第 2 著者 氏名（和/英） | 田岡 智志 / Satoshi TAOKA |
| 第 2 著者 所属（和/英） | 広島大学大学院 工学研究科 情報工学専攻 Graduate School of Engineering, Hiroshima University |
| 第 3 著者 氏名（和/英） | 渡邉 敏正 / Toshimasa WATANABE |
| 第 3 著者 所属（和/英） | 広島大学大学院 工学研究科 情報工学専攻 Graduate School of Engineering, Hiroshima University |
| 発表年月日 | 2002/7/30 |
| 資料番号 | CST2002-15 |
| 巻番号（vol） | vol.102 |
| 号番号（no） | 259 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |