Non-linear hierarchy for discrete event dynamical systems

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.