Communautés concernées et enjeux scientifiques

L'introduction des semianneaux de type (max,+) a été historiquement motivée soit par des applications au sens concret du terme (problème central de l'ordonnancement, problèmes de cheminement dans les graphes, modèles de systèmes à événements discrets) soit par des liens avec des problèmes mathématiques pour lesquels ces semianneaux apparaissaient comme l'outil naturel. La théorie de ces semianneaux continue de se développer autour de ces motivations, dont voici un bref aperçu.

1. Modélisation, Évaluation de Performance et Commande de Systèmes à Événements Discrets. (SED) Les systèmes dynamiques linéaires sur le semianneau (max,+) et leurs extensions sont des modèles de certaines classes importantes de réseaux de Petri temporisés. Les systèmes présentant des phénomènes de synchronisation/assemblage (ateliers, réseaux de transports, systèmes multiprocesseur) deviennent souvent modélisables par des dynamiques linéaires sur ces semianneaux une fois que les décisions d'ordonnancement ont été spécifiées [2]. Les automates à multiplicités (max,+) ou (min,+) fournissent une généralisation de ces modèles, ce qui revient à étendre partiellement au cas temporisé la modélisation ``à la Ramadge-Wonham'' du comportement logique de SED par des automates classiques. Des modèles généralisés (min, max,+) ont par ailleurs été appliqués à la vérification de contraintes temporelles pour des circuits. Les résultats d'algèbre linéaire (max,+) (théorie spectrale des matrices (max,+), généralisations aux produits de matrices (max,+) aléatoires) se traduisent en termes d'évaluation de performance (calcul de taux de production, conditions de stabilité) [2, 16, 27]. Une théorie de la commande des systèmes (max,+) est en cours d'émergence (commande par modèle interne [6], poursuite de modèle [24]). Récemment, des extensions aux cas ``multilinéaire'' (systèmes dynamiques homogènes ) ont permis de prendre en compte des réseaux de Petri plus généraux [3, 19, 25], ce qui revient à supprimer l'hypothèse d'ordonnancements fixés à l'avance, et à terme doit permettre de voir certains problèmes d'ordonnancement comme des problèmes de commande.
2. Commande Optimale, Optimisation, Théorie des jeux. On peut développer une vision ``linéaire'' de l'optimisation, les versions les plus simples de l'équation de la programmation dynamique étant linéaires sur des semianneaux de type (max,+). Cela recouvre dans le cas discret, les classiques problèmes de cheminement dans les graphes [18], et dans le cas continu, les EDP d'Hamilton-Jacobi-Bellman (associées à des problèmes de commande déterministe) qui sont justiciables d'une théorie similaire à celle des EDP linéaires usuelles (espaces fonctionnels, etc.) [29]. Un formalisme analogue à celui des probabilités a été développé, fondé sur la théorie des mesures idempotentes [1]. On obtient de la sorte des théorèmes limites pour l'optimisation ainsi que dans certains cas des solutions explicites. Ce qui est au travail ici est un ``morphisme'' ou plutôt une ``correspondance'' qui, en remplaçant les lois usuelles par les lois , ``transforme'' la théorie des probabilités en théorie de l'optimisation et le contrôle stochastique en théorie des jeux [5]. Il est important de noter que ce point de vue inclut et généralise la théorie de l'optimisation [5], et qu'on peut en attendre des retombées pour certaines classes de systèmes où l'algorithmique reste en partie à développer (systèmes à retards, systèmes non-linéaires). L'unification de ces théories, initiée dans [34], s'est par exemple révélée féconde dans l'étude des problèmes de commande ``sensible au risque'' [35], et reste aujourd'hui en chantier.
3. Analyse asymptotique (WKB, grandes déviations). La méthode dite WKB pour l'analyse asymptotique des EDP, ainsi que les résultats de type grandes déviations conduisent (par passage à la limite) à étudier des équations de Hamilton-Jacobi ou des mesures dans l'algèbre (max,+), qui relèvent de la théorie linéaire de la commande optimale présentée au point 2 de cette liste [30, 29]. Dans le même esprit, les asymptotiques à température nulle en physique statistique conduisent à étudier des opérateurs linéaires (max,+). Ces différentes applications relèvent en fait d'une même théorie de l'Analyse Idempotente.
4. Théorie des langages. Les automates à multiplicités sur le semianneau tropical apparaissent naturellement en théorie des langages. Certains problèmes de décision classiques comme la ``finite power property'' (quand est-ce que la somme des puissances (étoile) d'un langage reconnu par un automate fini converge en un nombre fini de coups) se ramènent à des problèmes de limitation (finitude de l'ensemble des multiplicités) pour des automates tropicaux, ou de manière presque équivalente, à des problèmes de finitude de semigroupes de matrices dans le semianneau tropical [20, 23]. Les automates tropicaux calculent aussi les ``complexités non-déterministes'' (nombre minimal de décisions à prendre pour reconnaître un mot, pour un automate non-déterministe usuel) [32].