著者
森田 圭介 中脇 博文 渡辺 敏正
出版者
一般社団法人電子情報通信学会
雑誌
電子情報通信学会技術研究報告. COMP, コンピュテーション
巻号頁・発行日
vol.95, no.13, pp.11-20, 1995-04-21
被引用文献数
4

ペトリネットの発火系列問題とは与えられた初期マーキングから順次発火できるトランジションの系列で,各トランジションが予め指定された回数だけ出現するものを見つける問題である。まず,ステートマシン(トランジションの入出力枝がそれぞれ1本以下のペトリネット)の発火系列問題に対して,計算時間,記憶容量共にO(|X|)に短縮した解法を提案する。ここで|X|は各トランジションの出現回数の総和である。次に,その拡張である枝重み付ステートマシンの発火系列問題に関して,技重みが2種類であるいくつかの部分族に対する線形時間解法についても述べる。