Performance evaluation of (max,+) automata
Stéphane Gaubert · IEEE Transactions on Automatic Control · 1995
Automata with multiplicities over the (max,+) semiring can be used to represent the behavior of timed discrete-event systems. This formalism, which extends both conventional automata and (max,+) linear representations, covers a class of systems with synchronization phenomena and variable schedules. Performance evaluation is considered in the worst, mean, and optimal cases. A simple algebraic reduction is provided for the worst case. The last two cases are solved for the subclass of deterministic series (recognized by deterministic automata). Deterministic series frequently arise due to the finiteness properties of (max,+) linear projective semigroups. The mean performance is given by the Kolmogorov equation of a Markov chain. The optimal performance is given by a Hamilton-Jacobi-Bellman equation.