| 講演名 | 1995/4/21 ステートマシンの接続構造を持つペトリネットの発火系列問題 森田 圭介, 中脇 博文, 渡辺 敏正, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | ペトリネットの発火系列問題とは与えられた初期マーキングから順次発火できるトランジションの系列で,各トランジションが予め指定された回数だけ出現するものを見つける問題である。まず,ステートマシン(トランジションの入出力枝がそれぞれ1本以下のペトリネット)の発火系列問題に対して,計算時間,記憶容量共にO(|X|)に短縮した解法を提案する。ここで|X|は各トランジションの出現回数の総和である。次に,その拡張である枝重み付ステートマシンの発火系列問題に関して,技重みが2種類であるいくつかの部分族に対する線形時間解法についても述べる。 |
| 抄録(英) | The Legal Firing Sequence Problem of Petri nets (LFS for short) is defined by : "Given a Petri net, an initial marking M and a firing count vector X (with each component X(t) denoting the prescribed total firing number of a transition t), find a firing sequence δ which is legal on M with respect to X", where δ is a sequence of transitions and is called legal on M with respect to X if and only if the first transition of δ is firable on M, the rest can be fired one by one subsequently and each transition t appears exactly X(t) times in δ. It is known that LFS is NP-complete and that LFS restricted to a state machine can be solved in O(|X|^2) time. First, we propose an O(|X|) time algorithm that solves LFS for state machines. Secondly, linear time algorithms for solving LFS for some classes of weighted state machines with two kinds of edge weights are given, where the term "weighted" means that some edge weights may be greater than 1. |
| キーワード(和) | ペトリネット / ステートマシン / 発火系列問題 / 多項式時間アルゴリズム / NP-完全性 |
| キーワード(英) | Petri nets / State machines / Legal Firing Sequence Problems / Polynomial-Time Algorithms / NP-completeness |
| 資料番号 | |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1995/4/21(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | ステートマシンの接続構造を持つペトリネットの発火系列問題 |
| サブタイトル（和） | |
| タイトル（英） | The Legal Firing Sequence Problem of Petri Nets with State Machine Structure |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ペトリネット / Petri nets |
| キーワード(2)（和/英） | ステートマシン / State machines |
| キーワード(3)（和/英） | 発火系列問題 / Legal Firing Sequence Problems |
| キーワード(4)（和/英） | 多項式時間アルゴリズム / Polynomial-Time Algorithms |
| キーワード(5)（和/英） | NP-完全性 / NP-completeness |
| 第 1 著者 氏名（和/英） | 森田 圭介 / Keisuke Morita |
| 第 1 著者 所属（和/英） | 広島大学工学部第二類回路システム工学講座 Department of Circuits and Systems, Faculty of Engineering, Hiroshima University, |
| 第 2 著者 氏名（和/英） | 中脇 博文 / Hirofumi Nakawaki |
| 第 2 著者 所属（和/英） | 広島大学工学部第二類回路システム工学講座 Department of Circuits and Systems, Faculty of Engineering, Hiroshima University, |
| 第 3 著者 氏名（和/英） | 渡辺 敏正 / Toshimasa Watanabe |
| 第 3 著者 所属（和/英） | 広島大学工学部第二類回路システム工学講座 Department of Circuits and Systems, Faculty of Engineering, Hiroshima University |
| 発表年月日 | 1995/4/21 |
| 資料番号 | |
| 巻番号（vol） | vol.95 |
| 号番号（no） | 13 |
| ページ範囲 | pp.- |
| ページ数 | 10 |
| 発行日 | |