Reference
B. De Schutter,
Max-Algebraic System Theory for Discrete Event
Systems. PhD thesis, Faculty of Applied Sciences, K.U.Leuven, Leuven,
Belgium, ISBN 90-5682-016-8, 331 pp., Feb. 1996.
Abstract
Discrete event systems (DESs) are systems in which the state changes only at
discrete points in time in response to the occurrence of particular events.
Typical examples of DESs are: flexible manufacturing systems, telecommunication
networks, parallel processing systems and traffic control systems. One of the
frameworks that can be used to model and to analyze certain types of DESs is
the max-plus algebra, which has maximization and addition as basic operations.
In this thesis we develop tools for solving some fundamental problems in the
max-algebraic system theory for DESs.
First we introduce a mathematical programming problem: the Extended Linear
Complementarity Problem (ELCP). We develop an algorithm to find all the
solutions of an ELCP.
We show that the problem of solving a system of multivariate max-algebraic
polynomial equalities and inequalities is equivalent to an ELCP. This enables
us to solve many other max-algebraic problems such as computing max-algebraic
matrix factorizations, performing max-algebraic state space transformations,
computing state space realizations of the impulse response of a max-linear
time-invariant DES, computing max-algebraic singular value decompositions and
QR decompositions, and so on.
We also study the max-algebraic characteristic polynomial and state space
transformations for max-linear time-invariant DESs. Next we develop a method to
solve the minimal state space realization problem for max-linear time-invariant
DESs. First we use our results on the max-algebraic characteristic polynomial
to develop a procedure to determine a lower bound for the minimal system order
of a max-linear time-invariant DES. Then we show that the ELCP can be used to
compute all fixed order partial state space realizations and all minimal state
space realizations of the impulse response of a max-linear time-invariant DES.
Finally we prove the existence of max-algebraic analogues of two basic matrix
decompositions from linear algebra: the singular value decomposition and the QR
decomposition.
Downloads
BibTeX
@phdthesis{DeS:96-02,
author = {De Schutter, Bart},
title = {Max-Algebraic System Theory for Discrete Event Systems},
school = {Faculty of Applied Sciences, K.U.Leuven},
address = {Leuven, Belgium},
month = feb,
year = {1996}
}
@misc{DeS:96-02e,
author = {De Schutter, Bart},
title = {Errata for the PhD thesis of Bart De Schutter ``Max-Algebraic
System Theory for Discrete Event Systems''},
note = {Last update: November 30, 2008.}
}