next up previous contents

Next: Théorie des codes Up: Home Page Previous: Produit de concaténation


Topologie profinie

En 1984, j'ai entrepris l'étude détaillée de la topologie des groupes finis et des topologies p-adiques sur le monoïde libre [34]. La topologie des groupes finis a été définie pour le groupe libre par M. Hall dans les années cinquante puis étendue aux monoïdes libres par C. Reutenauer. On dit qu'un groupe G sépare deux mots u et v s'il existe un morphisme de monoïdes f du monoïde libre dans G tel que f(u) soit différent de f(v) . On peut alors définir une distance pour laquelle deux mots sont proches s'il faut un groupe de grande taille pour les séparer. On obtient ainsi une topologie du monoïde libre particulièrement remarquable, pour laquelle la multiplication est uniformément continue. Comme on va le voir, l'étude de cette toplogie m'a conduit à des développements tout à fait inattendus.

J'ai démontré [69] que les ouverts de ces topologies sont clos pour les opérations classiques suivantes : union, produit et plus, quotient à droite et à gauche par un ensemble arbitraire. En fait si U0, ..., Uk sont des ouverts, et si a1, ..., ak sont des lettres, alors l'ensemble U00a1U1 ... akUk est également ouvert.

Il restait à décrire les ouverts et les fermés de cette topologie. J'ai proposé en 1985 [42] une conjecture qui permettait de tester si un langage reconnaissable donné est fermé (resp. ouvert) et plus généralement, de calculer l'adhérence d'un langage reconnaissable. Cette conjecture affirmait qu'un langage reconnaissable est fermé si et seulement si son semigroupe syntactique satisfait une condition algébrique (C) très simple d'énoncé. J'ai d'abord résolu cette conjecture dans deux cas particuliers significatifs. Je travaillais à la même époque sur une importante conjecture de J. Rhodes en théorie des semigroupes (pour la solution de laquelle J. Rhodes avait proposé 100$ de récompense). J'ai réalisé qu'il existait un lien entre la conjecture de Rhodes et ma conjecture topologique [55]. J'ai d'abord démontré que la conjecture topologique entrainait la conjecture de Rhodes [53]. Ultérieurement, j'ai montré avec S.W. Margolis l'équivalence des deux conjectures [73]. Enfin, j'ai donné avec C. Reutenauer [70] une version de la conjecture valable dans le groupe libre : (C') le produit d'un nombre fini de sous-groupes de type fini du groupe libre est fermé . Cette formulation a beaucoup contribué à populariser le problème qui a reçu à quelques mois d'intervalle une double solution en 1990-1991. Ch. Ash a démontré la conjecture de Rhodes par des méthodes de semigroupe et la conjecture (C') a été résolue par Ribes et Zalesskii par des techniques de théorie des groupes.

Revenant à la motivation de départ, j'ai caractérisé en 1994 les ouverts reconnaissables [82,98]: ce sont précisément les langages de niveau 1 dans la hiérarchie que j'avais étudiée avec Margolis. Leur caractérisation par semigroupe syntactique est donnée par (C) et découle du résultat de Ribes et Zalesskii.

De nombreuses conséquences de ces résultats sont résumées dans un article cosigné avec Henckell, Margolis et Rhodes [66]. Une autre retombée intéressante est la solution d'un problème dont l'énoncé ne fait appel qu'aux définitions les plus élémentaires de la théorie des automates. On dit qu'un automate fini (incomplet) déterministe est reversible si l'automate obtenu en retournant les flèches est aussi déterministe. Cela revient à dire que chaque lettre définit une fonction injective de l'ensemble des états dans lui-même. On munit ces automates reversibles d'un ensemble d'états initiaux et d'un ensemble d'états finaux. Les automates de ce type définissent une certaine classe de langages, qu'il s'agit de décrire de façon effective. Il est immédiat de vérifier que les idempotents du semigroupe syntactique de ces langages commutent, mais cette condition ne suffit pas à les caractériser et il faut rajouter une condition supplémentaire. Cette condition est que le langage soit fermé dans la topologie définie plus haut. On peut alors traduire cette condition en termes algébriques via (C') pour obtenir une caractérisation effective simple [51,74].

J'ai également travaillé sur la topologie p-adique [42,79], qui se définit de la même façon, en remplaçant groupe fini par p-groupe fini (p étant un nombre premier). J'ai établi, en collaboration avec J. Berstel et M. Crochemore [56], que l'on pouvait extraire de la suite de Thue-Morse une suite de mots qui converge vers le mot vide dans la topologie p-adique.



next up previous contents

Next: Théorie des codes Up: Home Page Previous: Produit de concaténation


Jean-Éric PIN, 5 Octobre 1996