Recherche des semi-flots, des verrous et des trappes dans les rĂ©seaux de Petri. (Finding semi-flows, deadlocks and traps in Petri nets). (French) Zbl 0567.68033

Knowing the semi-flows of a Petri net permits to characterize the invariant properties of the system. The paper presents a method of finding semi-flows that leads to searching positive integer solutions of the linear system \(x^ T\cdot A=0\), where \(x\in N^ m\) and \(A\in Z^{m\times n}\). An algorithm solves the problem by an improved Gauss- type elimination method. In the second part of the article another algorithm is presented which reduces the problem of finding deadlocks and traps in Petri nets to that of finding invariants. In spite of the exponential complexity of the algorithms, they are still advantageous in the design and validation of real time systems thanks to the sparse nature of the incidence matrices employed.
Reviewer: D.Cristea


68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
65F05 Direct numerical methods for linear systems and matrix inversion