1Performance Evaluation of (max,+) Automata

Abstract—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 sched-ules. 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 deter-ministic 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 perfor-mance is given by a Hamilton-Jacobi-Bellman equation