Next: Logique et automates Up: Home Page Previous: Théorie des semigroupes

Equations et variétés

Le théorème de Birkhoff affirme que toute variété de semigroupes peut être définie par une suite d'équations. Dans le cas des variétés de semigroupes finis, Eilenberg et Schützenberger ont montré que toute variété peut être ultimement définie par une suite d'équations. Celà signifie qu'un semigroupe S est dans la variété s'il satisfait toutes les équations à partir d'un certain rang, dépendant de S. Reiterman a donné une version plus satisfaisante de ce résultat. L'idée intuitive est de remplacer les suites d'équations par leur limite. Toute la difficulté consiste à formaliser rigoureusement cette notion de limite, ce qui se fait par des outils topologiques assez classiques. En partant de ces outils, P. Weil et moi-même avons d'ailleurs considérablement étendu le théorème de Reiterman [85]. En particulier, dans le cas des variétés de semigroupes ordonnés, les variétés ne sont plus définies à l'aide d'équations, mais à l'aide d' inéquations.

D'une façon générale, déterminer les équations d'une variété est un problème souvent difficile, car on ne connaît pas de méthode générale. Même dans le cas des variétés engendrées par un seul semigroupe de petite taille (moins de 10 éléments) on aboutit le plus souvent à des problèmes ouverts et les algorithmes de réécriture semblent inopérants.

J'ai toutefois déterminé (avec Straubing et Thérien) les équations de certaines petites variétés de semigroupes, ainsi que la description des variétés de langages correspondantes [40].

En appliquant un nouveau résultat de combinatoire des mots aux équations, j'ai montré avec H. Straubing que la variété des monoïdes J-triviaux contenait une infinité non dénombrable de sous-variétés [20].

J'ai également déterminé les équations du produit de la variété des semigroupes idempotents par elle-même. Ce résultat permet de décider en temps O(n²) si un semigroupe de taille n est élément de cette variété [33].

L'article [84], en collaboration avec P. Weil, donne un cadre général pour déterminer les équations de variétés obtenues comme produit de Mal'cev de deux autres variétés. La technique est très puissante et nous a permis de déterminer les équations de nombreuses variétés.

Next: Logique et automates Up: Home Page Previous: Théorie des semigroupes