Title :
A polynomial-time algorithm for finding a semi-generator of Petri net invariants
Author :
Tanida, Takenobu ; Watanabe, Toshio ; Onaga, Kenji
Author_Institution :
Fac. of Eng., Hiroshima Univ., Japan
Abstract :
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
Keywords :
Petri nets; linear programming; matrix algebra; Petri net invariants; linear programming technique; linearly independent elements; maximal subset; negative coefficients; place-transition incidence matrix; polynomial-time algorithm; semigenerator; Communication systems; Concurrent computing; Equations; Explosives; Linear programming; Linear systems; Petri nets; Polynomials; Protocols; Stochastic systems;
Conference_Titel :
Circuits and Systems, 1991., IEEE International Sympoisum on
Print_ISBN :
0-7803-0050-5
DOI :
10.1109/ISCAS.1991.176135
