Arbres à bourgeons et grammaires synchrones

Grammaires synchrones

Parce qu’elles permettent de décrire et d’engendrer des langages — ou ensembles de mots — les grammaires formelles [Cho56] sont des outils centraux en théorie des langages [Aut94]. Le processus emprunté par une grammaire formelle pour engendrer un mot est simple : on commence à partir d’un mot particulier, appelé axiome, auquel on applique successivement des dérivations, c’est-à-dire des substitutions de certains de ses facteurs par d’autres mots, selon un ensemble fixé de règles, dites règles de substitutions. Les mots que l’on peut obtenir ainsi forment le langage engendré par la grammaire. Plusieurs sortes de grammaires ont été introduites et étudiées : les grammaires hors contexte, les grammaires contextuelles, les grammaires sans restrictions, pour ne citer que ces exemples, qui possèdent chacune d’elles leur propre niveau de généralité, et permettent d’engendrer et de décrire certains types de langages plutôt que d’autres [HMU00].

L’objectif de ce chapitre est d’introduire un type particulier de grammaires dans le but d’engendrer des structures arborescentes selon un tout autre processus de génération. Dans nos grammaires, les substitutions doivent être synchrones : le principe est que, à chaque étape de substitution, toutes les feuilles de l’arbre sont substituées simultanément par de nouveaux arbres suivant un ensemble de règles de substitution fixé. Nous qualifions naturellement ces objets de grammaires synchrones. La motivation principale pour l’introduction de ces structures réside dans le fait que ces grammaires permettent d’engendrer des arbres tout en conservant un contrôle sur les hauteurs de chacun de ses sous-arbres. Rappelons à ce propos que la hauteur d’un arbre est la longueur du plus long chemin connectant sa racine à l’une de ses feuilles. De plus, sous certaines conditions, nous pouvons extraire, à partir d’une grammaire synchrone, une équation fonctionnelle de point fixe pour la série génératrice qui dénombre les arbres engendrés selon leur nombre de feuilles. Les résultats présentés ici sont utilisés à plusieurs reprises dans le chapitre 8, dans le but de dénombrer plusieurs types de structures arborescentes en rapport avec les arbres binaires équilibrés et le treillis de Tamari.

Arbres à bourgeons et grammaires synchrones

Ce chapitre est organisé comme suit. Dans le paragraphe 7.1, nous introduisons les arbre sà bourgeons, les grammaires synchrones, et le principe de substitution synchrone. Le para- graphe 7.2 est consacré à la description d’un procédé qui permet d’obtenir une équation fonctionnelle de point fixe pour la série génératrice dénombrant les structures arborescentes engendrées par une grammaire synchrone. Nous décrivons aussi un algorithme qui permet de calculer contraire, tous les arbres à bourgeons considérés par la suite sont sur B. Soit D un arbre à bourgeons. Les nœuds de D sont ses sommets qui ne sont pas des bourgeons. L’ensemble des bourgeons de D est noté Brg(D). Si x est un bourgeon de D étiqueté par b) de ses bourgeons, lus de la gauche vers la droite. Si b est un bourgeon de D, son évaluation ev(b) est la lettre de B qui l’étiquette. Par extension, l’évaluation ev(D) de D est l’élément de l’algèbre commutative Z[B] des polynômes sur B défini parsens de la définition 1.1.1 du chapitre 1. Il existe en effet pour tout n > 1 une infinité d’arbres à bourgeons de taille n. Nous pouvons par exemple construire une infinité d’arbres à bourgeons de taille 1 qui sont constitués d’une unique branche de longueur arbitrairement grande et qui possèdent un unique bourgeon.

Conditions sur les grammaires synchrones

Ainsi, et à plus forte raison, une grammaire synchrone localement finie engendre pour tout n > 1 un nombre fini d’arbres à bourgeons de taille n ainsi qu’un nombre fini d’arbres à bourgeons ayant une évaluation donnée. Avant de donner un critère suffisant permettant d’affirmer qu’une grammaire synchrone est localement finie, rappelons ce qu’est un ordre monomial. Un ordre monomial est un ordre total 6 défini sur un ensemble M de monômes, et qui vérifie les deux conditions suivantes :Démonstration. Soit u un mot sur B. Étant donné que l’ensemble B des types de bourgeons est fini, et que d’après (7.1.14), chaque dérivation dans S augmente strictement l’évaluation de tout arbre à bourgeon sur lequel elle est appliquée, il existe un entier ℓ tel que toute dérivation qui engendre un arbre à bourgeon ayant u comme évaluation fasse moins de ℓ étapes. Maintenant, comme l’ensemble R des règles de substitution est fini, le nombre de dérivations qui engendrent des arbres à bourgeons ayant u comme évaluation est fini. Le résultat suit finalement du fait que comme B est fini, il existe un nombre fini d’évaluations de longueur n, et donc, également un nombre fini de dérivations qui engendrent des arbres à bourgeons de taille n.