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.
Bajić, 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.
Downloads
BibTeX
@inproceedings{DeSDeM:98-41,
author = {De Schutter, Bart and Blondel, Vincent and De Moor, Bart},
title = {On the Complexity of the {B}oolean Minimal Realization Problem
in the Max-Plus Algebra},
booktitle = {Advances in Systems, Signals, Control and Computers
\normalfont(Proceedings of the International Conference on
Systems, Signals, Control, Computers (SSCC'98), Durban, South
Africa, Sept. 1998)},
volume = {II},
editor = {Baji\'{c}, Vladimir B.},
pages = {451--455},
year = {1998}
}