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.
Publisher page
Downloads
Addendum
- B. De Schutter, V. Blondel, R. de Vries, and B. De Moor, "On the boolean minimal realization problem in the max-plus algebra: Addendum," Tech. report 97-68a, ESAT-SISTA, K.U.Leuven, Leuven, Belgium, 5 pp., Dec. 1997. (abstract, bibtex, report (pdf))
BibTeX
@article{DeSBlo:97-68,
author = {De Schutter, Bart and Blondel, Vincent and de Vries, Remco and De
Moor, Bart},
title = {On the {B}oolean Minimal Realization Problem in the Max-Plus
Algebra},
journal = {Systems \& Control Letters},
volume = {35},
number = {2},
pages = {69--78},
month = sep,
year = {1998}
}