Soutenance mémoire
Dynamique symbolique sur un monoïde finiment présenté
Monoïdes finiment présentés
Cette partie est consacrée aux monoïdes finiment présentés, objets sur lesquels seront définis les décalages dans toute la suite. Notre étude se restreint à ces structures car elles constituent à nos yeux le juste milieu entre simplicité de la définition, puisque la description d’un tel monoïde est finie, et complexité de l’objet, puisque le problème du mot peut y être indécidable [Col86]. Un outil important pour l’étude de ces monoïdes est le graphe de Cayley (Partie 1.1.2), qui permet d’une part de visualiser leurs structures et d’autre part d’en caractériser certaines propriétés.
Définition
Un monoïde (M, ◦), ou plus simplement M, est constitué d’un ensemble d’éléments M stable par une loi de composition associative ◦, et qui possède un élément neutre εM pour cette loi. Nous prenons ici la convention de noter cette loi multiplicativement, en omettant la plupart du temps le symbole ◦.
Remarque. Dans toute la suite du manuscrit, nous ne considérons que des monoïdes dont le cardinal est infini.
Un monoïde M est libre s’il existe un sous-ensemble G de M tel que tout élément de M s’écrit d’une et une seule manière comme un produit fini d’éléments de G. On dit alors que M est libre sur G. Tous les monoïdes libres sur un même ensemble G sont isomorphes, c’est pourquoi on s’autorise à parler du monoïde libre sur G. Dans le cas où G est un ensemble fini à n éléments, on parle du monoïde libre à n générateurs, et on le note Mn. Soit M le monoïde libre sur G, et R un sous-ensemble de M × M, appelé ensemble de relations. On définit sur M une relation symétrique E ⊆ M × M de la façon suivant : on dit que (g, h) ∈ E si et seulement si g = sut et h = svt avec v, s, t ∈ M et (u, v) ∈ R ∪ {(m0 , m),(m, m0 ) ∈ R}. La clôture réflexive et transitive de la relation E est alors une relation d’équivalence ∼R. En quotientant le monoïde libre M par cette relation d’équivalence, on obtient le monoïde de présentation < G|R >. On dit qu’un monoïde est finiment présenté s’il possède une présentation < G|R > pour laquelle G et R sont des ensembles finis. Le cardinal de l’ensemble G est appelé le rang du monoïde M.
Exemple 1.1.1. Le monoïde des mots finis sur l’alphabet {0, 1} est un monoïde finiment présenté de rang 2 dont une présentation est < 0, 1|∅ >. L’opération dans ce monoïde est la concaténation, et l’élément neutre pour cette loi est le mot vide ε. Il est isomorphe au monoïde libre à deux générateurs M2.
Exemple 1.1.2. Une présentation du groupe diédral d’ordre 4, qui est le groupe des isométries du carré, est :
< a, b|a4 = b2 = ε, ba = a3 b >
Graphe de Cayley
Le graphe de Cayley d’un groupe donne une représentation visuelle de la structure du groupe par un graphe. C’est aussi un moyen pour construire des graphes avec de fortes propriétés de régularité. On peut également étendre cette notion pour définir le graphe de Cayley d’un monoïde.
Définition 1. Le graphe de Cayley du monoïde M =< G|R >, noté ΓM = (VΓ, EΓ) est un graphe orienté construit de la manière suivante : l’ensemble des sommets est VΓ = M, et les arêtes sont
EΓ = {(g, g.gi) ∈ M × M | gi est un générateur de M} .
Notons que le graphe de Cayley du monoïde M dépend donc de la représentation qu’on a choisie. Deux exemples en sont donnés sur la Figure 1 ; pour plus de clarté on a attribué une couleur à chaque générateur du monoïde. Dans la suite nous identifierons un élément du monoïde M avec le nœud qui le représente dans le graphe de Cayley ΓM. Lorsqu’aucune confusion n’est possible, le graphe de Cayley de M sera simplement appelé Γ. La longueur d’un élément g du monoïde M est la longueur du plus court chemin entre les sommets correspondant à g et à l’élément neutre ε dans le graphe de Cayley Γ ; on la note |g|. Certaines propriétés du monoïde peuvent être lues directement sur le graphe de Cayley. De manière informelle, les cycles dans le graphe correspondent aux relations R entre générateurs. En particulier, un graphe de Cayley est celui d’un monoïde libre si et seulement si le graphe est acyclique.
Cas des groupes finiment présentés
Un groupe est un ensemble d’éléments muni d’une loi de composition interne associative, qui possède un élément neutre pour cette loi et tel que chaque élément possède un inverse. Cette structure gagne donc en rigidité par rapport à celle d’un monoïde car on impose la présence des inverses.
Remarque. Si G est une partie d’un groupe, on notera par G−1 l’ensemble des inverses des éléments de G.
Nous avons choisi dans ce chapitre de d’abord traiter le cas des monoïdes finiment présentés. Toutes les notions définies précédemment sont toutefois compatibles avec les groupes finiment présentés, au sens où l’on peut voir un groupe finiment présenté G =< G|R > comme un cas particulier de monoïde : si G est un ensemble de générateurs pour le groupe, c’est-à-dire que tout élément du groupe s’écrit comme un produit fini d’éléments de G et d’inverses d’éléments de G, et que le groupe est défini par l’ensemble de relations R sur des éléments de G ∪ G−1 , alors le groupe G peut être vu comme le monoïde finiment présenté suivant :
G =< G ∪ G−1 |R ∪ {gg−1 = ε, g ∈ G} > .
Le graphe de Cayley du groupe nous donne également un moyen très simple de définir une distance entre les éléments du groupe. Étant donnés deux éléments g et h du groupe G, la distance entre g et h, notée dG(g, h), est la longueur du plus court chemin entre les sommets correspondant à g et h dans le graphe de Cayley Γ(G) de G.
De même que pour un monoïde, la longueur d’un élément g du groupe G est la distance entre g et l’élément neutre ε ; on la note |g| = dG(g, ε). Un résultat classique est que le groupe G muni de la distance dG est un groupe topologique. Notons qu’une fois encore la distance ainsi définie sur le groupe dépend de la présentation choisie, mais pour un groupe finiment présenté toutes les présentations donnent des distances équivalentes. On notera Fn le groupe libre à n générateurs. Par convention, lorsque l’on travaillera sur un groupe on omettra les inverses dans l’ensemble de générateurs.
|
Table des matières
Introduction
Motivation
Résultats principaux
1 Dynamique symbolique sur un monoïde
1.1 Monoïdes finiment présentés
1.1.1 Définition
1.1.2 Graphe de Cayley
1.1.3 Cas des groupes finiment présentés
1.2 Les décalages, deux points de vue complémentaires
1.2.1 Point de vue topologique
1.2.2 Définition par motifs interdits
1.2.3 Coïncidence des définitions
1.3 Classes de décalages
1.3.1 Décalages de type fini
1.3.2 Décalages sofiques
1.3.3 Décalages effectifs
2 Codage d’une machine de Turing dans un décalage sur Z2
2.1 Décalages substitutifs et décalages S-adiques
2.1.1 Substitutions
2.1.2 Composition de substitutions
2.1.3 Décalages S-adiques
2.1.4 Décalages substitutifs non déterministes
2.1.5 Substitutions non-déterministes et théorème de Mozes
2.2 Opérations et simulation
2.2.1 Simulation et classes stables
2.2.2 Exemples d’opérations et résultats classiques de simulation
2.2.3 La sous-action projective
2.3 Décalage sofique codant une machine de Turing
2.3.1 Machines de Turing dans un SFT
2.3.2 Espaces de calcul pour MT
2.3.3 Communication dans le décalage T{s1}
2.3.4 Initialisation des calculs
2.3.5 Diagramme espace-temps d’une MT dans un décalage sofique
3 Simulation de décalages effectifs 1D par des décalages de type fini 2D
3.1 Un résultat de simulation
3.1.1 Énoncé du résultat et idée de la preuve
3.1.2 Communication entre machines
3.1.3 Génération de motifs interdits
3.1.4 Détection de motifs interdits
3.1.5 Construction finale
3.2 Deux applications du théorème de simulation
3.2.1 Ordres sur les langages de motifs et son équivalent sur les décalages
3.2.2 Décalages S-adiques multidimensionnels effectifs
4 Décalages d’arbres
4.1 Généralités
4.1.1 Automate d’arbres
4.1.2 Décalages d’arbres irréductibles
4.1.3 Contexte, automate réduit et bloc synchronisant
4.1.4 Automates minimaux
4.1.5 Théorème de décomposition
4.2 Décalages de type fini
4.2.1 Décalages de sommets et de transitions
4.2.2 Conjugaison des décalages de type fini
4.3 Les décalages presque de type fini (AFT)
4.3.1 Définition
4.3.2 Caractérisation des AFT par leur couverture de Shannon
4.4 Procédures de décision
4.4.1 Calcul de la couverture de Shannon
4.4.2 Automate des paires et graphe des paires
4.4.3 Localité
4.4.4 Automate fermant à gauche
Conclusion
