# The metric space of infinite trees : algebraic and topological properties

André Arnold, Maurice Nivat

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

## To cite this version:

André Arnold, Maurice Nivat. The metric space of infinite trees : algebraic and topological properties. [Research Report] IRIA-RR-323, IRIA. 1978, pp.39. hal-04716523

HAL Id: hal-04716523

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

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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Inv: 04268- RR323

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

laboria

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

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_5.png" /></figure>

THE METRIC SPACE
OF INFINITE TREES :
ALGEBRAIC AND TOPOLOGICAL
PROPERTIES

André ARNOLD
Maurice NIVAT

Rapport de Recherche N° 323

Septembre 1978
THE METRIC SPACE OF INFINITE TREES
ALGEBRAIC AND TOPOLOGICAL PROPERTIES

A. Arnold, M. Nivat*

Résumé :

On met une structure d'espace ultramétrique compact sur l'ensemble des arbres infinis et l'on étudie la continuité de l'opération de composition. Il en résulte des applications aux schémas de programmes récursifs non déterministes.

Abstract :

The set of infinite trees is considered as an ultrametric compact space. The composition of trees is investigated. Applications to non deterministic recursive program schemes are given.

<footnote>* Laboratoire de calcul - B.P. 36, 59650 Villeneuve d'Ascq.</footnote>

<footnote>** 167, Bld Malesherbes - 75017 Paris.</footnote>
# 1. TOPOLOGICAL PREMIMINARIES

In this first section we recall some notions of topology which will be often used in the sequel.

## 1.1 Ultrametric spaces

Let $D$ be a set. A mapping $d$ from $D \times D$ into $\mathbb{R}_+$ is a *distance on D* if for any $x,y,z$ in $E$ we have

(i) $d(x,y) = 0 \text{ iff } x=y$

(ii) $d(x,y) = d(y,x)$

(iii) $d(x,z) \le d(x,y)+d(y,z)$

The distance $d$ is said *ultrametric* if

(iv) $d(x,z) \le \max(d(x,y),d(y,z))$

The set $D$, together with the distance $d$ is called a *metric space*.
It is an *ultrametric space* if $d$ is ultrametric.

For any $x \in D$ and $\epsilon>0$, the *open ball of center x and radius $\epsilon$* is the set $B_{\epsilon}(x) = \{y \in D | d(x,y) < \epsilon\}$.

The proofs of the following properties are just exercises in [6; ch IX, §2].

**Proposition 1** : Let $D$ be an ultrametric space

(i) Each open ball $B_{\epsilon}(x)$ is closed.

(ii) If $y \in B_{\epsilon}(x)$ then $B_{\epsilon}(x) = B_{\epsilon}(y)$

(iii) If $\epsilon \le \epsilon'$ and $B_{\epsilon}(x) \cap B_{\epsilon'}(y) \ne \emptyset$ then $B_{\epsilon}(x) \subset B_{\epsilon'}(y)$

(iv) For every $\epsilon>0$, $\{B_{\epsilon}(x) | x \in D\}$ is a partition of $D$.

Let $A$ be a subset of $D$. We note $B_{\epsilon}(A)$ the open set $U \{B_{\epsilon}(x) | x \in A\} = \{y \in D | \exists x \in A \text{ s.t. } d(x,y) < \epsilon\}$ and we note $\bar{A}$ the closure of $A$ w.r.t. the topology induced by the metric of $D$.
**Proposition 2**: (i) $\bar{A} = \bigcap_{\epsilon} \overline{B_{\epsilon}(A)}$ ; (ii) $B_{\epsilon}(A) = B_{\epsilon}(\bar{A})$ (iii) If D is ultrametric, each open set $B_{\epsilon}(A)$ is closed and thus $\bar{A} = \bigcap_{\epsilon} B_{\epsilon}(A) = \bigcap_{\epsilon} \overline{B_{\epsilon}(A)}$

**Proof**: (i) It is clear that $\bar{A} \subset \bigcap_{\epsilon} \overline{B_{\epsilon}(A)}$.

Let us prove the reverse inclusion : let $x \in \bigcap_{\epsilon} \overline{B_{\epsilon}(A)}$ ; for every $\epsilon$ there exist $y'$ in $B_{\epsilon}(A)$ such that $d(x,y')<\epsilon$ and $y$ in A such that $d(y,y')<\epsilon$ ; hence $d(x,y)<2\epsilon$ and thus $x \in \bar{A}$.

(ii) It is clear that $B_{\epsilon}(A) \subset B_{\epsilon}(\bar{A})$. Let $x$ in $B_{\epsilon}(y)$ with $y \in \bar{A}$. We get $d(x,y)<\epsilon$. Since $y \in \bar{A}$ then exists $z \in A$ such that $d(y,z)<\epsilon-d(x,y)$, hence $d(x,y) \le d(x,y)+d(y,z)<\epsilon$ and $x \in B_{\epsilon}(z) \subset B_{\epsilon}(A)$.

(iii) Since $B_{\epsilon}(A) = \bigcup \{B_{\epsilon}(x)/x \in A\}$ and since $\{B_{\epsilon}(x)/x \in D\}$ is a partition of D whenever D is ultrametric, $D-B_{\epsilon}(A)$ is a union of open balls, thus it is open and $B_{\epsilon}(A)$ is closed. $\square$

Now we extend the metric $d$ on $D$ in a metric on $D^n$ by

$d(<x_1, \cdots, x_n>, <y_1, \cdots, y_n>) = \max\{d(x_i, y_i) / 1 \le i \le n\}$. We choose this "max" extension instead of the usual "Euclidean" extension $(\sum_{1 \le i \le n} d(x_i, y_i))^2)^{1/2}$ because of the following property.

**Proposition 3 :**

(i) $B_{\epsilon}(<x_1, \cdots, x_n>) = B_{\epsilon}(x_1) \times \cdots \times B_{\epsilon}(x_n)$

(ii) If $d$ is ultrametric, its extension to $D^n$ is still ultrametric.

## 1.2 Complete spaces

Let $D$ be a metric space with distance $d$.

A sequence $(x_i)_{i \in \mathbb{N}}$ of elements of $D$ is said *convergent* if then exists $\bar{x} \in D$ such that $\forall \epsilon>0, \exists n \in \mathbb{N} \ \forall p \ge n, d(x_p, \bar{x}) < \epsilon$. If such an $\bar{x}$ exists it is unique and it is called the *limit* of the sequence. A sequence is said a *Cauchy sequence* if $\forall \epsilon>0, \exists n \in \mathbb{N}, \forall p \ge n, \forall q \ge n, d(x_p, x_q) < \epsilon$.
In an ultrametric space there is a simpler characterization of Cauchy sequences.

**Proposition 4** : Let $D$ be an ultrametric space. A sequence $(x_i)_{i \in \mathbb{N}}$ is a Cauchy sequence iff $\lim_{n \to \infty} d(x_n, x_{n+1}) = 0$.

It is well known that every convergent sequence is a Cauchy sequence and that the converse is not always true. Thus a metric space is said *complete* if every Cauchy sequence is convergent.

The following theorem is well known.

**Completion theorem** : Every metric space $(D,d)$ can be isometrically embedded into a complete metric space $(\hat{D}, \hat{d})$. This complete metric space is unique up to isometry and $D$ is dense in $\hat{D}$.

Let us recall that a subset $D$ of the metric space $\hat{D}$ is *dense* in $\hat{D}$ iff $\hat{D}=\bar{D}$, i.e. iff every point of $\hat{D}$ is the limit of a convergent sequence of elements of $D$.

The proof of this theorem is a generalization of the well known Cantor construction of real numbers. Actually the set $\hat{D}$ is the set of equivalence classes of Cauchy sequences in $D$, where two sequences $(x_i)$ and $(y_i)$ are said equivalent if $\lim_{n \to \infty} d(x_n, y_n) = 0$.

It should be noted that the completion of an ultrametric space is still ultrametric because of the following result.

**Proposition 5** : If $(\hat{D},d)$ is a metric space, if $D$ is dense in $\hat{D}$ and if $(D,d)$ is ultrametric then $(\hat{D},d)$ is ultrametric.

**Proof** : Let $\hat{x}, \hat{y}, \hat{z}$ be in $\hat{D}$. Let $\epsilon>0$. There exist $x, y, z$ in $D$ such that $d(x, \hat{x})<\epsilon$, $d(y, \hat{y})<\epsilon$ and $d(z, \hat{z})<\epsilon$. It follows that $d(\hat{x}, \hat{z}) \le d(\hat{x}, x)+d(x, z)+d(z, \hat{z})<2\epsilon+d(x, z)$; $d(x, y) \le d(x, \hat{x})+d(\hat{x}, \hat{y})+d(\hat{y}, y)<2\epsilon+d(\hat{x}, \hat{y})$; $d(y, z) \le d(y, \hat{y})+d(\hat{y}, \hat{z})+d(\hat{z}, z)\le 2\epsilon+d(\hat{y}, \hat{z})$.
Since $d$ is ultrametric on $D$, $d(x,z) \le \max(d(x,y),d(y,z)) < 2\epsilon + \max(d(\hat{x},\hat{y}),d(\hat{y},\hat{z}))$ thus $d(\hat{x},\hat{z}) < 4\epsilon + \max(d(\hat{x},\hat{y}),d(\hat{y},\hat{z}))$. This being true for every $\epsilon$, we get $d(\hat{x},\hat{y}) \le \max(d(\hat{x},\hat{y}),d(\hat{y},\hat{z}))$. []

The following exercise of [8;p 91] will be of interest in the sequel.

**Proposition 6** : Let $D$ be dense in $\hat{D}$. For every open set $A$ in $\hat{D}$, $\bar{A} = A \cap D$.

We will use this result in the following form :

**Corollary 7** : Let $D$ be an ultrametric space and $\hat{D}$ its completion. For every subset $A$ of $\hat{D}$, $B_{\epsilon}(A) = \overline{B_{\epsilon}(A) \cap D}$.

This follows from the fact that the open set $B_{\epsilon}(A)$ is closed.

## 1.3 Painlevé's limits

Here we recall a notion of convergence of sequences of sets. In his book [10;p 335] Kuratowski mention that this notion is originated in the works of Painlevé (1902).

Let $D$ be a topological space which is separated (or Hausdorff, or $T_2$), or more simply a metric space.

Let $(A_i)_i$ a sequence of subsets of $D$. The subset $LS(A_i)$ of $D$ is defined by : $x \in LS(A_i)$ iff for every neighborhood $V$ of $x$ and for any $n \in \mathbb{N}$ then exists $n' \ge n$ such that $V \cap A_{n'} \ne \emptyset$.

The subset $LI(A_i)$ of $D$ is defined by : $x \in LI(A_i)$ iff for every neighborhood $V$ of $x$ there exists $n \in \mathbb{N}$ such that for every $n' \ge n$, $V \cap A_{n'} \ne \emptyset$.

The following properties are straightforward consequences of the definitions.
**Definition 8 :** For any sequence $(A_i)_i$

(i) $\lim_{i} \overline{LS(A_i)} = \overline{LS(A_i)}$

(ii) $\overline{\lim_{i} LS(A_i)} = \overline{\lim_{i} LS(A_i)} = \overline{\lim_{i} A_i}$

(iii) $\overline{\lim_{i} LS(A_i)} = \overline{\lim_{i} LS(A_i)} = \overline{\lim_{i} A_i}$

We say that the sequence $(A_i)_i$ is *P-convergent* if $\overline{\lim_{i} LS(A_i)} = \overline{\lim_{i} A_i}$. Its *limit*, noted $\overline{\lim_{i} LS(A_i)} = \overline{\lim_{i} A_i}$. As usual, writing $\overline{\lim_{i} LS(A_i)}$ implies that the sequence $(A_i)_i$ is *P-convergent*.

The following results are proved in [10].

**Proposition 9 :**

(i) A sequence $(x_i)_i$ of elements of $D$ converges to $x$ iff the sequence $(\{x_i\})_i$ *P-converges* to $\{x\}$.

(ii) For any *P-convergent* sequence $(A_i)_i$, $\overline{\lim_{i} A_i} = \overline{\lim_{i} \overline{A_i}} = \overline{\lim_{i} \overline{A_i}}$.

(iii) For any *P-convergent* sequence $(A_i)_i$ and $(B_i)_i$, $\overline{\lim_{i} (A_i \cup B_i)} = \overline{\lim_{i} A_i} \cup \overline{\lim_{i} B_i}$.

(iv) If $(A_i)_i$ is a decreasing sequence (for set inclusion), it *P-converges* to $\overline{\bigcap_i A_i}$.

(v) If $(A_i)_i$ is an increasing sequence (for set inclusion), it *P-converges* to $\overline{\bigcup_i A_i}$.
## 2. THE METRIC SPACE $M^\infty(F,E)$

### 2.1 The metric space $M(F,E)$ and its completion

Here we recall some classical definitions and notations about finite trees.

A *graded alphabet* $F$ is a finite set of function symbols, each $f \in F$ is given with its *arity* $\rho(f) \in N$. We note $F_i$ the set $\{f \in F / \rho(f) = i\}$. The set $X = \{x_i / i \in N_+\}$ is a set of variables ; we note $X_0 = \emptyset$ and $X_k = \{x_1, \dots, x_k\}$ so that $X = \bigcup_{k \ge 0} X_k$.

For any set $E$ disjoint from $F$, the set $M(F,E)$ is defined inductively by :

* $EU_{F_0} \subset M(F,E)$

* if $f \in F_n$ with $n>0$, if $t_1, \dots, t_n \in M(F,E)$ then $f(t_1, \dots, t_n) \in M(F,E)$.

It is clear that $M(F,E)$ is the *free $F$-magma generated by $F$*. The elements of $M(F,E)$ can be regarded as *finite trees*.

Let us notice that $M(F,E) = \emptyset$ iff $F_0 \cup E = \emptyset$. Thus we always assume, in the sequel that $F_0 \cup E \ne \emptyset$. In particular $F_0 \ne \emptyset$.

In order to prove properties of finite trees we shall often use the principle of *structural induction* : if a property holds for any element in $EU_{F_0}$ and if it holds for $f(t_1, \dots, t_n)$ whenever it holds for $t_1, \dots, t_n$, then it holds for any tree in $M(F,E)$. Structural induction can be also used to define mappings on $M(F,F)$. It is the case for the two following mappings.

The *depth* of a finite tree $t$ of $M(F,E)$ is the integer $dp(t)$ defined inductively by

* if $t \in EU_{F_0}$, then $dp(t)=1$

* if $t = f(t_1, \dots, t_n)$, then $dp(t) = 1 + \max\{dp(t_i) / 1 \le i \le n\}$.

The *distance from the root* of a tree $t$ to the *nearest leaf labelled* by a symbol $a$ in $EU_{F_0}$ is the element $dr1(a,t)$ of $\mathbb{N}\{\omega\}$ defined by
if $t \in \mathbb{F}_0$, then $\text{drl}(a,t) = \begin{cases} 0 & \text{if } a=t \\ \omega & \text{otherwise} \end{cases}$

if $t = f(t_1, \dots, t_n)$ then $\text{drl}(a,t) = 1+\min\{\text{drl}(t_i)/1 \le i \le n\}$

It is straightforward that $\text{drl}(a,t)=\omega$ if a does not occur in $t$, otherwise $\text{drl}(a,t) \le \text{dp}(t)-1$.

We define the truncation at depth $n$ of a tree $t$, noted $\alpha_n(t)$. In order to do that we introduce a new symbol $\Omega$ of arity 0 which will be used to indicate that a branch of the tree $t$ has been cut off in the truncation. Thus $\alpha_n$ is a mapping from $M(F,E)$ into $M(F,EU\{\Omega\})$ defined inductively on $n$.

- for $n=0$, $\alpha_n(t)=\Omega$ for every $t$

- for $n>0$, if $t \in \mathbb{F}_0^U E$, then $\alpha_n(t)=t$

if $t=f(t_1, \dots, t_k)$ then $\alpha_n(t) = f(\alpha_{n-1}(t_1), \dots, \alpha_{n-1}(t_k))$.

It follows from this definition that $\text{dp}(\alpha_n(t)) \le n+1$.

One can prove easily by induction the following properties.

**Proposition 10 :**

(i) $\forall t \in M(F,E), \forall n \in N, \alpha_n(t)=t \quad \text{iff } n \ge \text{dp}(t) \quad \text{iff } \text{drl}(\Omega, \alpha_n(t))=\omega$ and $n < \text{dp}(t)$ implies $\text{drl}(\Omega, \alpha_n(t)) = \text{dp}(\alpha_n(t))-1=n$.

(ii) $\forall t, t' \in M(F,E), \forall n \in N, \text{ if } \alpha_n(t) = \alpha_n(t') \text{ then } n' \le n$ implies $\alpha_n(t) = \alpha_n(t')$.

(iii) $\forall t_1, t_2, t_3 \in M(F,E), \text{ if } \alpha_n(t_1) = \alpha_n(t_2) \text{ and } \alpha_n(t_2) = \alpha_n(t_3)$ then $\alpha_n''(t_1) = \alpha_n''(t_3)$ with $n'' = \min(n,n')$.

From the point (i) of this proposition, we get that if $t_1 \ne t_2$ then $\alpha_n(t_1) \ne \alpha_n(t_2)$ with $n = \max(\text{dp}(t_1), \text{dp}(t_2))$; hence the set $\{n/\alpha_n(t_1) \ne \alpha_n(t_2)\}$ is not empty and we define $\bar{\alpha}(t_1, t_2)$ as the least integer in this set. Thus we define the mapping $d$ from $M(F,E) \times M(F,E)$ into $R_+$ by

$$d(t_1, t_2) = \begin{cases} 0 & \text{if } t_1=t_2 \\ 2^{-\bar{\alpha}(t_1, t_2)} & \text{otherwise} \end{cases}$$
As an immediate consequence of the definition of $d$ and of the
point (iii) of proposition 10 we get.

**Proposition 11 :** The mapping $d$ is an ultrametric distance on $M(F,E)$

We note $M(F,E)$ the completion of $M(F,E)$ which is still an ultra-
metric space. We shall note by capital letters $T, T_1, \cdots, U, U_1, \cdots, V, V_1, \cdots, W, W_1, \cdots$
the elements of $M^\infty(F,E)$ and by lowercase letters $t, t_1, \cdots, u, u_1, \cdots, v, v_1, \cdots, w, w_1, \cdots$
the elements of $M(F,E)$. Also for any subset $A$ of $M^\infty(F,E)$ and for any $\varepsilon>0$ we note
$B_\varepsilon^\circ(A)$ the set $B_\varepsilon(A) \cap M(F,E)$. From corollary 7 we get $B_\varepsilon(A) = \overline{B_\varepsilon^\circ(A)}$.

The mapping $\alpha_n$ from $M(F,E)$ into $M_{\Omega}(F,E)$ can be extended to $M^{\infty}(F,E)$
in the following way. Let $T$ be in $M^{\infty}(F,E)$ ; let $\varepsilon=2^{-n}$ and let $t,t'$ be in $B_{\varepsilon}^{\circ}(T)$.
We have $d(t,t')<\varepsilon$ and thus, from the definition of $d$, $\alpha_n(t) = \alpha_n(t')$. Thus $\alpha_n$
has a common value on the ball $B_{\varepsilon}^{\circ}(T)$ ; we note $\alpha_n(T)$ this common value.

**Lemma 12 :** Let $T$ and $T'$ be in $M^\infty(F,E)$. For any $n \in \mathbb{N}$, $\alpha_n(T) = \alpha_n(T')$ iff $d(T,T') < 2^{-n}$.

**Proof :** Let $\varepsilon=2^{-n}$. If $d(T,T')<\varepsilon$ then $B_{\varepsilon}(T) = B_{\varepsilon}(T')$ and thus $B_{\varepsilon}^{\circ}(T) = B_{\varepsilon}^{\circ}(T')$,
hence $\alpha_{n}(T) = \alpha_{n}(T')$.

If $\alpha_n(T) = \alpha_n(T')$ there exist $t \in B_{\varepsilon}^\circ(T)$, $t' \in B_{\varepsilon}^\circ(T')$ such that $\alpha_n(t) = \alpha_n(T)$, $\alpha_n(T') = \alpha_n(t')$. Thus $d(t,t')<\varepsilon$ and $d(T,T') \le \max(d(t,T),d(t,t'),d(t',T'))<\varepsilon$. $\square$

Since $M^\infty(F,E)$ is a complete metric space we know that it is compact
iff it is *totally bounded*, i.e. if for any $\varepsilon>0$ it is covered by a finite number
of balls $B_\varepsilon(T)$. [8;p 298]. Thus we get :

**Proposition 13 :** If $E$ is a finite set then $M^\infty(F,E)$ is compact.

**Proof :** Let $\varepsilon>0$. From proposition 1, $M = \{B_\varepsilon(T) / T \in M^\infty(F,E)\}$ is a partition of $M^\infty(F,E)$. Let $n$ be an integer such that $2^{-n} \le \varepsilon$ ; the partition $M' = \{B_{2^{-n}}(T) / T \in M^\infty(F,E)\}$ is a subpartition of $M$. From lemma 12 the cardinality of $M'$ is equal to the cardinality of the set $\{\alpha_n(T) / T \in M^\infty(F,E)\}$. Since $F$ and $E$ are finite and since $\text{dp}(\alpha_n(T)) \le n+1$, this set is finite ; hence $M'$ is finite and $M$ is finite. $\square$
Let us remark that the condition "E is finite" cannot be dropped :
let $\varepsilon<1/2 = 2^{-1}$ ; for any $\varepsilon\in E\subset M^\infty(F,E)$ the ball $B_\varepsilon(e)$ contains only $\varepsilon$, because
$\alpha_n(e)=\varepsilon$ for every $n\ge 1$. Thus every covering of $M^\infty(F,E)$ contains the infinite set
of balls $\{B_\varepsilon(e)/\varepsilon\in E\}$.

## 2.2 Infinite trees

We have seen that elements of $M(F,E)\subset M^\infty(F,E)$ were finite trees. We
claim that elements of $M^\infty(F,E)-M(F,E)$ are infinite trees. We want to make pre-
cise this fact by comparing our construction with the classical construction of
infinite trees regarded as ideals of the ordered free F-magma [7].

Let us consider the F-magma $M(F,E\cup\{\Omega\})$. We regard it as an ordered
F-magma, and then we note it $M_\Omega(F,E)$, ordered by the usual syntactic order $<$
defined by

(i) $\forall t \in M_\Omega(F,E), \Omega \prec t$ and $t \prec \Omega$

(ii) $\forall t, t_1, \dots, t_m, t_1', \dots, t_m' \in M_\Omega(F,E), f(t_1', \dots, t_m') \prec t \text{ iff}$
$t = f(t_1, \dots, t_n)$ and $\forall i \in \{1, \dots, m\}, t_i' \prec t_i$.

By completion by ideals, $M_\Omega(F,E)$ can be embedded into the cpo $M_\Omega^\infty(F,E)$
in such a way that every element of $M_\Omega^\infty(F,E)$ is the least upper bound of a direc-
ted subset of $M_\Omega(F,E)$. Let us recall that a subset $D$ of $M_\Omega(F,E)$ is directed iff
$\forall t_1, t_2 \in D, \exists t_3 \in D$ such that $t_1 < t_3$ and $t_2 < t_3$.

We say that an element $T$ of $M_\Omega^\infty(F,E)$ is maximal if $\forall t' \in M_\Omega^\infty(F,E)$, $T \prec T'$ implies $T=T'$.
Considered as ideals of $M_\Omega(F,E)$ the maximal trees are exactly
the maximal ideals.

Now we can compare $M^\infty(F,E)$ and $M_\Omega^\infty(F,E)$.

**Proposition 14** : If $M(F,E)$ is not empty, $M^\infty(F,E)$ is the set of maximal elements of $M_\Omega^\infty(F,E)$.

**Proof** : We can extend the mapping $\alpha_n$, previously defined, to $M_\Omega^\infty(F,E)$. It can be proved casily that $\alpha_n$ becomes an increasing mapping from $M_\Omega^\infty(F,E)$ into itself and that $n \le m$ implies $\alpha_n(t) \le \alpha_m(t) < t$ for any $t$ in $M_\Omega^\infty(F,E)$.
For any $T$ in $M_{\Omega}^{\infty}(F,E)$ let us consider the set $\{\alpha_n(t')/t' \in M_{\Omega}(F,E), t'<T\}$. Since $dp(\alpha_n(t')) \le n+1$ and $\alpha_n(t') < T$, this set is finite. Since $\alpha_n$ is an increasing mapping and since $\{t' \in M_{\Omega}(F,E)/t' < T\}$ is directed, this set is directed. Let $\beta_n(T)$ its lub. Clearly there exists $t' < T$ such that $\beta_n(T) = \alpha_n(t')$. Since $\alpha_n(t') < \alpha_{n+1}(t') < \beta_{n+1}(T)$, the sequence $\beta_n(T)_n$ is increasing. Let us prove that its lub is $T$. We know that $\beta_n(T) < T$, for every $n$. Let $t' < T$; from proposition 10 we get $\alpha_n(t') = t'$ whenever $n \ge dp(t')$, hence $t' = \alpha_n(t') < \beta_n(T)$ and $T < \text{lub } \beta_n(T)$. $n$

Let $T$ be in $M_{\Omega}^{\infty}(F,E)$. The sequence $\alpha_n(T)_n$ is increasing. Let $\hat{T}$ be its lub. We prove that the mapping $T \to \hat{T}$ is a bijection between $M_{\Omega}^{\infty}(F,E)$ and the set of maximal trees of $M_{\Omega}^{\infty}(F,E)$.

First let us prove that $\hat{T}$ is maximal. Let $T'$ in $M_{\Omega}^{\infty}(F,E)$ such that $\hat{T} < T'$. Since $\alpha_n(T) < \hat{T} < T'$, we have $\alpha_n(T) = \alpha_n(\alpha_n(T)) < \beta_n(T')$. But, because of the special form of $\alpha_n(T)$-namely $drl(\Omega, \alpha_n(T)) \ge n$- we have $\beta_n(T') < \alpha_n(T)$, hence $T' = \text{lub}_n \beta_n(T') < \text{lub}_n \alpha_n(T) = \hat{T}$.

Now let $T, T'$ in $M_{\Omega}^{\infty}(F,E)$ such that $\hat{T} = \hat{T}'$. We have just proved that $\beta_n(\hat{T}) = \alpha_n(T)$, whence $\alpha_n(T) = \alpha_n(T')$, and, from lemma 12, $d(T, T') < 2^{-n}$. This being true for every $n$, we get $T = T'$.

At last let $T'$ be a maximal tree of $M_{\Omega}^{\infty}(F,E)$. First we prove that $drl(\Omega, \beta_n(T')) \ge n$. This comes from the fact that if a leaf of $\beta_n(T')$, labelled by $\Omega$, is at a distance less than $n$ from the root of $\beta_n(T')$, this leaf occurs also in $\beta_n(T')$ for any $m \ge n$. Then, by substituting a fixed tree $t \ne \Omega$ to this leaf in every $\beta_n(T')$ we get an increasing sequence $(t_m')_{m \ge n}$ such that $\beta_m(T') < t_m'$. But, since $T'$ is maximal, lub $t_m'=T'$, whence $\alpha_n(t_n') < \beta_n(T')$, which contradicts the definition of $t_n'$. Thus let $t_n$ be the tree of $M(F,E)$ obtained from $\beta_n(T')$ by substituting to $\Omega$ a fixed tree $t$ of $M(F,E)$, that we assumed non empty. Since $drl(\Omega, \beta_n(T')) \ge n$ we have $\alpha_n(t_n^-) = \beta_n(T')$. For any $m \ge n$ we have $\alpha_n(t_n) = \alpha_n(\alpha_m(t_m)) = \alpha_n(\beta_m(T')) < \beta_n(T') = \alpha_n(t_n)$, and, because $drl(\Omega, \alpha_n(t_m)) \ge n$, $\alpha_n(t_n) = \alpha_m(t_n)$. Therefore $(t_n)_n$ is a Cauchy sequence which converges to $T$ and $\alpha_n(t_n) = \alpha_n(T)$ for every $n$. Thus $\hat{T} = \text{lub}_n \alpha_n(T) = \text{lub}_n \alpha_n(t_n) = \text{lub}_n \beta_n(T') = T'$. $\square$
### 3. THE COMPOSITION PRODUCT

On the set $M(F,F)$, the $F$-magma operations, which consist in constructing the tree $f(t_1, \cdots, t_n)$ from the $n$-uple of trees $\langle t_1, \cdots, t_n \rangle$ and the symbol $f$ of arity $n$ can be regarded as special cases of the composition product, which from the tree $t \in M(F,EUX_n)$ and the $n$-uple $\langle t_1, \cdots, t_n \rangle$ gives the tree obtained by substituting $t_i$ to $x_i$ in $t$. This composition product is itself a special case of the "OI-substitution" [9] or "greffe complète" [5], arguments of which are sets of trees and not only single trees.

In this part we extend the notion of OI-substitution to sets of infinite trees. We show that this operation is continuous w.r.t. the Painlevé's limits of sequences of sets. As a special case we will get that $M^\infty(F,E)$ is a continuous $F$-magma w.r.t. the topology induced by the metric $d$ on $M^\infty(F,E)$ [11].

In order to handle trees and sets of trees more easily, here we introduce a little of notions and notations about *magmoïdes* [1,2].

#### 3.1 The magmoïdes $T(\Sigma)$ and $PT(\Sigma)$

Further on we assume that $E$ is a set disjoint from the set $X$ of variables. Let $\Sigma$ be the pair $\langle F,E \rangle$, where $F$ is a graded alphabet. For any integers $p$ and $q$ we note $T(\Sigma)^p_q$ the set $\{q\} \times [M(F,EUX)]^p$ of elements having the form $\langle q; t_1, \cdots, t_p \rangle$ with $t_i \in M(F,EUX_q)$. The set $T(\Sigma)$ is the disjoint union $\bigcup_{p,q} T(\Sigma)^p_q$.

On $T(\Sigma)$ we define a partial product, called *composition product*, which is associative, by :

$$ - \text{ if } u = \langle q; t_1, \cdots, t_p \rangle \in T(\Sigma)^p_q \text{ and} $$

$$ v = \langle r; t'_1, \cdots, t'_q \rangle \in T(\Sigma)^q_r \text{ then} $$

u.v is the element $\langle r; t_1'', \cdots, t_p'' \rangle$ of $T(\Sigma)^p_r$ where $t_i''$ is $t_i[\langle t_1''/x_1, \cdots, t_q''/x_q \rangle] \in M(F,EUX_q)$

Here it is worthwhile to notice that the integer $q$ which occurs as the first component of every element of $T(\Sigma)^p$ has, as only role, to specify the set of variables on which this element depends, and allows a "syntaxic" checking of whether a product of two terms is defined or not.
The magmoid $T(\Sigma)$ has two interesting sub-magmoïds. The first one is $H$, the magmoid of "torsions" : $H_q^P$ is the subset of elements of $T(\Sigma_q)^P$ in the form $\langle q; x_1, \dots, x_p \rangle$ ; each of them can be identified to a mapping $\Theta$ from $\{1, \dots, p\}$ into $\{1, \dots, q\}$. The second one, denoted by $\tilde{T}(\Sigma)$, is such that $\tilde{T}(\Sigma_q)^P$ is the set of elements of $T(\Sigma_q)^P$ which have exactly $x_1, \dots, x_q$ as list . of variables from left to right. We have the following decomposition property [2].

**Lemma 15** : For every element $t$ of $T(\Sigma_q)^P$, there exist $r \ge 0$, $\tilde{t} \in \tilde{T}(\Sigma)^P$, $\Theta \in (H_q^r)^P$ such that $t=\tilde{t}.\Theta$. This decomposition is unique.

Now we define $PT(\Sigma)$ as the disjoint union of the sets $PT(\Sigma_q)^P$ where $PT(\Sigma_q)^P = [P(T(\Sigma_q)^1]^P$. Let us remark that this set $PT(\Sigma_q)^P$, the set of p-uples of subsets of $T(\Sigma_q)^1$, is different of $P([T(\Sigma_q)^1]^P)$, the powerset of the p-fold cartesian product of $T(\Sigma_q)^1$. For the component-wise set-theoretical inclusion every set $PT(\Sigma_q)^P$ is a lattice. Moreover the mapping $\hat{\iota}: T(\Sigma)^P \to PT(\Sigma)^P$ defined by $\hat{\iota}(\langle q; t_1, \dots, t_p \rangle) = \langle \{\langle q; t_1 \rangle\}, \dots, \{\langle q; t_p \rangle\} \rangle$ is injective and thus $T(\Sigma_q)^P$ can be identified to the set of p-uples of singletons of $T(\Sigma_q)^1$.

On $PT(\Sigma_q)^P$ the composition product is defined by :

$$ 
\begin{array}{l}
\text{Let } V = \langle v_1, \dots, v_q \rangle \in PT(\Sigma)^q_r \\
- \text{ if } u = \tilde{u}.\Theta \in T(\Sigma)^1_q \text{ with } \Theta \in (H_q^n)^r \text{ then} \\
\quad \{u\} \cdot V = \{\tilde{u} \cdot \langle r; t_1, \dots, t_n \rangle / \langle r; t_i \rangle \in V_{\Theta(i)}\} \subset T(\Sigma)^1_r; \\
- \text{ if } U \subset T(\Sigma)^1_q \text{ then } U \cdot V = \bigsqcup_{u \in U} \{u\} \cdot V \subset T(\Sigma)^1_r; \\
- \text{ if } U = \langle U_1, \dots, U_p \rangle \in PT(\Sigma)^P_q \text{ then } U \cdot V = \langle U_1 \cdot V, \dots, U_p \cdot V \rangle \in PT(\Sigma)^P_r.
\end{array}
$$

It is clear that this product, which is actually the OI-substitution [5,9], is associative and has the following properties :

$$ 
\begin{aligned}
(U \circled{U'}) \circled{V} &= U \circled{V} \cup U' \circled{V} \\
U \circled{(V \circled{U} V')} &\supset U \circled{V} \cup U \circled{V'}
\end{aligned}
$$

We mention also that for $\Theta \in H_q^P$ and $V = \langle v_1, \dots, v_q \rangle \in PT(\Sigma)^q_r$, $\Theta \circled{V} = \langle V_{\Theta(1)}, \dots, V_{\Theta(p)} \rangle \in PT(\Sigma_q)^P$, identifying $\Theta \in T(\Sigma_q)^P$ and its canonical image $\hat{\Theta}$ in $PT(\Sigma_q)^P$.
## 3.2 The magmoïds $T^\infty(\Sigma)$ and $PT^\infty(\Sigma)$.

In an analogous way we define $T^\infty(\Sigma)$ as being the disjoint union of the sets $T^\infty(\Sigma)_q^P = \{q\} \times [M^\infty(F, EUX_q)]^P$ and $PT^\infty(\Sigma)$ as being the disjoint union of the sets $PT^\infty(\Sigma)_q^P = [P(T^\infty(\Sigma)_q^1)]^P$. The set $T(\Sigma)_q^P$ can be still considered as a subset of $PT^\infty(\Sigma)_q^P$.

Since $T^\infty(\Sigma)_q^P$ is equal to $\{q\} \times [M^\infty(F, EUX_q)]^P$, it is clear that the distance $d$ on $M^\infty(F, EUX_q)$ is also a distance on $T(\Sigma)_q^P$ having exactly the same properties. In particular $T^\infty(\Sigma)_q^1$ is $\{q\} \times M^\infty(F, EUX_q)$, thus we can identify $T(\Sigma)_q^1$ and $M^\infty(F, EUX_q)$; this identification will allow us to write $\alpha_n(t)$ for $t \in T(\Sigma)_q^1$ with the meaning $\alpha_n(t')$ where $t = \langle q; t' \rangle$.

We say that an element $P = \langle P_1, \dots, P_p \rangle$ of $PT^\infty(\Sigma)_q^P$ is *closed* if each $P_i$ is closed. If $P$ is not closed its closure is $\bar{P} = \langle \bar{P}_1, \dots, \bar{P}_n \rangle$. For every $P = \langle P_1, \dots, P_n \rangle$ in $PT^\infty(\Sigma)_q^P$, we set $B_\varepsilon(P) = \langle B_\varepsilon(P_1), \dots, B_\varepsilon(P_p) \rangle \in PT^\infty(\Sigma)_q^P$ and $B_\varepsilon^0(P) = \langle B_\varepsilon^0(P_1), \dots, B_\varepsilon^0(P_p) \rangle \in PT^\infty(\Sigma)_q^P$.

If $(P^{(i)}) = (\langle P_1^{(i)}, \dots, P_p^{(i)} \rangle)$ is a sequence of elements of $PT^\infty(\Sigma)_q^P$, we define, for $LX = \text{LI, LS, Lim}$, $LX(P^{(i)}) = \langle LX(P_1^{(i)}), \dots, LX(P_p^{(i)}) \rangle$.

It follows from those definitions that corollary 7, proposition 8 and 9 hold for $PT^\infty(\Sigma)_q^P$.

Now we define the composition product, denoted by $\circ$, of two closed elements of $PT^\infty(\Sigma)$ : if $P \in PT^\infty(\Sigma)_q^P$ and $Q \in PT^\infty(\Sigma)_r^Q$ are closed, then
$$ P \circ Q = \bigcap_{\varepsilon>0} \overline{B_\varepsilon^0(P) \cdot B_\varepsilon^0(Q)} \quad \text{included in } PT^\infty(\Sigma)_r^P. $$
It should be noted that $P \cdot Q$ is also equal to $\lim_{n \to \infty} \overline{(B_\varepsilon^0(P) \cdot B_\varepsilon^0(Q))}$ because of proposition 9-(iv) and that if $P$ and $Q$ are not closed, then $\bigcap_\varepsilon \overline{B_\varepsilon^0(P) \cdot B_\varepsilon^0(Q)} = \bar{P} \circ \bar{Q}$ because of proposition 2-(ii).

First we define the action of a torsion on $PT^\infty(\Sigma)$.
**Proposition 16** : If $\Theta \in \mathbb{H}_p^n$ and $P = \langle P_1, \cdots, P_p \rangle \in \text{PT}^{\infty}(\Sigma)_q^p$, then
$$ \Theta \odot \bar{P} = \langle \bar{P}_{\Theta(1)}, \cdots, \bar{P}_{\Theta(n)} \rangle. $$

**Proof** : For any $\varepsilon>0$, $B_{\varepsilon}^{\circ}(\Theta)=\Theta$ ; hence $B_{\varepsilon}^{\circ}(\Theta) \cdot B_{\varepsilon}^{\circ}(P) = \langle B_{\varepsilon}^{\circ}(P_{\Theta(1)}), \cdots, B_{\varepsilon}^{\circ}(P_{\Theta(n)}) \rangle$. Thus $\bigcap_{\varepsilon} B_{\varepsilon}^{\circ}(\Theta) \cdot B_{\varepsilon}^{\circ}(P) = \bigcap_{\varepsilon} \langle B_{\varepsilon}^{\circ}(P_{\Theta(1)}), \cdots, B_{\varepsilon}^{\circ}(P_{\Theta(n)}) \rangle = \langle \bar{P}_{\Theta(1)}, \cdots, \bar{P}_{\Theta(n)} \rangle$. $\Box$

**Corollary 17** : If $\Theta \in \mathbb{H}_p^n$ and $(P^{(i)})$ is a sequence of elements of $\text{PT}^{\infty}(\Sigma)_q^p$, then $\Theta \odot \text{LX}(P^{(i)}) = \text{LX}(\Theta \odot P^{(i)})$ for $\text{LX} = \text{LI,LS,Lim.}$

**Proof** : By definition $\text{LX}(P^{(i)}) = \langle \text{LX}(P_1^{(i)}), \cdots, \text{LX}(P_p^{(i)}) \rangle$ and from propositions 8 and 9 this is equal to $\langle \text{LX}(\bar{P}_1^{(i)}), \cdots, \text{LX}(\bar{P}_p^{(i)}) \rangle$. From proposition 16,
$$ \Theta \odot \text{LX}(P^{(i)}) = \langle \text{LX}'(\bar{P}_{\Theta(1)}^{(i)}, \cdots, \text{LX}(\bar{P}_{\Theta(n)}^{(i)})) \rangle = \text{LX}(\langle \bar{P}_1^{(i)}, \cdots, \bar{P}_n^{(i)} \rangle) = \text{LX}(\Theta \odot \bar{P}^{(i)}). \Box $$

Let us notice that in some cases the product $\odot$ in $\text{PT}^{\infty}(\Sigma)$ is the same that the product $\circ$ in $\text{PT}(\Sigma)$.

**Proposition 18** : If $P_1, \cdots, P_n$ are finite subsets of $\text{T}(\Sigma)_q^1$ and if $Q_1, \cdots, Q_q$ are finite subsets of $\text{T}(\Sigma)_r^1$, then $\langle P_1, \cdots, P_n \rangle \odot \langle Q_1, \cdots, Q_q \rangle = \langle P_1, \cdots, P_n \rangle \circ \langle Q_1, \cdots, Q_q \rangle$.

**Proof** : Let $P = \langle P_1, \cdots, P_n \rangle \in \text{PT}(\Sigma)_q^n \subset \text{PT}^{\infty}(\Sigma)_q^n$ and $Q = \langle Q_1, \cdots, Q_q \rangle \in \text{PT}(\Sigma)_r^q \subset \text{PT}^{\infty}(\Sigma)_r^q$. Since the sets $P_i$ and $Q_j$ are finite, they are closed, thus $P$ and $Q$ are closed also. Moreover the set $R = P_1 \cup P_2 \cup \cdots \cup P_n \cup Q_1 \cup Q_2 \cup \cdots \cup Q_q$ is finite ; thus we take $n' = \max\{\text{dp}(t)/r \in \mathbb{R}\}$ and $\varepsilon = 2^{-n'}$. From proposition 10.(i) we get $\alpha_n(t) = t$ for every $t$ in $R$, and from lemma 12 $\text{B}^{\circ}(t) = \text{B}(t) = \{t\}$. Hence $\text{B}^{\circ}(P)=P$, $\text{B}^{\circ}(Q)=Q$ and $P \odot Q = \bigcap_{\varepsilon} \overline{\text{B}_{\varepsilon}^{\circ}(P) \cdot \text{B}_{\varepsilon}^{\circ}(Q)} = \overline{P \cdot Q}$. Since $P \cdot Q = \langle P_1 \cdot Q, \cdots, P_n \cdot Q \rangle$ where each $P_i \cdot Q$ is finite, $P \cdot Q$ is closed and $P \odot Q = \overline{P \cdot Q} = P \cdot Q$. $\Box$
This product ◦ has some properties similar to the ones of the product • in PT(Σ).

**Proposition 19** :

(i) If $P = \langle P_1, \cdots, P_n \rangle \in PT^\infty(\Sigma)^n_q$ and $Q \in PT^\infty(\Sigma)^q_r$ are closed, then $P \circ Q = \langle P_1 \circ Q, \cdots, P_n \circ Q \rangle$

(ii) If $P \subset P'$ and $Q \subset Q'$ then $P \circ Q \subset P' \circ Q'$.

These results are straightforward consequences of the definition of $P \circ Q$.

From the definition of the product in $T(\Sigma)$ we have intuitively $d(u\cdot v, u'\cdot v')<\epsilon$ whenever $d(u, u')<\epsilon$ and $d(v, v')<\epsilon$. We generalize this remark in the following lemma.

**Lemma 20** : $\forall \epsilon>0, \forall \epsilon'>0, \forall u, u' \in T(\Sigma)^1_q$, if $d(u, u')<2^{-n}$ and if $\{u'\} \cdot B^\circ_\epsilon, (Q) \neq \emptyset$ then for any $w$ in $\{u\} \cdot B^\circ_\epsilon(Q)$ there exists $w'$ in $\{u'\} \cdot B^\circ_\epsilon(Q)$ such that $d(w, w')<\max(2^{-n}, \epsilon, \epsilon')$

**Proof** : First, let us remark that, by lemma 12, the condition $d(u, u')<2^{-n}$ is equivalent to $\alpha_n(u) = \alpha_n(u')$.

Now we prove this lemma by induction on $n$.

• If $n=0$, for any $w'$ in $\{u'\} \cdot B^\circ_\epsilon(Q)$, which is not empty, we have $\alpha_0(w) = \alpha_0(w')=\emptyset$, hence $d(w, w')<2^{-0} \le \max(2^{-0}, \epsilon, \epsilon')$.

• If $n \ge 1$ :

- if $u \in EU_F^0$, $\alpha_n(u)=u$, hence $\alpha_n(u')=u$ and $u'=u$. Moreover, in this case, $\{u\} \cdot B^\circ_\epsilon(Q) = \{u'\} \cdot B^\circ_\epsilon(Q) = \{u\}$ thus $w=w'$ and $d(w, w')=0 < \max(2^{-n}, \epsilon, \epsilon')$.

- if $u=x_i \in X_q$, we have still $u'=u$.

But $Q = \langle Q_1, \cdots, Q_n \rangle$ and $\{u\} \cdot B^\circ_\epsilon(Q) = B^\circ_\epsilon(Q_i); \{u'\} \cdot B^\circ_\epsilon(Q) = B^\circ_\epsilon(Q_i)$.

Thus, for any $w \in B^\circ_\epsilon(Q_i)$ there exists $w'' \in Q_i$ such that $d(w, w'')<\epsilon$ ; there exists also $w' \in B^\circ_\epsilon(Q_i)$ such that $d(w', w'')<\epsilon'$. Therefore $d(w, w') \le \max(d(w, w''), d(w'', w')) < \max(\epsilon, \epsilon') \le \max(2^{-n}, \epsilon, \epsilon')$.
- if $u=f(u_1, \dots, u_m)$, then $\alpha_n(u) = \alpha_n(u')$ implies $u'=f(u'_1, \dots, u'_m)$ with
$\alpha_{n-1}(u_i) = \alpha_{n-1}(u'_i)$.

Since $w \in \{u\} \cdot B_{\varepsilon}^{\circ}(Q)$, $w = f(w_1, \dots, w_m)$ with $w_i \in \{u_i\} \cdot B_{\varepsilon}^{\circ}(Q)$. Moreover
$\{u'\} \cdot B_{\varepsilon}^{\circ}(Q) = \{f\} \cdot \{u'_1\} \cdot B_{\varepsilon}^{\circ}(Q), \dots, \{u'_n\} \cdot B_{\varepsilon}^{\circ}(Q)$ and since $\{u'\} \cdot B_{\varepsilon}^{\circ}(Q)$ is not
empty, none of the $\{u'_i\} \cdot B_{\varepsilon}^{\circ}(Q)$ is empty. Thus we can apply the induction hypothesis : there exists $w'_i \in \{u'_i\} \cdot B_{\varepsilon}^{\circ}(Q)$ such that $d(w_i, w'_i) < \max(2^{-(n-1)}, \varepsilon, \varepsilon')$,
hence $d(f(w_1, \dots, w_n), f(w'_1, \dots, w'_n)) < \frac{1}{2} \max(2^{-(n-1)}, \varepsilon, \varepsilon') = \max(2^{-n}, \varepsilon/2, \varepsilon'/2) \le \max(2^{-n}, \varepsilon, \varepsilon')$. But $f(w_1, \dots, w_m) = w$ and $f(w'_1, \dots, w'_m) \in \{f\} \cdot \{u'_1\} \cdot B_{\varepsilon}^{\circ}(Q), \dots, \{u'_m\} \cdot B_{\varepsilon}^{\circ}(Q)$, $w \in \{u'\} \cdot B_{\varepsilon}^{\circ}(Q)$. $\square$

**Proposition 21** : Let $T$ be in $T^{\infty}(\Sigma)_q$ and $Q$ in $PT^{\infty}(\Sigma)_r$ such that $\forall \varepsilon>0$, $B_{\varepsilon}^{\circ}(T) \cdot B_{\varepsilon}^{\circ}(Q) \neq \emptyset$. Then for any $\varepsilon>0$ $B_{\varepsilon}^{\circ}(T) \cdot B_{\varepsilon}^{\circ}(Q) \subset B_{\varepsilon}^{\circ}(\{T\} \odot \overline{Q})$.

**Proof** : Let $\varepsilon>0$. For any $w$ in $B_{\varepsilon}^{\circ}(T) \cdot B_{\varepsilon}^{\circ}(Q)$ there exists $u \in B_{\varepsilon}^{\circ}(T)$ such that $w \in \{u\} \cdot B_{\varepsilon}^{\circ}(Q)$. But, by hypothesis, $B_{\varepsilon/2}^{\circ}(T) \cdot B_{\varepsilon/2}^{\circ}(Q)$ is not empty ; hence there exists $u' \in B_{\varepsilon/2}^{\circ}(T)$ such that $\{u'\} \cdot B_{\varepsilon/2}^{\circ}(Q)$ is not empty. Moreover $d(u,u') \le \max(d(u,T),d(T,u')) < \max(\varepsilon,\varepsilon/2)=\varepsilon$. From the definition of the distance $d$ there exists an integer $n$ such that $d(u,u') < 2^{-n}$ with $2^{-(n+1)} < \varepsilon \le 2^{-n}$. From lemma 20 there exists $w' \in \{u'\} \cdot B_{\varepsilon/2}^{\circ}(Q) \subset B_{\varepsilon/2}^{\circ}(T) \cdot B_{\varepsilon/2}^{\circ}(Q)$ such that $d(w,w') < \max(2^{-n},\varepsilon,\varepsilon/2) = 2^{-n}$ hence $d(w,w') \le 2^{-(n+1)} < \varepsilon$.

Now let $\varepsilon_0>0$ and $w=w_0 \in B_{\varepsilon_0}^{\circ}(T) \cdot B_{\varepsilon_0}^{\circ}(Q)$. By iteratively applying the previous construction we get a sequence $(w_i)_{i \in \mathbb{N}}$ with $w_i \in B_{\varepsilon_i}^{\circ}(T) \cdot B_{\varepsilon_i}^{\circ}(Q)$, where $\varepsilon_i = \varepsilon_0 \cdot 2^{-i}$ and $d(w_i, w_{i+1}) < \varepsilon_i$. From proposition 4 this sequence is a Cauchy sequence and has a limit $W$. Since $(B_{\varepsilon_i}^{\circ}(T) \cdot B_{\varepsilon_i}^{\circ}(Q))_{i \in \mathbb{N}}$ is a decreasing sequence of sets, for every $i \ge 0$, $\{w_j/j \ge i\} \subset B_{\varepsilon_i}^{\circ}(T) \cdot B_{\varepsilon_i}^{\circ}(Q)$. Hence $w \in B_{\varepsilon_i}^{\circ}(T) \cdot P_{\varepsilon_i}^{\circ}(Q)$. Since this holds for every $i \ge 0$, $w \in \bigcap_{i \in \mathbb{N}} B_{\varepsilon_i}^{\circ}(T) \cdot B_{\varepsilon_i}^{\circ}(Q) = \{T\} \odot \overline{Q}$.

From the definition of a convergent sequence there exists an integer $n$ such that $d(W,w_n)<\varepsilon_0$ ; hence $d(w_0,W) \le \max(d(w_0,w_1), d(w_1,w_2), \dots, d(w_n,W)) < \max(\varepsilon_0, \varepsilon_0 \cdot 2^{-1}, \dots, \varepsilon_0 \cdot 2^{-n+1}) = \varepsilon_0$.
Therefore $w_0 \in B_{\varepsilon_0}^{\circ}(W) \subset B_{\varepsilon_0}^{\circ}(\{T\} \odot \overline{Q})$. $\square$
In the following we give a condition equivalent to : $\forall \varepsilon>0, B_{\varepsilon}^{\circ}(T) \cdot B_{\varepsilon}^{\circ}(Q) \neq \emptyset$

**Proposition 22** : Let $T$ be in $T^{\infty}(\Sigma)^1_p$ and $Q$ in $PT^{\infty}(\Sigma)^p_q$. Then $\{T\} \odot \bar{Q} \neq \emptyset$ iff $\forall \varepsilon>0$, $B_{\varepsilon}^{\circ}(T) \cdot B_{\varepsilon}^{\circ}(Q) \neq \emptyset$.

**Proof** : In the proof of proposition 21, we have constructed $w$ in $\{T\} \odot \bar{Q}$, provided that $B_{\varepsilon}^{\circ}(T) \cdot B_{\varepsilon}^{\circ}(Q)$ is not empty for every $\varepsilon>0$.

On the other hand, since $\{T\} \odot \bar{Q} = \bigcap_{\varepsilon} B_{\varepsilon}^{\circ}(T) \cdot B_{\varepsilon}^{\circ}(Q)$, if $\{T\} \odot \bar{Q} \neq \emptyset$ then $B_{\varepsilon}^{\circ}(T) \cdot B_{\varepsilon}^{\circ}(Q)$, is not empty for every $\varepsilon>0$. Therefore $B_{\varepsilon}^{\circ}(T) \cdot B_{\varepsilon}^{\circ}(Q)$ is not empty for every $\varepsilon>0$. $\square$

We have mentioned that $T^{\infty}(\Sigma)$ could be regarded as the set of tuples of singletons. We use lemma 20 to prove that the composition product of two tuples of singletons is a tuple of singletons. Hence the restriction of the composition product on $PT^{\infty}(\Sigma)$ to the set of tuples of singletons can be regarded, via the natural injection $\hat{\i}$ from $T^{\infty}(\Sigma)$ into $PT^{\infty}(\Sigma)$, as a composition product on $T^{\infty}(\Sigma)$.

**Proposition 23** : If $U \in T^{\infty}(\Sigma)^p_q$ and $V \in T^{\infty}(\Sigma)^q_r$, then exists $W \in T^{\infty}(\Sigma)^p_r$ such that $\hat{\i}(U) \odot \hat{\i}(V) = \hat{\i}(W)$.

**Proof** : Let us remark that it is sufficient to prove the result for $p=1$, since if $U = \langle q; T_1, \dots, T_p \rangle$ then $\hat{\i}(U) = \langle \{q; T_1\}, \dots, \{q; T_p\} \rangle$ and $\hat{\i}(U) \odot \hat{\i}(V) = \langle P_1, \dots, P_p \rangle$ with $P_j = \langle q; T_j \rangle \odot \hat{\i}(V) = \hat{\i}(\langle q; T_j \rangle) \odot \hat{\i}(V)$. Thus if $P_j = \hat{\i}(W_j) = \langle r; T'_j \rangle$ then $\langle P_1, \dots, P_p \rangle = \hat{\i}(\langle r; T'_1, \dots, T'_p \rangle)$.

Let $\varepsilon>0$ and let $u' \in B_{\varepsilon}^{\circ}(U)$ and $v' \in B_{\varepsilon}^{\circ}(V)$. We have $B_{\varepsilon}^{\circ}(U) \cdot B_{\varepsilon}^{\circ}(\hat{\i}(V)) = B_{\varepsilon}^{\circ}(u') \cdot B_{\varepsilon}^{\circ}(\hat{\i}(v'))$ and $\{U\} \odot \hat{\i}(V) \subset B_{\varepsilon}^{\circ}(u') \cdot B_{\varepsilon}^{\circ}(\hat{\i}(v'))$. Since, clearly, no components of $B_{\varepsilon}^{\circ}(v')$ is empty, $B_{\varepsilon}^{\circ}(u') \cdot B_{\varepsilon}^{\circ}(\hat{\i}(v'))$ is not empty and we can apply proposition 21, getting $B_{\varepsilon}^{u'}(u') \cdot B_{\varepsilon}^{v'}(\hat{\i}(v')) \subset B_{\varepsilon}^{\circ}(\{u'\} \odot \hat{\i}(v'))$. But from proposition 19 $\{u'\} \odot \hat{\i}(v') = \{u'\} \odot \hat{\i}(v')$ which is equal to $\{u' \cdot v'\}$. Thus we get $\{u\} \odot \hat{\i}(v) \subset B_{\varepsilon}^{\circ}(u' \cdot v') = B_{\varepsilon}^{\circ}(u' \cdot v')$. In other words $\{u\} \odot \hat{\i}(v)$ is included in a ball of raadius $\varepsilon$; this being true for any $\varepsilon$, $\{U\} \odot \hat{\i}(V)$ is a singleton. $\square$
The "left additivity" of the composition product in PT(Σ), i.e. for $P \subset T(\Sigma)_q^1$, $P \cdot Q = \bigcup_{u \in P} \{u\} \cdot Q$, is a property also shared by the composition product in PT<sup>∞</sup>(Σ). In order to prove this result we need a lemma which makes sure that some special sequences in T<sup>∞</sup>(Σ) have accumulation points. Of course this lemma is useless whenever T<sup>∞</sup>(Σ) is compact, it is the case when the set E is finite.

**Lemma 24** : Let $(T_i)_i$ be a sequence in $T^\infty(\Sigma)_q^1$ and let $V$ be in $T^\infty(\Sigma)_r^1$. If for every $n \ge 0$ there exists $t_n \in B_{2^{-n}}^\circ(T_n)$, $A_n \in PT(\Sigma)_r^q$ and $u_n \in \{t_n\}$. $A_n$ such that $d(v, u_n) < 2^{-n}$ then the sequence $(T_i)_i$ has an accumulation point.

**Proof** : In this proof we identify $T(\Sigma)_m^1$ with $M(F, EU X_m)$.

For any integer $n$ and for any $t \in T(\Sigma)_r^1$ we note $\Delta_n(t)$ the set of finite trees obtained by substituting variables in $X_q$ to subtrees in $\alpha_n(t)$. Formally $\Delta_n$ is defined by induction :

$$ \bullet \quad \Delta_0(t) = \{\Omega\} = \{\alpha_0(t)\} $$

• for $n>0$

$$ - \text{ if } t \in EU X_r u F_0, \Delta_n(t) = X_q u(\{t\} \cap (EU F_0)) $$

$$ - \text{ if } t = f(t_1, \cdots, t_n), \Delta_n(t) = X_q u\{f(t'_1, \cdots, t'_n)/t'_i \in \Delta_{n-1}(t_i)\} $$

It can be easily proved by induction that if $u \in t \cdot A$ then $\alpha_n(t) \in \Delta_n(u)$.

From this and from the hypothesis of the lemma we get that for any $n \ge 0$, any $m \ge n$, $\alpha_n(t_n) \in \Delta_n(u_m)$. But $d(u_m, u_n) \le \max(d(u_m, V), d(V, u_n)) < 2^{-n}$; hence $\alpha_n(u_m) = \alpha_n(u_n)$; therefore $\Delta_n(u_n) = \Delta_n(u_m)$ and $\alpha_n(t_m) \in \Delta_n(u_n)$.

Since the set $\Delta_n(u_n)$ is finite, for every infinite subset $I$ of $N$ there exists an integer $i \ge n$ such that the set $\{\ell_n\}_n$ of integers and the auxiliary sequence $(I_n)_n$ of infinite subsets of $N$ by

$$ \bullet \quad \ell_0 = 0, I_0 = N $$

• $I_{p+1}$ is an infinite subset of $I_p$ such that $\forall i, j \in I_{p+1}$

$\alpha_{p+1}(t_i) = \alpha_{p+1}(t_j)$ and $\ell_{p+1}$ is the least integer in $I_{p+1}$ which is greater than $\max(p+1, \ell_p)$.
From this definition we get that for every $p \ge 0$ $\alpha_p(t_\ell) = \alpha_p(t_\ell)$ and thus $d(t_\ell, t_\ell) < 2^{-p}$. Hence $d(T_\ell, T_\ell) \le \max(d(T_\ell, t_\ell), d(t_\ell, t_\ell))$, $d(t_\ell, T_\ell) < \max(2^{-p}, 2^{-p}, 2^{-p+1}) = 2^{-p}$. Therefore the subsequence $(T_\ell)_p$ of $(T_n)_n$ is a Cauchy sequence and its limit is an accumulation point of $(T_n)_n$. $\square$

**Proposition 25** : Let P in $PT^\infty(\Sigma)_q^1$ and Q in $PT^\infty(\Sigma)_r^q$ be two closed elements. Then $P \otimes Q = \bigcup_{T \in P} \{T\} \otimes Q$.

**Proof** : It is clear from proposition 19-(ii) that $\bigcup_{T \in P} \{T\} \otimes Q \subset P \otimes Q$. Let us prove the reverse inclusion.

Let $U \in P \cdot Q = \bigcap_{\epsilon} \overline{B_{\epsilon}^\circ(P) \cdot B_{\epsilon}^\circ(Q)}$. For every $n \ge 0$ there exists $u_n \in B_{2^{-n}}^\circ(P) \cdot B_{2^{-n}}^\circ(Q)$ such that $d(U, u_n) < 2^{-n}$. But if $u_n \in B_{2^{-n}}^\circ(P) \cdot B_{2^{-n}}^\circ(Q)$, there exists $T_n \in P$, $t_n \in B_{2^{-n}}^\circ(T_n)$ such that $u_n \in \{t_n\} \cdot B_{2^{-n}}^\circ(Q)$.

By applying the previous lemma we get that the sequence $(T_n)_n$ has an accumulation point T which is in the closed set P.

Thus for every $\epsilon>0$ there exists $n$ large enough such that $2^{-n}<\epsilon$ and $d(T_n,T)<\epsilon$; hence $d(t_n,T)<\epsilon$ and $B_{2^{-n}}^\circ(t_n) \subset B_\epsilon^\circ(t_n) = B_\epsilon^\circ(T)$. Therefore $u_n \in B^\circ(T) \cdot B_{2^{-n}}^\circ(Q) \subset B_\epsilon^\circ(T) \cdot B_\epsilon^\circ(Q)$. Since this is true for an infinite number of $n$, the limit U of the sequence $(u_n)_n$ is in $\overline{B_\epsilon^\circ(T) \cdot B_\epsilon^\circ(Q)}$. Thus $U \in \bigcap_{\epsilon} \overline{B_\epsilon^\circ(T) \cdot B_\epsilon^\circ(Q)} = \{T\} \otimes Q$. $\square$

Before proving the associativity of this composition product, we need some continuity properties of it.
### 3.3 Continuity of the composition product

In this section we shall prove the continuity of the composition product in $PT^\infty(\Sigma)$ with respect to P-convergence. Let us remark that, because of propositions 23 and 9-(i), we shall get, by the way, the continuity of the composition product in the magmoïd $T^\infty(\Sigma)$ and more particularly that $M^\infty(F,F)$ is a continuous F-magma.

First let us show by an example that in some special cases this product is not continuous.

**Example 3.** Let $F = \{f, a\}$ with $\rho(f)=1$ and $\rho(a)=0$.

For every $n \ge 0$ let $t_n = \langle 1; f^n(x_1) \rangle \in T(F)_1^1$. Clearly the sequence $(t_n)_n$ converges to $T = \langle 1; f^\omega \rangle \in T^\infty(F)_1^1$; thus the sequence $(\{t_n\})_n$ P-converges to $\{T\}$.

Now let us consider $\emptyset$ as an element of $PT(F)_0^1 \subset PT^\infty(F)_0^1$. We get $\{t_n\} \circ \emptyset = \emptyset$, thus $(\{t_n\}) \circ \emptyset)_n$ P-converges to $\emptyset$. But $\{T\} \circ \emptyset \ne \emptyset$ as proved now.

By definition $\{T\} \circ \emptyset = \bigcap_n \overline{B_2^\circ(T) \cdot \emptyset}$. But $\langle 1; f^n(a) \rangle \in B_2^\circ(T)$; hence $\langle 0; f^n(a) \rangle = \langle 1; f^n(a) \rangle \cdot \emptyset \in B_2^\circ(T) \cdot \emptyset$. We deduce easily that $\langle 0; f^\omega \rangle = \lim_{n} \langle 0; f^n(a) \rangle$ belongs to $\{T\} \circ \emptyset$.

We get the same result if we replace $\{t_n\}$ by $P_n = \{t_i | i \le n\}$ : the sequence $P_n$ P-converges to $P = \bigcup_n P_n = \{t_i | i \ge 0\} \cup \{T\}$, but $P_n \circ \emptyset = \emptyset$ and $P \circ \emptyset \ne \emptyset$.

Thus we have to find a condition on two sequences $(P^{(i)})_{i \in N}$ and $(Q^{(i)})_{i \in N}$ sufficient to be sure that $\lim_{i} (P^{(i)} \circ Q^{(i)}) = \lim_{i} (P^{(i)} \circ \lim_{i} Q^{(i)})$. An suggested by the previous example this condition deals with the fact that $\{T\} \circ Q$ can be empty.

Let $P$ be in $PT^\infty(\Sigma)_q^1$ and $Q$ be closed in $PT^\infty(\Sigma)_r^q$. We denote $P/Q$ the set $\{T \in P / T \circ Q \ne \emptyset\}$. This definition is extended componentwise to $P$ in $PT^\infty(\Sigma)_q^P$.

**Lemma 26** : For any closed $P$ in $PT^\infty(\Sigma)_q^P$ and any closed $Q$ in $PT^\infty(\Sigma)_r^q$, $P/Q$ is closed.
**Proof :** It is sufficient to prove this result for $p=1$.

Let $T$ be in $\overline{P/Q}$. For every $\varepsilon>0$ there exists $T_\varepsilon \in P/Q \cap B_\varepsilon(T)$.
Since $T_\varepsilon \in P/Q$, $\{T\} \odot Q$ is not empty and from proposition 22 $B_\varepsilon^\circ(T_\varepsilon) \odot B_\varepsilon^\circ(Q) \neq \emptyset$.
But $B_\varepsilon^\circ(T_\varepsilon) = B_\varepsilon^\circ(T)$, thus $B_\varepsilon^\circ(T) \cdot B_\varepsilon^\circ(Q) \neq \emptyset$. This being true for every $\varepsilon>0$, we get,
from proposition 22, $\{T\} \odot \emptyset$.

Since $T$ is clearly an accumulation point of the set $\{T_\varepsilon / \varepsilon > 0\} \subset P/Q \subset P$,
and since $P$ is closed, $T \in P$ and thus $T \in P/Q$. $\square$

**Lemma 27 :** Let $P$ and $Q$ be closed elements of $PT^\infty(\Sigma)^p_q$ and $PT^\infty(\Sigma)^q_r$. Then
$P \odot Q = (P/Q) \odot Q$.

**Proof :** As usual we consider only the case $p=1$.

From proposition 25 we get : $P \odot Q = \bigcup \{\{T\} \odot Q/T \in P\} = \bigcup \{\{T\} \odot Q/T \in P, \{T\} \odot Q \neq \emptyset\} = (P/Q) \odot Q$. $\square$

Let now $\hat{P} = (P^{(i)})_i$ and $\hat{Q} = (Q^{(i)})_i$ be two sequences which
$P$-converge respectively to $P$ and $Q$. We say that $\hat{P}$ is acceptable with respect to
$\hat{Q}$ if $P/Q \in \text{LI}(\overline{P^{(i)}/Q^{(i)}})$

We can prove now the continuity of the composition product for
acceptable sequences.

**Theorem 28 :** Let $\hat{P} = (P^{(i)})_i$ be a sequence in $PT^\infty(\Sigma)^p_q$ and $\hat{Q} = (Q^{(i)})_i$ be
sequences in $PT^\infty(\Sigma)^q_r$ which $P$-converge respectively to $P$ and $Q$. If $\hat{P}$ is accep-
table w.r.t. $\hat{Q}$ then $P \odot Q = \text{Lim}(\overline{P^{(i)} \odot Q^{(i)}})$.

**Proof :** As usual we can assume that $p=1$. We can also assume that $P^{(i)}$ are
closed since this does not change neither the $P$-limits $\hat{P}$ and $\hat{Q}$, nor accep-
tability of $\hat{P}$ w.r.t. $\hat{Q}$.

Since $\text{LI}(P^{(i)} \odot Q^{(i)}) \subset \text{LS}(P^{(i)} \odot Q^{(i)})$, $\text{LI}(P^{(i)}) = \text{LS}(\text{R}^{(i)}) = P$
and $\text{LI}(Q^{(i)}) = \text{LS}(Q^{(i)}) = Q$, we have only to prove

(i) $\text{LI}(P^{(i)}) \odot \text{LI}(Q^{(i)}) \subset \text{LI}(P^{(i)} \odot Q^{(i)})$ and

(ii) $\text{LS}(P^{(i)} \odot Q^{(i)}) \subset \text{LS}(P^{(i)} \odot \text{LS}(Q^{(i)}))$.
**Proof of (i)** : Let U be in P ⊙ Q. From proposition 25 there exists T in P such that U ∈ {T} ⊙ Q and thus T ∈ P/Q.

Let ε>0. There exists $u_ε ∈ B_ε^°(T) ⋅ B_ε^°(Q)$ such that $d(U, u_ε)<ε$ ; thus there exists $t_ε ∈ B_ε^°(T)$ such that $u_ε ∈ \{t_ε\} ⋅ B_ε^°(Q)$. Since $T ∈ P/Q$ and since $\hat{P}$ is acceptable w.r.t. $\hat{Q}$, $T ∈ LI(P^{(i)}/Q^{(i)})$. By definition of LI there exists $n$ such that $i \ge n$ implies $B_ε(T) \cap (P^{(i)}/Q^{(i)}) \ne \emptyset$ ; thus there exists $T_i ∈ P^{(i)}/Q^{(i)}$ such that $d(T, T_i)<ε$ and thus $d(t_ε, T_i)<ε$.

We can write $t_ε = \tilde{t}_ε ⋅ θ_ε$, so that $u_ε ∈ \{\tilde{t}_ε\} ⋅ θ_ε ⋅ B_ε^°(Q) = \{\tilde{t}_ε\} ⋅ B_ε^°(θ_ε ⊙ Q)$ and thus $u_ε = \tilde{t}_ε ⋅ w_ε$ with $w_ε ∈ B_ε^°(θ_ε ⊙ Q)$. Therefore there exists $W_ε ∈ θ_ε ⊙ Q$ such that $d(w_ε, W_ε)<ε$. Since $θ_ε ⊙ Q = θ_ε ⊙ LI(Q^{(i)}) = LI(θ_ε ⊙ Q^{(i)})$ there exists $n'$ such that $i \ge n'$ implies $B_ε(W_ε) \cap (θ_ε ⊙ Q^{(i)}) \ne \emptyset$ and thus there exists $V_i$ in $θ_ε ⊙ Q^{(i)}$ such that $d(v_i, w_ε)<ε$.

Thus we have $u_ε = \tilde{t}_ε ⋅ w_ε$ with $\tilde{t}_ε ⋅ θ_ε ∈ B_ε^°(T_i)$ and $w_ε ∈ B_ε^°(V_i) ⊂ B_ε^°(θ_ε ⊙ Q^{(i)})$ and hence $u_ε ∈ B_ε^°(T_i) ⋅ B_ε^°(Q^{(i)})$ for every $i \ge \max(n, n')$. But, since $T_i ∈ P^{(i)}/Q^{(i)}$, we have $\{T_i\} ⊙ Q^{(i)} \ne \emptyset$ and, by propositions 22 and 21, $B_ε^°(T_i) ⋅ B_ε^°(Q^{(i)}) ⊂ B_ε^°(P^{(i)} ⊙ Q^{(i)})$. Since $d(U, u_ε)<ε$, we have $U ∈ B_ε(P^{(i)} ⊙ Q^{(i)})$ and thus there exists $U_i$ in $P^{(i)} ⊙ Q^{(i)}$ such that $d(U, U_i)<ε$, hence $B_ε(U) \cap B_ε(P^{(i)} ⊙ Q^{(i)})$ is not empty for every $i \ge \max(n, n')$.

As this holds for every $ε>0$, we get $U ∈ LI(P^{(i)} ⊙ Q^{(i)})$.

**Proof of (ii)** : Let U be in $LS(P^{(i)} ⊙ Q^{(i)})$. By definition of LS, for any $n>0$ there exists $i \ge n$ such that $B_{2-n}(U) \cap (P^{(i)} ⊙ Q^{(i)}) \ne \emptyset$. Thus there exists

$U_n ∈ P^{(i_n)} ⊙ Q^{(i_n)}$ such that $d(U, U_n) < 2^{-n}$; also there exists $T_n ∈ P^{(i_n)}$ such that $U_n ∈ \{T_n\} ⋅ Q^{(i_n)}$. From this we get that there exists $t_n ∈ B_{2-n}^°(T_n)$, $u_n ∈ \{t_n\} ⋅ B_{2-n}^°(Q^{(i_n)})$ such that $d(u_n, U_n) < 2^{-n}$. We can apply lemma 24 : the
sequence $(T_n)_n$ has an accumulation point $T$, which is in $LS(P^{(i)})$ since every $T_j$ is in $P^{(i_j)}$.

It follows that there exists a subsequence $(T_{j_n})$ of $(T_n)_n$ such that $d(T,T_{j_n})<2^{-n}$. Then we have $U_n \in \{T_{j_n}\} \bigcirc Q^{(i_j)}$ and $d(U_n,U_{j_n})<2^{-j_n} \le 2^{-n}$.
Since $(Q^{(i_j)})_n$ is a subsequence of $(Q^{(i)})_i$, $LS(Q^{(i_j)})_i \subset LS(Q^{(i)})_i$ and in order to prove that $U \in LS(P^{(i)}) \bigcirc LS(Q^{(i)})$, it is sufficient to prove that $U \in \{T\} \bigcirc LS(Q^{(n)})_n$. This is a direct consequence of the following lemma.

**Lemma 29** : Let $(T_n)_n$ be a sequence in $T^\infty(\Sigma)_q$ and $T \in T^\infty(\Sigma)_q$ such that $\forall n \ge 0$, $d(T,T_n)<2^{-n}$. Let $(Q^{(n)})_n$ be a sequence in $PT^\infty(\Sigma)_r^q$. Let $(U_n)_n$ be a sequence in $T^\infty(\Sigma)_r^l$ and $U$ in $T^\infty(\Sigma)_r^l$ such that $\forall n \ge 0$, $U_n \in \{T_n\} \bigcirc Q^{(n)}$ and $d(U,U_n)<2^{-n}$. Then $U \in \{T\} \bigcirc LS(Q^{(n)})_n$.

**Proof** : In this proof we need the assumption that $M(F,E)$ is not empty, that is $F_0 \cup E$ contains at least one symbol, noted $\bar{\Omega}$. We note $\bar{\alpha}_n(T)$ the tree obtained by substituting $\bar{\Omega}$ to $\Omega$ in $\alpha_n(T)$. It is clear that $d(T,T')<2^{-n}$ implies $\bar{\alpha}_n(T) = \bar{\alpha}_n(T')$ and that $\alpha_n(\bar{\alpha}_n(T)) = \alpha_n(T)$, hence $d(T,\bar{\alpha}_n(T))<2^{-n}$.

For any $n \ge 0$ there exist $t_n \in B^\circ_{2^{-n}(T_n)}$ and $u_n \in \{t_n\} \cdot B^\circ_{2^{-n}(Q^{(n)})}$ such that $d(U_n,u_n)<2^{-n}$, hence $d(U,u_n)<2^{-n}$.

Let $v_n = \bar{\alpha}_n(t_n) = \bar{\alpha}_n(T_n) = \bar{\alpha}_n(T)$; it can be proved easily that by replacing some subtrees in $u_n$ by $\bar{\Omega}$, we obtain $u'_n$ such that $u'_n \in \{v_n\} \cdot B^\circ_{2^{-n}(Q^{(n)})}$ and $d(u_n,u'_n)<2^{-n}$. Hence $d(T,v_n)<2^{-n}$ and $d(U,u'_n)<2^{-n}$.
We can write $v_n = \tilde{v}_n \cdot \theta_n$ with $\tilde{v}_n \in T(\Sigma)_{r_n}^1$ and $\theta_n \in \mathfrak{H}_q^r$. Since $d(t_n, t_{n+1}) \le \max(d(t_n, T), d(T, t_{n+1})) < 2^{-n}$, we have $v_n = \bar{a}_n(t_n) = \bar{a}_n(t_{n+1}) = \bar{a}_n(\bar{a}_{n+1}(t_{n+1})) = \bar{a}_n(v_{n+1})$ and from the definition of $\bar{a}_n$ there exists an increasing mapping $\gamma_n \in \mathfrak{H}_{r_{n+1}}^r$ such that $\theta_n = \gamma_n \cdot \theta_{n+1}$. For every $m \le r_n$ we note $l(n,m)$ the length of the path from the root of $v_n$ to its unique leaf labelled by $x_m$. It is clear that $l(n,m) \le n$. Moreover $l(n+1, \gamma_n(m)) = l(n,m)$.

Since $u'_n \in \{v_n\} \cdot B_2^{\circ-n}(Q^{(n)})$, $u'_n = \tilde{v}_n \cdot \langle w_1^{(n)}, \dots, w_{r_n}^{(n)} \rangle$ with $w_i^{(n)} \in B_2^{\circ-n}(Q_{\theta_n}^{(n)})$. Since $d(u'_n, u'_{n+i}) < 2^{-n}$ we get (*) for $i \le r_n$, $d(w_i^{(n)}, w_{\gamma_n(i)}^{(n+1)}) < 2^{-n+l(n,i)}$

For $n>0$ and $i \le r_n$ let us consider the sequence $(s_j)_j$ of integers defined by: $s_0 = i$; $s_{j+1} = \gamma_{n+j}(s_j)$. We have $\theta_{n+j+1}(s_{j+1}) = \theta_{n+j+1}(\gamma_{n+j}(s_j)) = \theta_{n+j}(s_j)$; thus for any $j \ge 0$, $\theta_{n+j}(s_j) = \theta_n(i)$. We have also $l(n+j+1, s_{j+1}) = l(n+j+1, \gamma_{n+j}(s_j)) = l(n+j, s_j)$, thus for any $j \ge 0$, $l(n+j, s_j) = l(n,i)$.

Therefore, from (*) we get $d(w_{s_j}^{(n+j)}, w_{s_{j+1}}^{(n+j+1)}) < 2^{-(n+j)+l(n,i)}$.
Thus the sequence $(w_{s_j}^{(n+j)})_j$ converges to $W_i^{(n)}$. And since
$w_i^{(n+j)} \in B_2^{\circ-(n+j)}(Q_{\theta_{n+j}}^{(n+j)}) = B_2^{\circ-(n+j)}(Q_{\theta_n}^{(n+j)})$, it is easy to prove that
$W_i^{(n)} \in \text{LS}(Q_{\theta_n}^{(j)})_j = Q_{\theta_n}^{(n)}(i)$ where $Q = \langle Q_1, \dots, Q_q \rangle = \text{LS}(Q^{(j)})_j$.

Let us remark that, from the definition of $W_i^{(n)}$, we get $W_i^{(n)} = W_{\gamma_n(i)}^{(n+1)}$.
Now let $w_i^{(n)}$ in $T(\Sigma)_q^1$ such that $d(w_i^{(n)}, w_i^{(n)}) < 2^{-n}$; we have
$s(w_i^{(n)}, w_i^{(n)}) \le \max(d(w_i^{(n)}, W_i^{(n)}), d(W_i^{(n)}, w_i^{(n)})) < \max(2^{-n}, 2^{-n+l(n,i)}) = 2^{-n+l(n,i)}$ and thus $d(u'_n, \tilde{v}_n \cdot w_i^{(n)}, \dots, w_{r_n}^{(n)}) < 2^{-n}$.
But $u_n'' = \tilde{v}_n \cdot \langle w_1^{(n)}, \dots, w_n^{(n)} \rangle \in \{\tilde{v}_n\} \cdot \langle B_{2-n}^\circ (Q_{\Theta_n}(1)), \dots, B_{2-n}^\circ (Q_{\Theta_n}(r_n)) \rangle =$
$= \{\tilde{v}_n\} \cdot \Theta_n \cdot B_{2-n}^\circ (Q) = \{v_n\} \cdot B_{2-n}^\circ (Q).$ But $v_n = \bar{\alpha}_n(T)$, thus $v_n \in B_{2-n}^\circ(T)$ and
$u_n'' \in B_{2-n}^\circ(T) \cdot B_{2-n}^\circ(Q)$. Since $d(U, u_n'') \le \max(d(U, u_n'), d(u_n', u_n'')) < 2^{-n}$, we get
$U \in \bigcap_n B_{2-n}^\circ(T) \cdot B_{2-n}^\circ(Q) = \{T\} \circ Q$. $\square$

We give now a sufficient condition for a sequence being acceptable w.r.t. another one

**Lemma 30** : If $\hat{P}$ and $\hat{Q}$ are decreasing sequences then $\hat{P}$ is acceptable w.r.t. $\hat{Q}$

**Proof** : We can assume without less of generality that $\hat{P}$ is a sequence in $\hat{P}^{\infty}(\Sigma)_q$.

First we prove that if $P \subset P'$ and $Q \subset Q'$ then $\bar{P}/\bar{Q} \subset \bar{P}'/\bar{Q}'$. Let $T$ be in $P/Q \subset P \subset P'$; then $\{T\} \odot Q \subset \{T\} \odot Q'$ is not empty, hence $T \in P'/Q'$.

Let $P = \lim_{i} \overline{P^{(i)}}$ and $Q = \lim_{i} \overline{Q^{(i)}}$. Since $(P^{(i)})_i$ and $(Q^{(i)})_i$ are decreasing sequences $(P^{(i)}/Q^{(i)})_i$ is also a decreasing sequence ; moreover for any $P \subset \overline{P^{(i)}}$, $Q \subset \overline{Q^{(i)}}$ and thus $P/Q \subset \overline{P^{(i)}}/\overline{Q^{(i)}}$. It follows that
$P/Q \subset \bigcap_i \overline{P^{(i)}/Q^{(i)}} = \lim_{i} \overline{P^{(i)}/Q^{(i)}}$. $\square$

Clearly $\hat{P}$ is also acceptable w.r.t. $\hat{Q}$ if every component $Q_i^{(i)}$ of every $Q^{(i)}$ is non empty since in this case it is obvious that $\overline{P^{(i)}/Q^{(i)}} = \overline{P^{(i)}}$.
### 3.4 Associativity of the composition product

In this section we note $C_n(P)$ the set $\mathbb{R}_2^{\circ-n}(P)$.

**Lemma 31** : Let $t \in T(\Sigma)_p^1$, $Q \in PT^\infty(\Sigma)_q^p$ and $R \in PT(\Sigma)_r^q$. Let $n>0$ and let $u \in \{t\} \cdot C_n(Q)$. Let $k>0$; if there exists $u' \in C_{2kn}(U)$ such that $\{u'\} \cdot R \neq \emptyset$ then there exists $u'' \in C_n(t) \cdot C_n(Q)$ such that $d(u',u'') < 2^{-kn}$ and $\{u''\} \cdot R \neq \emptyset$.

*Proof* : As in lemma 29 we assume that $M(F,E) \neq \emptyset$ and we define $\bar{\alpha}_n(t)$.

Let $t = \tilde{t} \cdot \theta$, with $\theta \in \mathcal{H}_p^\ell$. Then $u = \tilde{t} \cdot v$ with $v \in \theta \cdot C_n(Q)$. We put $t' = \bar{\alpha}_{kn}(t)$ and $v' = \bar{\alpha}_{kn}(v)$. It is clear that $d(t,t') < 2^{-kn} \cdot 2^{-n}$ and $d(v,v') < 2^{-kn} < 2^{-n}$. Moreover $t' = \tilde{t}' \cdot \theta'$ with $\theta' \in \mathcal{H}_p^{\ell'}$ and there exists an increasing mapping $\gamma \in \mathcal{H}_p^{\ell'}$ such that $\theta' = \gamma \cdot \theta$.

Let $u'' = \tilde{t}' \cdot \gamma \cdot v'$. Since $v' \in \theta \cdot C_n(Q)$, $\gamma \cdot v' \in \gamma \cdot \theta \cdot C_n(Q) = \theta' \cdot C_n(Q)$, hence $u'' \in \{\tilde{t}'\} \cdot \theta' \cdot C_n(Q) = \{t'\} \cdot C_n(Q) \subset C_n(t) C_n(Q)$. Moreover it can be easily proved by structural induction on $t'$ $d(u,u'') < 2^{-kn}$, hence $d(u',u'') < 2^{-kn}$.

In order to prove that $\{u''\} \cdot R$ is not empty, it is sufficient to prove that every variable in $u''$ occurs in $u'$, since $\{u'\} \cdot R \neq \emptyset$. From the definition of $u''$ it can be proved easily by induction that every variable in $u''$ occurs in $\bar{\alpha}_{2kn}(u)$. But since $d(u,u') < 2^{-2kn}$, $\bar{\alpha}_{2kn}(u) = \bar{\alpha}_{2kn}(u')$ and thus all the variables in $\bar{\alpha}_{2kn}(u)$ are in $u'$. $\square$

**Proposition 32** : The composition product in $PT^\infty(\Sigma)$ is associative.

*Proof* : Let $P \in PT^\infty(\Sigma)_q^p$, $Q \in PT^\infty(\Sigma)_r^q$ and $R \in PT^\infty(\Sigma)_s^r$, be closed sets. As usual we can assume that $p=1$.

Since $(C_n(P) \cdot C_n(Q))_n$ and $(C_n(R))_n$ are decreasing sequences, by lemma 30 we can apply theorem 28 and we get
$$ (P \circled{Q}) \circled{R} = \operatorname*{Lim}_{n} (C_n(P) \cdot C_n(Q)) \circled{Lim}_{n} (C_n(R)) = \operatorname*{Lim}_{n} (C_n(P) \cdot C_n(Q) \circled{C_n(R)}). $$
In the same way we get $P \circ (Q \circ R) = \lim_n \overline{C_n(P) \circ \overline{C_n(Q) \circ C_n(R)}}$.

Thus we have to prove : $\forall n>0$.

$$ \overline{C_n(P) \circ C_n(Q) \circ \overline{C_n(R)}} = \overline{C_n(P) \circ \overline{C_n(Q) \circ C_n(R)}}. $$

But for any $G$ and $H$ in $PT(\Sigma)$ we have $G \subset B_{\Sigma}^{\circ}(G)$ and $H \subset B_{\Sigma}^{\circ}(H)$), hence $G \cdot H \subset B_{\Sigma}^{\circ}(G) \cdot B_{\Sigma}^{\circ}(H)$ for every $\epsilon>0$. Therefore $\overline{G \cdot H} \subset \bigcap_{\epsilon} \overline{B_{\Sigma}^{\circ}(G) \cdot B_{\Sigma}^{\circ}(H)} = \overline{G} \circ \overline{H}$.

It follows that

$$ \overline{(C_n(P) \cdot C_n(Q) \cdot C_n(R))} \subset \overline{C_n(P) \cdot C_n(Q) \circ \overline{C_n(R)}} \text{ and} $$

$$ \overline{C_n(P) \cdot (C_n(Q) \cdot C_n(R))} \subset \overline{C_n(P) \circ C_n(Q) \cdot C_n(R)}. $$

But the composition product in $PT(\Sigma)$ is associative. Therefore, to complete the proof, we have to prove the two inclusions :

$$ (i) \quad \overline{C_n(P) \circ \overline{C_n(Q) \cdot C_n(R)}} \subset \overline{C_n(P) \cdot C_n(Q) \cdot C_n(R)} \quad \text{and} $$

$$ (ii) \quad \overline{C_n(P) \cdot C_n(Q) \circ \overline{C_n(R)}} \subset \overline{C_n(P) \cdot C_n(Q) \cdot C_n(R)}. $$

**Proof (i)** : Let $T$ be in $\overline{C_n(P) \circ \overline{C_n(Q) \cdot C_n(R)}}$. There exists $U$ in $\overline{C_n(P)}$ such that $T \in \{U\} \circ \overline{C_n(Q) \cdot C_n(R)}$.

Let $\epsilon < 2^{-n}$; there exist $u_{\epsilon} \in B_{\Sigma}^{\circ}(U)$, $t_{\epsilon} \in \{u_{\epsilon}\} \circ B_{\Sigma}^{\circ}(\overline{C_n(Q) \cdot C_n(R)})$ such that $d(T, t_{\epsilon}) < \epsilon$. But $u_{\epsilon} = \tilde{u}_{\epsilon} \cdot \theta_{\epsilon}$ and thus $t_{\epsilon} = \tilde{u}_{\epsilon} \cdot v$ with $v \in \theta_{\epsilon} \circ B_{\Sigma}^{\circ}(\overline{C_n(Q) \cdot C_n(R)}) = \theta_{\epsilon} \circ B_{\Sigma}^{\circ}(\overline{C_n(Q) \cdot C_n(R)}) = B_{\Sigma}^{\circ}(\theta_{\epsilon} \circ C_n(Q) \cdot C_n(R))$. Therefore there exists $v' \in \theta_{\epsilon} \circ C_n(Q) \cdot C_n(R)$ such that $d(v, v') < \epsilon$ and $t'_{\epsilon} = \tilde{u}_{\epsilon} \cdot v' \in \{u_{\epsilon}\} \circ C_n(Q) \cdot C_n(R)$. It can be proved by induction on $u_{\epsilon}$ that $d(t_{\epsilon}, t'_{\epsilon}) < \epsilon$ hence $d(T, t'_{\epsilon}) < \epsilon$ and $T \in B_{\Sigma}^{\circ}(\{u_{\epsilon}\} \circ C_n(Q) \cdot C_n(R))$. Since $d(U, u_{\epsilon}) < \epsilon < 2^{-n}$, $u_{\epsilon} \in C_n(U) \subset C_n(\overline{C_n(P)}) = C_n(\overline{C_n(P)}) = C_n(P)$, hence $T \in B_{\Sigma}^{\circ}(C_n(P) \cdot C_n(Q) \cdot C_n(R))$. This being true for every $\epsilon < 2^{-n}$, $T \in \overline{C_n(P) \cdot C_n(Q) \cdot C_n(R)}$.
**Proof (ii)** : Let $T \in \overline{C_n(P) \cdot C_n(Q)} \circ \overline{C_n(R)}$. There exists $U \in \overline{C_n(P) \cdot C_n(Q)}$ such that $T \in \{U\} \circ \overline{C_n(R)}$.

Let $k>0$; we put $\varepsilon = 2^{-2kn}$ and $\varepsilon' = 2^{-kn}$. There exist $u_k' \in B_\varepsilon^\circ(U)$, $t_k \in \{u_k'\} \cdot B_\varepsilon^\circ(\overline{C_n(R)}) = \{u_k'\} \cdot B_\varepsilon^\circ(\overline{C_n(R)}) = \{u_k'\} \cdot C_n(R)$ such that $d(T, t_k) < \varepsilon$.

Since $u_k' \in B_\varepsilon^\circ(U) \subset B_\varepsilon^\circ(\overline{C_n(P) \cdot C_n(Q)}) = B_\varepsilon^\circ(\overline{C_n(P) \cdot C_n(Q)})$, there exists $u_k \in C_n(P) \cdot C_n(Q)$ such that $d(u_k', u_k) < \varepsilon$.
Since $\{u_k'\} \cdot C_n(R) \neq \emptyset$ we can apply lemma 31 and we get $u_k'' \in C_n(P) \cdot C_n(Q)$ such that $d(u_k', u_k'') < \varepsilon' = 2^{-kn}$ and $u_k'' \cdot C_n(R) \neq \emptyset$.

Thus we can apply lemma 20 : there exists $t_k' \in \{u_k''\} \cdot C_n(R)$ such that $d(t_k, t_k') < 2^{-kn}$ and thus $d(T, t_k') < 2^{-kn}$. Since $t_k' \in C_n(P) \cdot C_n(Q) \cdot C_n(R)$, the limit $T$ of the sequence $(t_k')_k$ belongs to $\overline{C_n(P) \cdot C_n(Q) \cdot C_n(R)}$. $\square$
## 4. FIXED POINTS OF NON DETERMINISTIC RECURSIVE PROGRAM SCHEMES

Here we use the notions previously introduced to improve some
results in [3,4].

The first thing to do is to compare the definition of the composition product given here to the one used in [3,4].

Let us recall that this second composition product, that we shall
note $\Theta$ here, was defined by

- if $t \in T_{\Omega}(\Sigma)_n^1$ and $Q \in PT_{\Omega}^{\infty}(\Sigma)_q^n$ then $\{t\} \Theta Q$ is defined by induction
  on $t$

• if $t = x_i \in X_n$, then $\{t\} \Theta Q = Q_i$

• if $t = a \in F \cup F_0 \cup \{\Omega\}$, then $\{t\} \Theta Q = \{a\}$

• if $t = f(t_1, \dots, t_n)$, then $\{t\} \Theta Q = \{f(U_1, \dots, U_n) / U_i \in \{t_i\} - Q\}$.

- if $T \in T_{\Omega}^{\infty}(\Sigma)_n^1$ and $Q \in PT_{\Omega}^{\infty}(\Sigma)_q^n$ then $W \in \{T\} \Theta Q$ iff there exists an increasing sequence $(t_i)_i$ in $T_{\Omega}(\Sigma)_n^1$ and an increasing sequence $(W_i)_i$ in $T^{\infty}(\Sigma)_q^1$ such that

• $\text{lub}_i(t_i) = T$

• $\forall i, W_i \in \{t_i\} \Theta Q$

• $\text{lub}_i(W_i) = W$

- if $P = PT_{\Omega}^{\infty}(\Sigma)_n^1$ and $Q \in PT_{\Omega}^{\infty}(\Sigma)_q^n$ then $P \Theta Q = U_{T \in P} \{T\} \Theta Q$.

Let us prove the following property of the composition product
in $PT^{\infty}(\Sigma)$.

**Lemma 33** : Let $f \in F_n$ and $Q \in PT_{\Omega}^{\infty}(\Sigma)_q^n$. Then $\{f\} \Theta \bar{Q} = \bigsqcup_{T_i \in Q_i} \{f\} \Theta \langle \{T_1\}, \dots, \{T_m\} \rangle$
**Proof :** It is clear that $\bigcup_{T_i \in \bar{Q}_i} \{f\} \subset \langle \{T_1\}, \dots, \{T_m\} \rangle$ is included in $\{f\} \odot \bar{Q}$.

Let $U \in \{f\} \odot \bar{Q}$. For every integer $m$ there exists $u_m \in B_2^\circ \subset B_2^\circ(f) \cdot B_2^\circ(\bar{Q})$ such that $d(U, u_m) < 2^{-m}$. Since $B_2^\circ(f) = f$, $u_n = f(v_m^{(1)}, \dots, v_m^{(n)})$ with $v_m^{(j)} \in B_2^\circ(\bar{Q}_j)$.

Since $d(u_m, u_m') \le \max(d(u_m, U), d(u_m', U)) < \max(2^{-m}, 2^{-m'}')$, and $d(v_m^{(j)}, v_{m'}^{(j)}) < \max 2^{-m+1}, 2^{-m'+1})$. Therefore the sequence $(v_m^{(j)})_m$ is a Cauchy sequence and its limit $v^{(j)}$ is in $\bar{Q}_i$; moreover $d(v^{(i)}, v_n^{(j)}) < 2^{-m+1}$. Hence $u_m \in \{f\} \subset B_2^\circ(f) \cdot B_2^\circ(\bar{Q})$. It follows that the limit $U$ of the sequence $(u_m)_m$ is in $\bigcap_m B_2^\circ(f) \cdot B_2^\circ(\bar{Q}) = \{f\} \odot \bar{Q}$. $\square$

**Proposition 34 :** Let $P \in PT^\infty(\Sigma)_n^1 \subset PT^\infty(\Sigma)_n^1$ and $Q \in PT^\infty(\Sigma)_q^n \subset PT^\infty(\Sigma)_q^n$. If $P$ and $Q$ are closed then $P \odot Q = P \odot \bar{Q}$.

**Proof :** From the definition of $P$ and from proposition 25, it is sufficient to prove this result with $P = \{T\}$ where $T \in T^\infty(\Sigma)_n^1$.

In the case where $T = t \in T(\Sigma)_n^1$ the result is easily proved by structural induction on $t$:

$$ - \text{ if } t = x_i \in X_n, \{t\} \odot Q = \{t\} \odot Q = Q_i $$

$$ - \text{ if } t = a \in E \cup F_0, \{t\} \odot Q = \{t\} \odot Q = \{a\} $$

- if $t = f(t_1, \dots, t_m)$, then by induction hypothesis $\{t_i\} \odot Q = \{t_i\} \odot Q$, hence $\{t\} \odot Q = \{f(U_1, \dots, U_n)/U_i \in \{t_i\} \odot Q\} = \{f(t_1, \dots, t_m)\} \odot Q$ from lemma 33 and from the associativity of $\odot$.

Let now $T$ in $T^\infty(\Sigma)_n^1$. Let $(t_i)_i$ a sequence in $T^\infty(\Sigma)_n^1$, lub of which is $T$. Let $(W_i)_i$ an increasing sequence, with lub $W$ such that $W_i \in \{t_i\} \odot Q$.

Let $t_i^!$ be the tree obtained by replacing in $t_i^\circ \Omega$ by a constant symbol in $E \cup F_0$. It follows from the proof of proposition 14 that $\forall e \exists n \forall i \ge n \ t_i^! \in B_e^\circ(T)$.
Now it can be easily proved by induction on $t_i$ that there exists $W_i' \in \{t_i'\} \odot Q$ such that $W_i' < W_i'$ and always from the fact that lub $W_i$ is maximal, $\forall \epsilon \exists n' \forall i \ge n' d(W_i, W_i') < \epsilon$. But since $W_i' \in \{t_i'\} \odot Q$ there exists $w_i' \in B_\epsilon^\circ(t_i') \cdot B_\epsilon^\circ(Q)$ such that $d(W_i, w_i') < \epsilon$ and thus $d(W, w_i') < \epsilon$. But for $i \ge \max(n, n')$, $B_\epsilon^\circ(t_i') \subseteq B_\epsilon^\circ(T)$, hence $w_i' \in B_\epsilon^\circ(T) \cdot B_\epsilon^\circ(Q)$ and $W$, which is the limit of $(w_i')_i$, belongs to $\overline{B_\epsilon^\circ(T) \cdot B_\epsilon^\circ(Q)}$. Thus $W \in \{T\} \odot Q$.

Let now $W \in \{T\} \odot Q$. For every $k>0$ there exist $t_k \in B_{2-k}^\circ(T)$, $w_k \in \{t_k\} \cdot B_{2-k}^\circ(Q)$ such that $d(W, w_k) < 2^{-k}$. Let $u_k$ be $\alpha_k(t_k) = \alpha_k(T)$. This sequence is increasing and its lub is $T$.

Since all variables in $u_k$ are in $t_k$, $\{u_k\} \cdot B_{2-k}^\circ(Q) \ne \emptyset$ and from lemma 20 there exists $w_k' \in \{u_k\} \cdot B_{2-k}^\circ(Q)$ such that $d(w_k, w_k') < 2^{-k}$.

Let $u_k = \tilde{u}_k \cdot \theta_k$. By an argument similar to the one used in proof of lemma 29 we prove that there exists $W_k' \in \{u_k\} \odot Q = \{u_k\} \oplus Q$ such that $d(W_k', W_k') < 2^{-k}$, hence $d(W, W_k') < 2^{-k}$ and $\alpha_k(W) = \alpha_k(W_k')$. Moreover, from the construction of $W_k'$ we have $W_k' = \tilde{u}_k \odot <W_k^{(1)}, \dots, W_k^{(r_k)}>$, $W_{k+1}' = \tilde{u}_{k+1} \odot <W_{k+1}^{(1)}, \dots, W_{k+1}^{(r_{k+1})}>$, $\tilde{u}_k \cdot \theta_k = \tilde{u}_k \cdot \theta_k \cdot \gamma_k \cdot \theta_{k+1} < \tilde{u}_{k+1} \cdot \theta_{k+1}$ and $W_k^{(i)} = W_{k+1}^{(\gamma_k(i))}$. It follows that $W_k' < W_{k+1}'$. Hence the sequence $(W_k')_k$ is increasing. Since $\alpha_k(W) = \alpha_k(W_k') < W_k'$, $W < \text{lub}_k W_k'$ and since $W$ is maximal $W = \text{lub}_k W_k'$. Hence $W \in (\text{lub}_k u_k) \oplus Q = T \oplus Q$. $\Box$

## 4.1 Non deterministic recursive program schemes

Let $F$ be a finite set of function symbols, let $\Phi = \{\phi_1, \dots, \phi_k\}$ be a set of unknown functions symbols disjoint from $F$, the arity of $\phi_i$ being $n_i$, and $\text{or}$ a symbol of arity 2 not in $F \cup \Phi$. Let $G = F \cup \Phi \cup \{\text{or}\}$.

A non deterministic recursive program scheme (abbreviated ndrps) is a system of equations

$$ S = \left\{ \begin{array}{l} \phi_i(x_1, \dots, x_{n_i}) = u_i \\ i = 1, \dots, k \end{array} \right. $$
Let $E_S$ be the set $\overline{PT}^\infty(F)_{n_1}^1 \times \overline{PT}^\infty(F)_{n_2}^1 \cdots \times \overline{PT}^\infty(F)_{n_k}^1$ where $\overline{PT}^\infty(F)_{n}^1$ is the set of closed elements of $PT^\infty(F)_n$. $E_S$ is naturally ordered by inclusion componentwise and its largest element is $E_S = \langle T^\infty(F)_{n_1}^1, \cdots, T^\infty(F)_{n_k}^1 \rangle$

We associate to $S$ the mapping $\hat{S}$ from $E_S$ into itself in the following way :

Let $A = \langle A_1, \cdots, A_k \rangle \in E_S$ ; to this element $A$ we associate a mapping
$\sigma_A$ from $T(G)_n^1$ into $\overline{PT}^\infty(F)_n^1$ by

$\circ$ if $t = x_i \in X_n$ then $\sigma_A(t) = \{x_i\}$

◦ if $t = a \in F_0$ then $\sigma_A(t) = \{a\}$

◦ if $t = or(t_1, t_2)$ then $\sigma_A(t) = \sigma_A(t_1) \cup \sigma_A(t_2)$

• if t = f(t₁, ..., tₙ) then σ<sub>A</sub>(t) = {f} ⊙ <σ<sub>A</sub>(t₁), ..., σ<sub>A</sub>(tₙ)>

◦ if $t = \phi_i(t_1, \cdots, t_{n_i})$ then $\sigma_A(t) = A_i \circ \langle \sigma_A(t_1), \cdots, \sigma_A(t_{n_i}) \rangle$

From proposition 34 it follows that this mapping $\sigma_A$ is identical to the
one defined in [3,4]. Also it should be noticed, from the definition of ⊙ and
from the fact that the union of two closed sets is closed, that $\sigma_A(t)$ is closed.

Now we define $\hat{S}$ by $\hat{S}(A) = \langle \sigma_A(u_1), \dots, \sigma_A(u_k) \rangle$. It is clear that $\hat{S}(A) \in E_S$, from the definition of $\sigma_A$. Moreover since $\hat{S}$ is defined by using only set theoretical union and the composition product $\circ$ which are continuous operations (under acceptability conditions for $\circ$), we have

**Proposition 35** : Under acceptability conditions, $\hat{S}$ is continuous.

In [3,4] we have considered the decreasing sequence $(\hat{S}^n(E_S))_n$ and
proved that $v(\hat{S}) = \lim_n \hat{S}^n(E_S)$ contained all the fixed points of $\hat{S}$ and was itself
a fixed point when $S$ was what we call a "Greibach scheme". Here we prove that
$v(\hat{S})$ is always a fixed point of $\hat{S}$ and therefore

**Theorem 36** : $v(\hat{S})$ is the greatest fixed point of $\hat{S}$.

**Proof** : Since the sequence $\hat{S}^n(E_S)$ is decreasing, $v(\hat{S}) = \lim_n \hat{S}^n(E_S) = \lim_{n \to \infty} \hat{S}^n(E_S)$ ;
moreover it follows from lemma 30 that acceptability conditions hold and thus
$\hat{S}(v(\hat{S})) = \hat{S}(\lim_n \hat{S}^n(E_S)) = \lim_n \hat{S}^{n+1}(E_S) = v(\hat{S})$. $\square$
Let us consider now $A = \langle A_1, \dots, A_k \rangle$ such that every $A_i$ is a finite set of finite trees and thus a closed set. It can be easily proved that $\sigma_A(t)$ is also a finite set of finite trees. Thus each $\hat{S}^n(\emptyset)$ is a k-uple of finite sets of finite trees. Moreover the sequence $\hat{S}^n(\emptyset)$ is increasing and P-converges to $\mu(\hat{S}) = \bigcup_n \hat{S}^n(\emptyset)$.

**Theorem 37** : If $\mu(\hat{S})$ is a k-uple of non-empty sets, then it is the least fixed point of $\hat{S}$.

**Proof** : If $\mu(\hat{S})$ has no empty component then $\bigcup_n \hat{S}^n(\emptyset)$ has no empty component ; thus there exists $n_0$ such that $n \ge n_0$ implies $\hat{S}^n(\emptyset)$ has no empty component. Thus the acceptability conditions for $\hat{S}$ being continuous hold and $\hat{S}(\mu(\hat{S})) = \hat{S}(\lim_n \hat{S}(\emptyset)) = \lim(\hat{S}^{n+1}(\emptyset)) = \mu(\hat{S})$.

Moreover if $A = \hat{S}(A)$, we have $\emptyset \subset A$, hence $\hat{S}(\emptyset) \subset \hat{S}(A) = A$, and, by induction on $n$, $\hat{S}^n(\emptyset) \subset A$, whence $\bigcup_n \hat{S}^n(\emptyset) \subset A$ and $\mu(\hat{S}) \subset \bar{A} = A$. $\square$

## 4.2 Sets of trees computed by ndrps

We have defined in [3,4] the elements $\text{Res} = \langle \text{Res}(\phi_1), \dots, \text{Res}(\phi_k) \rangle$
$\in \text{PT}(F)_{n_1}^1 \times \dots \times \text{PT}(F)_{n_k}^1$ and $\text{Res}^\infty = \langle \text{Res}^\infty(\phi_1), \dots, \text{Res}^\infty(\phi_k) \rangle \in \text{PT}^\infty(F)_{n_1}^1 \times \dots \times \text{PT}^\infty(F)_{n_k}^1$,
where $\text{Res}(\phi_i)$ [resp : $\text{Res}^\infty(\phi_i)$] is the set of finite [resp : finite and infinite]
trees computed by $\hat{S}$ from $\phi_i(x_1, \dots, x_{n_i})$. It is proved in [3,4] that
$\text{Res} = \bigcup_n \hat{S}^n(\emptyset)$. Thus $\mu(\hat{S}) = \overline{\text{Res}}$ and theorem 37 implies.

**Corollary 38** : If none of the $\text{Res}(\phi_i)$ is empty, $\overline{\text{Res}}$ is the least fixed point of $\hat{S}$.

Let us remark that, since $\hat{S}$ is defined only on closed elements, if $\text{Res}$ is not closed it cannot be a fixed point of $\hat{S}$.

Let us show by an example that $\overline{\text{Res}}$ is not always a fixed point of $\hat{S}$
and thus that the condition : $\text{Res}(\phi_i)$ is not empty cannot be dropped in the
hypothesis of corollary 38.
**Example :** Let the ndrps S =

$$
\left\{
\begin{array}{l}
\phi = \psi(\rho) \\
\\
\psi(x) = x \text{ or } \psi(f(x)) \\
\\
\rho = \rho
\end{array}
\right.
$$

We get Res = <Ø,A,Ø> with A = {fⁿ(x)/n≥0} and thus Res = <Ø,Ā,Ø>.
Then ſ(Res) = <Ā ⊙ Ø, {x} ⊙ {f(x)}, {f} • Ø>. We have {x} ∪ Ā ⊙ {f(x)} = Ā
{f} ⊙ Ø = Ø
and Ā ⊙ Ø = ⋃ T∈Ā {T} ⊙ Ø = {fⁿ} ⊙ Ø.

If there exists a constant symbol $\bar{\Omega}$ in our alphabet, then
${f^\omega} \circ \emptyset = \bigcap_n B_2^n(f^\omega) \circ \emptyset \subset \bigcap_n \{f_i^\Omega(\bar{\Omega})/i \ge n\} \circ \emptyset = \{f^\omega\}$, hence $\hat{S}(\text{Res}) \ne \text{Res}$.

It should be noted that in this example Res = Res∞ ; thus Res∞
is not, in general, a fixed point of S̄.

Nevertheless we have proved in [3,4] that if S is a Greibach scheme
then Res∞ is equal to v(S̄) (and thus closed). We shall improve this result by
showing that in this case Res∞ is the unique fixed point of S̄ which has no empty
component.

**Lemma 39 :** Let A a fixed point of S̄. If $t \to t'$ then $\sigma_A(t') < \sigma_A(t)$

**Proof :** We prove this result by structural induction on t.

- if t = x_i then t' = x_i and σ_A(t) = σ_A(t')

- if $t \in F_0$ then $t = t'$ and $\sigma_A(t) = \sigma_A(t')$

- if t = f(t₁, ..., tₙ) then t' = f(t₁, ..., tᵢ', ..., tₙ) with tᵢ → tᵢ',
hence σₐ(tᵢ') ⊂ σₐ(tᵢ) and σₐ(t') = {f} ◦ <σₐ(t₁), ..., σₐ(tᵢ'), ..., σₐ(tₙ')>
⊂ {f} ◦ <σₐ(t₁), ..., σₐ(tᵢ), ..., σₐ(tₙ')> = σₐ(t).

- if t = or(t₁,t₂) then t' = t₁ or t' = t₂ and
σ<sub>A</sub>(t') ⊂ σ<sub>A</sub>(t₁) ∪ σ<sub>A</sub>(t₂) = σ<sub>A</sub>(t).

- if t = φᵢ(t₁, ..., tₙᵢ) then t' = uᵢ · <t₁, ..., tₙᵢ> and σ<sub>A</sub>(t') =
σ<sub>A</sub>(uᵢ) · <σ<sub>A</sub>(t₁), ..., σ<sub>A</sub>(tₙᵢ)>. But since A is a fixed point of S̄, σ<sub>A</sub>(uᵢ) = σ<sub>A</sub>(φᵢ),
hence σ<sub>A</sub>(t') = σ<sub>A</sub>(φᵢ) ◦ <σ<sub>A</sub>(t₁), ..., σ<sub>A</sub>(tₙᵢ)> = σ<sub>A</sub>(φᵢ(t₁, ..., tₙᵢ)) = σ<sub>A</sub>(t). □
**Proposition 40**: If $A = \langle A_1, \dots, A_k \rangle$ is a fixed point of $\hat{S}$ such that no $A_i$ is empty then $\overline{\mathrm{Res}} \subset A$.

**Proof**: Let $T \in \overline{\mathrm{Res}}^{\infty}(\phi_i)$. There exists an infinite computation

$\phi_i(x_1, \dots, x_{n_i}) = t_0 \to t_1 \to t_2 \to \dots$ in $S$ such that $\{T\} = \bigcap_n \sigma_{E_S}(t_n)$. From lemma 39 the sequence $(\sigma_A(t_n))_n$ is decreasing; since no $A_i$ is empty, and $\sigma_A(t_n)$ is a closed subset of the compact set $T^\infty(F)^{1}_{n_i}$, the infinite intersection $\bigcap_n \sigma_A(t_n)$ is not empty. Moreover, since $A \subset E_S$, $\sigma_A(t_n) \subset \sigma_{E_S}(t_n)$; then $\emptyset \neq \bigcap_n \sigma_A(t_n) \subset \bigcap_n \sigma_{E_S}(t_n) = \{T\}$

Therefore $\bigcap_n \sigma_A(t_n) = \{T\}$ and thus $T \in \sigma_A(t_0) = \sigma_A(\phi_i(x_1, \dots, x_{n_i})) = A_i$. It follows that $\overline{\mathrm{Res}}^{\infty}(\phi_i) \subset A_i$ and thus $\overline{\mathrm{Res}}^{\infty} \subset A$. Since $A$ is closed we have also $\overline{\mathrm{Res}}^{\infty} \subset A$. $\Box$

**Proposition 41**: If $S$ is a Greibach scheme then $\overline{\mathrm{Res}}^{\infty}$ is the only fixed point of $\hat{S}$ which has no empty component.

**Proof**: Let $A$ a fixed point of $\hat{S}$ which has no empty component. We have [3,4]
$A \subset v(\hat{S})$; from proposition 40 $\overline{\mathrm{Res}}^{\infty} \subset A$. But since $S$ is a Greibach scheme,
$\overline{\mathrm{Res}}^{\infty} = \overline{\mathrm{Res}}^{\infty} = v(\hat{S})$ [4] hence the result. $\Box$

But $\overline{\mathrm{Res}}^{\infty}$ is not always the least fixed point of $\hat{S}$ as shown by the
following example.

**Example**: Let $S$ be the Greibach scheme

$$ 
\begin{align*}
\phi_0(x) &= f(\phi_1(\phi_2(x))) \\
\phi_1(x) &= f(\phi_1(x)) \\
\phi_2(x) &= f(\phi_2(x))
\end{align*}
$$

It is clear that $\overline{\mathrm{Res}}^{\infty} = \overline{\mathrm{Res}}^{\infty} = v(\hat{S}) = \langle\{f^\omega\}, \{f^\omega\}, \{f^\omega\}\rangle$. But the following are also fixed points of $\hat{S}$:

$$ 
\begin{align*}
\langle\emptyset, \emptyset, \emptyset\rangle \\
\langle\emptyset, \emptyset, \{f^\omega\}\rangle \\
\langle\{f^\omega\}, \{f^\omega\}, \emptyset\rangle
\end{align*}
$$
Another consequence of proposition 40 is the following result
which generalizes to tree languages a result obtained by Nivat [14] about
languages.

**Proposition 42** : If $\overline{\mathbb{R}}$ has no empty component, then $\overline{\mathbb{R}} \subset \mathbb{R}^\infty$.

**Proof** : If $\overline{\mathbb{R}}$ has no empty component, then, from corollary 38, $\overline{\mathbb{R}}$ is a fixed point of $\tilde{S}$ with no empty component ; hence from proposition 40 $\overline{\mathbb{R}}^\infty \subset \mathbb{R}$.
Since $\overline{\mathbb{R}}$ is clearly included in $\overline{\mathbb{R}}^\infty$, we have also $\overline{\mathbb{R}} \subset \overline{\mathbb{R}}^\infty$ and thus
$\overline{\mathbb{R}} = \overline{\mathbb{R}}^\infty$. $\square$
REFERENCES

[1] A. Arnold. Systèmes d'équations dans le magmoïde. Ensembles rationnels et algébriques d'arbres. Thèse d'Etat, Lille (1977).

[2] A. Arnold, M. Dauchet. Théorie des magmoïdes. Publications du Laboratoire de Calcul, Université de Lille I (1977). To appear in RAIRO. Informatique Théorique.

[3] A. Arnold, M. Nivat. Non deterministic recursive program schemes. in "Fundamentals of Computing Theory, 1977". Lecture Notes in Computer Science n°56, Springer-Verlag (1977) 12-21.

[4] A. Arnold, M. Nivat. Algebraic semantics of non deterministic recursive program schemes. Publications du L.I.T.P. n°78-4, Paris (1978).

[5] G. Boudol. Langages polyadiques algébriques. Théorie des schémas de programme : sémantique de l'appel par valeur. Thèse 3° cycle, Paris VII (1975).

[6] N. Bourbaki. *Topologie générale*. Hermann, Paris (1967).

[7] B. Courcelle, M. Nivat. Algebraic families of interpretations. in 17th Symposium on foundations of Computer Science, Houston (1976).

[8] J. Dugundji. *Topology*. Allyn and Bacon, Boston (1966).

[9] J. Engelfriet, E.M. Schmidt. IO and OI. *J. Comput. System Sci* 15 (1977) 328-353 and 16(1978) 67-99.

[10] K. Kuratowski. *Topology*. Academic Press, New-York (1966).

[11] J. Mycielski, W. Taylor. A compactification of the algebra of terms. *Algebra Universalis* 6 (1976) 159-163.

[12] M. Nivat. On the interpretation of recursive polyadic program schemes. *Symposia Mathematica* 15 (1975) 255-281.
[13] M. Nivat. Mots infinis engendrés par une grammaire algébrique.
RAIRO Informatique Théorique 11 (1977) 311-327.

[14] M. Nivat. Adhérences de Langages algébriques, to appear.

[15] M. Nivat, A. Arnold. Calculs infinis, interprétations métriques et plus grands points fixes. in Colloque AFCET-SMF de Mathématiques Appliquées, Palaiseau (1978).