Réduction d’expressions spécifiées par une seule équation

Réduction d’expressions spécifiées par une seule équation

Dans ce chapitre, nous nous intéressons à l’in￿uence de la présence d’un élément absorbant sur l’ensemble particulier de tous les arbres compatibles avec un ensemble d’opérateurs S et une fonction d’arité a donnés. L’ensemble d’arbres étudié est donc T (S,a) tout entier, en reprenant les notations du chapitre précédent, et non plus un sous-ensemble spéci￿é par un système d’équations sur les arbres.

Nous généralisons dans ce chapitre légèrement la fonction d’arité par rapport au chapitre précédent, en autorisant des opérateurs d’arité quelconque, ce qui permet de modéliser l’associa tivité de certains opérateurs. L’ensemble T (S,a) est décrit par une seule équation unidimensionnelle très simple,

ce qui permet d’obtenir des résultats plus précis sur son comportement vis-à-vis de la simpli￿cation, notamment la convergence de l’espérance de la taille après réduction. Le butdecette section est de démontrer le théorème suivant, dont nous préciserons en détail les conditions dans la prochaine sous-section 3.2 

Élément absorbant et réduction

Dans la suite, nous ￿xons une arité a > 2 de l’opérateur ~. Nous considérons la réduction induite par l’existence d’un arbre constant ￿xé, P2T(S,a), qui est absorbant pour l’opérateur ~ d’arité a. On s’intéresse donc à la règle de simpli￿cation suivante : ~ T1 …Ta P, si Ti = P pouruni 2{1,…,a}.

Remarquez que la réduction considérée ne s’applique que si le père de P est un nœud ~d’arité a, alors que l’opérateur ~ peut avoir d’autres arités. Dans l’exemple 3.2 des expressions régulières L0 R avec une union d’arité quelconque, nous ne consi dèrerons, par exemple, que la réduction sur les opérateurs + d’arité 2. Cela su￿t pour montrer la dégénérescence des expressions.

Le schéma d’inversion lisse

Dans cette section nous dé￿nissons le cadre dans lequel nous nous plaçons. Définition 3.4. P ILasériecaractéristique associée à la suite A =(Ai)i2N estlasérieformelle A(y)= i>0 izi, où i = |Ai|. J Pour simpli￿er les notations, nous notons L := T (S,a) l’ensemble d’arbres étudié, Asasuite d’opérateurs triés par arité, et la série caractéristique associée à A.Avec ces notations, la série génératrice de L satisfait l’équation :

L(z)=z (L(z)). (3.1) Si on prend l’exemple des expressions régulières LR, (X)=3+X +2X2 est un polynôme de degré 2 et l’Eq. (3.1) peut se résoudre. Ce n’est pas possible en général lorsque est une série quelconque. Cependant dans certains cas on peut dériver le comportement asymptotique de l’équation fonctionnelle, comme on l’a déjà fait dans le cas des systèmes. Pour cela on demande un certain nombre de conditions, regroupées sous le nom de schéma d’inversion lisse p