Automates à multiplicité
Sylvain Lombardy
Ce cours présente les automates à multiplicité dans différents semi-anneaux : entiers, corps langages rationnels, semi-anneaux tropicaux, ...
On introduit d'abord le modèle des automates à multiplicité, ainsi que leurs différentes représentations, sagittale, matricielle ou linéaire.
On verra que ces automates représentent des séries formelles dites rationnelles, et que les opérations telles que le produit de Cauchy ou le produit d'Hadamard sont réalisables sur les automates.
Dans une première partie du cours, on présentera deux opérations qui préservent la série réalisée, l'une topologique, le revêtement, l'autre algébrique, la conjugaison. On verra les liens qui unissent ces opérations. Ensuite, on prouvera qu'une série est rationnelle si et seulement si elle appartient ainsi que ses "quotients" à un module finiment engendré. Le même type de caractérisation existe pour les séries représentables par automate déterministe.
On reviendra au niveau algorithmique pour élaborer des algorithmes de déterminisation ou de minimisation à partir de ces propriétés algébriques. L'existence ou la décidabilité de tels algorithmes dépend du semi-anneau de multiplicités. Enfin pour boucler la boucle, on verra que ces algorithmes s'expriment aussi comme conjugaisons et qu'ils permettent de relier l'équivalence de deux automates à la conjugaison.
Au total 12 cours, de 10h à 12h tous les lundis et vendredi suivants : 31 janvier, 04, 07, 11, 21, 25, 28 février, 04, 07, 11, 14, 18 mars 2011 à l'UPEMLV 5 bld Descartes, bât. Copernic, 4° étage salle 4B10R.
Accès Espace Numérique de Travail
