HP Labs Technical Reports
Click here for full text:
Cycle Times and Fixed Points of Min-Max Functions
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