| 講演名 | 1999/1/28 枝重み付きカクタスに対する発火系列問題の解法 岩本 道尚, 藤戸 敏弘, 田岡 智志, 渡邉 敏正, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | ペトリネットの発火系列問題とは, 与えられた初期マーキングから順次発火できるトランジションの系列で, 各トランジションが予め指定された回数(発火回数と呼ぶ)だけ出現するものを見つける問題である.トランジションの入出力枝がそれぞれ1本以下であるペトリネットをステートマシンと呼ぶ.カクタスとは, ステートマシン構造をもち, 枝の向きを無視したグラフで任意の2つの単純サイクルが高々1つのプレースを共有し, 且つその様な(無向)単純サイクルが実際に有向サイクルとなっているペトリネットのことである.本稿では, 任意の枝について枝重みを許したカクタスに対する発火系列問題は, 各トランジションの発火回数を1回と制限した場合に多項式時間で解けることを示す. |
| 抄録(英) | The Legal Firing Sequence problem of Petri nets(LFS for short)is defined by "Given a Petri net N, an initial marking M and a firing count vector X, find a firing sequence σ, starting from M, such that each transition t appears in σ exactly X(t)times as prescribed by X."A cactus N' is a state machine such that, when edge-directions are ignored, any pair of simple cycles share at most one place and every such(undirected)simple cycle is really a directed cycle in N'. We consider LFS under the constraint that N is a cactus with arbitrary edge-weights and X=1^^~. In this paper, we will show that the problem can be solved in O(|P|^2)time. |
| キーワード(和) | ペトリネット / ステートマシン / 枝重み付きカクタス / 発火系列問題 / 多項式時間アルゴリズム |
| キーワード(英) | Petri nets / State machines / Edge-weighted cactuses / Legal firing sequence problems / Polynomial time algorithms |
| 資料番号 | CST98-32 |
| 発行日 |
| 研究会情報 | |
| 研究会 | CST |
|---|---|
| 開催期間 | 1999/1/28(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Concurrent System Technology (CST) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 枝重み付きカクタスに対する発火系列問題の解法 |
| サブタイトル（和） | |
| タイトル（英） | Solving the Legal Firing Sequence Problem for Edge-weighted Cactuses |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ペトリネット / Petri nets |
| キーワード(2)（和/英） | ステートマシン / State machines |
| キーワード(3)（和/英） | 枝重み付きカクタス / Edge-weighted cactuses |
| キーワード(4)（和/英） | 発火系列問題 / Legal firing sequence problems |
| キーワード(5)（和/英） | 多項式時間アルゴリズム / Polynomial time algorithms |
| 第 1 著者 氏名（和/英） | 岩本 道尚 / Michihisa Iwamoto |
| 第 1 著者 所属（和/英） | 広島大学大学院工学研究科情報工学専攻 Graduate School of Engineering, Hiroshima University |
| 第 2 著者 氏名（和/英） | 藤戸 敏弘 / Toshihiro Fujito |
| 第 2 著者 所属（和/英） | 広島大学工学部第二類回路・システム工学講座 Department of Circuits and Systems, Faculty of Engineering, Hiroshima University |
| 第 3 著者 氏名（和/英） | 田岡 智志 / Satoshi Taoka |
| 第 3 著者 所属（和/英） | 広島大学工学部第二類回路・システム工学講座 Department of Circuits and Systems, Faculty of Engineering, Hiroshima University |
| 第 4 著者 氏名（和/英） | 渡邉 敏正 / Toshimasa Watanabe |
| 第 4 著者 所属（和/英） | 広島大学工学部第二類回路・システム工学講座 Department of Circuits and Systems, Faculty of Engineering, Hiroshima University |
| 発表年月日 | 1999/1/28 |
| 資料番号 | CST98-32 |
| 巻番号（vol） | vol.98 |
| 号番号（no） | 565 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |