
HP Labs Technical Reports
Click here for full text:
A Nonlinear Hierarchy for Discrete Event Dynamical Systems
Gaubert, Stephane; Gunawardena, Jeremy
HPLBRIMS9820
Keyword(s): nonexpansive maps; fixed points; cycle time
Abstract: Dynamical systems of monotone homogeneous functions appear in Markov decision theory, in discrete event systems and in PerronFrobenius theory. We consider the case when these functions are given by finite algebraic expressions involving the operations max, min, convex hull, translations and an infinite family of binary operations, of which max and min are limit cases. We set up a hierarchy of monotone homogeneous functions that reflects the complexity of their defining algebraic expressions. For two classes of this hierarchy, we show that the trajectories of the corresponding dynamical systems admit a linear growth rate (cycle time). The first class generalizes the minmax functions considered previously in the literature. The second class generalizes both maxplus linear maps and ordinary nonnegative linear maps. Notes: Stephane Gaubert, INRIA, Domaine de Voluceau, 78153 Le Chesnay Cedex, France.
7 Pages
Back to Index
