枝重み付ステートマシンの発火系列問題
スポンサーリンク
概要
- 論文の詳細を見る
ペトリネットの発火系列問題とは、与えられた初期マーキングから順次発火できるトランジションの系列で、各トランジションが予め指定された回数(発火回数と呼ぶ)だけ出現するものを見つける問題である。トランジションの入力枝がそれぞれ1本以下で枝重みが1種類であるペトリネットをステートマシンと呼ぶ。枝重み付ステートマシンとはステートマシンに2種類以上の枝重みを持たせたものをいう。本稿では、まず枝重み付きステートマシンの発火系列問題に関して、枝重みが2種類で且つ各トランジションの発火回数が全て1であると制限してもNP-完全であることを示す。次に、ネックレスと名付けた枝重み付ステートマシンに対して、枝重みが2種類である場合にオイラー型発火系列問題が多項式時間で解けることを示す。
- 社団法人電子情報通信学会の論文
- 1996-01-19
著者
関連論文
- 固定ルーティングネットワークにおける無故障な経由ルート数の評価
- 枝重み付ステートマシンの発火系列問題
- ステートマシンの接続構造を持つペトリネットの発火系列問題
- ペトリネットの最小初期部分マーキング問題について(グラフ,ネットワークとアルゴリズムおよび一般)