| 講演名 | 1996/1/19 枝重み付ステートマシンの発火系列問題 森田 圭介, 渡辺 敏正, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | ペトリネットの発火系列問題とは、与えられた初期マーキングから順次発火できるトランジションの系列で、各トランジションが予め指定された回数(発火回数と呼ぶ)だけ出現するものを見つける問題である。トランジションの入力枝がそれぞれ1本以下で枝重みが1種類であるペトリネットをステートマシンと呼ぶ。枝重み付ステートマシンとはステートマシンに2種類以上の枝重みを持たせたものをいう。本稿では、まず枝重み付きステートマシンの発火系列問題に関して、枝重みが2種類で且つ各トランジションの発火回数が全て1であると制限してもNP-完全であることを示す。次に、ネックレスと名付けた枝重み付ステートマシンに対して、枝重みが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δ in which 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|) time. First, we prove that LFS for weighted state machines with two kinds of edge weights is NP-complete, where the term "weighted" means that some edge weights may be greater than 1. Secibdly, we show that the Eulerian LFS for a similar state machine can be polynomially solvable if a state machine has a structure called a necklace. |
| キーワード(和) | ペトリネット / ステートマシン / 発火系列問題 / 多項式時間アルゴリズム / NP-完全性 |
| キーワード(英) | Petri Nets / State Machines / Legal Firing Sequence Problems / Polynomial-Time Algorithms / NP-Completeness |
| 資料番号 | CST95-33 |
| 発行日 |
| 研究会情報 | |
| 研究会 | CST |
|---|---|
| 開催期間 | 1996/1/19(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Concurrent System Technology (CST) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 枝重み付ステートマシンの発火系列問題 |
| サブタイトル（和） | |
| タイトル（英） | The Legal Firing Sequence Problem for Weighted State Machines |
| サブタイトル（和） | |
| キーワード(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 著者 氏名（和/英） | 渡辺 敏正 / Toshimasa Watanabe |
| 第 2 著者 所属（和/英） | 広島大学 工学部 第二類 回路システム工学講座 Department of Circuits and Systems, Faculty of Engineering, Hiroshima University |
| 発表年月日 | 1996/1/19 |
| 資料番号 | CST95-33 |
| 巻番号（vol） | vol.95 |
| 号番号（no） | 471 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |