**Reference:**

B. De Schutter,
V. Blondel,
R. de Vries, and
B. De Moor,
"On the boolean minimal realization problem in the max-plus algebra,"
*Systems & Control Letters*, vol. 35, no. 2, pp. 69-78,
Sept. 1998.

**Abstract:**

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.

Online version of the paper

Corresponding technical report: pdf file (251 KB)

@article{DeSBlo:97-68,

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

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

journal={Systems \& Control Letters},

volume={35},

number={2},

pages={69--78},

month=sep,

year={1998},

doi={10.1016/S0167-6911(98)00035-8}

}

Go to the publications overview page.

This page is maintained by Bart De Schutter. Last update: August 12, 2020.