Travail commun avec Véronique Froidure

On présentera un algorithme de calcul des semigroupes finis et le logiciel qui est en cours de développement à partir de cet algorithme. L'idée est de pouvoir traiter tous les types usuels de semigroupe (semigroupes de transformations - provenant par exemple d'un automate déterministe -, semigroupes de matrices - provenant par exemple d'un automate non déterministe -, semigroupes de matrices à coefficients dans un semianneau fini - provenant par exemple d'un automate avec sortie dans le semianneau tropical -, etc.). On se donne donc un ensemble fini ordonné de générateurs A, pris dans un des univers décrits précédemment et on cherche à calculer le semigroupe engendré par A. On obtient en sortie les graphes de Cayley droit et gauche du semigroupe ainsi qu'une présentation du semigroupe par un système de réécriture confluent et noethérien (toutes ces notions seront rappelées au cours de l'exposé). On donnera également des algorithmes pour le calcul des relations de Green et pour le calcul de l'ordre syntactique d'une partie du semigroupe. On donnera également des indications sur les structures de données utilisées pour implanter ces algorithmes.