情報処理学会 第75回全国大会講演要旨

離散事象システムの有用なモデルの1つであるP/T ペ
トリネットにおいて，その挙動を考える際に，最も基本的
な問題のうち可到達判定問題がある．これは，初期マーキ
ングM0 から最終マーキングMd へトークンが遷移可能
かどうかを判定するものであるが，この問題の解法には
被覆木，状態方程式，ペトリネットの構造と性質に着目す
る3 つの手法があり，被覆木を用いた方法は一般に膨大
な計算量を必要とする一方，状態方程式を用いる方法は，
ペトリネットの性質を代数方程式の解の存在として考察
できる利点があるため，その解法や，解の表現方法などに
ついての研究が進められてきている．
ここでは，状態方程式の解法としてよく知られたFourie-
Motzkin 法により初等的T-インバリアントおよび特解が
導出できることを述べるともに，従来のFourie-Motzkin
法では得られなかった解の導出について，Fourie-Motzkin
法のアルゴリズムを改良することでそれらの一部が得ら
れることを示す．