ペトリネットの状態方程式の非負整数解のレベル表現と生成元の基礎的考察

摘要

P/Tペトリネットとその拡張形は，離散事象システムのモデリング，解析，検証ツールとして広い分野に利用されている．特に，P/Tペトリネットはそれらの基本形として有用であり，状態方程式による解析が可能であることが特徴の1つである．状態方程式Ax=b(A∈Z{sup}(m×n), b∈Z{sup}(m×1))は一般に無限個の非負整数非同次解x∈(Z{sub}+){sup}(n×1)を有するが，それらx∈(Z{sub}+){sup}(n×1)を表現する生成元の数は有限であることが知られている．非負整数非同次解x∈(Z{sub}+){sup}(n×1)の特別な場合（すなわち，b=0{sup}(m×1)である非負整数同次解（Tインバリアント）の生成元は従来から研究されてきたが，非負整数非同次解x∈(Z{sub}+){sup}(n×1)の極小解である特解（一般に複数個存在する）やその生成元はほとhど研究されていない．本論文では拡大A{top}～x{top}～=0{sup}(m×1) (A{top}～:=[A,-b] ∈z{sup}((n+1)×1))自体は，Ax=0{sup}(m×1)と同様に，代数的特徴が明確な生成元，レベル表現を有すること，x{top}～∈(Z{sub}+){sup}((n+1)×1) はAx=b≠0{sup}(m×1)のx∈(Z{sub}+){sup}(n×1)に対する同次解とその生成元，特解やその生成元を一部として含hでいることに着目して，Ax=b≠0{sup}(m×1)の同次解のみならず特解の生成元に関する基礎的考察を行った．また，生成元の導出アルゴリズムと生成元（特に，特解の生成元）の性質の複雑さとの関係を示し，今後の問題点を明示している．これらの内容はTインバリアントと特解の各レベルのすべての生成元を導出するための基礎となる．