Dw=03512 RR 261

IRIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

<figure><img src="image_1.png" /></figure>

ÉVALUATION DES INDEX
RATIONNELS DE QUELQUES
FAMILLES DE LANGAGES

Jean-Marc STEYAERT

Rapport de Recherche N° 261

Novembre 1977

43p.
# ÉVALUATION DES INDEX RATIONNELS DE QUELQUES FAMILLES DE LANGAGES

Jean-Marc Steyaert

Résumé :

Nous étudions l'index rationnel de classes de langages incluses dans celle des langages à index. Ces classes sont définies à partir de systèmes de réécriture sur les arbres. Nous donnons d'abord des propriétés de ces systèmes puis les utilisons pour obtenir une majoration en $2^{\alpha^n}$ de l'index rationnel des ETOL.

Abstract :

We study the rational index of classes of languages contained in index languages, and defined by rewriting systems on trees. We first prove properties of these systems and apply them to get an upper bound of $2^{\alpha^n}$ for the rational index of ETOL languages.

<figure><img src="image_2.png" /></figure>
# 1. Introduction

L'étude des langages formels développée dans les dernières années s'est faite autour de deux pôles principaux : d'une part à partir de la classification de Chomsky et de la définition de langages par grammaires, systèmes de réécriture libre ou automates, d'autre part à partir des systèmes de Lindenmayer et de la définition de langages par règles de réécriture parallèle. Dans le premier formalisme on rend facilement compte des propriétés des langages rationnels, algébriques, à index, définis par "stack-automata", "context-sensitive" etc... Dans le second on distingue deux générations : d'abord les langages stricts comme OL, DOL, TOL puis des langages étendus où certains mots engendrés ne sont pas retenus, EDTOL, ETOL parmi les plus importants. Alors que les OL, DOL, TOL sont assez incomparables avec les langages du premier type, les langages étendus possèdent des propriétés voisines et se laissent plus facilement situer dans la hiérarchie de Chomsky.

Un cadre agréable pour une étude unifiée de ces langages à été introduit par l'étude des "macro-grammars" [Fi] puis [Dw] et de façon parallèle par l'étude des ensembles d'arbres et de leur feuillages : "dendrolanguages" [Ro] [Do] [Br] etc...

La classe de forêts la plus large qui nous intéresse est celle des forêts algébriques ; ces forêts et certaines de leurs restrictions ont été étudiées de nombreuses façons différentes, soit comme représentant des calculs de schémas de programme soit comme arbres de dérivation de langages, soit enfin pour leurs propriétés algébriques (homomorphismes, transductions...). Nous les considérerons ici uniquement comme arbres de dérivation de langages.

D'un autre côté nous utilisons la notion d'index rationnel d'un langage [BN] [BCN]. Cette notion permet de classer de façon commode et très synthétique les langages algébriques ; elle est en particulier utile pour distinguer des familles de langages fermées par transduction rationnelle ou pour montrer leur non-principalité. Un outil nécessaire dans les évaluations d'index rationnel est l'arbre de dérivation des mots des langages considérés.

Dans cet article (qui prolonge [St]) nous abordons l'étude des index rationnels de deux classes de langages obtenues comme feuillages de forêts algébriques restreintes : les forêts linéaires qui sont une extension des forêts corégulières [AD] et dont les feuillages contiennent donc les EDTOL et les forêts élémentaires strictes qui étendent les schémas ELBT de [Dw] et dont les feuillages sont les ETOL [Rz].
Nous montrons que l'index rationnel des langages de ces familles est majoré par $2^{\alpha n^2}$ pour quelque $\alpha$ et donnons un exemple de langage DOL dont l'index rationnel est au moins $2^{\alpha\sqrt{n}}$. Il y a là un trou qui est certainement de même nature que celui observé pour les algébriques [BCN].

Cet article se veut indépendant ; nous reprenons donc à notre manière un certain nombre de résultats connus nécessaires aux constructions.

Dans la partie 2 nous rappelons la notion d' index rationnel et donnons les définitions élémentaires sur les grammaires algébriques et rationnelles sur le magma-libre : nous introduisons en particulier les grammaires linéaires et élémentaires ainsi que la forme standard de ces dernières. Dans la partie 3 nous introduisons la notion de forêt maximale qui autorise un traitement général de l'intersection d'un langage et d'un langage rationnel. On montre en particulier que le feuillage de toute forêt maximale rationnelle est un langage rationnel. La partie 4 est consacrée à la notion d'arborescence de dérivation qui permet de parler naturellement de la suite des réécritures faites et d'évaluer des bornes supérieures sur la taille minimale des arbres engendrés et donc sur leurs feuillages. La section 5 est dévolue à l'intersection d'une forêt algébrique et d'une forêt rationnelle et à l'évaluation d'une borne supérieure des index rationnels des langages définis en 2. Enfin dans la section 6 nous donnons un exemple montrant la presque optimalité du résultat précédent.
## 2. Définitions et rappels

### 2.1 Index rationnel

Par la suite nous considérons des langages sur un monoïde libre $W^*$.
On note $\text{Rat}_n$ l'ensemble des langages reconnaissables par un automate fini (non déterministe) à au plus n états ; $\text{Rat} = \bigcup_{n \in \mathbb{N}} \text{Rat}_n$

**Définition** : Soit $L \subseteq W^*$, $K \in \text{Rat}(W^*)$. On note $d_K(L) = \min\{|f|/f \in K \cap L\}$ lorsque $K \cap L \neq \emptyset$.

**Définition** : $L'$ *index rationnel* d'un langage $L \subseteq W^*$ est la fonction $g_L : N \to N$ définie par :

$$g_L(n) = \max\{d_K(L) / K \in \text{Rat}_n(W^*) \& K \cap L \neq \emptyset\}$$

**Note** : le fait de ne considérer que des langages rationnels dans $W^*$ n'est pas une restriction. En effet soit $W' \supset W$ et $K' \in \text{Rat}_n(W'^*)$. Alors $K = K' \cap W^*$ appartient à $\text{Rat}_n(W^*)$ et $d_K(L) = d_K(L')$, pour $L \subseteq W^*$.

On a alors les propriétés élémentaires suivantes :

- $g_L$ est une fonction non décroissante

- pour $L \in \text{Rat}$ $g_L$ est linéaire.

La façon dont $g_L$ croît indique la complexité du langage $L$. Pour pouvoir parler aisément de ce comportement on introduit un préordre sur les fonctions de $N \to R^+$.

**Définition** : soient $f, g \in [N \to R^+]$ ; $f$ croît moins vite que $g$ ($f \ll g$) ssi il existe un réel $p$ tel que $f(n) \le p \cdot g(n)$ pour presque tout $n \in \mathbb{N}$ (i.e. pour tout $n \ge n_0$).

**Définition** : Un langage $L$ est dit d'ordre supérieur $f$ (resp. d'ordre inférieur $f$) ssi $g_L \subseteq f (f \subseteq g_L)$.

La hiérarchie ainsi obtenue sur les langages est assez compatible avec les opérations usuelles sur les langages. Citons en particulier

**Proposition 2.1** [BN] : Soit $L \subseteq W^*$, $L' \subseteq W'^*$, $\tau$ une transduction rationnelle telle que $L' = \tau(L)$. Il existe $p \in \mathbb{N}$ tel que $g_L, \underline{\underline{\tau}}_\lambda n \cdot ng_L(pn)$.
## 2.2 Grammaires algébraiques et rationnelles sur le magma-libre

Soit $T$ un ensemble fini ; on dira que $T$ est *valué* s'il est muni d'une application $\alpha : T \to N$ dite arité. On note alors $T_i = \alpha^{-1}(i)$.

On utilisera par la suite plusieurs ensembles valués simultanément ; on notera toujours $\alpha$ les différentes applications arité sans qu'il y ait con-fusion possible.

Soit $T$ un alphabet valué $(T_0, \emptyset)$. On définit l'ensemble $M(T)$ comme étant le plus petit ensemble tel que :

$$i) \forall t \in T_0 \quad t \in M(T)$$

$$ii) \forall u \in T_p \quad \begin{array}{l} \forall t_1, \dots, t_p \in M(T) \\ u(t_1, \dots, t_p) \in M(T). \end{array}$$

Les éléments de $M(T)$ seront appelés arbres : nous utiliserons aussi la représentation bidimensionnelle des arbres

<figure><img src="image_3.png" /></figure>

Rappelons enfin que l'ensemble $M(T)$ des arbres sur l'alphabet $T$ est isomorphe au magma libre sur $T$ ce qui justifiera notre terminologie.

**Définition** : On appelle grammaire *algébrique* sur $M(T)$ un quintuplet
$G = (T,U,X,S,P)$ où :

- $T$ est un alphabet valué fini dit alphabet terminal,

- $U$ est un alphabet fini dit alphabet non-terminal,

- $X$ est un ensemble de variables d'arité 0,

- $S$ est l'axiome et par convention est de la forme

$$S = A(t_1 \cdots t_p) \text{ pour } A \in U_p \text{ et } t_i \in M(T).$$

Par la suite nous désignerons souvent l'axiome par

$$S = A_0(Z_1, \dots, Z_{p_0}) \text{ et ferons alors référence implicite à cette forme.}$$

- $P$ est un sous-ensemble de $M(UUX) \times M(TUUUX)$ vérifiant la condition :
pour tout

$$(t,t') \in P, \ t = A(x_1 \cdots x_p) \text{ pour } A \in U_p \text{ et } x_i \in X \\ \text{et } t' \in M(TUUU\{x_1 \cdots x_p\})$$
P est l'ensemble des productions. Une production (t,t') est dite terminale si $t' \in M(TU X)$, non-terminale sinon.

Nous utiliserons par la suite un certain nombre de sous-classes des grammaires algébriques :

- grammaires *rationnelles* : $U = U_0$

- grammaires *co-régulières* : les membres droits des productions non-terminales sont du type $B(t_1 \cdots t_m)$ pour $B \in U_m$, $t_i \in M(TU X)$

- grammaires *linéaires* : les membres droits des productions non-terminales sont du type $f(A_1(t_1^1 \cdots t_r^1), \cdots, A_m(t_1^m \cdots t_r^m))$ pour $f \in T_m$, $A_i \in U_r$, $t_i^j \in M(TU X)$ ou du type corégulier.

- grammaires *élémentaires simples* : l'ensemble des non-terminaux $U$ est la réunion de $U^\circ$ (récursifs) et $U^\sigma$ (non-récursifs) disjoints ; $U^\sigma$ est muni d'un ordre partiel $\sigma$ :
  On note $U^{\sigma A} = \{B \in U^\sigma / A \sigma B\}$.

Les productions sont alors telles que, pour tout $(t,t') \in P$
et non-terminale :

* si $t = A(x_1 \cdots x_p)$ avec $A \in U^\circ$, alors
  $t' = B(t_1 \cdots t_m)$ avec $B \in U^\circ$ et $t_i \in M(TUU^\sigma U X)$.
  ou $t' \in M(TUU^\sigma U X)$

* si $t = A(x_1 \cdots x_p)$ avec $A \in U^\sigma$, alors
  $t' = M(TUU^{\sigma A} U X)$.

Les grammaires rationnelles, corégulières et linéaires ont été considérées dans la littérature sous des formes plus ou moins voisines et sous des dénominations diverses.

**Notation** : soit $t \in M(T)$ et u un sous-arbre de t. On note $(t:u)$ le contexte de u dans t : il s'agit de l'arbre incomplet obtenu en enlevant u dans t.
Le remplacement de u par u' dans t est noté $(t:u)[u']$.

Dans la notation bidimensionnelle on aura

<figure><img src="image_4.png" /></figure>

<figure><img src="image_5.png" /></figure>

<figure><img src="image_6.png" /></figure>
**Notation** : Soit $t \in M(T)$, $a \in T_0$, $t' \in M(T)$ on note $t[a\backslash t']$ l'arbre obtenu en substituant $t'$ à toutes les occurrences de $a$ dans $T$.

Cette notation sera étendue à des substitutions en parallèle sur plusieurs symboles.

**Définition** : Soient $t$ et $t' \in M(T_U U)$. On dit que $t$ se réécrit en $t'$ dans $g$ ($t \vdash t'$) ssi il existe des sous-arbres $u$ et $u'$ de $t$ et $t'$ respectivement tels que :

(i) $t' = (t:u)[u']$

(ii) $u = A(t_1 \cdots t_p)$ pour $A \in U_p, t_i \in M(T_U U)$

(iii) il existe une production $(v,v') \in P$ telle que
$$ v = A(x_1 \cdots x_p) \text{ et } u' = v'[\overrightarrow{x_i \setminus t_i}] $$

On note $\mathrel{\substack{\overline{\phantom{x_i}} \\ |}}_g$ la fermeture transitive de $\mathrel{\substack{\overline{\phantom{x_i}} \\ |}}_g$ et on l'appelle *dérivation*.

**Définition** : La *forêt engendrée par G* est le sous-ensemble de $M(T)$ défini par
$$ L(G) = \{t \in M(T) / S \mathrel{\substack{\overline{\phantom{x_i}} \\ |}}_g^* t\} $$

Une réécriture de $t$ est gauche si le non-terminal transformé est le premier dans l'ordre préfixe gauche.

Une dérivation est gauche si toutes ses réécritures le sont.

On a alors le très important résultat [Bo] [Ro]

**Proposition 2.2** : A toute dérivation $S \mathrel{\substack{\overline{\phantom{x_i}} \\ |}}^* t$ dans $G$ on peut associer une dérivation gauche $S \mathrel{\substack{\overline{\phantom{x_i}} \\ |}}^* t$, dans $G$.

Nous aurons besoin par la suite des notions de *front* et de *front étendu* d'un arbre dérivé.

**Définition** : Soient $T$ et $U$ deux alphabets valués (respectivement terminal et non-terminal). On appelle *front* le morphisme $\Phi_1$ de $M(T_U U)$ dans $U^* \mathrel{\substack{\overline{\phantom{x_i}} \\ |}}^*$ † donné par :

$$ \Phi_1(a) = \varepsilon \quad \text{pour } a \in T_0 $$

$$ \Phi_1(f(t_1, \dots, t_p)) = \Phi_1(t_1) \cdots \Phi_1(t_p) \quad \text{pour } f \in T_p $$

$$ \Phi_1(A(t_1, \dots, t_p)) = A \quad \text{pour } A \in U_p, p \in N $$

<footnote>† Le monoïde $U^*$ est formé des mots sur l'alphabet $U$ ; l'arité n'est pas prise en compte, car il n'est pas un arbre, il n'a pas de root, il n'a pas deUCTE.</footnote>
On appelle *front étendu* le morphisme $\Phi_2$ de $M(TUU)$ dans $(T_0^U UU)^*$
donné par :

$$ \Phi_2(a) = a \quad \text{pour } a \in T_0 $$

$$ \Phi_2(f(t_1, \cdots, t_p)) = \Phi_2(t_1) \cdots \Phi_2(t_p) \quad \text{pour } f \in T_p $$

$$ \Phi_2(A(t_1, \cdots, t_p)) = A \quad \text{pour } A \in U_p, p \in N $$

Une réécriture sur un arbre $t \in M(TUU)$ est *descendante* si elle porte sur un non-terminal du front de t. Une dérivation est descendante si toutes les réécritures qui la composent le sont.

## 2.3 Forêts rationnelles

Nous avons défini les forêts rationnelles au moyen de systèmes de réécriture sur le magma-libre. On peut aussi les caractériser comme ensembles d'arbres reconnus par des automates finis. Nous nous bornons ici à un seul type d'automates : les automates finis descendants (non-déterministes).

**Définition** : Un automate fini descendant est donné par un quintuplet

$A = (T, Q, q_0, q_f, \emptyset)$ où T est un alphabet valué fini

Q est l'ensemble des états

$q_0 \in Q$ est l'état initial

$q_f \in Q$ est l'état final.

Q table de l'automate est une partie de
$$ \bigcup_{\phi \in \alpha(T)} Q \times T_p \times Q^{\max(1,p)} $$

le fonctionnement d'un tel automate est classique [Do] et nous rappelons :

**Proposition 2.3** : La famille des forêts rationnelles est identique à celle des forêts reconnaissables par automate fini descendant non déterministe.

## 2.4 Formes normales

De même que dans le cas des grammaires algébriques sur le monoïde libre il est possible de donner des formes "régulières" aux productions d'une grammaire algébrique.

Une grammaire algébrique d'arbres est dite sous forme normale ssi ses productions non-terminales sont du type :

$$ A(x_1 \cdots x_p) \to B(C_1(x_1 \cdots x_p) \cdots C_m(x_1 \cdots x_p)) $$
**Proposition 2.4 [Ro]** : Pour toute grammaire algébrique, on peut construire effectivement une grammaire algébrique sous forme normale équivalente.

Notons enfin pour terminer ce paragraphe que la forme particulière que nous avons imposée à l'axiome ne constitue pas une restriction : il est aisé de transformer toute grammaire à axiome dans M(TUU) en une grammaire du type défini.

## 2.5 Forme standard des grammaires élémentaires simples

**Définition** : Une grammaire élémentaire simple est dite sous forme standard si l'ensemble $U^σ$ des non-terminaux non-récursifs est réduit à un seul élément (noté C en général) d'arité 2 et si l'ensemble des productions P contient pour uniques productions portant sur C

$$C(x,y) \to x \text{ et } C(x,y) \to y.$$

C est un non-terminal qui permet uniquement des choix. Nous voulons maintenant démontrer la proposition :

**Proposition 2.5** : Pour toute grammaire élémentaire simple G il existe une grammaire élémentaire simple G' sous forme standard qui lui est équivalente. La construction est de plus effective.

Introduisons tout d'abord le concept de grammaire de type fini.

Rappelons que si U est un ensemble muni d'un ordre partiel σ et $A \in U$, on note $U^{\sigma A} = \{B \in U | A \in B\}$.

**Définition** : Une grammaire est *de type fini* ssi l'ensemble des non-terminaux U peut être muni d'un ordre partiel strict σ tel que pour toute production $A(x_1 \cdots x_p) \to t$ de P on ait $t \in M(TUU^\sigma U X)$.

**Lemme 2.6** : Soit G de type fini. Alors pour tout $t \in M(TUUUX)$,

$$L(G,t) = \{t' \in M(TUUUX) / t \stackrel{*}{\leftarrow} G t'\} \text{ est fini.}$$

**Preuve** : par induction sur le nombre de non-terminaux de t.

(i) $n=0$ immédiat

(ii) étape d'induction.

Soit t un arbre à n+1 non-terminaux ; alors t est de la forme
$t = t'[y\u]$ où $t'$ a n non-terminaux, une seule occurrence de la variable $y \in X$ et $u$ a exactement un non-terminal.

Dans ces conditions, $t \stackrel{*}{\vdash} v$ ssi il existe $v', v_1'', \dots, v_x''$ tels que :
$t \stackrel{*}{\vdash} v'$, pour tout $i \le r$ $u \stackrel{*}{\vdash} v_i''$ et $v = v'$ [$y_i \setminus v_i''$] où les $y_i$ sont des notations pour les diverses occurrences de $y$ dans $v'$.

Par l'hypothèse d'induction, il existe un nombre fini de $v'$ tels que $t' \stackrel{*}{\vdash} v'$ ainsi qu'un nombre fini de $v_i''$. En conséquence il existe un nombre fini de $v$ tels que $t \stackrel{*}{\vdash} v$. $\square$

L'ensemble $L(G,t)$ précédemment décrit peut être mis sous une forme arborescente au moyen du non-terminal de choix C.

Soit $t_1, \dots, t_n$ l'ensemble des dérivés de $t$ par $G$. On appelle $\Gamma(t)$ l'arbre

bidimensionnelle
$$ C(t_1, C(t_2, (\dots C(t_{n+1}, t_n))))\dots). \text{ En notation} $$

<figure><img src="image_7.png" /></figure>

Passons maintenant à la transformation d'une grammaire élémentaire simple $G = (T, U^\sigma \cup U^\sigma, X, S, P)$ en une grammaire équivalente sous forme standard.

Remarquons que la grammaire $G_\sigma = (T, U^\sigma, X, S_\sigma, P_\sigma)$ où $S_\sigma$ est un élément quelconque et $P_\sigma$ est la restriction de $P$ aux productions sur $M(U^\sigma U X)$ est de type fini. Les arbres $\Gamma(t)$ utilisés par la suite se rapporterons à cette grammaire.

Soit $G' = (T, U^\rho \cup \{C\}, S, P')$ définie par

$$ P' = \{C(x_1, x_2) \to x_1, C(x_1, x_2) \to x_2\} \\ U\{A(x_1 \cdots x_p) \to B(\Gamma(u_1), \cdots, \Gamma(u_m)) / B, A \in U^\rho \text{ et } A(x_1 \cdots x_p) \to B(u_1 \cdots u_m) \in P\} \\ U\{A(x_1 \cdots x_p) \to \Gamma(u) / A \in U^\rho \text{ et } A(x_1 \cdots x_p) \to u \in P\} $$

Les productions de $P$ et $P'$ sont ici naturellement groupées par paires : nous qualifierons deux productions d'une même paire d'homologues.
**Lemme 2.7** : $L(G) = L(G')$.

**Preuve** : $L(G) \subseteq L(G')$.

Considérons une dérivation gauche dans $G$

$S \vdash t_1 \vdash \cdots \vdash t_n \in M(T)$. Il existe $i_0$ tel que $t_{i_0} \text{ contient un non-terminal de } U^0 \text{ et } t_{i_0+1} \text{ n'en contient plus. Posons alors pour } 0 \le i \le i_0, \quad t_i = A_i(u_1^i \cdots u_{p_i}^i) \text{ et soient } A_i(x_1 \cdots x_{p_i}) \to A_{i+1}(v_1^{i+1} \cdots v_{p_{i+1}}^{i+1}) \text{ la i-ème production appliquée. On a immédiatement}$

$$u_j^{i+1} = v_j^{i+1} \xrightarrow{[x_k \setminus u_k^i]} .$$

Considérons alors la suite des productions homologues dans $G'$. On obtient une suite d'arbres dérivés $\hat{t}_i, 0 \le i < i_0$ tels que
$$ \hat{t}_i = A_i(u_1^i, \dots, u_{p_i}^i) \text{ et pour tout } 0 \le i < i_0, \ 1 \le j \le p_i $$
$$ \hat{u}_j^{i+1} = \Gamma(v_j^{i+1}) [\xrightarrow{\overrightarrow{x_k}} u_k^i] \quad \text{et} \quad \hat{u}_j^0 = u_j^0 $$

Toute dérivation d'un $u_j^i$ peut maintenant être décomposée en dérivations de $v_j^i$ et donc être simulée dans $G'$ par des projections à partir de $\hat{u}_j^i$.

Inversement montrons que $L(G') \subseteq L(G)$.

Considérons une dérivation dans $G'$. Avec les mêmes notations que dans la partie précédente on obtient un

$$ \hat{t}_{i_0} = A_{i_0} (\hat{u}_1^{i_0}, \dots, \hat{u}_{p_{i_0}}^{i_0}) \quad \text{et un} $$

$\hat{t}_{i_0+1} \in M(TU\{C\})$. On considère de façon semblable la dérivation homologue dans $G$. Cette dérivation produit un arbre

$$ t_{i_0} = A_{i_0} (u_1^{i_0}, \dots, u_{p_{i_0}}^{i_0}). $$

Il ne reste plus qu'à constater que toute suite de choix sur un $\hat{u}_j^i$ peut être simulée par des dérivations sur $u_j^i$ dans $G$. $\square$

La proposition annoncée est alors démontrée puisque $G'$ est en forme standard.
Ce résultat a une conséquence supplémentaire, les grammaires élémentaires simples sous forme standard sont l'analogue des ELB schemes [Dw], qui engendrent les ETOL stricts. Anticipant sur la définition formelle du feuillage d'une forêt, nous énonçons le corollaire.

**Corollaire 2.8** : les feuillages des forêts élémentaires simples sont les ETOL stricts.
### 3. Forêts maximales et Feuillages

#### 3.1 Les langages que nous considérons sont donnés la plupart du temps par un système de dérivation sur des arbres, le mot résultant étant le mot formé par les feuilles de l'arbre de dérivation. L'intersection de deux langages peut alors se voir comme celle de la forêt de dérivation de l'un et d'une forêt spéciale liée à l'autre langage. Dans le cas où le langage est rationnel cette forêt est très simple.

**Définition** : soir T un alphabet valué. On appelle *feuillage* le morphisme $\Phi$ de $M(T)$ dans $T_0^*$ défini par :

$$ (i) \quad \forall a \in T_0 \quad \Phi(a) = a $$

$$ (ii) \quad \forall a \in T_p, \forall t_1 \cdots t_p \in M(T) $$

$$ \Phi(a(t_1 \cdots t_p)) = \Phi(t_1) \cdots \Phi(t_p) $$

soit maintenant un langage $L \subset W^*$ et T un alphabet valué tel que $W \subset T_0$ ; nous voulons considérer l'ensemble des arbres de $M(T)$ dont le feuillage est un mot L.

**Définition** : soit $L \subset W^*$, T un alphabet gradué contenant W ; on appelle *forêt maximale engendrée par L relativement à T* (et on note $\Phi_T^{-1}(L)$) l'ensemble $\{t \in M(T) / \Phi(t) \in L\}$.

L'ensemble T est en général sous-entendu.

**Remarques** : $O - \forall F \subset M(T) \quad \Phi(F) = L \implies F \subset \Phi^{-1}(L)$ d'où le nom de forêt maximale

1. On a évidemment $\Phi(\Phi^{-1}(L)) \subset L$

2. Soit $\hat{T} = \{n \in N / \exists a \in T \ \alpha(a) = n+1\}$

L'égalité $\Phi(\Phi^{-1}(L)) = L$ a lieu ssi
$$ \{n \in N / \exists w \in L \ |w| = n\} = \{n \in N / \exists n_1 \cdots n_p \in \hat{T} \ \text{p} \in N \ \text{n} + 1 = \sum_{i=1}^{p} n_i \} $$

3. L'égalité a lieu dès que $T_2 \neq \emptyset$.

*Par la suite nous supposerons toujours que $\Phi(\Phi^{-1}(L)) = L$ pour tous les langages L considérés.*
## 3.2 Forêts rationnelles maximales

**Proposition 3.1** : Soit $L \in \mathrm{Rat}$ ; alors $\Phi^{-1}(L) \in \mathrm{Frat}$.

**Preuve** : Soit $A = (\overline{[q]}, 1, \overline{q}, Q)$ un automate $^+$ fini reconnaissant $L \in W^*$. On construit un automate fini descendant $B$ reconnaissant $\Phi^{-1}(L) \in M(T)$. $B$ est donné par $(T, P, p_0, p_f, P)$ avec :

$$ - P = [\overline{q}]^2 u \{p_f\} $$

$$ - p_0 = (1, \overline{q}) $$

- P est l'union des deux ensembles $P_1$ et $P_2$ avec

$$ P_1 = \left\{ \left( (q, q'), a, (q, q_1), (q_1, q_2), \dots, (q_p, q') \right) / \forall a \in T_p, p \ge 1, \forall q, q' \in \overline{[q]} \right\} $$

$$ P_2 = \left\{ \left( (q, q'), a, p_f \right) / \forall a \in W \ \forall q, q' \in \overline{[q]} \ (q, a, q') \in Q \right\} $$

soit $H$ la forêt reconnue par $B$. On montre que $\Phi^{-1}(L)=H$.

$$ - \Phi^{-1}(L) \subset H $$

Soit $w \in L$ ; $w$ est reconnu par $A$ avec une succession d'états $1, q_1, \dots, q_n, \overline{q}$ ($|w| = n+1$). Notant $w_i$ la i-ème lettre de $w_i$ on a pour tout $\forall i \le n$ $(q_{i-1}, w_i, q_i) \in Q$ et $(q_n, w_{n+1}, \overline{q}) \in Q$. Soit $t \in \Phi^{-1}(w)$. On montre que $t$ est reconnu par $B$ par induction sur la hauteur.

On montre en fait le résultat un peu plus fort que pour tout $w$ reconnu par $(\overline{[q]}, q_1, q_2, Q)$ et $t \in \Phi^{-1}(w)$, $t$ est reconnu par $(T, P, (q_1, q_2), p_f, P)$

$$ - H \subset \Phi^{-1}(L). $$

On vérifie que $t \in H$ ssi il existe un calcul de $B$ tel que les feuilles $w_1, \dots, w_{n+1}$ de $t$ sont atteintes dans des états $(1, q_1), \dots, (q_n, \overline{q})$.

La définition de $P$ donne alors que $w=w_1 \cdots w_{n+1} \in L$. $\square$

Cette proposition est classique en ce sens qu'elle est plus ou moins intégrée dans nombre de preuves sur les intersections de forêts algébriques et rationnelles.

$L$''intérêt est en fait qu'elle admet une réciproque.

<footnote>† On note $[\overline{q}] = \{q \in N / 1 \le q \le \overline{q}\}$</footnote>
Introduisons d'abord la notion de forêt peigne.

**Définition** : La forêt P(T) des arbres peignes sur T est définie par :

(i) $\forall a \in T_0 \quad a \in P(T)$

(ii) $\forall a \in T_{p+1} \quad \forall b_1 \cdots b_p \in T_0 \quad \forall t \in P(T)$
$a(b_1, b_2, \cdots, b_p, t) \in P(t)$

(iii) tous les arbres peignes sont obtenus par (i) et (ii).
En représentation bidimensionnelles les arbres peignes sont du type suivant

<figure><img src="image_8.png" /></figure>

**Proposition 3.2** : La forêt P(T) est rationnelle.

**Preuve** : La construction d'un automate d'arbres finis descendant reconnaissant P(T) est immédiate.

**Proposition 3.3** : Soit $L \in \text{Frat}$ ; si $L \in P(T)$ alors $\Phi(L) \in \text{Rat}$.

**Preuve** : Soit $A = (T, Q, q_0, q_f, \emptyset)$ un automate fini descendant reconnaissant L.
On construit une grammaire linéaire droite pour $\Phi(L)$ de la façon suivante :

$$G = (T_0, U, u_0, P) \quad \text{avec}$$

$$- U = \{ (q,a) / q \in Q, a \in T \}$$

$$- P = P_1 \cup P_2 \quad \text{où}$$

$$P_1 = \left\{ \begin{array}{l} (q,a) \to b_1 b_2 \cdots b_p (q',a') / \forall a' \in T \\ \forall (q,a,q_1, \cdots, q_p,q') \in Q \quad \text{tel que} \\ \quad \forall i \le p \quad (q_i, b_i, q_f) \in Q \end{array} \right\}$$

$$P_2 = \left\{ (q,a) \to a / \forall (q,a,q_f) \in Q \right\} \cup \left\{ u_0 \to (q_0,a) / a \in T \right\}$$

On montre aisément que le langage engendré par cette grammaire est $\Phi(L)$.
**Théorème 3.4** : $\Phi^{-1}(L) \in \text{Frat} \Leftrightarrow L \in \text{Rat}$.

**Preuve** : $\Phi^{-1}(L) \in \text{Frat}$ et $P(T) \in \text{Frat}$ ; donc $\Phi^{-1}(L) \cap P(T) \in \text{Frat}$. Or $\Phi^{-1}(L)$ contient tous les arbres peigne à feuillage dans L.

$$D'\text{où } \Phi(\Phi^{-1}(L) \cap P(T)) = L.$$

$\Phi^{-1}(L) \cap P(T)$ étant une forêt peigne et étant rationnelle, L est rationnel. $\square$

**Remarque** : On peut montrer que si $\Phi^{-1}(L) \in \text{Falg}$ alors $L \in \text{Alg}$ par une construction voisine mais plus compliquée. La réciproque i.e. $\forall L \in \text{Alg} \ \Phi^{-1}(L) \in \text{Falg}$ est fausse [St2].

Nous conjecturons que les forêts algébriques maximales sont rationnelles.
## 4. Forêts algébriques : Arborescence de dérivation, Arbres minimaux

### 4.1 Lors de la définition de la forêt engendrée par une grammaire algébrique, nous avons parlé d'une dérivation comme suite de réécritures. En fait si on considère les dérivations gauches cette suite de réécritures est munie d'un ordre naturel que l'on peut représenter sous forme d'arborescence. C'est ce que nous allons préciser maintenant.

On considère sur $(N_+)^*$ ensemble des suites finies d'entiers non nuls les trois ordres suivants :

- ordre préfixe noté $u^<v$ :

$$u^<v \quad \text{ssi} \quad \exists w \ u,w=v$$

- ordre lexicographique noté $u^<v$ :

$$u^<v \quad \text{ssi} \ (u^<v) \text{ ou } (\exists w, u', v' \in (N_+)^* \ \exists a, b \in N_+ \\ a < b \ \& \ u=wau' \ \& \\ v=wbv')$$

- ordre lexicopréfixe noté $u^<v$ et défini par :

$$u^<v \quad \text{ssi} \ (u^<v) \text{ ou } \exists w \in (N_+)^* \ \exists a, b \in N_+$$

$$[a < b \ \& \ u=wa \ \& \ v=wb]$$

On considérera également les restrictions de ces ordres aux sous-monoïdes de $N_+^*$ du type $[r]^*$.

**Définition** : Une *r-arborescence* $^+$ ($D,h$) *sur H* est la donnée d'un domaine fini $D \subset [r]^*$ (1er *ensemble des indices*). Fermé pour l'ordre lexicopréfixe $\forall u \in D \ \forall v \ u^<v \Rightarrow v \in D$ et d'une application *étiquette* $h: D \to H$.

Une *branche* d'une *r-arborescence* en est la restriction à un sous-ensemble du domaine totalement ordonné pour l'ordre préfixe et maximal : on notera souvent et par abus (d,h) une branche de (D,h).

Soit $G = (T, \Pi, \Upsilon, S, P)$ une grammaire algébrique et soit $S \stackrel{*}{\subset} G$ t'une dérivation gauche $\delta$ de $t \in M(T \cup U)$. L'arborescence $d = (D, h)$ sur $P \cup N_+^*$ associée à $\delta$ est définie pas à pas de la façon suivante :

(i) Si $t=S$ alors $d=(D,h)$ avec $D=\{\epsilon\}$, $h(\epsilon)=\epsilon$

† On traitera simultanément le cas où $r$ est fini et le cas où $r=\omega$ ; dans ce cas $[\omega] \sim N_+$.
(ii) Si $S \stackrel{*}{\vdash} t$ et $t \vdash t'$, on définit $d'=(D',h')$ associée à $t'$ à partir de $d=(D,h)$ associée à $t$.

Soit $w = \min_{<\ell}\{w \in D / h(w) \in N_+^*\}$, i.e. le plus petit des indices dont l'étiquette n'est pas une production, et soit $\Pi$ la production qui permet de réécrire $t$ en $t'$: $\Pi$ est du type $A(x_1 \cdots x_p) \to S$ $A \in U$, $S \in M(TUUU)$.

Il existe $u, u', u_1, \dots, u_p \in M(TUU)$ tels que

$$t' = (t:u)[u']$$

$$u = A(x_1, \dots, x_p)[x_i^+ \setminus u_i^+]$$

$$u' = S[x_i^+ \setminus u_i^+]$$

Soit $f = \phi_1(u')$.

- si $f=\epsilon$ alors $D'=D$

$$h'(w) = \Pi \text{ et } \forall v \neq w, h'(v) = h(v)$$

- si $f \neq \epsilon$ alors $D'=DU\{wi/1 \le i \le |f|\}$

$$\text{et } h'(w) = \Pi, \forall i, 1 \le i \le |f|, h'(wi) = wi,$$

$$\forall v \in D - \{w\} \ h'(v) = h(v).$$

La proposition suivante montre la validité de cette construction : en particulier qu'elle s'arrête ssi l'arbre dérivé est dans $M(T)$.

**Lemme 4.1** : Soit $\delta$ une dérivation de $t$ et $d$ l'arborescence associée :

$$\text{Card}\{w \in D / h(w) \in P\} = |\phi_1(t)|$$

**Preuve** : par induction sur la longueur de la dérivation

a) Si $t=S$ alors la propriété est vraie trivialment.

b) L'étape d'induction se vérifie facilement à partir de la définition de l'arborescence associée.

**Proposition 4.2** : Soit $\delta$ une dérivation de $t$ et $d$ l'ω-arborescence associée. $d$ est une arborescence sur $\{\text{ssi } t \in M(T)\}$.

**Preuve** : Un arbre est dans $M(T)$ ssi son front est réduit au mot vide.

Le lemme assure le résultat.
Nous avons donné ici la construction d'une arborescence de
dérivation dans le cas le plus général : il est alors nécessaire que
l'ensemble des indices soit dans $N_+^*$, comme le montre l'exemple suivant.

**Exemple :** $G = (\{h,a,b\}, \{A,B,C\}, \{x,y\}, A, P)$

b

$$P = p_1 : \begin{array}{rcl} A & \rightarrow & \overline{\phantom{x}}x \end{array}$$

<figure><img src="image_9.png" /></figure>

$$p_2 : \begin{array}{c} A \\ \downarrow x \end{array} \rightarrow \begin{array}{c} B \\ \begin{array}{c} \overline{\phantom{x}}h \\ \overline{\phantom{x}}x \end{array} \end{array}$$

<figure><img src="image_10.png" /></figure>

<figure><img src="image_11.png" /></figure>

$$p_4 : \begin{array}{c} B \\ \downarrow x \end{array} \rightarrow \begin{array}{c} h \\ \overline{\phantom{x}}y \end{array}$$

<figure><img src="image_12.png" /></figure>

$$p_6 : \begin{array}{c} C \\ \downarrow x \end{array} \rightarrow \begin{array}{c} y \\ \overline{\phantom{x}}y \end{array}$$

Il est aisé de voir que $L(G)$ est formé des arbres du type

<figure><img src="image_13.png" /></figure>

où les $\beta_i$ sont du type

<figure><img src="image_14.png" /></figure>
L'arborescence de dérivation associée à un tel arbre est
alors du type

<figure><img src="image_15.png" /></figure>

Dans certains cas cependant le branchement de l'arborescence de
dérivation peut être borné a priori.

Soit $G$ une grammaire linéaire, $g$ le maximum des longueurs des fronts de membres droits de production

$$ (g = \max\{|\phi_2(t)|/\exists t'(t',t) \in P\}). $$
**Proposition 4.3** : Si G est linéaire les arborescences associées aux dérivations sont des g-arborescences.

**Preuve** : Montrons d'abord le lemme

**Lemme 4.4** : Soit G linéaire ; pour tout $t \in M(T)$ tel que $S \stackrel{*}{=} t$, il existe $p \in N$, $s \in M(T)$ tel que $s(x_1, \dots, x_p) = 0$, $u_1, \dots, u_p$ de la forme $A_i(t_1^i, \dots, t_m^i)$, $A_i \in U$, $t_j^i \in M(T)$ tels que $t = s(x_i^-, u_i^-)$.

En d'autres termes, tous les non-terminaux de t sont sur le front de t.

**Preuve** : Par induction sur la longueur de la dérivation

a) Si $t=S$ la propriété est évidemment vraie.

b) Supposons la propriété vraie pour les dérivations de longueur n et soit $S \stackrel{*}{=} t$ de longueur $n+1$. Alors $S \stackrel{n}{=} t' \stackrel{t'}{=} t$. $t'$ vérifie la propriété.

$$t'=s[x_i^-, u_i^-] \text{ avec les notations de l'énoncé, et supposons}$$
$$\phi_1(t') = A_1 A_2 \cdots A_p.$$

La dérivation étant gauche la réécriture produisant t porte sur $A_1$. Deux cas se présentent selon qu'elle est terminale ou non :

- réécriture terminale : $A_1 \to u \in M(TU)$
  $\begin{array}{c} A_1 \\ \top \\| \\ x_1 \dots x_m \end{array}$

$$\text{alors } t = s[x_1^- \setminus [x_i^- \setminus t_i^1]] [x_j^- \setminus u_j^-]_{j>1}$$

et vérifie l'hypothèse d'induction.

- réécriture non-terminale :
  $A_1 \to \begin{array}{c} B_1 \\ \top \\ x_1 \dots x_m \end{array} \begin{array}{c} f \\ \top \\ v_1 \dots v_{n_1} \end{array} \begin{array}{c} \dots \\ \top \\ B_1 \dots B_m \end{array} \begin{array}{c} \dots \\ \top \\ v_1 \dots v_{n_m} \end{array}$

on vérifie encore que

t vérifie l'hypothèse d'induction.

□
Il est maintenant aisé de conclure. La construction pas à pas de l'arborescence associée à une dérivation $S \overset{*}{\mid} t$ dans une grammaire linéaire G montre que :

- ou bien la réécriture est terminale et le front du sous-arbre réécrit est de longueur nulle ce qui ne crée pas de nouvel indice.

- ou bien la réécriture est non terminale du type ci-dessus et le front du sous-arbre est de longueur au plus g.

## 4.2 Arbres minimaux

Nous utilisons maintenant la notion d'arborescence de dérivation pour estimer des bornes supérieures sur la taille minimale des arbres engendrés par une grammaire.

**Lemme 4.5** : Soit G une grammaire linéaire, $\delta$ une dérivation produisant un arbre dans M(T) et d l'arborescence associée à $\delta$. Si sur une même branche de d deux étiquettes ont même membre gauche, il existe une dérivation $\delta'$ plus courte produisant un élément de M(T).

**Preuve** : Soit $S \vdash t_1 \cdots \vdash t_n = t$ la dérivation $\delta$.

D'après le lemme 4.4, les $t_i$ sont de la forme

$t_i = s_i[x_j^\rightarrow \setminus u_j^\rightarrow]$ où $s_i \in M(T)$ et les $u_j$ sont de la forme

$A_j(v_1^j \cdots v_m^j)$ avec $A_i \in U$, $v_k^j \in M(T)$.

Reprenant les notations de la proposition 4.3 on a donc que $d=(D,h)$ est une g-arborescence. Soient $f$ et $ff'$ les index respectifs de deux noeuds de d étiquetés par des productions de même membre gauche. Considérons alors la g-arborescence d' sur $P$ définie par $d'=(D',h')$ avec $D' = (D\setminus\{fv/fv \in D\}) \cup \{fv/ff'v \in D\}$

$h'(w) = h(w)$ pour tout $w \in D - \{fv/fv \in D\}$

$h'(w) = h(w')$ pour tout $w = fv$ et $w' = ff'v$.
Intuitivement d'est l'arborescence associée à une dérivation où les productions d'index supérieur à ff'sont substituées à celles d'index supérieur à f.

La forme des $t_i$ entraîne alors que la dérivation gauche $\delta'$ associée à d' produit un arbre terminal $t'$. De plus l'arborescence d'est plus petite que l'arborescence d.

**Proposition 4.6** : Soit $G$ une grammaire linéaire, telle que $L(G) \neq \emptyset$ ; il existe une dérivation terminale dont l'arborescence associée est de profondeur au plus égale au nombre de non-terminaux.

**Preuve** : immédiate d'après le lemme 4.5

Nous évaluons maintenant la taille des arbres minimaux des forêts linéaires.

Etant donné une grammaire linéaire $G$ nous avons déjà défini deux paramètres s'y rapportant : $g$, maximum des longueurs des fronts des membres droits de production, $n$ le nombre de non-terminaux. Définissons de plus $p$ comme étant le maximum des longueurs des feuillages des sous-arbres à racines non terminales des membres droits de productions

$$p=\max \left\{ \begin{array}{l} |\Phi(t)|/t=S \quad \text{ou} \quad A \in U \ t_1 \cdots t_m \in M(TUX) \ (u_1, u_2) \in P, \\ \text{t=A(t_1, \cdots, t_m)} \quad \text{& t est sous-arbre de } u_2 \end{array} \right\}$$

**Proposition 4.7.** : Soit $G$ une grammaire linéaire telle que $L(G) \neq \emptyset$ ; il existe alors un arbre de $L(G)$ dont le feuillage a pour longueur $(g \times p)^n$ au plus.

**Preuve** : Montrons le lemme suivant dont la propriété découle immédiate-ment par la proposition 4.6.

**Lemme 4.8** : Soit $G$ une grammaire linéaire et t un arbre dérivé. Si l'arborescence de dérivation associée à t est de profondeur au plus $m$, $|\Phi(t)|$ est au plus $(g \times p)^m$.

**Preuve** : par induction sur la profondeur de l'arborescence de dérivation, on montre en fait le résultat plus fort que, $|\Phi_2(t)| \leq g^m$ et que chaque
sous-arbre de t ayant pour racine un non-terminal a un feuillage de longueur au plus $p^m$.

(i) Pour $m=1, t=S$ et la propriété est vraie.

(ii) Pas d'induction = soit t dont l'arborescence de dérivation $d=(D,h)$ est de profondeur $m+1$. Soit $d'$ l'arborescence obtenue à partir de d par $d'=(D',h')$

$$D' = \{w | w \in D \text{ & } |w| < m\}$$

$$h'(w) = \begin{cases} w & \text{si } w \in D \\ h(w) & \text{sinon} \end{cases}$$

soit $t'$ l'arbre dont $d'$ est l'arborescence associée. $t'$ est tel que $|\Phi_2(t')| \le g^m$ et chacun de ses sous-arbres à racine non-terminale a un feuillage de longueur $p^m$ au plus. De plus, il existe une suite de productions qui dérivent $t'$ en $t$: celles qui font passer de $d'$ à $d$.

Ces productions transforment alors un sous-arbre de $t'$ de la forme $A(t_1 \cdots t_m)$ en un sous-arbre $f(A_1(u'_1 \cdots u'_m) \cdots A_r(u'_r \cdots u'_m))$ ou en $u(t'_1 \cdots t'_r)$.

Dans chacun des cas on vérifie immédiatement que :

$$- |\Phi_2(t)| \le g^{m+1}$$

- le feuillage des $u_j^i$ est de longueur $p^{m+1}$ au plus.

D'où le lemme et la proposition. $\square$

<figure><img src="image_16.png" /></figure>

Passons maintenant au cas des grammaires élémentaires simples. Nous supposerons qu'elles sont données sous la forme standard obtenue par la construction 2.5 i.e. que les productions sont de l'un des trois types

(a) $C(x_1,x_2) \to x_1, \quad C(x_1,x_2) \to x_2$

(b) $A(x_1 \cdots x_p) \to B(\Gamma(t_1) \cdots \Gamma(t_m))$

(c) $A(x_1 \cdots x_p) \to \Gamma(t)$.

(Rappelons que $\Gamma(t)$ représente un arbre de la forme

$$C(u_1, C(u_2, \cdots C(u_r, u_{r+1}) \cdots)).$$

Dans ces conditions soit n le nombre de non-terminaux récursifs et soit p la longueur du plus grand feuillage des $u_i$ apparaissant dans les $\Gamma(t)$.

$$p = \max\{|\Phi(u)|/u=S \text{ ou } u \in M(TUX) \text{ & } u \text{ est sous-arbre d'un membre droit de production}\}.$$
On a alors le résultat suivant

**Proposition 4.9** : Soit $d=(D,h)$ une arborescence de dérivation dans une grammaire élémentaire simple sous forme standard.

Il existe $r_0 \in N$ et $D_0 \subset [p]^*$ tels que

$$ (i) \quad D = \{1^r / 0 \le r \le r_0\} \cup \{1^{r_0 w} / w \in D_0\} $$

(ii) les étiquettes des noeuds d'index $1^r, r<r_0$, sont du type (b), celle de $1^{r_0}$ est du type (c), les autres sont de type (a).

**Preuve** : Remarquons d'abord qu'un arbre contient au plus un non-terminal récursif et ce à sa racine. Dans une dérivation descendante, tant que l'on applique des règles de type (b) on engendre des noeuds d'index $1^r$ dans l'arborescence associée. On applique alors une fois et une seule une règle de type c sur un noeud d'index $1^{r_0}$ fait des règles de type a. Il reste à montrer que $D_0 \subset [p]^*$.

Pour cela nous définissons d'abord une famille de forêts sur $M(T_u\{C\})$ à partir de $G$.

$$ C_0 = \{u_i / S=A(u_1, \dots, u_m)\} $$

Pour tout $i$

$$ C_{i+1} = \{t[x_j \to \overrightarrow{u_j}] / \forall j \ u_j \in C_i \ \& \ \exists (u, u') \in P, (t=u' \ \& \ t \in M(T_u\{C\} \cup X)) \ \text{ou} \\ \qquad u'=B(\dots, t, \dots)) \}. $$

$$ \text{Notons } C = \bigsqcup_{i \in N} C_i. $$

$$ \text{Soit } C' = \{t' / t \in C \text{ t } \dashv \text{ t}'\} $$

**Lemme 4.10** : $\max\{|\phi_2(t')| / t' \in C'\} \le p$.

**Preuve** : immédiate pour $C_0$.

On vérifie que l'induction passe de $C_i$ à $C_{i+1}$.

Il reste alors à remarquer que les sous-arbres rencontrés dans les dérivations de $G$ sont des éléments de $C$ et $C'$. Q.E.D.
**Lemme 4.11.** : Avec les notations précédentes un arbre dérivé a un feuillage de longueur au plus $p^{r_0}$.

**Preuve** : En effet les sous-arbres d'un arbre dont l'arborescence de dérivation à $r_0$ pour caractéristique sont dans $C_{r_0}$ (par induction).

Il reste à vérifier la propriété pour les éléments de $C_{r_0}$ ce qui est immédiat.

Nous sommes maintenant en mesure de donner une borne supérieure sur la taille des arbres minimaux.

**Lemme 4.12** : Si d est une arborescence terminale de dérivation de caractéristique $r_0>n$ (nombre de non-terminaux), il existe une arborescence plus courte produisant également un arbre terminal.

**Preuve** : analogue à celle du lemme 4.5.

**Proposition 4.13** : Soit $G$ une grammaire élémentaire simple sous forme standard, telle que $L(G) \neq \emptyset$ ; il existe $t \in L(G)$ avec $\phi|(t)|<p^n$.

**Preuve** : immédiate d'après les lemmes 4.11 et 4.12.
# 5. Index rationnels des feuillages de forêts linéaires et élémentaires simples

## 5.1 Intersection d'une forêt algébrique et d'une forêt rationnelle

Nous reprenons ici cette construction classique de façon à mettre en évidence les paramètres utiles à l'évaluation des index rationnels des feuillages.

Soit $G = (T, U, X, S, P)$ une grammaire algébrique sous forme normale. Soit $A = (T, Q, 1, \bar{q}, Q)$, avec $Q=[\bar{q}]$, un automate fini descendant sur $M(T)$. On note $A_q$ les automates dérivés de $A$ opérant sur $M(TU\times Q)$ (où les éléments de $X\times Q$ sont d'arité nulle) définis par

$$A_q = (TU\times Q, q, \bar{q}, Q') \text{ avec}$$

$$Q' = \bigcup\{j, (x_i, j) \to \bar{q} \mid \forall j \in Q \ \& \ \forall x_i \in X\}$$

La construction d'une grammaire pour $L(G) \cap L(A)$ se fait alors en deux temps ; on construit :

- d'abord une grammaire $G' = (Tu\{\#\}, U', X', S', P')$ telle que $L(G') \cap \Phi^{-1}(T_0) = L(G) \cap L(A)$

- puis $G'' = (T, U'', X'', S'', P'')$ telle que $L(G'') = L(G') \cap \Phi^{-1}(T_0)$

### (a) Construction de $G'$

On a $U' = Q \times U$ et l'élément $(q, A)$ de $U'$ est noté $q^A$ pour alléger l'écriture. L'arité de $q^A$ est $\alpha(q^A) = \bar{q} \times \alpha(A)$.

Par définition $X' = X \times Q = \{x_j^i / x_j \in X, e \in Q\}$ soit $S=A_0(z_1, \dots, z_{p_0})$ alors $S' = IA(\hat{z}_1, \dots, \hat{z}_{p_0})$ avec la notation suivante :

$\hat{z}_j$ est une suite de $\bar{q}$ arbres

$z_j^1, \dots, z_j^{\bar{q}}$ telle que

$$z_j^k = \begin{cases} z_j & \text{si } z_j \in L(A_k) \\ \# & \text{sinon.} \end{cases}$$
(b) Construction de P'

Notation : on note par la suite
$$ 
\left\{
\begin{array}{l}
\bar{A}(t_1 \cdots t_m) = lA(t_1 \cdots t_m) \cdots \bar{q}A(t_1 \cdots t_n) \\
\bar{x}_i = x_i^1, x_i^2, \cdots, x_i^n
\end{array}
\right.
$$

P' est défini comme la réunion de trois ensembles
$P'_1, P'_2$ et $P'_3$.

$$
P'_{1} = \left\{ qA(\bar{x}_{1}, \cdots, \bar{x}_{p}) \rightarrow x_{i}^{q} / q \in Q, A(x_{1} \cdots x_{p}) \rightarrow x_{i} \in P \right\}
$$

$$
P'_{2} = \left\{ \begin{array}{l} qA(\bar{x}_1, \dots, \bar{x}_p) \to u' / q \in Q, \ u \in M(TUX), \ A(x_1 \cdots x_p) \to u \in P, \ h_Q(u') = u \\ \text{et } u' \in L(A_q) \end{array} \right\}
$$

$\rho$ est le morphisme de magma défini par

$$
\begin{cases}
h_Q(\alpha) = \alpha & \text{si } \alpha \in T \\
h_Q(x_i^q) = x_i & \text{si } x_i \in X'
\end{cases}
$$

$$
P'_{3} = \left\{ \begin{array}{l} q A(\bar{x}_{1} \cdots \bar{x}_{p}) \rightarrow q B(\bar{C}_{1}(\bar{x}_{1} \cdots \bar{x}_{p}) \cdots \bar{C}_{m}(\bar{x}_{1} \cdots \bar{x}_{p})) / \\ A(x_{1} \cdots x_{p}) \rightarrow B(C_{1}(x_{1} \cdots x_{p}) \cdots C_{m}(x_{1} \cdots x_{p})) \in P \end{array} \right\}
$$

Lemme 5.1 : $L(G') \cap \Phi^{-1}(T_0) = L(G) \cap L(A)$

Preuve :

• c

Il s'agit de montrer que tout arbre de $L(G')$ n'ayant pas #
dans son feuillage est dans $L(G)$ et dans $L(A)$

- dans $L(G)$

Pour la clarté de la preuve considérons que les sous-arbres $\bar{z}_i$
de l'axiome S de G sont en fait de nouveaux terminaux formant l'ensemble Z
et en conséquence les $z_j^i$ de S' dans G' forment $Z' = Z \times Q$.

Considérons alors la transduction descendante d'arbres $\tau$
(voir par exemple [AD]) de $M(TUUUZ)$ dans $M(TUU'UZ')$ définie par :

- ensemble d'états Q
$$ - \{ q, \alpha(x_1 \cdots x_p) \to \alpha(q_1 x_1; \cdots, q_p x_p / \alpha \in T, q, \alpha \to q_1 \cdots q_p \in Q \} $$

$$ - \{ q, z_i \to z_i^q / z_i \in Z \} $$

$$ - \{ q, A(x_1 \cdots x_p) \to qA(1x_1 \cdots \bar{q}x_1, 1x_2 \cdots \bar{q}x_2 \cdots 1x_p \cdots \bar{q}x_p / q \in Q, A \in U \} $$

Remarquons de plus qu'à chaque production de $P'$ est associée naturellement une production de $P$.

Considérons alors la dérivation descendante dans $G'$

$S' \vdash t_1' \vdash \cdots \vdash t_n'$ et son analogue (modulo la remarque ci-dessus) dans $G$ : notons la $S \vdash t_1 \cdots \vdash t_n$. On montre simultanément l'existence de cette dérivation et la propriété suivante par induction sur la longueur :

$$ i \le n \qquad t_i' \in \tau(1, t_i) $$

- vrai pour $i=0$ : $S'=\tau(1,S)$

- supposons la propriété vraie jusqu'à $t_{i-1}$.

On a alors $t_{i-1}' \in \tau(1, t_{i-1})$

$t_{i-1}'$ et $t_{i-1}$ sont donc tels que

$$ t_{i-1} = u[x_i^\rightarrow \setminus v_i^\rightarrow] \text{ et } t_{i-1}' = u[x_i^\rightarrow \setminus v_i^\rightarrow] \text{ avec } u \in M(TU\dot{X}) \text{ et} $$

$v_i' \in \tau(q_i, v_i)$ pour quelque $q_i$ et les $v_i$ ont un élément de $U$ pour racine. On vérifie alors cas par cas l'hypothèse d'induction

- dans $L(A)$.

La preuve se fait simultanément ; la transduction $\tau$ est en fait une version déguisée de l'automate $A$. $\tau$ ne produit un élément de $M(T)$ que si cet élément est accepté par $A$.

<figure><img src="image_17.png" /></figure>

Il suffit de montrer que $L(G) \cap L(A) \subset L(G')$.

Soit $S \vdash t_1 \vdash t_2 \cdots \vdash t_n = t$ une dérivation dans $G$ telle que $t \in L(A)$.

Chacun des $t_i$ est tel que il existe un $\hat{t} \in M(TU\dot{X}_i)$

$$ t_i = \hat{t}[x_j^\rightarrow \setminus A_j^\rightarrow (t_1^j \cdots t_m^j)] \quad \text{et} $$

$t = \hat{t}[x_j^\rightarrow \setminus v_j^\rightarrow]$. De plus considérons un calcul de $A$ sur $t$ (calcul acceptant $t$). Soit $q_1 \cdots q_r$ la suite des états de $A$ sur les noeuds
correspondants aux feuilles $x_j$ de $\hat{t}$ ; on a que pour tout $1 \le j \le r$
$v_j \in L(A_{q_j})$ et de plus $A_j(t_1^j \cdots t_m^j) \stackrel{*}{=} v_j$.

Nous construisons maintenant une dérivation de $t$ dans $G'$
qui est parallèle à celle dans $G$ et "suit" l'automate $A$ sur $t$.

Soit $\lambda$ la transduction descendante déterministe d'arbres
de $M(TUU)$ dans $M(TUU')$ définie par : $(TUU,Q,R)$ où $Q$ est l'ensemble
des états, $R$ est l'ensemble des règles

$$
\[
R = \left\{
  \begin{array}{l}
    q, A(x_1 \cdots x_p) \to q A(1x_1, 1x_2, \cdots, \bar{q}x_2 \cdots 1x_p \cdots \bar{q}x_p / q \in Q, A \in U) \\
    \text{u} \quad \{ q, f(x_1 \cdots x_p) \to f(1x_1, \cdots, 1x_p / q \in Q, f \in T ) \}
  \end{array}
\right\}
\]
$$

Nous noterons $\lambda(q,u)$ le transducté de $u$ en partant dans $l$'état $q$.

Soit, avec les notations précédentes,

$$
t'_{i} = \hat{t}[x_{j}^{\rightarrow} \lambda (q_{j}, A_{j}^{\rightarrow} (t_{1}^{j} \cdots t_{m_{j}}^{j}))]
$$

Alors $S' \vdash t'_i \vdash \cdots \vdash t'_n = t$ est une dérivation de $t$ dans $G'$.
La vérification est immédiate, par cas suivant la nature de la transition de $t_i$ à $t_{i+1}$.
□

(c) Construction de G''

Il s'agit en fait d'une construction très générale qui permet
d'éliminer les arbres comportant certains symboles : # en l'occurrence.

Construction générale :

Soit $G = (T, U, X, S, P)$ une grammaire sous forme normale et
soit $\bar{T} \subset T_0$.

On veut obtenir $G^1 = (T^1, U^1, X, S^1, P^1)$ telle que $L(G^1) = L(G) \cap \Phi^{-1}(\bar{T})$.

Soit $S = A_0(z_1 \cdots z_{p_0})$.

On définit $\omega \in \{0,1\}^p$ par :

$$
\forall i \in [p] \quad \omega_i = 1 \iff \Phi(u_i) \in \bar{T}^*
$$
Revenons à la construction de $G^1$ ; on a :

$$-T^1 = T \setminus (T_0 \setminus \bar{T})$$

$$-U^1 = U \cup U \times \{\omega\}.$$

Les éléments de $U \times \{\omega\}$ seront notés $A\omega$

- $S^1 = A\omega(z_1 \cdots z_{P_0})$ avec la notation introduite plus haut pour $S$.

- $P^1 = P_1 \cup P_\omega$ où $(P_0)$ étant l'arité de la racine de l'axiome)

$$P_\omega = \left\{ \begin{array}{l} A\omega(x_1 \cdots x_{P_0}) \to B(C_1 \omega(x_1 \cdots x_{P_0}) \cdots C_m \omega(x_1 \cdots x_{P_0})) / \\ A(x_1 \cdots x_{P_0}) \to B(C_1(x_1 \cdots x_{P_0}) \cdots C_m(x_1 \cdots x_{P_0})) \in P \end{array} \right\}$$

$$\cup \left\{ A\omega(x_1 \cdots x_{P_0}) \to x_i / A(x_1 \cdots x_{P_0}) \to x_i \in P \text{ & } \omega_i = 1 \right\}$$

$$\cup \left\{ \begin{array}{l} A\omega(x_1 \cdots x_{P_0}) \to u / A(x_1 \cdots x_{P_0}) \to u \in P \\ \phantom{A\omega(x_1 \cdots x_{P_0}) \to } \text{& } u \in M(T^1 \cup X^1), x^1 = \{x_i / \omega_i = t\} \end{array} \right\}$$

$$P_1 = \left\{ t \to t' / t \to t' \in P \text{ & } t' \in M(T^1 \cup X) \right\}$$

Nous allons montrer

**Lemme 5.2** : $t \in L(G^1)$ ssi $t \in L(G) \cap \Phi^{-1}(\bar{T})$.

Pour cela on montre d'abord le lemme plus général.

**Lemme 5.3** : Soit $G = (T, U, X, S, P)$ une grammaire algébrique sous forme normale ; soit $G^2 = (T, U^2, X, S^2, P^2)$ une grammaire algébrique telle que $U^2 \subset U \times Q$ pour quelque ensemble $Q$, $S^2 = A_0q(z_1 \cdots z_{P_0})$ si

$$S = A_0(z_1 \cdots z_{P_0}) \text{ et } P^2 \subset P_{<Q} \text{ où}$$

$$P_{<Q} = \left\{ t'_1 t'_2 / t_1 t_2 \in P \text{ & } h_{<Q}(t'_1) = t_1, h_{<Q}(t'_2) = t_2 \right\}$$

$h_{<Q}$ étant le morphisme défini par

$$h_{<Q}(\alpha(x_1 \cdots x_p)) = \alpha(x_1 \cdots x_p) \text{ si } \alpha \in T$$

$$h_{<Q}(Aq(x_1 \cdots x_p)) = A(x_1 \cdots x_p) \text{ si } Aq \in U^2.$$

Alors $L(G^2) \subset L(G)$.
**Preuve** : Par induction sur les dérivations. A toute dérivation $G'$ on associe une dérivation de $G$ telle que à chaque étape les dérivés $t'$ dans $G^2$ et $t$ dans $G$ vérifient $t=h_{<Q>}(t')$ : il suffit pour cela de prendre à chaque étape la production analogue dans $G$. Si la dérivation s'arrête dans $G^2$, la dérivation associée dans $G$ est terminale et donne le même arbre (puisqu'exempt de non-terminaux).

Par application du lemme 5.3 on montre donc que si $t \in L(G^1)$ alors $t \in L(G)$.

Montrons que :

**Lemme 5.4** : $\Phi(G^1) \cap \bar{T}^* = \emptyset$

**Preuve** : Par induction sur les dérivations on montre :

(a) Soit $t = A\omega(t_1 \cdots t_p)$ un sous-arbre d'un arbre dérivé alors si $\Phi_1(t_i)$ contient un élément de $T_0 - \bar{T}$, $\omega_i=0$.

(b) Soit $t = A(t_1 \cdots t_p)$ un sous-arbre d'un arbre dérivé alors pour tout $i, \Phi_1(t_i) \in (\bar{T} \cup U')^*$.

(c) le front des arbres dérivés ne contient aucun élément de $T_0 - \bar{T}$.

• La propriété est vraie pour l'axiome par construction

• Supposons que $t$ vérifie la propriété et soit tel que $t \vdash t'$ par une réécriture descendante.

Distinguons deux cas selon la nature du non-terminal réécrit :
$$ - t = \hat{t}[x\setminus A(t_1 \cdots t_p)], A \in U. $$

si la production est du type :

$$ A(x_1 \cdots x_p) \to B(C_1(x_1 \cdots x_p) \cdots C_m(x_1 \cdots x_p)) $$

alors $t' = \hat{t}[x\setminus B(C_1(t_1 \cdots t_p) \cdots C_m(t_1 \cdots t_p))]$ et, les propriétés (a), (b), (c) sont immédiatement vérifiées.

si la production est du type $A(x_1 \cdots x_p) \to x_i$ ou $A(x_1 \cdots x_p) \to u$, (par construction $u \in M(T' \cup X)$) : les sous-arbres de type (a) ou (b) ne sont pas modifiés et donc (b) et (a) sont vérifiées ;
le front de $t'$ est obtenu en remplaçant $A$ par $\Phi_1(t_i)$
ou $\Phi_1(u[x_i^-, t_i^>]})$ dans $\Phi_1(t)$.

les $t_i$ vérifiant (b) $t'$ vérifie (c).

- $t = \hat{t}[x\wedge A\omega(t_1, \dots, t_p)]$, $A\omega \in U \times \{\omega\}$.

si la production est du type $A\omega(x_1, \cdots, x_p) \to B(C_1, \omega, \cdots)$ on vérifie
aisément (a) (b) et (c) sur $t'$

si la production est du type $A\omega(x_1, \cdots, x_p) \to x_i$ ou $A\omega(x_1, \cdots, x_p) \to u$
$(x_i$ apparaît dans $u$ seulement si $\omega_i=1)$ : les sous-arbres de
type (a) ou (b) ne sont pas modifiés et donc (a) et (b) sont
vérifiées ; le front de $t'$ est obtenu en remplaçant $A\omega$ par
$\Phi_1(t_i)$ ou $\Phi_1(u[x_i, t_i])$ dans $\Phi_1(t)$.

les $t_i$ vérifiant (a), (c) est vérifiée par $t'$.

Ceci achève la preuve du lemme 5.4.

On a donc montré la partie $\Rightarrow$ du lemme 5.2. Montrons en la réciproque.

Pour cela étudions la forme d'une dérivation gauche dans $G$
produisant un arbre dans $\Phi^{-1}(\bar{T})$.

Certaines productions sont interdites. En effet l'application
d'une production du type $A(x_1, \cdots, x_p) \to u$ où $u$ contient des symboles de
$T_0 \setminus \bar{T}$ produit certainement un élément hors de $\Phi^{-1}(\bar{T})$. La seule façon
d'introduire des éléments de $T_0 \setminus \bar{T}$ est d'utiliser des arbres $u_i$ (sous-
arbres de l'axiome) en contenant. L'introduction de ces $u_i$ ne peut se
faire que par des règles $A(x_1, \cdots, x_p) \to u$ ou $A(x_1, \cdots, x_p) \to x_i$ appliquées au
dernier non-terminal restant à dériver sur une branche. Il suffit donc
de repérer un tel non-terminal et de supprimer ses réécritures inter-
dites : c'est ce qui est fait en introduisant dans $G^1$, $U_\omega$ et $P_\omega$. QED.

Pour en terminer revenant aux notations initiales on contruit
donc la grammaire $G''$

= (T, U", X", S", P") où

$$
U'' = Q \times U \cup Q \times U \times \{\omega\}
$$

X'' = X' = X \times Q \quad \text{les non-terminaux voient leur arité multipliée}
\qquad \text{par } \bar{q}

$$
S'' = 1A_0^\omega (\hat{z}_1, \dots, \hat{z}_{P_0})^+
$$

+ on peut en fait poser maintenant $\hat{z}_i = z_i, \dots, z_i \quad \overline{q \text{ fois}}$
P'' = P' ∪ P''
ω est de longueur $\bar{q}×P_0$

$$ω_{\bar{q}(i-1)+j} = 1 \text{ ssi } u_i \in L(A_j).$$

$$P' = \left\{ \begin{array}{l} qA(\bar{x}_1 \cdots \bar{x}_p) \to x_i^q / q \in Q, A(x_1 \cdots x_p) \to x_i \in P \\ \cup \quad qA(\bar{x}_1 \cdots \bar{x}_p) \to u' / q \in Q, u \in M(TU X), \\ \phantom{\cup \quad qA(} A(x_1 \cdots x_p) \to u \in P, h_Q(u') = u \ \& \ u' \in L(A_q) \end{array} \right\}$$

$$\cup \quad \left\{ \begin{array}{l} qA(\bar{x}_1 \cdots \bar{x}_p) \to qB(\bar{C}_1(\bar{x}_1 \cdots \bar{x}_p) \cdots \bar{C}_m(\bar{x}_1 \cdots \bar{x}_p)) / \\ \phantom{\cup \quad qA(} A(x_1 \cdots x_p) \to B(x_1 \cdots x_p) \cdots C_m(x_1 \cdots x_p) \in P \end{array} \right\}$$

$$P'_ω = \left\{ qAω(\bar{x}_1 \cdots \bar{x}_{P_0}) \to x_i^q / q \in Q, ω_{\bar{q}(i-1)+q} = 1 \quad A(x_1 \cdots x_{P_0}) \to x_i \in P \right\}$$

$$\cup \quad \left\{ \begin{array}{l} qAω(\bar{x}_1 \cdots \bar{x}_{P_0}) \to u' / q \in Q, u \in M(TU X), A(x_1 \cdots x_{P_0}) \to u \in P, h_Q(u') = u \\ \phantom{\cup \quad qAω(} u' \in L(A_q), \{x_i^q/x_i^q\} \text{ occurre dans } u' \\ \phantom{\cup \quad qAω(} \text{et } ω_i^q = 0 \} = \emptyset \end{array} \right\}$$

$$\cup \quad \left\{ qAω(\bar{x}_1 \cdots \bar{x}_{P_0}) \to q^B(C_1ω(\quad) \cdots A(x_1 \cdots x_{P_0}) \to B(\quad) \cdots \in P) \right\}$$

Soit $G = (T, U, X, S, P)$ une grammaire élémentaire simple, on appelle *profondeur* de la grammaire et on note $\text{prof}(G)$ :

$$h = \max\{\text{hauteur}(t) / (t', t) \in P \text{ ou } t=S\}$$

**Corollaire 5.5** : Soit $G = (T, U^P \cup U^\sigma, X, S, P)$ une grammaire élémentaire simple sous forme normale, $A = (T, Q, 1, \bar{q}, Q)$ un automate fini. La grammaire $G'' = (T, U'', X'', S'', P'')$ obtenu par la construction est élémentaire simple $U'' = U'' \cup U''^\sigma$ et on a :

$$\text{card}(U''^P) = \text{card}(U^P) \times \bar{q}$$

$$\text{card}(U''^\sigma) = \text{card}(U^\sigma) \times \bar{q}$$

$$\text{prof}(G'') = \text{prof}(G)$$

**Preuve** : D'après la construction précédente on a

$$U''^P = \{ qA / A \in U^P, q \in Q \}$$

$$\cup \quad \{ qAω / A \in U^P, q \in Q, \text{ A d'arité } P_0 \}$$

$$U''^\sigma = \{ qA / A \in U^\sigma, q \in Q \}$$

$$\cup \quad \{ qAω / A \in U^\sigma, q \in Q, \text{ A d'arité } P_0 \}$$
et $qA \sigma q'B \quad \text{ssi } A \sigma B$

$qAw \sigma q'Bw \quad \text{ssi } A \sigma B.$

enfin $\text{prof}(G'') = \text{prof}(G)$ immédiatement. $\square$

Dans le cas où $G = (T,U,X,S,P)$ est une grammaire linéaire et si $A = (T,Q,1,\bar{q},Q)$ est un automate _ascendant déterministe_, la construction peut être faite directement [cf [AD] pour une construction analogique].

Rappelons qu'un automate fini d'arbres peut être considéré de façon équivalente comme ascendant on descendant. La condition de déterminisme ici prescrite entraîne que pour $(q_1 \cdots q_p)$ et $f \in T_p$ donnés, il existe un unique $q$ tel que, $f \to q_1 \cdots q_p \in Q$.

Soit
$$A<q,q_1\cdots q_p> \text{ l'automate}$$
$$(T \cup X_p, Q \cup \{\omega\}, q, \omega, Q \cup \Omega(q_1, \dots, q))$$

tel que

$$Q(q_1 \cdots q_p) = \left\{ \begin{array}{l} q_i, x_i \to \omega / 1 \le i \le p \\ \qquad \cup \quad \{ q, a \to \omega / q \in T_0, q, a \to \bar{q} \in Q \} \end{array} \right.$$

Soit

$C' = (T, U' \cup \{E\}, X, S', P')$ telle que

$$U' = \bigcup_{p \in N} Q \times U_p \times Q^P = \{ qAw / q \in Q, A \in U_p, w \in Q^P \}$$

$$S' = \begin{array}{l} E(z_1, \dots, z_p) \text{ où } S = A_0(z_1, \dots, z_p) \\ \text{où } F \in U \end{array}$$

$$P' = \left\{ \begin{array}{l} qAw(x_1 \cdots x_p) \to f(B'_1(t_1^1 \cdots t_m^1) \cdots B'_r(t_1^r \cdots t_m^r)) / \\ \phantom{qAw(x_1 \cdots x_p) \to f(B'_1(t_1^1 \cdots t_m^1) \cdots} B'_i = u_i B_i v_i \in U' \text{ pour } 1 \le i \le r \\ A(x_1 \cdots x_p) \to f(B_1(t_1^1 \cdots t_m^1) \cdots B_r(t_1^r \cdots t_m^r)) \in P \\ f(x_1 \cdots x_p) \in L(A<q, u_1 \cdots u_r>) \\ t_j^i \in L(A<v_j^i, w) \text{ pour } 1 \le i \le r, 1 \le j \le m_i \end{array} \right\}$$

$$\cup \left\{ E(u_1 \cdots u_p) \to I A_0^w(u_1 \cdots u_p) / u_i \in L(A<\bar{w}_i, \bar{q} \cdots \bar{q}>), 1 \le i \le p \right\}$$
**Proposition 5.6** : $L(G') = L(G) \cap L(A)$.

**Preuve** : Montrons $L(G') \subset L(G) \cap L(A)$.

Soit $S' \vdash t_1' \cdots \vdash t_n' = t'$ une dérivation terminale dans $G'$. Pour tout $1 \le i \le n$, soit $t_i$ l'arbre obtenu en remplaçant dans $t_i'$ chaque symbole $qAw \in U'$ par $A$. D'après la construction de $P'$, $S = t_1' \vdash t_2' \cdots \vdash t_n' = t'$ est une dérivation dans $G$. Il reste à montrer que $t' \in L(A)$.

Soit $A'$ l'automate $(TuU', Q, l, \bar{q}, Q')$ extension de $A$ à $M(TuU')$ tel que
$$Q' = \{U \mid q, qBw \to w_1 \cdots w_p / qBw \in U' \}$$
Il est clair que si $t \in M(T)$ et $t \in L(A')$ alors $t \in L(A)$.

Montrons maintenant par induction sur la dérivation que $t' \in L(A')$.

(i) Supposons que $t_i' \in L(A')$.

$t_i'$ est de la forme $\hat{t}[x\qquad A(s_1, \cdots, s_p)]$ avec $\hat{t} \in L(A \subset I, q)$ ($\hat{t}$ n'a qu'une seule occurrence de variable : $x$) et pour tout $1 \le j \le p$ $s_j \in L(A \subset w_j)$. On vérifie aisément que $t_{i+1}'$ obtenu en appliquant à $qAw(s_1, \cdots, s_p)$ une production de $P'$ vérifie encore l'hypothèse d'induction.

Inversement montrons que $L(G) \cap L(A) \subset L(G')$.

Soit $S = t_1' \vdash t_2' \cdots \vdash t_n' = t$ une dérivation dans $G$ de $t$ et supposons que $t \in L(A)$. Nous construisons pas à pas une suite d'arbres $t_1', t_2', \cdots, t_n' = t$ dans $M(TuU')$ telle que $S' \vdash t_1' \cdots \vdash t_n'$ est une dérivation de $t$ dans $L(G')$. Cette suite est construite à partir de $t_n'$ en revenant en arrière jusqu'à $S'$. Supposant $t_{i+1}'$ construit, $t_i'$ est obtenu de la façon suivante :

$t_i = \hat{t}[x\A(s_1 \cdots s_m)]$ et $t_{i+1}$ est obtenu par dérivation de $A(s_1 \cdots s_m)$ suivant l'une des productions :

$$- A(x_1 \cdots x_m) \to f(B_1(t_1^1, \cdots, t_m^1)) \cdots B_r(t_1^r \cdots t_m^r))$$

alors
$$t_{i+1} = \hat{t}[x\f(B_1(t_1^1, \overrightarrow{x_j}, \overrightarrow{s_j})) \cdots t_m^1(\overrightarrow{x_j}, \overrightarrow{s_j})]$$

A étant déterministe pour chaque $s_j$, il existe un $q_j$ unique tel que $s_j \in L(A \subset q_j)$ ; de plus

$$t_{i+1}^{\prime} = \hat{t}'[x\f(\cdots p_l B_l p_1^{\prime \ell} \cdots p_m^{\prime \ell} (t_1^{\prime \ell}[\overrightarrow{x_j}, \overrightarrow{s_j}] \cdots t_m^{\prime \ell}[\overrightarrow{x_j}, \overrightarrow{s_j}]) \cdots)]$$

et notons que $t_k^{\prime \ell} \in L(A \subset p_k^{\prime \ell}, q_1, \cdots, q_m)$ ; enfin il existe un $q$ unique tel que

$f \in L(A \subset q, p_1, \cdots, p_r)$.
Dans ces conditions $t_i'$ est obtenu comme

$$t_i' = \hat{t}'[x\,qAq_1\cdots q_m(s_1\cdots s_m)]$$

$$- A(x_1\cdots x_m) \to u \in M(TU\dot{X}).$$

alors $t_{i+1}' = \hat{t}[x\setminus u[x_j'\vec{s_j}]\vec{s_j}]$. Avec les mêmes notations

$$t_{i+1}' = \hat{t}'[x\setminus u[x_j'\vec{s_j}]\vec{s_j}] \text{ et il existe } q \text{ tel que } u \in L(A_{<q,q_1\cdots q_m})$$

alors $t_i' = \hat{t}'[x\,qAq_1\cdots q_m[s_1\cdots s_m]]$.

Remarquons que dans les deux cas $t_i'|\to t_{i+1}'$ dans $G'$ par construction de $P'$, que (par induction) $t_i = h_Q(t_i')$, $h_Q$ étant le morphisme d'arbres remplaçant les $qAq_1\cdots q_m$ par $A$, enfin que $S'|\to t_i'$ toujours par construction. $\square$

**Corollaire 5.7** : Soit $G = (T,U,X,S,P)$ une grammaire linéaire, $A = (T,Q,1,\bar{q},Q)$ un automate ascendant déterministe. La grammaire $G' = (T,U',X,S',P')$ obténue par la construction, est linéaire et, si a note l'arité maximale des éléments de $U$
$$\text{card}(U') = \text{card}(u) \times_q \bar{q}^{a+1}$$
$$\text{prof}(P') = \text{prof}(P).$$

## 5.2 Index rationnel des feuillages

**Lemme 5.8** : Soit $G$ une grammaire de type fini à $k$ non-terminaux et de profondeur $p$. Alors les arbres dérivés sont de hauteur $p+\max^k$ au plus.

**Preuve** : par récurrence sur $k$.

Si $k=1$ les dérivations sont de longueur $1$ et la propriété est vraie.

Considérons une grammaire $G$ à $k+1$ non-terminaux. Deux cas se présentent :

- il n'existe pas de non-terminal dominant tous les autres ; alors $G$ est en fait la réunion de $n$ grammaires à $k_1\cdots k_n <k$ non-terminaux et de profondeur $p$ au plus et on a $p+\max^{k>\max\{p+\max^{k_i}\}}$.
- il existe A dominant tous les autres non-terminaux, qui se dérive en un arbre de hauteur p ; chacun des non-terminaux peut se dériver dans cette grammaire à k-1 non-terminaux en un arbre de hauteur $p^{k-1}$, l'arbre dérivé de A ayant alors une hauteur maximale de $p+p^k$.

**Remarque :** Ce maximum est atteint par les grammaires

$$G_i = (\{f,a\}, \{A_1, \dots, A_i\}, \{x,y\}, A_i, P_i)$$
$$P_i = \{ A_j(x,y) \to A_{j+1}(A_{j+1}(x,y), A_{j+1}(x,y)/1 \le j < i) \}$$

<figure><img src="image_18.png" /></figure>

**Proposition 5.9 :** Soit G une grammaire élémentaire stricte à R non-terminaux-récursifs, N non-terminaux non-récursifs et de profondeur p. Soit A un automate d'arbres à n états. Si $L(G) \cap L(A) \neq \emptyset$, il existe un arbre de profondeur au plus

$$R \times n \times p^{N \times n}$$

**Preuve :** La grammaire $G''$ obtenue en 5.1 a d'après le corollaire 5.5, $R \times n$ non-terminaux-récursifs, $N \times n$ non-terminaux non-récursifs, et est de profondeur p. Il existe une grammaire $G'''$ élémentaire stricte sous forme standard telle que $L(G'') = L(G')$

$G'''$ a $R \times n$ non-terminaux-récursifs et les sous-arbres de choix sont de profondeur $p^{N \times n}$ d'après le lemme 5.8.

D'après la proposition 4.13 il existe alors un arbre de profondeur $R \times n \times p^{N \times n}$ au plus et donc de feuillage de longueur au plus

$$\lambda R \times n \times p^{N \times n}$$

**Définition :** On note $D\text{Exp}(n^2)$ la classe des langages dont l'index rationnel est majoré par $2^{\alpha n^2}$ pour $\alpha \in \mathbb{R}$.
**Théorème 5.10** : La classe des feuillages de forêts élémentaires simples est incluse dans $DExp(n^2)$.

**Preuve** : Soit $G$ ayant $L$ pour feuillage. Soit $K \subset \mathrm{Rat}_n$, alors $\Phi^{-1}(K) \in \mathrm{Frat}_n$ et par la proposition précédente si $L \cap K \neq \emptyset$ il contient un mot de longueur $\lambda^{R \times n^2 \times p} N \times n^2 \le 2^{\alpha n^2}$ pour quelque $\alpha \in R$. $\square$

**Corollaire 5.11** : $\mathrm{ETOL} \subset DExp(n^2)$.

**Proposition 5.12** : Soit $G$ une grammaire linéaire à $N$ non-terminaux d'arité a au plus et de profondeur $p$. Soit $A$ un automate ascendant déterministe à $n$ états.

Si $L(G) \cap L(A) \neq \emptyset$, il existe un arbre de feuillage au plus $\lambda^{N \times n^{a+1}}$

**Preuve** : d'après la proposition 4.7 et le corollaire 5.7.

**Théorème 5.13** : La classe des feuillages de forêts linéaires est incluse dans $DExp(n^2)$.

Soit $G$ ayant $L$ pour feuillage. Soit $K \subset \mathrm{Rat}_n$ ; $\Phi^{-1}(K) \in \mathrm{FDrat}_n$ et par la proposition précédente, si $L \cap K \neq \emptyset$ il contient un mot de longueur au plus

$\lambda^{N \times 2^{(a+1)n^2}} < 2^{\alpha n^2}$ pour quelque $\alpha \in R$.
## 6. Un langage DOL d'index rationnel $\mathbb{Q}^{\alpha\sqrt{n}}$

Considérons le langage $\mathcal{B}$ défini par le système de réécriture parallèle.

$\{a \to aa, b \to 0b, c \to abc\}$ et d'axiome c.

$$ \mathcal{B} = \left\{ a^{2^n} 0^{n_b} a^{2^{n-1}} 0^{n-1_b} \dots a^{4} 0^{2} ba^{2} 0ba^{bc} / n \ge 0 \right\} $$

On définit la famille d'automates finis reconnaissant les langages

$$ \mathcal{D}_p = a^+(0^p)^+ ba^+(0^{p+1})^+ b \dots a^+(0^{2p-1})^+ b (a+0+b+c)^+ $$

$\mathcal{D}_p$ peut être reconnu par un automate à $\frac{3}{2}(p^2+p)$ états.

Pour estimer la longueur du plus petit mot de $\mathcal{D}_p \cap \mathcal{B}$ remarquons qu'il est tel que

* $n$ est multiple de $p$

* $n+1$ est multiple de $p+1$

* $n-p+1$ est multiple de $2p-1$.

On a besoin des deux propriétés arithmétiques.

**Lemme 6.1** : Soient $k$ nombres $p_1, \dots, p_k$. Le plus petit entier positif $\Pi$ tel que pour tout $1 \le i \le k$ $p_i$ divise $\Pi-p_i$ est $ppcm(p_1 \cdots p_k)$.

**Preuve** :

- pour tout $i$ $ppcm(p_1 \cdots p_k) = \lambda_i p_i$ avec $\lambda_i \ge 1$ donc $p_i$ divise $ppcm(p_1 \cdots p_k)-p_i$.

- Soit $0 < \Pi < ppcm(p_1 \cdots p_k)$ vérifiant la propriété. Alors pour tout $i$, $p_i$ divise $\Pi-p_i$ et $ppcm(p_1 \cdots p_k)-p_i$ donc $ppcm(p_1 \cdots p_k)-\Pi$, ce qui contredit la définition du ppcm. $\square$
**Lemme 6.2** : Le plus petit mot de $\mathcal{D}_p \cap \mathcal{B}$ est tel que $n=ppcm(p,p+1,\cdots,2p-1)-p$.

**Preuve** : par application du lemme 6.1

☐

Nous évaluons maintenant la valeur de ppcm(p,p+1,···,2p-1).

**Lemme 6.3** : pour tous p, k<p

$$ppcm(p,p+1, \dots, p+k) \le \left( \prod_{0 \le i \le k} (p+i) \right) / (k!)$$

**Preuve** : Soit $P = \prod_{0 \le i \le k} (p+i)$. Soit

$$\delta = \text{pgcd}(\frac{P}{p}, \dots, \frac{P}{p+k}) ; \text{ on a alors le résultat classique}$$

$$P = \delta \times \text{ppcm}(p,p+1,\cdots,p+k).$$

Il reste donc à trouver une borne supérieure pour $\delta$.

Remarquons que $\delta$ divise toute expression obtenue par somme ou différence à partir des $\frac{P}{p+i}$, en particulier les différences successives de la fonction $\frac{P}{x}$ aux points $p,p+1,\cdots,p+k$ et donc la différence k-ième égale (au signe près) à

$$P \times \sum_{0 \le i \le k} (-1)^i \binom{p+k}{i} \frac{1}{p+i} = k!$$

$$\text{d'où } \text{ppcm}(p,p+1,\cdots,p+k) > \frac{P}{k!}$$

**Proposition 6.4** : L'index rationnel de $\mathbb{R}$ croît au moins comme $2^{\alpha\sqrt{n}}$ pour $\alpha \in \mathbb{R}$.

**Preuve** : par les lemmes 6.2 et 6.3, le plus petit mot de $\mathcal{B} \cap \mathcal{D}_p$ correspondant à un exposant $n_p$ supérieur à

$$\frac{p(p+1)\cdots(2p-1)}{(p-1)!} = \frac{(2p-1)!}{((p-1)!)^2}$$

$$\text{d'où } n_p > 2^{2p-1}.$$

Soit $q = \frac{3}{2}(p+p^2)$ on a donc que $n_p > \alpha\sqrt{q}$ pour $\alpha \in \mathbb{R}$ et donc que la longueur du plus petit mot de $\mathcal{B} \cap \mathcal{D}_p$ est au moins $2^{\alpha\sqrt{q}}$. ☐

☐
Bibliographie :

[AD] A. Arnold & M. Dauchet : *Transductions de forêts reconnaissables monadiques. Forêts corégulières.* RAIRO Informatique Théorique Vol 10,n°3, Mars 1976

[BCN] L. Boasson, B. Courcelle, M. Nivat : *A new complexity measure for languages*. Conference on Theoretical Computer Science University of Waterloo Aug. 1977.

[BN] L. Boasson & M. Nivat : *Ordres et types de langages*. CRAS notes n°A559 - A625 - A703 mars 1977

[Bo] G. Boudol : *Langages polyadiques algébriques*. Thèse de 3° cycle Université Paris 7 1975

[Br] W.S. Brainerd : *Tree generating regular systems*. Information and Control 14, 217-231 (1969).

[Dw] P.J. Downey : *Formal languages and recursion schemes*. PhD Thesis Harvard Univ. 1974.

[Fi] M.J. Fischer : *Grammar with macro-like productions*. PhD Thesis Harvard Univ. 1968.

[Ro] W.C. Rounds : *Mappings and Grammars on trees*. Math. Syst. Theory Vol 4,n°3.

[Rz] G. Rosenberg : *Extension of tabled OL-systems and Languages*. Int. Journal of Comp. and Inform. Sciences. Vol 2,n°4, 1973.

[St1] JM Steyaert : *Sur les index rationnels des feuillages de forêts linéaires*. CRAS note A394 Juillet 1977.

[St2] JM Steyaert : *Forêts algébriques maximales*. à paraître.