Décalages

Les décalages sont des systèmes dynamiques particuliers, définis très simplement comme des suitesde lettres que l’on décale une par une. Ils peuvent être vus de plusieurs points de vue. D’un pointde vue symbolique d’abord, on peut s’intéresser au langage correspondant, défini comme l’ensemble des motifs finis apparaissant dans les configurations, et à sa complexité ; d’un point de vue graphique ensuite, on peut regarder l’ensemble des étiquettes de chemins infinis sur un graphe, en fonction de la forme du graphe ; d’un point de vue topologique enfin, on peut utiliser les notions vues dans le chapitre précédent. Dans ce chapitre, nous nous intéressons donc aux décalages en reliant ces trois approches, au niveau des La définition des sous-décalages bilatères, par rapport à celle des unilatères, fait donc intervenir une condition supplémentaire de surjectivité. Cela vient du fait que l’on peut définir un sous-décalage pour un monoïde  quelconque somme un sous-système dynamique de σ, vu en tant qu’action continue du monoïde  sur ANous serons parfois amenés à considérer les composantes fortement connexes des graphes. La relation de liaison par un chemin induit un ordre partiel sur les composantes fortement connexes ; il y a donc des composantes connexes maximales et minimales. Règles locales. On a vu dans le chapitre précédent que les fonctions continues d’un espace symbolique dans un autre consistent en l’application parallèle de règles locales en chaque cellule. Une condition supplémentaire de préservation de tous les décalages impose alors que ces règles locales soient identiques.

Même si le résultat reste vrai pour des sous-décalages plus complexes (cf notamment une généralisation intéressante aux espaces uniformes dans..), on se restreint toujours ici à  = ❩ ou Groupages. Les mémorisation et groupage généraux d’un SDD «mémorisaient» les m derniers points de l’orbite. Dans le cas d’un sous-décalage, une interversion d’indices – comme pour le produit – permet de retrouver un sous-décalage, ce qui amène aux définitions suivantes. Si d = 1, on dira que Φ est hors-contexte ; il s’agit d’une généralisation de la notion de «lettre à lettre» aux morphismes d’itérés de sous-décalages. On parlera en particulier de simulation hors- contexte lorsque le morphisme impliqué est lettre à lettre. On notera alors que la relation de simulation hors-contexte est un préordre. Étant donné un sous-décalage sofique, on peut construire un graphe correspondant à un mémorisé donné, ou à un groupé donné : puisqu’il s’agit là de facteurs, ceci peut être réalisé par le fait 2.2.6. Inversement, si l’on a le graphe du mémorisé, on peut retrouver un graphe du sous-décalage de départ, puisqu’il est facteur de son mémorisé. C’est également le cas pour le groupé : on peut retrouver un graphe du sous-décalage m-dégroupé en remplaçant chaque arc d’étiquette (aRemarque 2.4.1. On peut voir que l’ensemble des étiquettes de chemins finis d’un graphe G = (V, E) sur A est exactement le langage de son système d’étiquettes. Le graphe peut donc être vu comme un automate fini reconnaissant le langage du sous-décalage, où les sommets représentent des états qui sont tous initiaux et terminaux. On peut construire l’automate non déterministe suivant (A, Q, δ, QEn continuant à utiliser la théorie des automates, on peut obtenir un graphe minimal représentant un sous-décalage donné. L’adaptation est simple car on requiert la résolubilité forte – ce qui est très différent de la notion de présentation minimale présentée par exemple dans [42, 73].

 Dans un graphe minimal, pour tout sommet v, il existe un mot u du langage du système d’étiquettes telle que tous les chemins étiquetés par u passent par v. En effet, si un sommet ne vérifiait pas cette condition, on pourrait l’ôter ainsi que les arcs adjacents et obtenir un graphe, toujours résoluble, avec un sommet de moins et le même système d’étiquettes. Autrement dit, un graphe G est synchronisant si l’étiquetage des chemins infinis est une conjugaison entre les systèmes d’arcs et d’étiquettes bilatères. L’ordre du synchronisme k égale alors le diamètre de la conjugaison inverse EΣ dans le système unilatère d’arcs d’un graphe k-synchronisant ; le graphe n’admettant alors que des sommets accessibles, cette conjugaison peut être vue comme une conjugaison de Σ dans le système bilatère d’arcs de ce graphe. De façon symétrique, il existe une autre conjugaison bipermutive, unidirectionnelle à gauche et d’inverse lettre à lettre de Σ dans un système bilatère d’arcs. Graphe réduit. Nous allons voir ici, dans le cas des STF, un autre type de minimisation que celui présenté dans la section précédente. Un graphe (V, E) est dit réduit à gauche (resp. à droite) s’il n’admet pas un couple de sommets distincts qui ont même voisinage entrant (resp. sortant), i.e. tel que les sommets initiaux des arcs arrivant à (resp. partant de) chacun de ces deux sommets sont identiques.