Performance evaluation of (max,+) automata
Author:
- S. GaubertSGS. Gaubert
- 1 January 1995
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 40 (12) , 2014-2025
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 EvaluationKeywords
This publication has 10 references indexed in Scilit:
- Finite-valued distance automataTheoretical Computer Science, 1994
- Supervisory control of timed discrete-event systemsIEEE Transactions on Automatic Control, 1994
- Model-Checking in Dense Real-TimeInformation and Computation, 1993
- Compiling real-time specifications into extended automataIEEE Transactions on Software Engineering, 1992
- Ergodic Theory of Stochastic Petri NetworksThe Annals of Probability, 1992
- Improved limitedness theorems on finite automata with distance functionsTheoretical Computer Science, 1990
- Discrete event systems with stochastic processing timesIEEE Transactions on Automatic Control, 1990
- The control of discrete event systemsProceedings of the IEEE, 1989
- Rational Series and Their Languages1988
- Linear Algebra in Dioids: A Survey of Recent Results1984