**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.

Corresponding technical report: pdf file (154 KB)

@inproceedings{DeSDeM:98-41,

author={B. {D}e Schutter and V. Blondel and B. {D}e Moor},

title={On the complexity of the boolean minimal realization problem in the max-plus algebra},

booktitle={Advances in Systems, Signals, Control and Computers \rm(Proceedings of the International Conference on Systems, Signals, Control, Computers (SSCC'98), Durban, South Africa, Sept. 1998)},

volume={II},

editor={V.B. Baji\'c},

pages={451--455},

year={1998}

}

Go to the publications overview page.

This page is maintained by Bart De Schutter. Last update: March 20, 2022.