マークグラフにおけるトランジションの潜在的同時発火可能性判定アルゴリズム

スポンサーリンク

概要

論文の詳細を見る
ペトリネットは,分散,並列,非同期性などの性質を有するシステムをモデルする有用な手段である.ペトリネットにおける潜在的同時発火可能性判定問題とは,初期マーキングをもつペトリネットとペトリネット中の複数個のトランジションの集合Aが指定されたとき,初期マーキングから到達可能なマーキングの集合の要素で,Aのすべてのトランジションが発火可能であるようなマーキングが存在するか否かを判定する問題である.ペトリネットの部分クラスである1-有界自由選択ペトリネットについてのこの問題はNP完全であるが,別の部分クラスであるマークグラフに限定した場合については,|A|=2のときは,|F|をアークの総数とすると,時間計算量O(|F|)のアルゴリズムが知られている.本論文では,この結果を拡張し,マークグラフに対して,O(|A||F|+|A|)の時間計算量で判定するアルゴリズムを示す.
社団法人電子情報通信学会の論文
1994-10-25

著者

関連論文

もっと見る

スポンサーリンク