Two efficient methods for computing petri net invariants

We consider only P-invariants that are nonnegative integer vectors in this paper. An P-invariant of a Petri net N = (P, T, E, alpha, beta) is a \P\-dimensional vector Y with Y-t (.) A = (0) over bar 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 an overflow of 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: (i) FM1(-)M2 that finds a smallest possible set of invariants including all ms-invariants; (ii) STFM-T that necessarily produces one or more invariants if they exist. Experimental results are given to show their superiority over existing ones.