Fli;w. HEWLETT a: ~ PACKARD Cycle Times and Fixed Points of Min-Max Functions

cycle time, discrete event system, fixed point, max-plus algebra, min-max function The dynamic behavior of discrete event systems with only maximum timing constraints (or, dually, only minimum timing constraints) can be studied by linear methods based on max-plus algebra, as discussed in the recent book "Synchronization and Linearity " by Baccelli, Cohen, Quadrat and Olsder. Systems with both maximum and minimum constraints are non-linear from this perspective and only limited re-sults about their behavior have so far been ob-tained (Olsder 1991, 1993; Gunawardena, 1993). In this paper we describe some new results and conjectures about such systems which generalize the initial earlier work and shed a new light on aspects of the linear theory. Our main result is a necessary and sufficient condition for the existence of a fixed point (eigenvector) for any min-max function. The work described here wa