
HP Labs Technical Reports
Click here for full text:
From Maxplus Algebra to Nonexpansive Mappings: a Nonlinear Theory for Discrete Event Systems
Gunawardena, Jeremy
HPLBRIMS199907
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 maxplus 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.
21 Pages
Back to Index
