Two efficient methods for computing Petri net invariants
Katsushi Takano, Satoshi Taoka, M. Yamauchi, Takuo Watanabe · 2002
We consider only P-invariants that are nonnegative integer vectors. A P-invariant of a Petri net N=(P, T, E, /spl alpha/, /spl beta/) is a |P|-dimensional vector Y with Y/sup /spl dagger//spl middot//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) with nonnegative rational coefficients, it is common to try to obtain either several invariants or the set of all MS-invariants. The Fourier-Motzkin method (FM) is wellknown for computing a set of invariants including all MS-invariants, but it has critical deficiencies. We propose the following two methods: (1) FM1_m2 that finds a smallest possible set of invariants including all MS-invariants; and (2) STFM_T/sub _/ that necessarily produces one or more invariants if they exist. Experimental results are given to show their superiority over existing ones.