Max-plus steady states in discrete event dynamic systems with inexact data

Max-plus algebra is defined as the set of all real numbers with two binary operations (maximum and addition). This combination of the operations forms a very applicable tool for the investigation of systems working in discrete steps (discrete event dynamic systems). The search for the steady states in such systems leads to the study of the eigenvectors of the production matrix in the corresponding max-plus algebra. A vector x is said to be an eigenvector of a square matrix A if A circle times x = lambda circle times x for some lambda is an element of R. In real systems, the input values are usually taken to be in some interval. This paper investigates the properties of eigenspaces for vectors with interval (inexact) coefficients. We suppose that an interval vector X can be split into two subsets according to a forall-exists quantification of its interval entries, i.e., X = X-for all circle plus X-there exists. If for any vector of X there is at least one vector of X-there exists such that their vector maximum is an eigenvector of A, then X is said to be a lambda AE-eigenvector. Analogously, if there is at least one vector of X-there exists such that for any vector of X-for all their vector maximum is an eigenvector of A, then X is said to be a lambda EA-eigenvector. The properties of such eigenvectors are studied and their characterizations by equivalent conditions are presented. Polynomial and pseudopolynomial algorithms for checking some types of lambda EA/lambda AE-eigenvectors are suggested.