HP Labs Technical Reports

Cycle Times and Fixed Points of Min-Max Functions

Gunawardena, Jeremy

HPL-94-40

Keyword(s):

Abstract: 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 results about their behavior have so far been obtained (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 was done as part of project STETSON, a joint project between HP Labs and Stanford University on asynchronous hardware design.

Back to Index