Max-plus Algebraic Description of Evolutions of Weighted Timed Event Graphs

Timed event graphs (TEGs) are mathematical models for the dynamics of discrete systems. A TEG is a directed graph consisting of two kinds of nodes, called places and transitions, and directed arcs between places and transitions. Each place can contain tokens that move around by firings of transitions, which is determined by the holding times assigned to places. In the weighted timed event graphs (WTEGs), the weights are assigned to the arcs and these weights represent the number of the tokens consumed or produced by the firing of the adjacent transitions. Unlike usual timed event graphs, weights on arcs make it difficult to describe the evolution of systems in simple mathematical formulae. The main purpose of this paper is to derive max-plus algebraic evolution equations for unitary WTEGs. We focus on the numbers indicating how many times each transition fires to reach the original token configuration again. Such numbers are known as the minimal T-semiflow and are computed from arc weights. We expand the dimension of the firing time vector by dividing the original variables into several variables, but it does not depend on the number of tokens. We also show that max-plus coefficient matrices in the evolution equation provide important information about the dynamics of a unitary WTEG. For example, the nilpotency of the coefficient matrix in the highest order term means the liveness of the WTEG. In this case, the average cycle time of the WTEG is computed as the eigenvalue of a certain max-plus matrix.