Décalages d’arbres

Ce quatrième chapitre est consacré aux décalages d’arbres, et plus particulièrement à la classe des décalages d’arbres sofiques. La Partie 4.1 présente les outils pour étudier les décalages d’arbres sofiques : automate d’arbres et au- tomate minimal. La Partie 4.1.5 est consacrée au théorème de décomposition, grâce auquel nous montrons que la conjugaison des décalages d’arbres de type fini est un problème décidable. La Partie 4.3 étudie la classe des décalages d’arbres presque de type fini, classe intermédiaire entre la classe des décalages d’arbres de type fini et la classe des décalages d’arbres sofiques est un monoïde libre son graphe de Cayley ne contient aucun cycle, c’est pourquoi on parle de décalage d’arbres dans cette partie. Rappelons que nous nous donnons un alphabet fini A.désigne la lettre qui apparaît en position x dans l’arbre t. Le support élémentaire de taille n est formé de l’ensemble des mots sur f0; 1; : : : ; d 1g de longueur au plus n. Un bloc désigne un motif élémentaire, et si u est un bloc on note juj sa hauteur. On rappelle que si T est un décalage d’arbres, son langage d’ordre n, noté L. Dans cette partie nous présentons une version des automates finis d’arbres qui reconnaît des configurations infinies ou des blocs finis. Dans ce modèle le calcul remonte des branches infinies vers la racine.

L’acceptation ou non d’un arbre est déterminée simplement par l’existence d’un calcul de l’automate remontant jusqu’à la racine, car tous les états sont choisis terminaux. Cette version d’auto-mate d’arbres correspond à la version standard d’automates d’arbres montants, lorsque tous les états sont à la fois initiaux et terminaux. Pour d’autres version d’automates d’arbres le lecteur pourra se référer à [CDGaucun fils. On définit une notion de calcul d’un automate d’arbres sur un arbre fini complet de la manière suivante. Un calcul fini de l’automate A = (V; A; ) sur un arbre fini complet u est un arbre fini complet C sur l’alphabet V tel que, pour tout nœud x de u, il existe une transition (CSur chacun des arbres, tous les nœuds d’un même niveau partagent la même couleur et deux niveaux consécutifs ont des couleurs différentes. Le décalage d’arbres TExemple 4.1.4. Les arbres acceptés par l’automate de l’Exemple 4.1.2 sont ceux qui ne contiennent aucun chemin le long duquel on trouve un nombre pair de entre deux . Le décalage d’arbres TLes automates d’arbres acceptent exactement les décalages d’arbres sofique,et les automates d’arbres locaux accepte exactement les décalages d’arbres de type fini. Les démonstrations de ces caractérisations sont similaires à celles des résultats correspondants pour les décalages sur N ou sur Z (voir [LM95].

Tout décalage d’arbres de type fini est accepté par un automate d’arbre déterministe local. Réciproquement tout décalage d’arbres accepté par un automate d’arbres déterministe local est de type fini.un décalage d’arbres de type fini défini par l’ensemble fini de motifs interdits F . Sans perte de généralité, on peut supposer que les motifs de l’ensemble F sont tous des blocs de hauteurs m avec m entier stric- tement positif. On définit un automate d’arbres déterministe A = (V; A; ) dont les états sont les blocs du langage d’ordre m : V = L. On définit l’au- tomate d’arbres A = (V; A; ), dont les transitions sont données par la règle suivante : (p; q; a) ! r , a = (r) où  est la fonction locale qui définit . Alors par définition cet automate est déterministe et reconnaît bien le décalage T.La réciproque de la Proposition 4.1.3 peut être démontrée en utilisant la no- tion de couverture de Shannon d’un décalage sofique, définie dans la Partie 4.1.4. Ainsi les notions d’irréductibilité pour les décalages et pour les automates sont directement corrélés.Les automates d’arbres reconnaissent les décalages d’arbres sofiques, mais pour l’instant nous n’avons pas trouvé d’automate d’arbres canonique reconnaissant un décalage d’arbres T. Dans ce but, nous définissons la notion de contexte d’un bloc fini, qui correspond à la notion de follower set de Lind et Marcus [LM95] pour les décalages sur N ou Z.Soit T un décalage d’arbre. Un contexte c est un motif fini dont une des feuilles joue un rôle spécial, on dira qu’elle est marquée. Si u est un motif, c(u) est le motif obtenu en remplaçant la feuille marquée du contexte c par le motif u. Si c(u) apparaît dans un motif du langage L(T), on dit alors que c est un contexte du motif u dans T.