ペトリネットのサイフォン·トラップ抽出に基づくFourier-Motzkin法の安定性向上

摘要

ペトリネットN=(P,T,E,α,β)のP-インバリアントとは,NのPT接続行列Aに対して「Y^t·A=0を満たす|P|次元ベクトルY」である.全ての非負整数極小サポートインバリアント抽出法としてよく知られるFourier-Motzkin(FM)法には,途中で記憶すべき解候補ベクトルの爆発的増加に起因するメモリ不足のために,インバリアントが存在するにも関わらず何も算出されない場合が起り得る,この欠点を回避し,より多くの極小サポートインバリアントを求めるために,Nの部分ネットであるサイフォン·トラップネットを抽出し,それにFM法を適用する手法STFM_Nが提案されている.本稿では、STFM_N評のサイフォン·トラップネット抽出法にNのトランジションの点次数を考慮した改良を加えた手法STFM_N+を提案し,計算機実験により,既存手法よりメモリー不足の発生を抑え,結果的に極小サポートインバリアントが求まる場合を増やすことを示す.