HP Labs Technical Reports
Click here for full text:
From Max-plus Algebra to Nonexpansive Mappings: a Nonlinear Theory for Discrete Event Systems
Keyword(s): cycle time; discrete event system; fixed point; max- plus semiring; nonexpansive map; topical function
Abstract: Please Note. This abstract contains mathematical formulae which cannot be represented here. 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 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.
Back to Index