# Arbres infinis et systemes d'equations

Bruno Courcelle

► To cite this version:

Bruno Courcelle. Arbres infinis et systemes d'equations. [Rapport de recherche] IRIA-RR-328, IRIA. 1978, pp.27. hal-04716517

HAL Id: hal-04716517

https://inria.hal.science/hal-04716517v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons Attribution 4.0 International License
Inv. 05568 RR328

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

ARBRES INFINIS
ET
SYSTÈMES D'ÉQUATIONS

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

Bruno COURCELLE

Rapport de Recherche N° 328

Octobre 1978

<figure><img src="image_3.png" /></figure>
ARBRES INFINIS ET SYSTEMES D'ÉQUATIONS

Bruno Courcelle

IRIA

Résumé :

On examine certains cas où la valeur d'un arbre infini (i.e. d'une expression infinie bien formée telle qu'une série entière) peut être définie comme l'unique solution d'un système (infini) d'équations. On en déduit une nouvelle caractérisation algébrique de l'ensemble des arbres infinis.

Abstract :

In certain cases, the value of an infinite tree (i.e an infinite well formed expression such that a formal power series) can be defined as the unique solution of a possibly infinite system of equations. One obtains a new algebraic characterization of the algebra of infinite trees.
## Introduction :

Précisons tout d'abord de quel type d'arbres nous allons parler.

On se donne un ensemble $F$ de symboles de fonction chacun muni d'une arité (i.e. nombre d'arguments). A toute expression bien formée sur cet ensemble correspond classiquement un arbre fini étiqueté par les éléments de $F$, tel que le nombre des descendants immédiats de tout noeud est l'arité de son étiquette. Nous allons considérer des arbres de même type mais *infinis*, qui correspondent intuitivement à des *expressions bien formées infinies*. Un exemple familier d'une telle expression est la série formelle :

$$1 + z \cdot z + z \cdot z \cdot z + \dots + z^n + \dots$$

écrite avec les symboles de fonction binaires $\cdot$ et $+$, la constante 1 et la variable z (1 et z sont d'arité 0).

La notion d'arbre infini s'introduit assez naturellement en théorie des schémas de programmes. Cousineau [5] représente par un arbre infini, l'ensemble des calculs d'un programme itératif. Rosen [14], Courcelle et Nivat [9] associent un arbre infini $T(\Sigma)$ à un schéma de programme récursif $\Sigma$ en "exécutant symboliquement" tous les appels récursifs. Toutes les propriétés sémantiques de $\Sigma$ sont alors contenues dans $T(\Sigma)$. On peut caractériser l'équivalence de deux schémas comme l'égalité des arbres infinis qui leur sont associés (Courcelle et Nivat [9]).

Notons $M^\infty(F)$ l'ensemble des arbres infinis construits avec $F$. On peut le définir mathématiquement de plusieurs façons :

(1) comme *complétion au sens de la théorie des ensembles ordonnés* de l'ensemble des arbres finis muni d'un ordre convenable,

(2) comme *séparé-complété* (Bourbaki [4]) de l'ensemble des arbres finis muni d'une distance convenable (qui généralise la distance ultramétrique classique en théorie des séries formelles).

(3) "directement" comme ensemble des graphes infinis d'un certain type (voir le § 1 ci-dessous).
On appelle *F-magma A* la donnée d'un ensemble $|A|$ et pour chaque symbole k-aire $f \in F$, d'une fonction (totale) $f_A : |A|^{k} \to |A|$. Il est clair que tout arbre fini $T$ (considéré comme une expression bien formée) a une valeur $t_A$ dans $A$. Il s'agit en fait de pouvoir définir la valeur $T_A$ d'un arbre infini. Dans le cas d'un schéma de programme $\Sigma$, et d'une *interprétation A* de $\Sigma$ (i.e. un F-magma A muni d'un ordre partiel qui satisfait certaines propriétés) la valeur $T(\Sigma)_A$ est la valeur calculée par $\Sigma$ dans A c'est à dire par le programme $(\Sigma,A)$. Le lecteur consultera Courcelle et Nivat [9,10] pour plus de détails sur les schémas de programme récursifs.

On peut définir la valeur $T_A$ d'un arbre infini $T$ dans un F-magma $A$ en faisant sur $A$ des hypothèses topologiques :

(i) $A$ est un F-magma ordonné complet, i.e. une interprétation ([9,10], ADJ[1]) et cette hypothèse correspond à la définition (1) des arbres infinis, ou

(ii) $A$ est un F-magma métrique compact et à opérateur contractants (Arnold et Nivat [2]) et cela correspond à la définition (2) ci-dessus.

En corollaire, on caractérise $M^{\infty}(F)$ comme un objet initial dans les catégories respectives suivantes :

(i') la catégorie des F-magmas ordonnés complets,

(ii') la catégorie des F-magmas métriques compacts et contractants.

Cet article tente de répondre aux questions suivantes :

(α) Dans quelle mesure peut-on se passer des hypothèses topologiques sur $A$ pour définir $T_A$ ?

(β) De quelle catégorie $M^{\infty}(F)$ est-il objet initial ?

L'idée directrice est la suivante. Si $f$ est un symbole unaire, l'arbre $T = f^\omega$ (constitué d'une unique branche infinie dont chaque noeud a l'étiquette $f$) satisfait l'équation $T = f(T)$. Sa valeur $T_A$ dans un F-magma $A$ devra satisfaire l'équation $T_A = f_A(T_A)$. Il est clair que si l'équation $x = f_A(x)$ a une unique solution $x_0$ dans $A$ alors on pourra poser $T_A = x_0$. Autrement, $T$ sera dit sans valeur dans $A$.
Plus généralement, la valeur $T_A$ d'un arbre infini $T$ s'obtient (si elle existe) comme solution *unique* d'un système (éventuellement infini) d'équations associé canoniquement à $T$.

On considère dans cet article des systèmes d'équations de la forme
$$ x_i = f(x_{j_1}, \dots, x_{j_k}) \quad \text{où} \quad x_i, x_{j_1}, \dots, x_{j_k} \text{ sont des variables et f est un opérateur d'ariték.} $$
Et l'on pose les définitions suivantes : un F-magma A est algébriquement clos (resp. intègre) si tout système d'équations, fini ou infini, a au moins (resp. au plus une solution). Dans un F-magma A intègre et algébriquement clos, tout arbre infini $T$ a une valeur $T_A$. En d'autres termes, il existe un unique homomorphisme de F-magmas : $M^{\infty}(F) \to A$. Ainsi $M^{\infty}(F)$ est l'objet initial de la catégorie des F-magmas intègres et algébriquement clos. D'où une nouvelle question :

($\gamma$) Que contient cette catégorie en dehors de $M^{\infty}(F)$ ?

Elle contient les magmas métriques compacts pourvus d'opérateurs contrac-
tants, et les quotients de $M^{\infty}(F)$ par des congruences *semi-fermées* (i.e. telles que
chaque classe d'équivalence est *fermée* pour la distance sur $M^{\infty}(F)$ évoquée plus haut
et étudiée en détail dans [2]), et d'autres choses encore que nous ne savons pas
décrire.

Par contre un F-magma de la forme $M^{\infty}(F)/\equiv$ où $\equiv$ est la congruence associée à une classe $C$ d'interprétations (Courcelle, Nivat [9,10]) n'est pas intègre en général, même si $C$ est une classe équationnelle, donc de la forme sur laquelle nous savons dire le plus de choses (Courcelle [7]). Les propriétés de fermeture de ces congruences sont étudiée en appendice. Beaucoup de preuves sans difficultés réelles sont laissées au lecteur.

Je remercie A. Arnold de ses critiques et de ses suggestions.
# 1. Le F-magma des arbres infinis

(1.1) Soit F un ensemble fini ou infini de symboles avec arité. L'arité de $f \in F$ est l'entier positif ou nul $\rho(f)$.

Un F-magma est un objet $A = \langle |A|, \langle f_A \rangle_{f \in F} \rangle$ où $|A|$ est un ensemble (le domaine de $A$) et $f_A$ un opérateur $\rho(f)$-aire sur $|A|$ (si $\rho(f)=0$ alors $f_A$ est un élément de $|A|$). Un homomorphisme de F-magmas $h : A \to A'$ est une application $h : |A| \to |A'|$ telle que $h(f_A(d_1, \dots, d_k)) = f_A(h(d_1), \dots, h(d_k))$ pour tout $f \in F$ $d_1, \dots, d_k \in |A|$, où $k$ est l'arité de $f$.

Soit $N_+$ l'ensemble des entiers strictement positifs $N_+^*$ le monoïde libre engendré (son unité, le mot vide se note $\emptyset$).

Un arbre est une fonction partielle $T$ de $N_+^*$ dans $F$ telle que :

(1) $\text{Dom}(T) = \{u \in N_+^* | T(u) \text{ est défini}\}$ est clos par préfixe i.e. $u \in \text{Dom}(T)$ si $u \in \text{Dom}(T)$.

(2) Pour tout $u \in \text{Dom}(T)$ alors $u \in \text{Dom}(T)$ ssi $1 \le i \le \rho(T(u))$.

Un élément $u$ de $\text{Dom}(T)$ est un noeud de $T$. Le sous-arbre de $T$ issu du noeud $u$ est l'arbre $T'$ tel que $T'(v) = T(uv)$ pour tout $v \in N_+^*$. On le note $T/u$.

Donnons quelques exemples.

Soit $F = \{f,g,a\}$ avec $\rho(f)=2$, $\rho(g)=1$, $\rho(a)=0$.

La fonction $t : \{1,2\}^* \to F$ telle que

$$t(\epsilon) = f \qquad t(21) = g$$

$$t(1) = g \qquad t(211) = a$$

$$t(11) = a \qquad t(22) = a$$

$$t(2) = f$$

est un arbre que l'on représentera graphiquement ainsi :

<figure><img src="image_4.png" /></figure>
Il correspond au terme fgafgaa écrit en notation polonaise préfixe (qui n'est pas ambigüe puisque les arités des symboles sont fixées).

La fonction $T : \{1,2\}^{*} \rightarrow F$ telle que :

$$
\begin{cases}
T(2^n) = f, & n \ge 0 \\
T(2^n 1^m) = g & \text{si } 0 < m \le n \\
T(2^n 1^{n+1}) = a & n \ge 0
\end{cases}
$$

correspond à l'arbre infini représenté sur la figure 1. Le sous arbre issu du
noeud 22 est entouré par une ligne brisée. []

Si $\rho(f)=1$ pour tout $f \in F$ alors $M^{\infty}(F)$ s'identifie à $F^{\omega}$, l'ensemble des mots infinis sur $F$, c'est à dire des suites $(f_i)_{i \in N}$ telles que $f_i \in F$ pour tout $i$ (c.f. [13]). Par exemple, le mot $(fg)^{\omega}$ s'identifie à l'arbre $T$ tel que $T(1^n)=f$ si $n$ est pair ou nul, $T(1^n)=g$ si $n$ est impair.

(1.2) On munit $M^{\infty}(F)$ d'une structure de F-magma en définissant $f_{M^{\infty}(F)}$ pour $f \in F$ par :

1) Si $\rho(f)=0$ alors $f_{M^{\infty}(F)}$ est l'arbre T tel que $T(\epsilon)=f$ et $T(u)$ indéfini si $u \neq \epsilon$,

2) Si $\rho(f)=k$ alors $f_{M^{\infty}(F)}$ est la fonction k-aire sur $M^{\infty}(F)$ telle que
$f_{M^{\infty}(F)}(T_1, \dots, T_k) = T$ avec :

$$
\begin{cases}
T(\epsilon) = f \\
T(iu) = T_i(u) \text{ pour } 1 \le i \le k \text{ et } u \in \text{Dom}(T_i)
\end{cases}
$$

On omettra dorénavant l'indice $M^{\infty}(F)$.

Un arbre $T$ est *fini* si $\text{Dom}(T)$ est fini. Il s'identifie alors canoniquement à une expression (finie) bien formée écrite avec l'ensemble de symboles $F$. On les note en représentation polonaise préfixe.
On note $M(F)$ l'ensemble des arbres finis. C'est un sous-$F$-magma de $M^\infty(F)$,
et même le $F$-magma libre : pour tout $F$-magma $A$ il existe un unique homomorphisme
$M(F) \to A$ noté $h_A$. Si l'on considère $t \in M(F)$ comme une expression bien formée, elle
a dans $A$ une valeur $t_A = h_A(t)$.
<figure><img src="image_5.png" /><figcaption>Figure 1</figcaption></figure>
(1.3) On se pose le problème suivant : pour quels F-magmas A peut-on étendre de manière unique $h_A$ en un homomorphisme : $M^\infty(F) \to A$ ? En d'autres termes, quand peut-on attribuer à chaque $T \in M^\infty(F)$ une valeur $T_A$ dans $|A|$ de telle sorte que $T_A = f_A(T_1, \dots, T_k)$ si $T = f(T_1, \dots, T_k)$ ?

Si $T = g^\omega$ (avec $\rho(g)=1$, voir(1.1))$ alors $T=g(T)$ et la valeur $T_A$ dans $A$ devra satisfaire l'équation $T_A = g_A(T_A)$. Si l'équation $x = g_A(x)$ a une seule solution dans $A$, alors $T_A$ sera définie de manière unique comme la solution de cette équation.

Plus généralement, si $T$ est un arbre infini arbitraire on introduit le système d'équations :

$X_{U_0} = f_A(X_{U_1}, \dots, X_{U_k})$ si $U_0 = f(U_1, \dots, U_k)$ où $X_U$ est une variable associée à chaque sous-arbre $U$ de $T$. Si ce système (éventuellement infini) a une et une seule solution dans $A$, $T$ aura dans $A$ une valeur, à savoir la composante de la solution du système considéré associée à $X_T$.

(1.4) Donnons maintenant des définitions formelles. Soit $X$ un ensemble de variables (d'arité 0), $Y$ un ensemble de paramètres (d'arité 0) ; un système d'équations en $X$ et $Y$ est une application $F : X \to M(F \times Y)$ telle que pour tout $x \in X$, $E(x)$ est de l'une des trois formes suivantes :

$$ (i) \ E(x) = f \qquad (f \in F \text{ et } \rho(f)=0) $$

$$ (2) \ E(x) = y \qquad (y \in Y) $$

$$ (3) \ E(x) = f x_1 \cdots x_k \quad (f \in F, \rho(f) = k \ge 1, x_1, \dots, x_k \in X) $$

On en parlera aussi comme de l'ensemble des équations :$\{x = F(x) / x \in X\}$.

Etant donnés un F-magma $A$ et une application $\phi : Y \to |A|$, une *solution de* $E_{A,\phi}$ (c'est à dire une solution de $F$ dans $A$ pour les valeurs des paramètres données par $\phi$) est une application $\theta : X \to |A|$ telle que $\theta(x) = f_A$ si $E(x)=f$, $\theta(x) = \phi(y)$ si $F(x)=y$ et $\theta(x) = f_A(\theta(x_1), \dots, \theta(x_k))$ si $E(x) = f x_1 \cdots x_k$. On la note aussi $(\theta(x))_{x \in X}$.

Donnons quelques définitions supplémentaires relatives aux systèmes.
Soit $\mathcal{E} : X \to \mathcal{M}(\mathcal{F}U\mathcal{X}\mathcal{U}\mathcal{Y})$ un système, soit $X'$ une partie de $X$ telle que $\mathcal{E}(x) \in \mathcal{M}(\mathcal{F}U\mathcal{X}'U\mathcal{Y})$ pour tout $x \in X'$. On dit alors que la restriction $\mathcal{E}'$ de $\mathcal{E}$ à $X'$ est un sous-système de $\mathcal{E}$, ce qu'on note $\mathcal{E}' \subseteq \mathcal{F}$. Intuitivement, $\mathcal{E}'$ est une partie de l'ensemble des équations de $\mathcal{E}$ qui reste un système.

Deux systèmes $E_1$ et $E_2$ sont compatibles s'il existe un système $E_3$ tel que $E_1 \subseteq E_3$ et $E_2 \supseteq E_3$. On peut définir alors les deux sous-systèmes de $E_3$, $F_1 \cap E_2$ et $E_1 \cup E_2$ en les ensembles de variables respectifs $X_1 \cap X_2$ et $X_1 \cup X_2$ (où $X_i$ est l'ensemble des variables de $E_i$). Soient enfin $E_1$ et $E_2$ (en les ensembles de variables $X_1$ et $X_2$) et $\alpha : X_1 \to X_2$ une application. On dit que $\alpha$ est un homomorphisme de systèmes, ce que l'on note $\alpha : E_1 \to F_2$ si $E_2(\alpha(x)) = \alpha(E_1(x))$ pour tout $x \in X_1$. A toute solution $\theta : X_2 \to |A|$ de $E_2$ on peut associer la solution $\theta \circ \alpha : X_1 \to |A|$ de $E_1$.

Un F-magma $A$ est algébriquement clos (resp. intègre) si tout système $\mathcal{E}_{A,\phi}$ admet au moins (resp. au plus) une solution. (Dans un anneau intègre, l'équation $x=ax+b$ admet une solution au plus lorsque $a \neq 1$ ; le terme algébriquement clos a été pris par analogie avec la théorie des corps).

D'autre part, un F-magma $A$ est libre si pour tous $f, f' \in \mathcal{F}$ d'arité $k, \ell$, tous $d_1, \dots, d_\ell \in |A|$, $f_A(d_1, \dots, d_k) = f'_A(d'_1, \dots, d'_\ell)$ si et seulement si $f=f'(\text{et } k=\ell)$, $d_1=d'_1, \dots, d_k=d'_k$.

(1.5) **Proposition :** $M^{\infty}(\mathcal{F})$ est libre, intègre et algébriquement clos.

Remarquons que notre définition des systèmes a exclus les équations de la forme $x=x$ qui ont plusieurs solutions.

(1.6) **Proposition :** *Pour tout F-magma A intègre et algébriquement clos*
*il existe un unique homomorphisme h_A : M^∞(F) → A*

**Preuve :** Montrons d'abord l'unicité de $h_A$. La famille $(h_A(T))_{T \in M^\infty(\mathcal{F})}$ est solution, donc est l'unique solution du système d'équations $\mathcal{E}$ en l'ensemble de variables $X = \{x_T/T \in M^\infty(\mathcal{F})\}$ tel que $\mathcal{E}(x_T) = f(x_{T_1}, \dots, x_{T_k})$ pour tout $T \in M^\infty(\mathcal{F})$ et $T = f(T_1, \dots, T_k)$. On appelle $\mathcal{F}$ le système canonique.
Réciproquement $E_A$ a une solution $(a_T)_{T \in M^\infty(F)}$ puisque $A$ est algébriquement clos. On pose alors $h_A(T) = a_T$. $\square$

Si $A$ est intègre et algébriquement clos, on associe de manière analogue à tout $T \in M^\infty(F,Y)$ (où $Y$ est un ensemble de paramètres), une unique application $T_A : |A|^Y \to |A|$ telle que $y_A$ soit y-ième projection, i.e. $y_A(\alpha) = \alpha(y)$ pour tout $\alpha \in |A|^Y$ et telle que $\alpha$ étant fixée dans $|A|^Y$ l'application $T \to T_A(\alpha)$ soit un homomorphisme de $F$-magmas.

Et d'autre part :

(1.7) **Proposition** : *Tout F-magma A libre, unitaire et algébriquement clos est isomorphe à $M^\infty(F,Y)$ pour quelque ensemble de paramètres $Y$ dont la cardinalité est au plus celle de $|A|$.*

On a donc obtenu :

- une caractérisation "catégorique" de $M^\infty(F)$, comme un objet initial d'une catégorie (dont on montrera plus loin qu'elle ne se réduit pas à $M^\infty(F)$ !) (c.f. (1.6))

- une caractérisation "algébrique" des magmas $M^\infty(F,Y)$ à un isomorphisme près.

(1.8) **Remarque** : Soit $A$ un F-magma et $\phi$ une surjection $Y \to |A|$. S'il existe un homomorphisme de F-magmas $\theta : M^\infty(F,Y) \to A$ alors $A$ est algébriquement clos. Ainsi tout F-magma complet (c.f. Courcelle, Nivat [9]) est algébriquement clos mais non nécessairement intègre (c.f. section 4).
## 2. Quelques sous-magmas de $M^\infty(F)$

(2.1) Pour tout $T \in M^\infty(F)$ soit $S(T)$ l'ensemble de ses sous-arbres. Soit $F(T)$ la restriction du système canonique $E$ défini en (1.6) à $X_T = \{x_U/U \in S(T)\}$.

On dit que $T$ a une valeur dans $A$ si $F(T)$ a une et une seule solution dans $A$.

Soit $M(T)$ le plus petit sous-magma de $M^\infty(F)$ contenant $S(T)$.

(2.2) **Proposition** : *Un arbre $T$ a une valeur dans $A$ si et seulement si il existe un unique homomorphisme $h : M(T) \to A$.*

*Preuve* : Si $T$ a une valeur dans $A$, la solution $(a_U)_{U \in S(T)}$ de $F(T)$ définit h de manière unique sur $S(T)$ par $h(U) = a_U$, et donc de manière unique sur $M(T)$. Réciproquement, si $h : M(T) \to A$ est un homomorphisme, $(h(U))_{U \in S(T)}$ est une solution de $E(T)$.

Si $E(T)$ admettait une autre solution, on pourrait trouver un autre homomorphisme $h' : M(T) \to A$. [ ]

Soit $M_A$ l'ensemble des $T \in M^\infty(F)$ qui ont une valeur dans $A$.

(2.3) **Proposition** : *Si $A$ est intègre, $M_A$ est un sous-magma de $M^\infty(F)$ et si $T \in M_A$ alors $S(T) \subseteq M_A$. Il existe un unique homomorphisme $h_A : M_A \to A$.*

*Preuve* : Soient $T_1, \dots, T_k \in M_A$ et $f \in F$ d'arité k. Il faut montrer que $T = f(T_1, \dots, T_k) \in M_A$. Il est clair que chaque système $E(T_i)$ est un sous-système de $E(T)$ et donc qu'il existe un système $E'$ réunissant les équations des $E(T_i)$, en l'ensemble de variables $\{x_U/U \in S(T_1) \cup \dots \cup S(T_k)\}$. Montrons d'abord que $E'$ a une et une seule solution. Si $E_1$ et $E_2$ sont deux systèmes compatibles en les ensembles de variables respectifs $X_1$ et $X_2$, ayant chacun une solution $\theta_1$ et $\theta_2$, alors $\theta_1$ et $\theta_2$ coïncident sur $X_1 \cap X_2$ puisque, A étant intègre, le système $E_1 \cap E_2$ a une solution au plus, et donc $\theta_1(x) = \theta_2(x)$ si $x \in X_1 \cap X_2$. On a pour $E_1 \cup E_2$ la solution $\theta$ telle que $\theta(x) = \theta_i(x)$ si $x \in X_i$.
Dans le cas qui nous intéresse, on peut donc définir une solution pour $E(T_1) \cup E(T_2), E(T_1) \cup E(T_2) \cup E(T_3), \dots, E(T_1) \cup \dots \cup E(T_k) = E'$.

Le système $E(T)$ n'est autre que $E'$ augmenté éventuellement de l'équation $x_T = f(x_{T_1}, \dots, x_{T_k})$. Si $E(T)=E'$ alors $E(T)$ a une unique solution. Sinon $x_T \in \{x_{T_1}, \dots, x_{T_k}\}$ et on déduit de l'unique solution de $E'$ une unique solution pour $E(T)$.

Il résulte de (2.2) qu'il existe un homomorphisme $M_A \to A$, que l'on note $h_A$ puisqu'il coïncide avec $h_A : M_A \to A$ lorsque $A$ est intègre et algébriquement clos. $\square$

(2.4) **Remarque** : Si $A$ n'est pas intègre, $M_A$ peut n'être pas un sous-magma de $M_A \stackrel{\infty}{(F)}$ et l'on peut avoir $U \in S(T)$ sans valeur dans $A$ bien que $T$ en ait une. $\square$

La proposition (1.7) se généralise ainsi :

(2.5) **Proposition** : *Tout F-magma $A$ libre et unitaire est isomorphe à un sous-magma de $M_A \stackrel{\infty}{(F,Y)}$ pour quelque ensemble $Y$ dont la cardinalité est au plus celle de $|A|$.*

**Preuve** : On choisit $Y$ en bijection par $\theta$ avec $|A| - \{f_A(d_1, \dots, d_\rho(f)) / f \in F, d_1, \dots, d_\rho(f) \in A\}$.

Tout élément de $|A|$ s'écrit de manière unique comme $T_A(\theta)$ pour quelque $T \in M_A(\mathbb{F}, Y)$. $\square$

(2.6) **Remarque** : On pourrait tenter de définir $T_A$ par un autre système que $E(T)$, par exemple de la manière suivante : à chaque noeud $u$ de $T$ on associe une variable $x_u$ et l'on définit $X'_T = \{x'_u/u \in \text{Dom}(T)\}$.

Soit alors $E'(T)(x'_u) = f$ si $T(u) = f$ et $\rho(f) = 0$,

$E'(T)(x'_u) = f(x'_{u1}, \dots, x'_{uk}) \text{ si } T(u) = f \text{ et } \rho(f) = k$.
L'application $\alpha : X'_T \to X'_T$ définie par $\alpha(X'_u) = X_{T/u}$ réalise un homomorphisme de $E'(T)$ sur $E(T)$.

On voit alors (c.f.(1.4)) que :

1) si $E(T)$ a une solution $\theta$ alors $E'(T)$ en une aussi à savoir $\theta_\alpha$,

2) si $A$ est intègre, $\theta_\alpha$ est l'unique solution de $E'(T)$,

3) mais $E'(T)$ peut avoir une solution sans que $E(T)$ en ait une, ou en avoir plusieurs quand $E(T)$ en a une et une seule.

4) si $A$ est intègre et algèbriquement clos, $T_A$ peut être défini au moyen de $E'(T)$ comme de $E(T)$, comme la composante de la solution de $E'(T)_A$ associée à $x'_E$ aussi bien que comme la composante de la solution de $E(T)_A$ associée à $x'_T$.

(2.7) Un F-magma $A$ sera dit *rationnellement clos* (resp. *finiment intègre*) si pour tout système $E$ en un nombre fini de variable, tout $\phi : Y \to A$ (c.f.(1.4)) $E_{A,\phi}$ a au moins (resp. au plus) une solution.

Il existe un plus petit sous-magma rationnellement clos de $M^\infty(F)$ que l'on note $R^\infty(F)$. C'est l'ensemble des *arbres rationnels* ; il contient strictement $M(F)$ puisque l'équation $x = g(x)$ n'a pas de solution dans $M(F)$.

(2.8) **Proposition** : *Pour tout F-magma finiment intègre et rationnellement clos A, il existe un et un seul horomorphisme (encore noté) $h_A : R^\infty(F) \to A$.*

La proposition suivante figure essentiellement dans Huet [12] :

(2.9) **Proposition** : *Un arbre $T \in M^\infty(F)$ est rationnel si et seulement si il est composante d'une solution dans $M^\infty(F)$ d'un système fini, si et seulement si il a un nombre fini de sous-arbre distincts.*

Il en résulte que même si $F$ est infini, l'ensemble $\text{Sym}(T)$ des symboles ayant une occurrence dans un arbre rationnel $T$ (i.e. $\text{Sym}(T) = \{T(u) \mid u \in \text{Dom}(T)\}$) est une partie finie de $F$.
Au prix de quelque technique on obtient le résultat suivant (c.f.[6] ;
la condition nécessaire est énoncée dans [1]).

(2.10) **Proposition** : *Un arbre* $T \in \mathcal{M}^\infty(F)$ *est rationnel si et seulement si :*

1) $\mathrm{Sym}(T)$ est fini

2) $T^{-1}(f) = \{u \in \mathbb{N}_+^* | T(u)=f\}$ est un langage rationnel pour tout $f \in F$.

(2.11) *Autres travaux sur les arbres rationnels.*

Le lecteur trouvera dans Courcelle, Kahn et Vuillemin [8] des résultats
de décidabilité et de mise en forme normale pour les systèmes finis d'équations
et leurs solutions dans $M^\infty(F)$ et dans Cousineau [5], la définition d'arbres ra-
tionnels par "expressions régulières". Tiuryn [15] caractérise $R^\infty(Fu\{\Omega\})$
(c.f. section 4) comme "le F-magma régulier libre". Un F-magma **régulier**
("a regular F-algebra" dans [15]) A est essentiellement un F-magma ordonné où
toute équation $x=t$ (avec $t \in M(Fu\{x\})$) admet une plus petite solution de la forme
$\text{Sup}\{t_A^n(\underline{\perp_A})/n \in \mathbb{N}\}$ ($\perp_A$ est le plus petit élément de $|A|$). On fait une hypothèse
semblable pour tout système fini (plus compliquée à écrire). Remarquons qu'un
système fini peut admettre plusieurs solutions dans un F-magma régulier. En
résumé, une F-magma régulier est rationnellement clos mais non nécessairement
finiment intègre (c.f.(1.8)), et de plus il est ordonné.

Elgot, Bloom et Tindell[11] introduisent l'objet Ftr (relatif à l'alpha-
bet F muni d'une arité) défini comme la collection des $\langle S_1, \cdots, S_n \rangle$ où $S_i \in R^\infty(FuV_p)$
$V_p = \{v_1, \cdots, v_p\}$ pour $n, p \in \mathbb{N}$. Ils montrent que c'est (une représentation de) la
théorie itérative (Bloom, Elgot [3]) libre engendrée par $\{fv_1 \cdots v_k / k=p(f)\}$,
c'est à dire essentiellement que les systèmes d'équations de la forme

$$
\left\{
\begin{array}{l}
S_1 = U_1 [S_1 / v_{p+1}, \dots, S_n / v_{p+n}] \\
\bullet \\
\bullet \\
\bullet \\
S_n = U_n [S_1 / v_{p+1}, \dots, S_n / v_{p+n}]
\end{array}
\right.
$$

ont une unique solution dans $R^\infty(FuV_p)$ si les $U_i$ sont des éléments de
$R^\infty(FuV_{p+n}) - V_{p+n}$ et $U_i[S_1/v_{p+n}, \dots, S_n/v_{p+n}]$ désigne la substitution de $S_j$ à
chaque occurrence de $v_{p+j}$ dans $U_i$ (c.f. Courcelle [6]).
Mentionnons seulement la relation suivante entre théories itératives et magmas rationnellement clos :

Si $T$ est une théorie itérative, si $\bar{f} \in T_{1,k}$ pour chaque $f \in F$ d'arité $k$ et chaque $\bar{f}$ est "idéal" (c.f. [3]) alors chaque $T_{1,p}$ est un $F$-magma finiment intègre et rationnellement clos si l'on pose

$$f_{T_1,p}^{(a_1, \dots, a_k)} = \bar{f} \cdot (a_1, \dots, a_k)$$

pour tous $a_1, \dots, a_k \in T_{1,p}$ (avec les notations de [3]).

### 3. Construction de magmas intègres et algébriquement clos

(3.1) Commençons par donner une condition suffisante pour qu'un $F$-magma soit intègre et algébriquement clos.

Soit un $F$-magma $A$. L'ensemble desparties de $|A|$ est canoniquement muni d'une structure de $F$-magma $P(A)$ par

$$f_{P(A)} = \{f_A\} \text{ si } \rho(f)=0$$

$$f_{P(A)}(B_1, \dots, B_k) = f_A(B_1, \dots, B_k) = \{f_A(b_1, \dots, b_k) / b_i \in B_i\}$$

si $\rho(f)=k$ et $B_i \subset |A|$ pour $i=1, \dots, k$.

Soit $Y$ en bijection par $\phi$ avec $|A|$, soit $X$ l'ensemble de variables $\{x_T/T \in \mathbb{M}^{\infty}(FUY)\}$ et $E$ le système canonique (tel que

$$E(x_T) = y \text{ si } T=y \in Y, F(x_T) = f \text{ si } T=f \text{ et}$$

$$E(x_T) = f x_{T_1} \cdots x_{T_k} \text{ si } T = f(T_1, \dots, T_k). \text{ Soit } \phi'(y) = \{\phi(y)\} \text{ pour tout } y \in Y.$$

Le système $E_{P(A),\phi'}$ a *une plus grande solution* $(B_T)_{T \in \mathbb{M}^{\infty}(FUY)}$ par le théorème de Knaster-Tarski. Elle est explicitement définie par :
$$
B_T = \bigcap \{B_T^\alpha / \alpha \text{ est un ordinal}\}
$$

$$
B_{T}^{\circ} = |A|
$$

$$
B_T^\lambda = \bigcap \{B_T^\alpha / \alpha < \lambda\} \quad \text{si } \lambda \text{ est un ordinal limite,}
$$

$$
B_{T}^{\alpha+1} = \{f_{A}\} \text{ si } T=f
$$

$$
\begin{align*}
B_T^{\alpha+1} &= \{\phi(y)\} = \phi'(y) \quad \text{si } T=y \\
&= f_A(B_{T_1}^{\alpha}, \dots, B_{T_k}^{\alpha}) \quad \text{si } T = f(T_1, \dots, T_k)
\end{align*}
$$

On vérifie sans peine que $B_T^\alpha \subseteq B_T^{\alpha'}$ pour $\alpha > \alpha'$.

Si maintenant $(a_T)_{T \in \mathbb{M}^\infty(F)}$ est une solution de $F_{A,\phi}$ alors $a_T \in B_T^\alpha$
pour tout $\alpha$ (cela se montre par induction sur $\alpha$) et donc $a_T \in B_T$. Il en résulte,
avec ces notations :

(3.2) **Proposition** : *Le F-magma A est intègre (resp. intègre et algébriquement clos) si chaque B<sub>T</sub> a au plus un élément (resp. est singleton).*

(3.3) **Remarques** : 1) Si chaque $B_T$ a au plus un élément, $M_A = \{T \in \mathbb{M}^\infty(F) / B_T \neq \emptyset\}$ et $B_T = \{T_A\}$ pour $T \in M_A$.

2) Pour tout F-magma A, et tout T∈M(F,Y), $B_T^ω = \{T_A(\phi)\}$.

3) Un exemple très simple montre que les conditions de la proposition 7 ne sont pas nécessaires : $F = \{f\}, \rho(f)=1, A$ de domaine $\{1,2,3\}$ tel que $f_A(1)=1, f_A(2)=3, f_A(3)=2$. Soit $T = f^\omega = fff\cdots$ ; alors $B_T = \{1,2,3\}$ mais l'équation $x = f_A(x)$ a une et une seule solution.

(3.4) Un F-magma A muni d'une distance d qui le rend compact et telle que pour un réel c, 0<c<1 on ait :

$d(f_A(a_1, \cdots, a_k), f_A(a'_1, \cdots, a'_k)) \le c. \max\{d(a_i, a'_i) / i \le k\}$
pour tous $f \in F, a_1, \cdots, a_k, a'_1, \cdots, a'_k \in |A|$ avec $k=\rho(f)$ est dit _contractant_.
Les $f_A$ sont alors des fonctions uniformément continues.
Le F-magma $M^∞(F)$ est contractant si on le munit de la distance ultra-métrique (Bourbaki [4]):

$$ 
\begin{aligned}
d(T, T') &= \sup\{2^{-|u|} / u \in \text{Dom}(T) \cap \text{Dom}(T') \text{ et } T(u) \neq T'(u)\} \text{ si } T \neq T' \\
&= 0 \qquad \text{si } T=T'
\end{aligned}
$$

et si l'on prend $c=1/2$. D'autre part, $M(F)$ est dense dans $M^∞(F)$ et $M^∞(F)$ est le séparé complété de $M(F)$ (c.f. Arnold et Nivat [2]).

(3.5) **Proposition** : *Un F-magma contractant A est intègre et algébriquement clos. L'homomorphisme $h_A : M^∞(F) \to A$ est uniformément continu.*

**Preuve** : L'hypothèse de contraction entraîne que les $f_A$ sont continues, et puisque $B_T^\circ = |A|$ est compact, $B_T^n$ est compact (récurrence sur $n$) ; donc $(B_{T^n}^n)_{n \in N}$ est une suite décroissante de compacts non vides ; son intersection $B_T^\omega$ est non vide.

D'autre part, le diamètre $\delta(B_T^n)$ de $B_T^n$ est certainement inférieur ou égal à $c^n \delta(B_T^\circ) = c^n \delta(|A|)$. Il en résulte que $\delta(B_T^\omega)=0$ et donc que $B_T^\omega$ est réduit à un élément. Alors $B_T^{\omega+1}$ est aussi non vide, contenu dans $B_T^\omega$. Donc $B_T^{\omega+1} = B_T^\omega$. Il résulte de la proposition (3.2) que A est intègre et algébriquement clos.

Finalement si $T, T' \in M^\infty(F)$, si $T(u) = T'(u)$ pour tout $u \in N_+^*$ tel que $|u| \le n$ (c'est à dire si $d(T, T') < 2^{-n}$),
$$ d(T_A, T_A') \le c^{n+1} \cdot \delta(|A|). $$

Il en résulte que $h_A : M^\infty(F) \to A$ est uniformément continu. $\square$

Une autre construction va nous fournir des F-magmas intègres et algébriquement clos non nécessairement contractants.

(3.6) Une *congruence* sur $M^\infty(F)$ est une relation d'équivalence ~ telle que $f(T_1, \dots, T_k) \sim f(T'_1, \dots, T'_k)$ si $T_i \sim T'_i$ pour $1 \le i \le k$.
Elle est dite *fermée* (Bourbaki [4]) si pour tous $T, T', T_n, T'_n \in M^\infty(F)$ tels que $\lim_{n \to \infty} T_n = T$, $\lim_{n \to \infty} T'_n = T$ et $T_n \sim T'_n$ pour tout $n$ alors $T \sim T'$, autrement dit si le graphe de $\sim$ est une partie fermée de $M^\infty(F) \times M^\infty(F)$ pour la topologie as-sociée à la distance définie en (3.4). Elle est dite *semi-fermée en $T \in M^\infty(F)$* si pour tous $S$ et $U_n \in M^\infty(F)$ tels que $\lim_{n \to \infty} U_n = T$ et $U_n \sim S$ pour tout $n$, alors $T \sim S$. Elle est *semi-fermée* si elle est semi-fermée en tout $T \in M^\infty(F)$ et cela équivaut à dire que la classe d'équivalence $[S]_\sim$ de tout $S \in M^\infty(F)$ est fermée.

(3.7) **Remarque** : Si $A$ est contractant, le noyau $\sim_A$ de l'homomorphisme $h_A : M^\infty(F) \to A$, c'est à dire l'équivalence *teille* que $T \sim_A T' \iff h_A(T) = h_A(T')$ est une congruence fermée. Il en résulte que $A$ est isomorphe au quotient de $M^\infty(FUY)$ par une congruence fermée.

(3.8) **Exemple** : Donnons un exemple d'une congruence semi-fermée mais non fermée.

Soit $F = \{a,b\}$ avec $\rho(a) = \rho(b)=1$ (on identifie donc $M^\infty(F)$ à $\{a,b\}^\omega$ ainsi qu'il a été dit en (1.1)).

Définissons les suites :

$$u_n = ababbabba\cdots ab^n a \in F^*$$

$$v_n = aabaabbaabbbaa\cdots aab^n aa \in F^*$$

$$w_n = aaabaaabaaaa\cdots aaab^n aaa \in F^*$$

pour $n \ge 1$, ainsi que leurs bornes supérieures respectives $u,v,w$ dans $F^*UF^\omega$ ordonné par l'ordre préfixe. Ainsi

$$u = ababbabba\cdots ab^n a \cdots \in F^\omega.$$

Soit $\sim$ la congruence sur $F^\omega$ définie par :

$$x \sim x' \text{ ssi } x=x' \text{ ou } x=y_u w \text{ et } x'=y_v w$$

pour quelque $n \in \mathbb{N}$ et $y \in F^*$.

L'écriture d'un mot $x$ sous la forme $y_u w$ ou $y_v w$ étant unique, la classe de $x$ modulo $\sim$ contient au plus deux éléments. Elle est donc fermée. Mais $\sim$ n'est pas fermée car $\lim_{n \to \infty} u_n w = u$, $\lim_{n \to \infty} v_n w = u$, et $u_n w \sim v_n w$ mais $u \not\sim v$. []
(3.9) **Proposition** : *Soit* ~ *une congruence sur* $M^\infty(F)$. *Le F-magma* A = $M^\infty(F)/$~ *est algébriquement clos.* *Si* ~ *est semi-fermée en tout* U∈S(T) (*pour* T∈$M^\infty(F)$ *alors* T a une valeur dans A.*

Enonçons tout de suite son corollaire.

(3.10) **Théorème** : *Si ~ est une congruence semi-fermée sur $M^\infty(F)$ alors $M^\infty(F)/$~ est intègre et algébriquement clos.*

Associé à (3.7) et (3.8), ce théorème montre qu'il existe des magmas intègres et algébriquement clos non contractants.

**Preuve de la proposition (3.9) :**

Montrons que $A = M^{\infty}(F)/$ est algébriquement clos : soit $\phi : Y \to |A|$ de la forme $\phi(y) = [\phi'(y)]_{\sim}$ pour quelque $\phi' : Y \to M^{\infty}(F)$ et F un système en l'ensemble X de variables et l'ensemble Y de paramètres. Le système $F_{M^{\infty}(F),\phi'}$ a une solution $(T_X)_{X \in X}$ et $([T_X]_{\sim})_{X \in X}$ est une solution de $F_{A,\phi'}$.

Soit maintenant $T \in M^\infty(F)$ tel que $\sim$ est semi-fermée en tout $U \in S(T)$. Le système $E(T)$ défini en (2.1) a la solution $([U]_\sim)_{U \in S(T)}$ dans A.

Soit $([S_U]_\sim)_{U \in S(T)}$ une solution arbitraire de $E(T)$ dans A. On va montrer que $U \sim S_U$ pour tout $U \in S(T)$. Définissons pour cela $S_U^{(n)}$ pour $n \in N$ en posant :

$$
\begin{align*}
S^{(0)} &= S_U \\
S_U^{(n+1)} &= f(S_U^{(n)}, \dots, S_U^{(n)}) \text{ si } U = f(U_1, \dots, U_k) \\
           &= f \text{ si } U = f \in F \text{ et } \rho(f)=0
\end{align*}
$$

Il est clair que pour tout $U \in S(T)$, $S_U^{(n)} \sim S_U$ et $d(S_U^{(n)}, U) \le 2^{-n}$ (par récurrence sur n), et donc $\lim_{n \to \infty} S_U^{(n)} = U$. Puisque $\sim$ est semi-fermée en tout $U \in S(T)$, $S_U \sim U$. $\square$

La preuve du théorème (3.10) est analogue.
L'exemple qui suit montre qu'il existe d'autres magmas intègres
et algébriquement clos que ceux issus du théorème (3.10).

(3.11) **Exemple** : Soit $F = \{f,g,a,b\}$ avec $\rho(f) = \rho(g) = 1$ et $\rho(a) = \rho(b) = 0$.

Soit $\sim$ la plus petite congruence sur $M(F)$ telle que :

fa $\approx$ a

ga $\approx$ a

fgft $\approx$ gt pour tout $t \in M(F)$.

Au moyen de la proposition (3.2), on va montrer que $A = M(F)/\approx$ est
intègre et algébriquement clos. On note $[t]$ la classe d'équivalencede $t \in M(F)$
modulo $\approx$, on identifie $M(F)$ à $\{f,g\}^{*\{a,b\}}$ et $M^\infty(F)-M(F)$ à $\{f,g\}^\omega$.

On va montrer que $B_T = \{a\}$ pour tout $T \in \{f,g\}^\omega$. Le résultat viendra
alors de la proposition (3.2) et des remarques (3.3).

Or pour tous $T \in \{f,g\}^\omega$, $u \in \{f,g\}^*$ et $n \in \mathbb{N}$ :

1) $[a] \in B_T^n$

$$
2) [ub] \in B_T^n \quad \text{ssi } ub \approx ww'b \quad \text{pour quelques } w,w' \in \{f,g\}^*
$$

tels que |w|=n et ww' est un facteur gauche de T.

On va montrer que $[ub] \notin B_T^\omega$.

Remarquons si $ub \approx ww'b$ alors $u$ et $ww'$ ont le même nombre de $g$.
Donc $[ub] \in B_T^\omega$ implique $T = wgf^\omega$ ou $T = f^\omega$. On vérifie sans peine que l'on
ne peut avoir $ub \approx wgf^n b$ (resp. $ub \approx f^n b$) pour une infinité de $n$. Donc
$[ub] \notin B_T^\omega$. Ainsi $B_T = B_T^\omega = \{[a]\}$.

Ainsi $A$ est intègre et algébriquement clos.

Soit ~ la congruence : T~T' si et seulement si $T_A=T'_{A'}$ définie sur $M^\infty(F)$.
Elle n'est pas semi-fermée car $f^n g f^n b \sim gb$ pour tout n, $\lim_{n\to\infty} f^n g f^n b = f^\omega$,
$f^\omega_A = [a]$ et $(gb)_A = [gb] \neq [a]$ et donc $f^\omega \not\sim gb$. []
(3.12) Ces constructions posent de nombreux problèmes :

Soit $\sim$ une congruence finiment engendrée sur $M(F)$ :

1. Quand $M(F)/\sim$ est-il intègre ? algébriquement clos ?
que peut-on dire de la plus petite congruence $\sim$ sur $M^{\infty}(F)$ contenant
$\approx$ et telle que $M(F)/\sim$ est intègre ?

2. Que peut-on dire de la plus petite congruence $\equiv$ sur $M^{\infty}(F)$ contenant $\approx$ et telle que $M^{\infty}(F)/\equiv$ est intègre ? quand coïncide-t-elle avec la plus petite congruence semi-fermée contenant $\approx$ ?

3. Pour quelles congruences fermées sur $M^{\infty}(F)$ le F-magma $M^{\infty}(F)/\equiv$ est-il contractant ?

4. Appendice : Propriétés de fermeture des congruences sur le magma ordonné $M_{\Omega}^{\infty}(F)$.

(4.1) Rappelons que $M_{\Omega}^{\infty}(F) = M^{\infty}(Fu{\Omega})$ (où $\Omega$ est un nouveau symbole d'arité 0) est ordonné par $\prec$ ainsi défini :

{ T $\prec$ T', si et seulement si Dom(T) $\subseteq$ Dom(T') \\ et pour tout u∈Dom(T), T(u)=Ω ou T(u)=T'(u) }

Ainsi, $M^{\infty}(F) = \{T \in M_{\Omega}^{\infty}(F) / \Omega \notin \text{Sym}(T)\}$ et c'est l'ensemble des éléments maximaux de $M_{\Omega}^{\infty}(F)$. Soit $M_{\Omega}^{\infty}(F) = M(Fu\{\Omega\})$.

Si l'on considère $\Omega$ comme une notation pour "l'arbre vide", $T \prec T'$ signifie approximativement que $T$ est "un sous-arbre initial" de $T'$.

Le lecteur consultera Courcelle [6], Courcelle et Nivat [9,10], ADJ[1] pour plus de détails sur $M_{\Omega}^{\infty}(F)$.

Etant donnée une congruence $\alpha$ sur $M_{\Omega}^{\infty}(F)$, il existe plusieurs manières
de l'étendre à $M_{\Omega}^{\infty}(F)$ qui interviennent en théorie des schémas de programmes
(Courcelle [6], Courcelle et Nivat [9,10]) que nous allons rappeler.
(4.2) On associe à $\alpha$ un préordre $\leq_\alpha$ sur $M_\Omega(F)$ en prenant la clôture transitive de $\alpha U$.

On l'étend à $M_\Omega^\infty(F)$ en posant :

$$ \begin{cases} T \leq_{\alpha} T' & \text{si et seulement si pour tout } t \in M_{\Omega}^{\infty}(F) \text{ tel que } t \prec_{\alpha} T \\ \text{il existe } t' \in M_{\Omega}^{\infty}(F) \text{ tel que } t' \prec_{\alpha} T' \text{ et } t \leq_{\alpha} t'. \end{cases} $$

Finalement, on définit une confruence sur $M_\Omega^\infty(F)$ en posant :

$$ T \equiv_{\alpha} T' \text{ si et seulement si } T \leq_{\alpha} T' \text{ et } T' \leq_{\alpha} T. $$

(La congruence $\equiv_\alpha$ est l'équivalence induite sur $M(F)$ par la classe $C_\alpha$ de toutes les interprétations où l'ensemble d'équations $\alpha$ est valide).

(4.3) Une autre manière d'étendre $\alpha$ à $M_\Omega^\infty(F)$ consiste à définir d'abord $\sim_\alpha^\circ$ par :

$$ \left\{ \begin{array}{l} T \sim_{\alpha}^\circ T' \text{ si et seulement si il existe dans } M_\Omega^\infty(F) \text{ deux suites croissantes} \\ (t_n)_{n \in N} \text{ et } (t'_n)_{n \in N} \text{ telles que } t_n \leq_{\alpha} t'_n \text{ pour tout } n, T = \text{Sup}\{t_n\} \text{ et} \\ T' = \text{Sup}\{t'_n\}. \end{array} \right. $$

On définit ensuite $\sim_\alpha^\circ$ comme la clôture transitive de $\sim_\alpha^\circ$.

(4.4) **Remarque** : $T \sim_\alpha T'$ implique $T \equiv_\alpha T'$ mais $\sim_\alpha$ et $\equiv_\alpha$ ne coïncident pas en général ainsi que le montre l'exemple suivant :

On prend le même alphabet et les mêmes conventions que dans l'exemple (3.11).

Soit $\alpha$ la plus petite congruence sur $M_\Omega(F)$ telle que $fg \alpha gft$ pour tout $t \in M_\Omega^\infty(F)$.

$$ \text{Soient } T = (fg)^\omega \text{ et } T' = (fg^2)^\omega. $$

Il n'est pas difficile de montrer que $T \equiv_\alpha T'$. Mais $T$ n'est pas équivalent à $T'$ modulo $\sim_\alpha$. Afin de le montrer remarquons que $T$ satisfait la propriété suivante :

(*) pour toute suite croissante $t_n$ dans $M_\Omega^\infty(F)$ telle que $T = \text{Sup}(t_n)$, $|t_n|_f/|t_n|_g \to 1$ lorsque $n \to \infty$ ($|t|_x$ est le nombre d'occurrences de $x$ dans $t$ pour $x \in F$ et $t \in M_\Omega^\infty(F)$).
Si $t \sim_{\alpha} t'$, $t, t' \in M_{\Omega}(F)$ alors $|t|_f = |t'|_f$ et $|t|_g = |t'|_g$ et donc si $T_1 \sim_{\alpha} T_2$ et $T_1$ satisfait la propriété (*) il en va de même de $T_2$. Donc tout $T'' \sim_{\alpha} T$ satisfait (*). Mais il est clair que $T'$ ne la satisfait pas $(|t'_n|_f / |t'_n|_g) \to 2$ lorsque $n \to \infty$ si $t'_n$ est une suite croissante dans $M_{\Omega}(F)$ qui tend vers $T'$. $\square$

(4.5) **Remarque** : La congruence $\equiv_{\alpha}$ de l'exemple (4.4) n'est pas semi-fernée. En effet,

$T = (fg)^{\omega} \equiv_{\alpha} T_n = f^n g^n (fg)^{\omega}$ pour tout $n$, et $\lim_{n \to \infty} T_n = f^{\omega}$. Or $f^{\omega} \leq_{\alpha} (fg)^{\omega}$ mais l'inégalité inverse n'a pas lieu car $fg\Omega \not\equiv_{\alpha} f^{\omega}\Omega$ pour tout $m \in N$. $\square$

On a pourtant un résultat de fermeture :

Un arbre $T \in M_{\Omega}^{\infty}(F)$ est dit $\leq_{\alpha}$-maximal si pour tout $T' \in M_{\Omega}^{\infty}(F)$, $T \leq_{\alpha} T'$ implique $T \equiv_{\alpha} T'$. Ces arbres sont étudiés dans Courcelle [7].

(4.6) **Proposition** : *Si $T$ est $\leq_{\alpha}$-maximal alors $\equiv_{\alpha}$ est semi-fernée en $T$.*

**Preuve** : Soit $U_n \in M_{\Omega}^{\infty}(F)$ tel que $\lim_{n \to \infty} U_n = T$ et $S \in M_{\Omega}^{\infty}(F)$ tel que $U_n \equiv_{\alpha} S$ pour tout $n$. On peut supposer que $d(U_n, T) < 2^{-n}$ et l'on définit sanspeindre $t_n \in M_{\Omega}^{\infty}(F)$ tel que $t_n < U_n$, $t_n < T$ et $T = \text{Sup}\{t_n\}$. On a $t_n \leq_{\alpha} S$ et donc $T \leq_{\alpha} S$. Puisque $T$ est $\leq_{\alpha}$-maximal, $T \equiv_{\alpha} S$. $\square$

Mettons en évidence pour conclure une famille remarquable de congruences sur $M_{\Omega}^{\infty}(F)$.

Soit $\Pi_0$ un ensemble de paires de la forme $(fv_1, \cdots, v_k, fv_{i_1}, \cdots, v_{i_k})$, $f \in F$, $k = \rho(f), v_1, \cdots, v_k$ sont des variables et $(i_1, \cdots, i_k)$ est une permutation de $(1, \cdots, k)$.

Soit $\Pi$ la plus petite congruence sur $M_{\Omega}(F)$ telle que
$$ \text{ft}_1 \cdots \text{t}_k \in \Pi \text{ ft}_{i_1} \cdots \text{t}_{i_k} \text{ pour tous } \text{t}_1 \cdots \text{t}_k \in M_{\Omega}^{\infty}(F) \text{ et } (\text{fv}_1 \cdots \text{v}_k, \text{fv}_{i_1} \cdots \text{v}_{i_k}) \in \Pi_0. \text{ On dit que } \Pi \text{ est une congruence permutative et on obtient le résultat suivant :} $$
(4.7) **Proposition** : *Soit $\Pi$ une congruence permutative.*

1) *Les relations* $\equiv_{\Pi}$, $\sim_{\Pi}^{\circ}$ et $\sim_{\Pi}$ *coincident*.

2) *La congruence* $\equiv_{\Pi}$ *est fermée*.

3) *Tout* $T \in M_{\Omega}^{\infty}(F)$ *est* $\leq_{\Pi}$ *maximal*.

**Preuve** : Il est montré dans [7] (4.6 et 4.15) que pour $t \in M_{\Omega}^{\infty}(F)$ et $T' \in M_{\Omega}^{\infty}(F)$, $t \leq_{\Pi} T'$ si et seulement si il existe $t' \prec_{\Pi} T'$ tel que $t \in \Pi$ et $t'$.

Soient $T$ et $T' \in M_{\Omega}^{\infty}(F)$ tels que $T \equiv_{\Pi} T'$. On va montrer que $T \sim_{\alpha} T'$.
Pour tout $n$, soit $T^{(n)} \in M_{\Omega}^{\infty}(F)$ tel que :

$$
\begin{align*}
T^{(n)}(u) &= T(u) \quad \text{si } u \in \text{Dom}(T), |u| \le n \\
&= \Omega \quad \text{si } u \in \text{Dom}(T), |u| = n+1
\end{align*}
\text{indéfini autrement.}
$$

On a donc $T^{(n)} \prec T^{(n+1)}$ et $\lim_{n \to \infty} T^{(n)} = T$.

On définit de même $T^{(n)}$ relativement à $T'$.

Pour tout $n$, il existe $t' \in M_{\Omega}^{\infty}(F)$ tel que $T^{(n)} \in \Pi t' \prec T'$ et à cause de la forme particulière de $\Pi^{\circ}$, la plus longue branche de $t'$ a au plus $n+1$ noeuds et donc $t' \prec T^{(n)}$. De même $T^{(n)} \in \Pi t \prec T^{(n)}$ pour quelque $t \in T_{\Omega}^{(n)}(F)$. Donc $T^{(n)} \equiv_{\Pi} T^{(n)}$. La proposition (4.4) de [7] dit alors que $T^{(n)} \in \Pi T^{(n)}$. On a donc $T \sim_{\alpha} T'$.

L'assertion 1 résulte alors de (4.4).

Montrons que $\equiv_{\Pi}$ est fermée.

Soient $U_n, U'_n$ deux suites dans $M_{\Omega}^{\infty}(F)$ telles que $\lim_{n \to \infty} U_n = T$, $\lim_{n \to \infty} U'_n = T'$ pour tout $n$. On peut supposer (quite à extraire des sous-suites de $(U_n)$ et $(U'_n)$) que $d(U_n, T) < 2^{-n}$ et $d(U'_n, T') < 2^{-n}$ pour tout $n$ et donc que $U_n^{(n)} \prec T'$ (avec les notations du début de cette preuve). On a vu que $U_n \equiv_{\Pi} U'_n$ implique $U_n^{(n)} \in \Pi U_n^{(n)}$ puisque $T = \lim_{n \to \infty} U_n^{(n)}$ et $T' = \lim_{n \to \infty} U_n^{(n)}$, on a $T \sim_{\alpha} T'$ et donc $T \equiv_{\Pi} T'$.

Enfin, l'assertion 3 résulte de (4.8) et (4.15) de [7]. $\square$

Une question se pose : quelles sont les congruences $\Pi$ sur $M_{\Omega}^{\infty}(F)$ qui
satisfont la proposition (4.7) ?
Références :

[1] ADJ, (J. Goguen, J. Thatcher, E. Wagner, J. Wright). Initial Algebra Semantics and Continuous Algebras, J. Assoc. Comput. Math. 24(77) 68-95.

[2] A. Arnold, M. Nivat, The metric space of infinite trees, algebraic and topological properties, Rapport Laboria à paraître.

[3] S. Bloom, C. Elgot, The existence and construction of free iterative Theories, J. Comput. System Sci. 12(1976) 305-318.

[4] N. Bourbaki, Topologie Générale, 4e édition, Hermann, Paris.

[5] G. Cousineau, Algebraic definition of Control structures, à paraître dans Theor. Comput. Sci.

[6] B. Courcelle, A representation of trees by Languages, II, Theor. Comput. Sci. 7(1978) 25-55.

[7] B. Courcelle, On recursive equations having a unique solution, Communication au 19<sup>e</sup> Symp. on Foundations of Computer Science, Ann Arbor, (1978).

[8] B. Courcelle, G. Kahn, J. Vuillemin, Algorithmes d'équivalence et de réduction à des expressions minimales dans une classe d'équations récursives simples, Proc. 2<sup>nd</sup> ICALP, Saarbrüchen, Lecture Notes in Comput. Sci. Vol(14), Springer-Verlag pp. 200-213.

[9] B. Courcelle, M. Nivat, Algebraic Families of Interpretations 17<sup>th</sup> Symp. on Foundations of Computer Science Houston (1976) et Rapport Laboria 189.

[10] B. Courcelle, M. Nivat, The algebraic semantics of recursive program schemes, Communication au Colloque Mathematical Foundation of Computer Science (1978), in Lecture Notes in Computer Science (édité par J. Winkowski) Vol. 64, Springer-Verlag. pp.16-30
[11] C. Elgot, S. Bloom, R. Tindell, On the algebraic Theory of rooted trees, IBM Research Report RC 6230, (1976).

[12] G. Huet, Résolution d'équations dans les langages d'ordre 1,2,...,w. Thèse d'Etat, Université Paris 7 (1976).

[13] M. Nivat, Mots infinis engendrés par une grammaire algébrique, RAIRO Informatique Théorique 11(1977) 311-327.

[14] B. Rosen, Program Equivalence and Context-free grammars, J. Comput. System Sci. 11(1975) 358-374.

[15] J. Tiuryn, Fixed-points and algebras with infinitely long expressions I dans "Mathematical Foundations of Computer Science '77", Lecture Notes in Comput. Sci. Vol 53, Springer-Verlag (1977) 513-522.