**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.

Mon Feb 26 18:28:19 MET 1996