P/Tペトリネットの発火回数ベクトルの実行可能性判定法－解ベクトルのgeneratorを活用する方法

摘要

P/TペトリネットN＝（P，T，F，W）と初期マーキングM{sub}0∈(Z{sub}+){sup}(m×1)，最終マーキングM{sub}d∈(Z{sub}+){sup}(m×1)が与えられたとき，M{sub}d∈R(N)であるかを判定する問題を可到達判定問題という．ここで，R(N)は初期マーキングM{sub}0から到達可能なマーキングの集合とする．一九可到達判定に関わる問題として，状態方程式Ax＝bのある1つの非負整数解x∈(Z{sub}+){sup}(n×1)の実行可能性判定問題がある．本論文では，Ax＝bの1つの非負整数解x∈(Z{sub}+){sup}(n×1)を考える．すなわち，Ax＝bの任意の非負整数解x∈(Z{sub}+){sup}(n×1)を表現できる有限個のgeneratorが既知であることを前提にし，xの実行可能性判定法を提案する．一つには，この判定法は与えられた1つのxに指定されたgeneratorのみを使う．これにより，用いるgeneratorの個数を減らして考えることができる．また，その指定された．generatorの個々の実行可能性判定を用い，すべてのgeneratorが実行可能な場合は明らかであるが，それ以外の場合はBorrowの概念を用い，generator同士の組合せを考えて，xの判定に活かしている．