Experimental Evaluation of Two Algorithms for Computing Petri Net Invariants(Special Section on Concurrent Systems Technology)

概要

論文の詳細を見る
We consider only P-invariants that are nonnegative integer vectors in this paper. An P-invariant of a Petri net N=(P, T, E, α, β)is a |P|-dimensional vector Y with Y^t・A=0 for the place-transition incidence matrix A of N. The support of an invariant is the set of elements having nonzero values in the vector. Since any invariant is expressed as a linear combination of minimal-support invariants(ms-invariants for short)with nonnegative rational coefficients, it is usual to try to obtain either several invariants or the set of all ms-invariants. The Fourier-Motzkin method(FM)is well-known for computing a set of invariants including all ms-invariants. It has, however, critical deficiencies such that, even if invariants exist, none of them may be computed because of memory overflow caused by storing candidate vectors for invariants and such that, even when a set of invariants are produced, many non-ms invariants may be included. We are going to propose the following two methods:(1)FM1_M2 that finds a smallest possible set of invariants including all ms-invariants;(2)STFM that necessarily produces one or more invariants if they exist. Experimental results are given to show their superiority over existing ones.
社団法人電子情報通信学会の論文
2001-11-01