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 Yt A = 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.

A siphon-trap of a Petri net N is defined as a place set S with S = S, where S = { u| N has an edge from u to a vertex of S} and S = { v| N has an edge from a vertex of S to v}. A minimal siphon-trap is a siphon-trap such that any proper subset is not a siphon-trap. The following polynomial-time algorithms are proposed: (1) FDST for finding, if any, a minimal siphon-trap or even a maximal class of mutually disjoint minimal siphon-traps of a given Petri net; (2) FDSTi that repeats FDST i times in order to extract more minimal siphon-traps than FDST. (3) STFM_T (STFM_Ti, respectively) which is a combination of the Fourier-Motzkin method and FDST (FDSTi) and which has high possibility of finding, if any, at least one minimal-support nonnegative integer invariant.