Réduction d’expressions spécifiées par un système

Réduction d’expressions spécifiées par un système

 Système combinatoire d’arbres

Dans cette partie, nous 8*/-éfinissonsproprementcequenousentendonsparsystèmes combinatoires d’expressions. des arbres d’expressions sous forme de classe combinatoire et de systèmes Dans toute cette partie, les arbres considérés sont des arbres planaires étiquetés enracinés, c’est-à-dire qui vérifient les conditions suivantes : a. (enracinés) tout nœud possède un unique père, à l’exception d’un seul nœud, appelé racine b. (planaires) les fils d’un nœud sont ordonnés,

si bien que les deux arbres • /\• et • /\ sont distincts c. (étiquetés) chaque nœud est étiqueté par un symbole. • La taille d’un arbre est son nombre de nœuds. Pour un nœud N d’un arbre planaire enraciné, nous appelons arité de N le nombre de fils du nœud N. Les nœuds d’arité 0 sont classiquement appelés feuilles, les nœuds d’arité 1 sont appelés nœuds unaires, ceux d’arité 2 nœuds binaires.

Nous employons le terme arité et non degré comme en théorie des graphes, car pour un arbre, vu comme un graphe, le degré d’un nœud difiérent de la racine est son arité plus un. Nous nous intéressons à des arbres d’expressions qui suivent une syntaxe précise. Les systèmes de séries génératrices associées se ront donc polynomiaux.

Comme nous l’avons ex pliqué dans l’introduction, nous pourrions vouloir considérer que ^ a une arité non fixée pour mo déliser son associativité. Nous sortons du cadre des systèmes polynomiaux dans ce cas, cf le chapitre 3. Les étiquettes des nœuds sont associées à une arité fixe : par exemple, pour la syntaxe des expressions logiques, l’opérateur ¬ est unaire, tandis que l’opérateur ^ est binaire.

Dans la suite de cette section, chaque opérateur aura une seule arité fixée. De façon plus formelle, soit S un ensemble fini d’éléments appelés opérateurs, et soit a une fonction de S dans N. Pour un symbole d’opérateur s, la valeur a(s) est appelée l’arité de l’opérateur s, et désigne le nombre de fils qu’un opérateur peut avoir.

Soit ⇤ un nouveau symbole de feuille qui n’est pas dans S. On étend la fonction d’arité à ce nouveau symbole en posant a(⇤)=0. Définition 2.4 (Expression incomplète). I Uneexpression incomplète sur S est une expression de T (S [{⇤},a).

La taille d’une expression incomplète est son nombre de nœuds dans S (les feuilles ⇤ ne sont pas comptées). J Autrement dit, une expression incomplète est simplement un arbre de T (S,a) dont certaines feuilles sont étiquetées par un nouveau symbole ⇤ (par exemple l’arbre T1 de la figure 2.1).

De façon informelle, ces arbres incomplets représentent des expressions partielles, chaque feuille ⇤ étant destinée à être complétée par une expression. Une expression est simplement uneexpression incomplète qui necontient aucune feuille ⇤. Nous appelerons parfois expression complète une telle expression par opposition aux expressions incomplètes. Définition 2.5 (Arité d’une expression incomplète). I Si T est une expression incomplète sur S, nous appelons arité de T, noté a(T) son nombre de feuilles ⇤.

Cette définition est consistante avec l’arité d’un symbole, en considérant un sym bole s 2 S d’arité a(s) comme une expression incomplète constituée d’une racine Ne pas compter les ⇤ dans la taille d’un arbre simplifiera les notations lors de l’expression de la taille d’un arbre provenant d’une substitution. Les expressions incom plètes sont aussi appelées des contexte

Réduction d’expressions spécifiées par un système étiquetée par s, et ayant a(s) enfants étiquetés par ⇤ (par exemple l’opérateur ^ ^ peut être vu comme /\ ⇤⇤). Dans toute la suite, l’arité des symboles de S est sous-entendue fixée. On désigne par T⇤(S):=T (S [{⇤},a) (resp. T (S):=T (S,a)) l’ensemble des expressions incomplètes (resp. complètes) sur S. Naturellement, T (S) ✓T⇤(S). Remarque 2.6.

Les expressions incomplètes sont très proches des motifs définis par [Mar92], dans le cadre de la recherche de motifs dans des arbres. L’auteur utilise le joker (wildcard) ⇤ comme symbole spécial de feuille, à la place de ⇤. J Définition 2.7 (Substitution d’arbres). I Si T est une expression incomplète sur S, d’arité t = a(T), et T1, …,Tt sont des expressions (possiblement incomplètes) sur S,

alors T[T1,…,Tt] désigne l’ex pression obtenue en remplaçant la i-ième feuille ⇤ par Ti pour chaque i 2 [t] (en ordonnant les t feuilles ⇤ par ordre d’apparition dans le parcours en profondeur de l’arbre, en traitant les fils d’un nœud de gauche à droite). Nous généralisons cette notation à des ensembles d’expressions : si T1, …,Tt sont des ensembles d’expressions (incomplètes), alors T[T1,…,Tt] :={T[T1,…,Tt] :T1 2T1,…,Tt 2Tt} désigne l’ensemble des expressions obtenues en remplaçant la i-ième feuille ⇤ par un élément de Ti.