A polynomial-time algorithm for finding a semi-generator of Petri net invariants
T. Tanida, Takahiro Watanabe, Kenji Onaga · 1991
A polynomial-time algorithm is proposed for finding a semigenerator of Petri net invariants. Invariants of a Petri net are solutions to a linear system of equations Ax=0 for the place-transition incidence matrix A representing this Petri net. The notion of a semigenerator is introduced: it is a maximal subset consisting of linearly independent elements of a generator, and any invariant can be expressed as linear combination of those elements in the set with negative coefficients allowed. The proposed algorithm adopts a linear programming technique.>