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 (r ecognized by deter- ministic automata). Deterministic series frequently aris e 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. Keywords—Discrete Event Systems, (max,+) algebra, Automata, Ration al Series, Performance Evaluation

This publication has 10 references indexed in Scilit: