A sufficient condition for the liveness of weighted event graphs |
| |
Authors: | Olivier Marchetti Alix Munier-Kordon |
| |
Institution: | Laboratoire d’Informatique de Paris 6, Université Pierre et Marie Curie, 4 Place Jussieu, Paris 75252 Cedex 05, France |
| |
Abstract: | Weighted event graphs (in short WEG) are widely used to model industrial problems and embedded systems. In an optimization context, fast algorithms checking the liveness of a marked WEG must be developed. The purpose of this paper is to develop a sufficient condition of liveness of a WEG. We first show that any unitary WEG can be transformed into a graph in which the values of the arcs adjacent to any transition depend on the transition. Then, a simple sufficient condition of liveness can be expressed on this new graph and polynomially computed. This condition is shown to be necessary for a circuit with two transitions. |
| |
Keywords: | Petri nets Weighted event graph Liveness |
本文献已被 ScienceDirect 等数据库收录! |