From max-plus algebra to nonexpansive mappings: a nonlinear theory for discrete event systems

Discrete event systems provide a useful abstraction for modelling a wide variety of systems: digital circuits, communication networks, manufacturing plants, etc. Their dynamics-stability, equilibrium states, cyclical behaviour, asymptotic average delays-are of vital importance to system designers. However, in marked contrast to continuous dynamical systems, there has been little systematic mathematical theory that designers can draw upon. In this paper, we survey the development of such a theory, based on the dynamics of maps which are nonexpansive in the l(infinity) norm. This has its origins in linear algebra over the max-plus semiring but extends to a nonlinear theory that encompasses a variety of problems arising in other mathematical disciplines. We concentrate on the mathematical aspects and set out several open problems. (C) 2002 Elsevier Science B.V. All rights reserved.