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

https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2823462