Theory of linear systems over dioids

Theory of linear systems over dioids

Stéphane Gaubert

Abstract We develop a system theory for linear systems over certain dioid structures (semirings with idempotent addition).

We study general systems of linear equations in certain dioids. The introduction of a new notion of symmetrization results in the linear closure of these algebras: the generic system of n linear equations with n unknowns admits a unique solution in the symmetrized dioid, given by Cramer's formulae. We adapt the Jacobi and Gauss-Seidel algorithms to this context. We also give some duality results. The spectral theory of irreducible (max,+) matrices is extended to the reducible case.

Later, we consider the associated linear system theory (representation by kernels and convolutions in dioid, use of the Fenchel transform). We obtain a lower bound for minimal realizations in terms of minors.

We develop some algorithms for an algebra of rational series devoted to timed event graphs. We present MAX, the program written in MAPLE which implements these algorithms (transfer series, periodic throughput). Finally, we show that the resource optimization problem reduces to an algebraic enumeration of constraints modulo some simplification rules. These constraints also reduce to a sub-eigenvector problem.

Key words Dioids, Linear Systems, Discrete Event Systems, Timed Event Graphs, Symmetrization.

BibTeX entry @PHDTHESIS{gaubert92a, author={S. Gaubert}, title={Th\'eorie des syst\`emes lin\'eaires dans les dio\"\i des}, type={Th\`ese}, school={\'Ecole des Mines de Paris}, month={July}, year={1992}, }


Stephane Gaubert
Mon Feb 26 18:28:19 MET 1996