DocumentCode :
2823462
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
fYear :
1991
fDate :
11-14 Jun 1991
Firstpage :
2838
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Circuits and Systems, 1991., IEEE International Sympoisum on
Print_ISBN :
0-7803-0050-5
Type :
conf
DOI :
10.1109/ISCAS.1991.176135
Filename :
176135
Link To Document :
بازگشت