Methods and Applications of (max,+) Linear Algebra

Abstract : Exotic semirings such as the $(\max,+)$ semiring'' $(\mathbb{R}\cup\{-\infty\},\max,+)$, or the tropical semiring'' $(\mathbb{N}\cup\{+\infty\},\min,+)$, have been invented and reinvented many times since the late fifties, in relation with various fields: performance evaluation of manufacturing systems and discrete event system theory; graph theory (path algebra) and Markov decision processes, Hamilton-Jacobi theory; asymptotic analysis (low temperature asymptotics in statistical physics, large deviations, WKB method); language theory (automata with multiplicities). Despite this apparent profusion, there is a small set of common, non-naive, basic results and problems, in general not known outside the $(\max,+)$ community, which seem to be useful in most applications. The aim of this short survey paper is to present what we believe to be the minimal core of $(\max,+)$ results, and to illustrate these results by typical applications, at the frontier of language theory, control, and operations research (performance evaluation of discrete event systems, analysis of Markov decision processes with average cost). Basic techniques include: solving all kinds of systems of linear equations, sometimes with exotic symmetrization and determinant techniques; using the $(\max,+)$ Perron-Frobenius theory to study the dynamics of $(\max,+)$ linear maps. We point out some open problems and current developments.
Keywords :
Type de document :
Rapport
[Research Report] RR-3088, INRIA. 1997
Domaine :

Littérature citée [39 références]

https://hal.inria.fr/inria-00073603
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 13:17:48
Dernière modification le : samedi 17 septembre 2016 - 01:27:38
Document(s) archivé(s) le : dimanche 4 avril 2010 - 22:04:08

Identifiants

• HAL Id : inria-00073603, version 1

Citation

Stéphane Gaubert. Methods and Applications of (max,+) Linear Algebra. [Research Report] RR-3088, INRIA. 1997. 〈inria-00073603〉

Métriques

Consultations de la notice

354

Téléchargements de fichiers