16
1 Botanique
1.2.2 Familles simples d’arbres
Afin d’avoir un point de vue global, passons en revue quelques classes d’arbres déjà
rencontrées ou à venir en les voyant comme des ensembles d’arbres marqués :
– la classe P des arbres planaires devient un ensemble d’arbres marqués lorsque
chaque nœud est marqué par son arité (i.e., le nombre de ses fils) ∈ N ;
– la classe B des arbres binaires complets devient un ensemble d’arbres marqués en
remarquant que chaque nœud est soit d’arité 0, soit • d’arité 2. Les symboles
( 0) et (•, 2) sont ainsi associés aux nœuds de l’arbre.
– la classe C des arbres binaires devient un ensemble d’arbres marqués grâce aux
symboles ( 0) et (•, 2) auxquels il faut ajouter les symboles (• g , 1) et (• d , 1)
qui correspondent aux nœuds simples, d’arité 1, dont l’enfant unique est soit à
gauche soit à droite.
– la classe des arbres représentant des expressions booléennes construites sur un
ensemble de variables booléennes (fini ou non) X = {x 1 , . . . , x k , . . . }, étendu
avec les littéraux négatifs (notés x i ; leur ensemble sera noté X) et avec les
opérateurs logiques ∧, ∨ et →, devient un ensemble d’arbres marqués : en effet,
chaque nœud est marqué par une lettre de l’alphabet A = X ∪ X ∪ {∧, ∨, →} et
l’ensemble de symboles associé est
S = {(∧, 2), (∨, 2), (→, 2), (x 1 , 0), (x 1 , 0), (x 2 , 0), (x 2 , 0), . . . }.
Cet ensemble est fini lorsque X est fini, infini sinon.
– la classe des arbres d’expressions (mathématiques), par exemple celle des
expressions construites avec une seule variable x, les opérateurs binaires
+ et ∗ (où dans cet exemple ∗ désigne le produit), et l’opérateur unaire
d’exponentiation exp ; cette classe devient un ensemble d’arbres marqués par les
lettres de l’alphabet A = {x, exp, +, ∗} et l’ensemble de symboles associé est
S = {(x, 0), (exp, 1), (+, 2), (∗, 2)}. Une représentation d’un tel arbre se trouve
figure 1.14.
Ceci nous amène à la notion de famille simple d’arbres qui est due à Meir et
Moon [185]. En renvoyant aux sections 1.1.1 pour la définition de l’ensemble P E
et 1.2.1 pour celle d’un arbre marqué, nous définissons une famille simple d’arbres
comme suit.
Fig. 1.14 Un arbre de taille
10, représentant l’expression
exp(x ∗ x) + (x ∗ (x + x)), où
∗ désigne le produit
1 Botanique
1.2.2 Familles simples d’arbres
Afin d’avoir un point de vue global, passons en revue quelques classes d’arbres déjà
rencontrées ou à venir en les voyant comme des ensembles d’arbres marqués :
– la classe P des arbres planaires devient un ensemble d’arbres marqués lorsque
chaque nœud est marqué par son arité (i.e., le nombre de ses fils) ∈ N ;
– la classe B des arbres binaires complets devient un ensemble d’arbres marqués en
remarquant que chaque nœud est soit d’arité 0, soit • d’arité 2. Les symboles
( 0) et (•, 2) sont ainsi associés aux nœuds de l’arbre.
– la classe C des arbres binaires devient un ensemble d’arbres marqués grâce aux
symboles ( 0) et (•, 2) auxquels il faut ajouter les symboles (• g , 1) et (• d , 1)
qui correspondent aux nœuds simples, d’arité 1, dont l’enfant unique est soit à
gauche soit à droite.
– la classe des arbres représentant des expressions booléennes construites sur un
ensemble de variables booléennes (fini ou non) X = {x 1 , . . . , x k , . . . }, étendu
avec les littéraux négatifs (notés x i ; leur ensemble sera noté X) et avec les
opérateurs logiques ∧, ∨ et →, devient un ensemble d’arbres marqués : en effet,
chaque nœud est marqué par une lettre de l’alphabet A = X ∪ X ∪ {∧, ∨, →} et
l’ensemble de symboles associé est
S = {(∧, 2), (∨, 2), (→, 2), (x 1 , 0), (x 1 , 0), (x 2 , 0), (x 2 , 0), . . . }.
Cet ensemble est fini lorsque X est fini, infini sinon.
– la classe des arbres d’expressions (mathématiques), par exemple celle des
expressions construites avec une seule variable x, les opérateurs binaires
+ et ∗ (où dans cet exemple ∗ désigne le produit), et l’opérateur unaire
d’exponentiation exp ; cette classe devient un ensemble d’arbres marqués par les
lettres de l’alphabet A = {x, exp, +, ∗} et l’ensemble de symboles associé est
S = {(x, 0), (exp, 1), (+, 2), (∗, 2)}. Une représentation d’un tel arbre se trouve
figure 1.14.
Ceci nous amène à la notion de famille simple d’arbres qui est due à Meir et
Moon [185]. En renvoyant aux sections 1.1.1 pour la définition de l’ensemble P E
et 1.2.1 pour celle d’un arbre marqué, nous définissons une famille simple d’arbres
comme suit.
Fig. 1.14 Un arbre de taille
10, représentant l’expression
exp(x ∗ x) + (x ∗ (x + x)), où
∗ désigne le produit