On the boolean minimal realization problem in the max-plus algebra

One of the open problems in the max-plus-algebraic system theory for discrete event systems is the minimal realization problem. In this paper we present some results in connection with the minimal realization problem in the max-plus algebra. First we characterize the minimal system order of a max-linear discrete event system. We also introduce a canonical representation of the impulse response of a max-linear discrete event system. Next we consider a simplified version of the general minimal realization problem: the. boolean minimal realization problem, i.e., we consider models in which the entries of the system matrices are either equal to the max-plus-algebraic zero element or to the max-plus-algebraic identity element. We give a lower bound for the minimal system order of a max-plus-algebraic boolean discrete event system. We show that the decision problem that corresponds to the boolean realization problem (i.e., deciding whether or not a boolean realization of a given order exists) is decidable, and that the boolean minimal realization problem can be solved in a number of elementary operations that is bounded from above by an exponential of the square of (any upper bound of) the minimal system order. We also point out some open problems, the most important of which is whether or not the boolean minimal realization problem can be solved in polynomial time. (C) 1998 Elsevier Science B.V. All rights reserved.