HP Labs Technical Reports

A Non-linear Hierarchy for Discrete Event Dynamical Systems

Gaubert, Stephane; Gunawardena, Jeremy

HPL-BRIMS-98-20

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 Perron-Frobenius 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 min-max functions considered previously in the literature. The second class generalizes both max-plus linear maps and ordinary non-negative linear maps. Notes: Stephane Gaubert, INRIA, Domaine de Voluceau, 78153 Le Chesnay Cedex, France.

7 Pages

Back to Index