Machines de Mealy, (semi-)groupes d’automate, problèmes de décision et génération aléatoire

Automates de Mealy et théorie des groupes

Cette thèse est à l’intersection des mathématiques et de l’informatique. La partie mathématique provient de la théorie des (semi-)groupes, une théorie qui s’est initialement développée à la fin du XVIIIe siècle avec Lagrange, mais surtout au siècle suivant avec Galois et Cauchy. Conçue à l’origine pour étudier les racines de polynômes, cette notion de groupe s’est rapidement révélée utile car elle généralise de façon abstraite l’idée de symétrie. De fait, le théorème de Frucht [39] dit, en substance, que tout groupe fini peut être vu comme l’ensemble des symétries d’un graphe. Au cours du XXe siècle, cette notion de (semi-)groupe est devenue plus abstraite tout en incorporant des éléments de divers horizons des mathématiques (topologie, analyse, algèbre multi-linéaire), pour devenir une branche majeure des mathématiques contemporaines.

La partie informatique de cette thèse, la théorie des automates, a été formalisée plus tardivement, dans les années 1950 [4], mais est une des briques de base de l’informatique théorique, et se retrouve très tôt dans la notion de calcul. En effet, on peut voir les automates comme une abstraction simple d’un modèle de calcul, moins puissante que les fameuses machines de Turing, mais tout de même capable de modéliser de nombreux phénomènes. La théorie des automates est naturellement en lien avec la logique [4] et la théorie des langages (formels ou naturels).

Ces deux théories, des (semi-)groupes et des automates ont très tôt été reliées, notamment par Schützenberger qui introduit dès les balbutiements de la théorie des automates, en 1956 [90], la notion de monoïde syntaxique qui permet de caractériser dans des termes d’algèbre les langages reconnus par un automate. Par exemple, dans [89], Schützenberger montre que les automates reconnaissant les langages sans étoile sont exactement ceux dont le monoïde syntaxique est apériodique. Dès lors, une branche importante de l’étude des langages formels et de la théorie des automates a utilisé les semi-groupes comme un outil, voir par exemple [88, 85].

À l’inverse, dès les années 60, Gluškov [43] propose d’utiliser les automates, et plus exactement les automates de Mealy, pour engendrer des (semi-)groupes. C’est cette construction qui nous intéresse plus particulièrement dans cette thèse. En effet, cette idée s’avère extrêmement fructueuse en théorie des (semi-)groupes, puisque nombre de conjectures et de problèmes ouverts ont été résolus en utilisant ces (semi-)groupes engendrés par des automates de Mealy. On peut résumer grossièrement et subjectivement la chronologie des groupes de Mealy en quelques dates : en 1972, Alešin donne un exemple d’un groupe de Burnside infini comme sous-groupe d’un groupe d’automate [2]. Puis, en 1980 Grigorchuk améliore le résultat d’Alešin en exhibant un exemple de 2-groupe infini engendré par un automate de Mealy [50]. Grigorchuk montre en 1984 que le groupe d’Alešin Grigorchuk est à croissance intermédiaire, répondant ainsi à une question de Milnor [49]. Gupta et Fabrykowski donnent en 1985 un nouvel exemple de groupe d’automate ayant une croissance intermédiaire [36], et Gupta et Sidki donnent, dans [57], en utilisant les automates de Mealy, en 1989 des exemples de p-groupes infinis pour tout nombre premier p. En 2000, Grigorchuk et Zuk effectuent des calculs sur le spectre et la mesure spectrale de l’opérateur de Markov de la marche aléatoire simple sur le groupe de l’allumeur de réverbères [55]. Ces calculs les conduiront à réfuter une conjecture d’Atiyah peu après, tandis qu’en 2004, Wilson montre, en présentant l’exemple d’un groupe d’automate, qu’un groupe peut avoir une suite de systèmes de générateurs telle que le taux de croissance de ce groupe soit aussi proche de 1 que désiré, répondant ainsi à une question de Gromov. En 2005, Glasner et Mozes montrent que le groupe libre de rang 2 peut être engendré par un automate (biréversible) de Mealy [42]. Dans la foulée, Steinberg, M. Vorobets et Y. Vorobets démontrent que tous les groupes libres de rangs finis pouvaient être engendrés par des automates de Mealy [97]. En 2010, I. Bondarenko, V. Bondarenko, Sidki et Zapata utilisent la structure de l’automate pour montrer que les problèmes de l’ordre et de la conjugaison sont décidables pour une certaine classe de groupes d’automate [19]. Et en 2014, Gillibert montre que le problème de l’ordre et de la finitude sont indécidables pour les semi-groupes d’automate [41], tandis que Klimann démontre que le problème de finitude est décidable pour une classe très structurée d’automates [63].

On voit qu’ici la situation est renversée par rapport au paragraphe précédent : la théorie des (semi-)groupes se sert des automates de Mealy comme d’un outil. En fait, dans un certain nombre de cas, les automates sont même utilisés comme une boîte noire, qui fournit un (semi-)groupe et que l’on peut oublier après coup. Dans cette thèse nous allons au contraire nous concentrer sur cet automate et ses propriétés, en vue de fournir des informations sur le (semi-)groupe engendré.

À la chasse aux papillons

Ou, j’espère, un exemple intéressant d’automate.

Dans cette section, on procède à l’étude détaillée d’un automate de Mealy, dont on montre entre autres qu’il engendre un groupe de Burnside infini. Elle nécessite d’avoir déjà rencontré, au moins de loin, les automates de Mealy ou tout au moins les transducteurs.

Pourquoi le Bread-and-Butterfly ? 

Dans le cadre de l’article [29], nous cherchions des automates ayant une quantité indénombrable de points singuliers (voir le chapitre III pour plus de détails). On a réussi en modifiant l’automate de Grigorchuk. Prenons deux copies de cet automate, inversons les lettres sur l’une des copies puis identifions certains états : on obtient l’automate représenté figure III.5. On s’est alors intéressé à cet exemple, et on s’est demandé quelles propriétés de l’automate de Grigorchuk étaient conservées. Au final, l’automate ne nous a pas semblé avoir de propriétés réellement remarquables, en dehors de celle que l’on recherchait initialement. Cependant, on a continué de regarder ce type de constructions, en se concentrant sur la propriété de Burnside. On a de nouveau modifié l’automate G de Grigorchuk pour obtenir l’automate BBF. On a choisi de dédoubler l’alphabet entre lettres négatives sur une copie de l’automate et positives sur l’autre (d’où le choix surprenant de ±0). On a alors identifié les états a, b et e des deux automates. Restait à définir les actions sur l’alphabet de signe opposé. On a choisi de calquer l’idée du produit direct (voir plus loin, dans l’introduction technique, section 2), et on a défini l’action comme étant triviale sur l’alphabet de signe opposé et envoyant certains états sur l’identité et d’autres sur a (sans que cette décision semble changer profondément le groupe engendré). Comme on le voit, ces choix sont assez arbitraires (trois « on a choisi » dans le paragraphe) et suivent, pour l’instant, une démarche de type « essai-échec » plus qu’une théorie construite. On espère bien entendu pouvoir obtenir une formalisation dans un second temps .

Commençons par un peu de vocabulaire : l’ensemble Q = {a, b, ±c, ±d, e} est appelé l’ensemble des états de BBF. L’ensemble Σ = {±0, ±1} est quant à lui appelé son alphabet.

Groupe de Burnside 

Un groupe de Burnside est un groupe ayant un nombre fini de générateurs, et où tous les éléments ont une puissance non nulle qui vaut l’identité. En 1902, Burnside demande dans [24] s’il existe un groupe infini satisfaisant ces conditions. On voit que tous les groupes finis sont des groupes de Burnside, tandis que Z et ⊗N Z/2Z sont infinis mais ne sont pas des groupes de Burnside, respectivement car Z possède des éléments d’ordre infini (tous les éléments différents de 0 en fait), et ⊗N Z/2Z ne peut être engendré par un nombre fini d’éléments. La réponse à la question de Burnside, qui ne fut donnée que 62 ans plus tard, est positive. Cependant ces premiers exemples ne sont pas vraiment manipulables. Alešin en 1972 [2], puis Grigorchuk en 1980 [50], proposent des exemples de groupes de Burnside infinis sous la forme, chronologiquement, d’un sous-groupe puis d’un groupe d’automate. Ces exemples ont certainement constitué un tournant dans l’étude des groupes d’automate, et continuent d’être décortiqués, analysés et généralisés.

Après expérimentations en GAP, il nous a semblé que le groupe <BBF>  était peut être un groupe de Burnside infini. Nous montrons que c’est bien le cas en adaptant une démonstration présente dans [58].

Croissance du groupe

Quand on a fait la démonstration que le groupe du Bread-and-Butterfly est de Burnside infini, on a beaucoup utilisé la longueur de la représentation, dans l’automate, d’un élément du groupe. La question « combien d’éléments peut-on représenter avec des mots de longueur au plus ? ? » vient alors à l’esprit [73]. Si l’on se pose cette question pour le groupe des entiers, avec comme générateurs 1 et −1, alors on crée à chaque pas deux nouveaux éléments, la croissance est donc linéaire. Dans le cas du plan discret cette croissance est quadratique, et si l’on regarde le groupe libre, alors cette croissance est exponentielle. L’une des grandes réussites des groupes d’automate a été, en 1984 avec l’article de Grigorchuk [49], de montrer qu’il existait des groupes qui croissent plus vite que tout polynôme mais moins vite que toute exponentielle. On parle alors de croissance intermédiaire, et Grigorchuk a ainsi résolu un problème ouvert vingt ans plus tôt par Milnor [76].

Table des matières

Introduction
I Automates de Mealy et théorie des groupes
1 À la chasse aux papillons
1.1 Semi-groupe et groupe d’automate
1.2 Groupe de Burnside
1.3 Structure des fonctions de transitions, automate dual
1.4 Action sur les mots et points singuliers
1.5 Croissance du groupe
1.6 Génération aléatoire
2 Théorie des groupes et automates de Mealy
2.1 Automates de Mealy, groupes d’automate
2.2 Propriétés structurelles des automates de Mealy et des (semi-)groupes
d’automate
2.3 Outils pour les automates de Mealy
3 Quelques problématiques sur les (semi-)groupes d’automate
3.1 Propriétés des (semi-)groupes d’automate
3.2 Problèmes impliquant les groupes d’automate
3.3 Dynamique de l’action
3.4 Transfert des propriétés structurelles de l’automate au groupe
II Automates de Mealy et le problème de Burnside
1 L’arbre lexicographique de Schreier
2 Cas des automates non biréversibles
3 Cas des automates biréversibles, connexes et ayant un nombre premier d’états
3.1 Arbres de la jungle, tiges et lianes
3.2 Équivalences et combinatoire sur les tiges
3.3 Application au problème de Burnside
4 Remarques et conclusions
4.1 Dénombrement dans les arbres de Schreier
4.2 Conclusion
III Dynamique de l’action du groupe d’automate sur l’arbre enraciné infini
1 Points singuliers
2 Points singuliers et propriétés structurelles de l’automate
2.1 Automates contractants
2.2 Automates contractants, points singuliers et produit(s)
2.3 Automates biréversibles
3 Points singuliers et graphes de Schreier
4 Paires commutantes et pavages de Wang
5 Conclusion
IV Génération aléatoire de groupes
1 Automates cycliques
1.1 Groupe engendré par un automate cyclique
1.2 Union d’automates cycliques
2 Cas des automates cycliques à deux états
2.1 Aparté : sur la probabilité que deux permutations aient le même ordre
3 Cas général
4 Remarques et conclusions
Conclusion

Télécharger le rapport complet