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

Reference:
B. De Schutter, V. Blondel, and B. De Moor, "On the complexity of the boolean minimal realization problem in the max-plus algebra," Advances in Systems, Signals, Control and Computers (Proceedings of the International Conference on Systems, Signals, Control, Computers (SSCC'98), Durban, South Africa, Sept. 1998) (V.B. Bajic, ed.), vol. II, pp. 451-455, 1998.

Abstract:
One of the open problems in the max-plus-algebraic system theory for discrete event systems is the minimal realization problem. 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 show that the corresponding decision 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.