Dynamique symbolique sur un monoïde finiment présenté

Dans ce premier chapitre nous présentons les décalages dans le cas qui cor- respond au cadre le plus général de cette thèse, celui des des décalages définis sur un monoïde finiment présenté. La Partie 1.1 définit la notion de monoïde finiment présenté. Sur ces monoïdes il est possible de définir les décalages de deux façons équivalentes, qui correspondent à une approche topologique (Par- tie 1.2.1) ou combinatoire (Partie 1.2.2). La Partie 1.3 présente les trois classes de décalages dont il sera question dans la suite du manuscrit. 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 im- portant 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.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 M.

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) 2 E si et seulement si g = sut et h = svt avec v; s; t 2 M et (u; v) 2 R [ f(mmonoïde de présentation < GjR >. On dit qu’un monoïde est finiment présenté s’il possède une présentation < GjR > 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 f0; 1g est un monoïde finiment présenté de rang 2 dont une présentation est < 0; 1j; >. 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 M.

Le graphe de Cayley d’un groupe donne une représentation visuelle de la struc- ture 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.graphe de Cayley ; on la note jgj. 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.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.Nous avons choisi dans ce chapitre de d’abord traiter le cas des monoïdes fi- niment présentés. Toutes les notions définies précédemment sont toutefois com- patibles avec les groupes finiment présentés, au sens où l’on peut voir un groupe finiment présenté G =< GjR > comme un cas particulier de monoïde.