Décalages d’arbres

Décalages d’arbres

Ce quatrième chapitre est consacré aux décalages d’arbres, et plus particu- liè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., l’ensemble des mots sur l’alphabet f0; 1; : : : ; d1g, sera un nœud, et le nœud correspondant à l’élément neutre du monoïde, ou de manière équivalente au mot vide, sera appelé la racine et noté par « . Si x est un nœud et que i est un élément de f0; 1; : : : ; d 1g alors on dit que y = xi est le idé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(T), est formé de tous les blocs élémentaires qui apparaissent dans des configurations de T. Les nœuds d’un bloc de taille n correspondant à un mot de longueur n sur f0; 1; : : : ; d 1g sont appelés les feuilles, ce sont des nœuds sans fils.Sans perte de généralité nous allons supposer dans toute la suite que les arbres considérés sont des arbres binaires, c’est-à-dire que nous nous restreignons au cas où d = 2. Dans ce cas nous parlerons de fils gauche et droit. On utilisera la notation (a; t. En particulier, un bloc de hauteur 1 sera noté (a; b; c), où a étiquette la racine, b le fils gauche de la racine et c le fils droit de la racine.

Automate d’arbres

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 Test de type fini.

Les 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]Proposition 4.1.1 ([AB09]). 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.