A sufficient condition for the liveness of weighted event graphs

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. (C) 2008 Elsevier B.V. All rights reserved.