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

laboria

Institut de Recherche
d'Informatique
et d'Automatique

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

laboratoire de recherche
en informatique
et automatique

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

FRONTIERS OF INFINITE TREES

Bruno COURCELLE

Rapport de Recherche N° 272
Janvier 1978
FRONTIERS OF INFINITE TREES

Bruno Courcelle

Résumé :

Le feuillage d'un arbre infini est un mot (infini) généralisé appelé arrangement. Une équation en arrangements a une solution initiale qui est le feuillage de sa solution dans le domaine des arbres infinis. Certains systèmes d'équations peuvent être résolus explicitement.

Abstract :

The frontier of an infinite tree is a generalized (infinite) word called an *arrangement*. An equation in arrangements has an initial solution which is the frontier of its solution in the domain of infinite trees. Certain systems of equations can be solved explicitly.

N.B. - This work will be presented at the «3ième Colloque sur les arbres», at Lille (Feb. 1978).

N.B. - Le travail sera présenté au «3ième Colloque sur les arbres», à Lille, Février 1978.
## Introduction

The theory of languages deals with finite words and sets of finite words. Infinite words as sequences of elements of some finite alphabet X indexed by $N$ have been considered in many papers, (in particular [M] and [N]). But with such a definition, the set $X^\omega$ of infinite words is not closed under the reversal and the concatenation is some what unnatural : $uv=u$ for infinite $u$.

A more general concept of infinite word is considered in this paper, and is called an *arrangement*. An arrangement of elements of X is a family of elements of X indexed by some linearly ordered set. (It is convenient to reserve the term "infinite word" for elements of $X^\omega$).

The *frontier* of an infinite tree is the sequence of labels of its terminal nodes, considered from left to right and this clearly generalizes the corresponding concept for finite trees [T].

An arrangement is *generated* by a context-free grammar if and only if it is the frontier of an *infinite derivation tree* of the grammar. In [N], an infinite word generated by a context-free grammar is the part of the frontier which is to the left of the left-most infinite branch of an infinite derivation tree of the grammar.

We restrict ourselves in this paper to "schematic" grammars (see [C]) i.e. to mere systems of equations in arrangements (an not in *sets* of arrangements). A typical example is $u=aub$ which has no solution in $X^*$ but the solution $u=a^\omega b^{-\omega}$ in the class $A_\omega(X)$ of countable arrangements.

Let us summarize the main results of this paper :

1. Frontiers of infinite trees and countable arrangements coincide (up to an isomorphism).

2. To have the same frontier (up to an isomorphism) is an equivalence relation on $M^\infty(F)$ (the set of infinite trees) which is not algebraic (in the sense of [C,N]).

3. A system $\Sigma$ has one and only one solution $<T_1, \cdots, T_k>$ in $M^\infty(F)$. By taking the frontiers, one obtains a solution $<A_1, \cdots, A_k>$ of $\Sigma$ in $A(X)$ (the class of all arrangements) which is *initial in the category of all solutions of $\Sigma$ in A(X)$*. It cannot be said *minimal* since $A(X)$ is not ordered, but equipped with *morphisms* which are embeddings. There may exist several morphisms from an arrangement to another. Such a situation is considered in general in [I].
# 1. ARRANGEMENTS

(1.1) Let $\mathcal{X}$ be a finite alphabet. An arrangement is a triple $A = <|A|, \pi, h>$ consisting of :

1) a set $|A|,$

2) a linear order $\pi$ on $|A|,$

3) a mapping $h : |A| \to \mathcal{X}$.

Let $\mathcal{A}(\mathcal{X})$ be the class of all arrangements and $A_f(\mathcal{X})$ (resp. $A_\omega(\mathcal{X})$) the class of *finite* (resp. *countable*) arrangements i.e. such that $|A|$ is finite (resp. countable).

If $X = \{a\}$, an arrangement $A$ is simply a *linearly ordered set* denoted by $A = <|A|, \pi>$. By convention, "let $A = <|A|, \pi>^>$ be an arrangement..." means that $X$ is singleton.

Let $\epsilon$ be the unique arrangement $A$ such that $|A|=\emptyset$. Words on $X$ will be identified with finite arrangements : to the word $u = a_1a_2\cdots a_n$ (where $a_i\in X$) will correspond the arrangement $\{1,2,\cdots,n\},\le,h\}$ where $h(i)=a_i$ for $i = 1,2,\cdots,n$. The notation $x^*$ will be used instead of $A_f(\mathcal{X})$. An arrangement of the form $\mathcal{N},\le,h$ corresponds to an infinite word in the sense of $\mathcal{N}$. Let $x^\omega$ be the set of such arrangements and $x^\infty = x^\omega \cup x^*$.

For $a\in X$, let $a^\omega = \mathcal{N},\le,h$, $a^\omega = \mathcal{N},\le,h$ and $a^{-\omega} = \{-n/n\in\mathcal{N}\},\le,h$ with $h(i)=a$ for all $i$. In order to compare arrangements, we define morphisms.

Let $A = <|A|, \pi, h>$ and $A' = <|A'|, \pi', h'>$ belong to $\mathcal{A}(\mathcal{X})$. A morphism $\alpha : A \to A'$ is a mapping $\alpha:|A| \to |A'|$

1) which is one-to-one and order-preserving, i.e. (since $\pi$ and $\pi'$ are linear), $\alpha(x)\pi'\alpha(y) \Leftrightarrow x\pi y$ for all $x,y\in|A|,$

2) such that $h(x) = h'(\alpha(x))$ for $x\in|A|$.

If $\alpha$ is onto, it is called an *isomorphism* and we write $A \cong A'$.

It would be pleasant to identify isomorphic arrangements but this will not be always possible since there may exist several isomorphisms : $A \to A'$. For $A$ and $A'$ in $X^\infty$ there exists at most one isomorphism : $A \to A'$, hence $A \cong A'$ can be replaced by $A \cong A'$ without any ambiguity. We will often do so for arbitrary arrangements when the abuse is not troublesome. Let us finally point out that there may exist morphisms $\alpha : A \to B$ and $\beta : B \to A$ although $A$ and $B$ are not isomorphic.
Just take $A = a(ab^2ab^2a)^\omega$ and $B = ab^2a(ab^2ab^2a)^\omega$ (this depends on definitions and notations given below ; thanks to B. Lang for this example).

(1.2) We will define the concatenation of arrangements, which will generalize the concatenation of words for finite arrangements. We will also have $a^{-\omega}a^{\omega} = a^\omega$ as one may guess.

This will be done in terms of another operation called the *substitution* which we now define.

Let $A = \langle |A|, \pi, h \rangle \in A(X)$ and $\sigma = |A| \to A(X)$ be a partial mapping. Let us extend $\sigma$ into a total mapping $\bar{\sigma}$ by taking for $\bar{\sigma}(x)$ the one-element arrangement $x$ (i.e. $\langle \{1\}, \pi, k \rangle$ where $k(1)=x$) when $\sigma(x)$ is undefined and $\sigma(x)$ otherwise.
Let $\bar{\sigma}(x) = \langle |\bar{\sigma}(x)|, \pi_x, h_x \rangle$ for $x \in |A|$.

Let $\sigma(A) = A' = \langle |A'|, \pi', h' \rangle$ with :

$$1) |A'| = \{(x,y)/x \in |A| \text{ and } y \in |\bar{\sigma}(x)|\}$$

$$2) (x,y)\pi'(x',y') \text{ if and only if either } x \neq x' \text{ and } x\pi x' \\ \text{ or } x=x' \text{ and } y\pi_x y'$$

Note that $\sigma(A)$ does not depend on $h$ if $\sigma$ is total.

Furthermore, if $\alpha : A_1 \to A_2$ is a morphism, $\sigma_i : |A_i| \to A(X)$ is a substitution for $i=1,2$, $\delta_x : \sigma_1(x) \to \sigma_2(\alpha(x))$ is a morphism for all $x$ such that $\sigma_1(x)$ is defined, one can define a canonical morphism $\gamma : \sigma_1(A_1) \to \sigma_2(A_2)$ by taking

$$\gamma((x,1)) = (\alpha(x),1) \quad \text{if } \sigma_1(x) \text{ is not defined}$$

$$\gamma((x,y)) = (\alpha(x), \delta_x(y)) \text{ if } \sigma_1(x) \text{ is defined and } y \in |\sigma_1(x)|$$

As an example, for $A \in A(X)$, let $A^\omega = \sigma(\langle N, \le \rangle)$ and $A^{-\omega} = \sigma(\langle -N, \le \rangle)$ where $\sigma(i)=A$ for all $i \in N$ and $i \le j$ iff $j \le i$ for $i,j \in N$

The concatenation of $A$ and $A' \in A(X)$ is defined by $A.A' = \sigma(\langle \{0,1\}, \le \rangle)$ where, $\sigma(0)=A$ and $\sigma(1)=A'$.

(1.3) **Proposition** : The concatenation is associative. Namely, there exists a *canonical isomorphism* : $A_1 \cdot (A_2 \cdot A_2) \to (A_1 \cdot A_2) \cdot A_3$ **for** $A_1, A_2, A_3 \in A(X)$.

Hence we will write $A_1 \cdot A_2 \cdot A_3$ or even $A_1 A_2 A_3$ for $A_1 \cdot (A_2 \cdot A_3)$.

For arrangements in $X^*$, this concatenation coincides with the usual one. But it does not with the concatenation on $X^\infty$ described in $\mathbb{N}$ (Recall that $uv=u$ if $u \in X^\omega, v \in X^\omega$) In fact, the reader will show that $a^w a^\omega$ is not isomorphic to $a^\omega$.
4) there exists $w \in \{0,1\}^*$ such that $L_n^w$ is prefix-free and $u_i^{lexw}$ for all $i=0, \dots, n$,

5) for all $i,j \in \{0,1,\dots,n\}$ such that $i \neq j$ and $i \neq n$, there exists $Z_{i,j} \in \{0,1\}^*$ such that $L_n^w \cup \{Z_{i,j}\}$ is prefix-free and $u_i^{lexw} \cup Z_{i,j}^{lexw}$.

Assuming this, we will take $L = \bigcup_{n \in \mathbb{N}} L_n$ and $\ell: L \to X$ defined by $\ell(u_n) = h(n)$. We construct $u_n$ inductively:

* $u_0 = 10$. Note that 3) and 4) hold, the other conditions being trivially satisfied.

* $\dots$ having defined $u_n$, we now define $u_{n+1}$ in the following way.:

i) if $(n+1)\pi i$ for all $i=0,1,\dots,n$, let $v$ be a word defined by 3) for $L_n$. Then we take $u_{n+1} = v10$.

ii) if $i\pi(n+1)$ for $i=0,1,\dots,n$, let $w$ be defined by 4) for $L_n$. Then we take $u_{n+1} = w10$.

iii) if $i\pi(n+1)\pi j$ for some $i,j \in \{0,\dots,n\}$ and $\{k/0 \le k \le n, i\pi k \pi j\} = \{i,j\}$ then we take $u_{n+1} = Z_{i,j}^{10}$ where $Z_{i,j}$ is defined by 5) for $L_n$.

Conditions 3 to 5 express that there is room left for other elements to the left and to the right of what has already been constructed and between any two elements. These possibilities are used in cases i), ii) and iii) of the definition of $L_{n+1}$. The factors "10" are used to preserve conditions 3 to 5.

Details are left to the reader.

The rest of the proof follows from:

(1.8) **Lemma:*** Let $L \in \{0,1\}^*$ be prefix-free. There exists a complete language $K \in \{0,1\}^*$ such that $<L, lex> \le <K, lex>$.

*Proof:* Let $L \in \{0,1\}^*$ be prefix-free.

We define a mapping $\phi: L \to \{0,1\}^*$, we will take $K = \phi(L)$, and $\phi$ will be the required isomorphism $\phi: <L, lex> \to <K, lex>$.

A prefix $u$ of some word in $L$ is *critical* if :

$$u_0 \in \{0,1\}^* nL = \emptyset \iff u_1 \in \{0,1\}^* nL = \emptyset.$$
Note that L is complete if and only if it has no critical prefix
by lemma (1.6).

Let $x_1 \cdots x_k \in L$ with $x_1, x_k \in \{0,1\}$.

Then $\phi(x_1 \cdots x_k) = y_1 \cdots y_k$

where $y_i = x_i$ if $x_1 \cdots x_{i-1}$ is not critical
$= \epsilon$ if $x_1 \cdots x_{i-1}$ is critical.

**Claim 1 :** *Let $u, u' \in L$. If $\phi(u) \le \phi(u')$ then $u=u'$.*

Assume by contradiction that $u \neq u'$. Then $u=v_0w$ and $u'=v_1w'$ for some $v,w,w' \in \{0,1\}^*$ (or vice-versa); but $v$ is *not* critical hence $\phi(u)=x_0y$ and $\phi(u')=x_1y'$ for some $x,y' \in \{0,1\}^*$ and we cannot have $\phi(u) \le \phi(u')$.

Q.E.D.

**Claim 2 :** *Let $u, u' \in L$. If $u \le u'$ then $\phi(u) \le \phi(u')$.*

We have $u=v_0w$ and $u'=v_1w'$ for some $v,w,w' \in \{0,1\}^*$ hence $v$ is *not* critical and $\phi(u)=x_0y$, $\phi(u')=x_1y'$ for some $x,y,y' \in \{0,1\}^*$.

Q.E.D.

Claim 1 shows that K is prefix-free and that $\phi$ is one-to-one, claim 2
that $\phi$ preserves *lex*. We need only show that K is complete.

Let $\phi(u)=v_0w$ for some $u \in L$, $v,w \in \{0,1\}^*$. Then, by the definition of $\phi$, we can write :

$u = x_1 \cdots x_k$ with $x_l=0$ for some $1 \le l \le k$,

$v = y_1 \cdots y_{l-1}$ 
$w = y_{l+1} \cdots y_k$ 
$x_1 \cdots x_{k-1}$ is not critical.

as in the definition of $\phi$,

Hence there exists $u' = x_1 \cdots x_{l-1} w \in L$ for some $z \in \{0,1\}^*$ and clearly,

$\phi(u') = y_1 \cdots y_{l-1} w'$ for some $w' \in \{0,1\}^*$
$= v_1 w'$.

Lemma (1.6) shows then that K is complete.

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

If we represent prefix-free languages by trees, the transformation
of L into K corresponds to the suppression of nodes with only one son.

As an example, if $L = \{0,1010,100010,100011\}$ then $K = \{0,100,101,11\}$.

The tree

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

becomes

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

associated

associated

with L

with K
## II. THE FRONTIER OF AN INFINITE TREE

(2.1) Let $F = \{*\}UX$. The symbol $*$ will be given the arity 2 and each $x \in X$ the arity 0.

We recall from [C] the definition of $M^\infty(F)$, the set of infinite (and finite) trees on $F$ by adapting it to the special set $F$ that we are considering.

A *tree* $T$ is a partial mapping : $\{0,1\}^* \to X\{*\}$ such that :

1) $\text{Dom}(T) = \{u \in \{0,1\}^* | T(u) \downarrow\}^*$ is prefix-closed,
   (i.e. $u \llcorner v \in \text{Dom}(T) \Rightarrow u \in \text{Dom}(T)$). $\text{Dom}(T)$ is the set of *nodes* of $T$.

2) $T(u) \in X$ if and only if $u$ is maximal in $\text{Dom}(T)$ w.r.t. $\llcorner$.

Let $T_# = \{u \in \{0,1\}^* | T(u) \in X\}$, the set of *terminal nodes*. Then $T_#$ is prefix-free. It is complete if and only if $T$ is *locally finite$[C]$* (denoted by $T \in M^{\text{loc}}(F)$). Recall that $T$ is locally finite if and only if each node $u$ is an *ancestor* of some terminal node $v$ (i.e. $u \llcorner v$). $M(F)$ denotes the set of finite trees.

Some examples will show why such mappings are called trees.

(2.2) *Examples* :

<figure><img src="image_6.png" /></figure>
Other examples of trees are :

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

The trees $T_1, T_2, T_3$ are locally finite, but $U$ is not.

The *frontier* of $T \in \mathcal{M}^\infty(F)$ is the countable arrangement $\Phi(T) = \langle T_\# , \underline{lex} , T \rangle$
(the third element of this triple is in fact the restriction of $T$ to $T_\#$).

Hence $\Phi(T_0)=a^\omega$, $\Phi(T_1)=a^{-\omega}$, $\Phi(T_2)=a^\omega a^{-\omega}$, $\Phi(U)=\epsilon$.

For a finite $T$, $\Phi(T) \in X^*$ and coincides with the usual frontier $[T]$.
An immediate consequence of theorem (1.7) is

$$
(2.3) \textit{Theorem} : A_\omega(X) = \{\Phi(T)/T \in \mathcal{M}^\infty(F)\} = \{\epsilon\} \cup \{\Phi(T)/T \in \mathcal{M}^{\text{loc}}(F)\}
$$
### III. EQUIVALENT TREES

**Definition**: Two trees $T, T' \in M^\infty(F)$ are equivalent, denoted by $T \equiv T'$ if they have the same frontier (up to an isomorphism).

We now aim to investigate this equivalence.

$$ (3.1) \quad \textbf{Proposition} : \Phi(T*T') = \Phi(T) \cdot \Phi(T'). $$

By $T*T'$ we mean the tree :

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

$$ (3.2) \quad \textbf{Example} : \text{ Let } T_3 = T_0*T_1 \text{ (where } T_0, T_1 \text{ are from (2.2))).} $$

This tree looks like :

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

$$ \text{Clearly } \Phi(T_3) = \Phi(T_2) = a^{\omega} \cdot a^{-\omega} $$

□

$$ (3.3) \quad \textbf{Corollary} : T_1*(T_2*T_3) \equiv (T_1*T_2)*T_3 \text{ for all } T_1,T_2,T_3 \in M^\infty(F). $$

Let us recall that each $T \in M^\infty(F)$ is the least upper bound of a directed subset of $M(FU\{\Omega\})$ with respect to the ordering $\prec$, the least partial order such that $\Omega \prec t$ for all $t$ and $t_1*t_2 \prec t_3*t_4$ if $t_1 \prec t_3$ and $t_2 \prec t_4$. In other words, $t \prec t'$ if and only if $t'$ is obtained from $t$ by the replacement of some $\Omega$'s by arbitrary elements of $M(FU\{\Omega\})$. See [C] or [C,N].
As an example, $T_0$ of (2.2) is the least upper bound of the $t_n$'s where

$$ t_n = \left. \begin{array}{c|c} a & * \\ \hline a & * \\ \hline \vdots & \vdots \\ \hline a & * \\ \hline \Omega \end{array} \right\} \text{ n times.} $$

An equivalence $\equiv$ on $M^\infty(F)$ is said *algebraic* (see [C,N]) if there exists a preorder $R$ on $M(FU\{\Omega\})$ such that

$$ (1) \quad t \prec t' \Rightarrow tRt' $$

$$ (2) \quad t_1 Rt'_1 \text{ and } t_2 Rt'_2 \Rightarrow t_1 * t_2 Rt'_1 * t_2' $$

(3) for all $T = \text{Sup}(\Delta) \in M^\infty(F)$, $T' = \text{Sup}(\Delta') \in M^\infty(F)$ where $\Delta, \Delta'$ are directed subsets of $M(FU\{\Omega\})$ then :
$$ T \equiv T' \Leftrightarrow \forall t \in \Delta \ \exists t' \in \Delta' \text{ s.t. } tRt' \text{ and } \forall t' \in \Delta' \ \exists t \in \Delta \text{ s.t. } t'Rt. $$
One could hope that $\equiv$ would satisfy (3) with $R$ being the least preorder satisfying (1), (2), (4) and (5) :

$$ (4) \quad t_1 * (t_2 * t_3) R (t_1 * t_2) * t_3 $$

$$ (5) \quad (t_1 * t_2) * t_3 Rt_1 * (t_2 * t_3) $$

But this does not hold, as shown by

(3.4) **Example 3**: (see example (2.2))

$$ \Phi(T_4) = a^{\omega} a^{\omega} a^{-\omega} \quad \text{where } T_4 = T_0 * T_2 $$

$$ \Phi(T_5) = a^{\omega} a^{-\omega} a^{\omega} \neq \Phi(T_4) \quad \text{where } T_5 = T_2 * T_1 $$

Note that $T_4$ and $T_5$ are the least upper bounds of the following sequences of elements $(t_4^{(n)})_{n \ge 1}$ and $(t_5^{(n)})_{n \ge 1}$ :
<figure><img src="image_10.png" /></figure>

Let $\sim$ be the equivalence relation generated by (4) and (5) ; then,
it is not difficult to prove that for $t,t' \in M(Fu\{\Omega\})$, $\Phi(t) = \Phi(t')$ if and
only if $t \sim t'$.

Then $\Phi(t_4^{(n)}) = \Phi(t_5^{(n)}) = a^n \Omega a^n \Omega a^n$ hence $t_4^{(n)} \sim t_5^{(n)}$.

It follows that $t_4^{(n)}Rt_5^{(n)}$ and $t_5^{(n)}Rt_4^{(n)}$. If (3) holds, we get
$T_4 \equiv T_5$ which is not the case (a formal proof that $a^{\omega-\omega}a^{\omega-\omega}a^{\omega-\omega}a^{\omega-\omega}$ is left
to the reader).

But we can prove more than that :

(3.5) **Proposition** : The equivalence $\equiv$ is not algebraic.

**Proof** : Assume that $\equiv$ is algebraic for some preorder $R$ on $M(Fu\{\Omega\})$ satisfying
(1), (2), (3).

Using the trees of example (3.4) we are to prove that :

(6) $\forall n, \exists m \text{ s.t. } t_4^{(n)} Rt_5^{(m)}$,

and

(7) $\forall n, \exists m \text{ s.t. } t_5^{(n)} Rt_4^{(m)}$

Hence we get $T_4 \equiv T_5$, contradiction.
For each $n$, let $T_6^{(n)}$ be the following tree :

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

with $a$ at each terminal node and $*$ at other nodes.

It is clear that $t_4^{(n)} <_{T_6^{(n)}}$ and that :

$$ \Phi(T_6^{(n)}) = a^n a^\omega a^{-\omega} a^n a^{-\omega} a^n = a^\omega a^{-\omega} a^{-\omega} \quad \text{since } a^n a^\omega = a^\omega \text{ and } a^{-\omega} = a^{-\omega} a^n = \Phi(T_5) $$

Hence by (3), $t_4^{(n)} \nLt'$ for some finite $t' <_{T_5}$.

There exists $t_5^{(m)}$ such that $t' <_{T_5} t_5^{(m)}$ hence $t_4^{(n)} R t_5^{(m)}$.

We have proved (6) and the proof of (7) is similar.

# IV - SOLVING EQUATIONS ON $\mathcal{A}(X)$.

We want to solve in $\mathcal{A}(X)$ systems of equations of the form

$$ \Sigma \left\{ \begin{array}{l} u_1 = t_1 \\ \bullet \\ \bullet \\ \bullet \\ u_k = t_k \end{array} \right. $$

the $u_i$'s are variables of arity 0, $V = \{u_1, \dots, u_k\}$, $t_i \in \mathcal{M}(\mathcal{FUV})$ and $t_i \notin \mathcal{V}$ for $i = 1, \dots, k$.
The binary operation symbol `*` will be interpreted in $\mathcal{A}(X)$ as the concatenation.

It will be useful to solve $\Sigma$ in $M^\infty(F)$ first. We obtain a unique solution $\langle T_1(\Sigma), \dots, T_k(\Sigma) \rangle$. By (3.1), the $k$-tuple $\langle \Phi(T_1(\Sigma)), \dots, \Phi(T_k(\Sigma)) \rangle$ is a solution of $\Sigma$ in $\mathcal{A}(X)$ (and in fact in $A_\omega^1(X)$).

(4.1) **Theorem 1.** $\Sigma$ has one and only one solution in $M^\infty(F)^k$ denoted by $\langle T_1(\Sigma), \dots, T_k(\Sigma) \rangle$

2. The $k$-tuple $\langle \Phi(T_1(\Sigma)), \dots, \Phi(T_k(\Sigma)) \rangle$ is a solution of $\Sigma$ in $A_\omega(X)$.

(4.2) **Examples :**

<table>
  <tbody>
    <tr>
      <td>u<sub>0</sub> = a * u<sub>0</sub></td>
      <td>has solution T<sub>0</sub> in M<sup>∞</sup>(F) and solution a<sup>ω</sup> = Φ(T<sub>0</sub>) in A<sub>ω</sub>(X)</td>
    </tr>
    <tr>
      <td>u<sub>1</sub> = u<sub>1</sub> * a</td>
      <td>" " T<sub>1</sub> " " " a<sup>-ω</sup> = Φ(T<sub>1</sub>) " "</td>
    </tr>
    <tr>
      <td>u<sub>2</sub> = a * (u<sub>2</sub> * a)</td>
      <td>" " T<sub>2</sub> " " " a<sup>ω</sup> a<sup>-ω</sup> = Φ(T<sub>2</sub>) " "</td>
    </tr>
    <tr>
      <td>u = u * u</td>
      <td>" " U " " " ε = Φ(U) " "</td>
    </tr>
  </tbody>
</table>

where $T_0, T_1, T_2, U$ are defined in (2.2).

The equation $W = W(aW)$ has the solution $W$ in $M^\infty(F)$ where

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

Let $\mathcal{D}$ be the set of numbers of the form $m/2^n$ for $m,n \in \mathbb{N}$, $n>0$ and $0<m<2^n$ ordered by $\le$ as usual. Then $\Phi(W)$ is isomorphic to $\mathcal{D}$. To show this we define $\alpha : W_\# \to \mathcal{D}$ recursively by :

$$
\begin{align*}
\alpha(10) &= 1/2 \\
\alpha(0u) &= \alpha(u)/2 \\
\alpha(11u) &= 1/2 + \alpha(u)/2 \tag*{\text{)} for all } u \in W_\#
\end{align*}
$$
The following diagram should help the reader:

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

Recall that every countable dense linear order without greatest and least element is isomorphic to $D$ (and to $Q$).

The order type $<\mathcal{Z}, \leq>$ can be defined by the following equation where $u_1$ and $u_0$ are defined above:

$$z = u_1 * u_0.$$

(4.3) **Notations**: For a system $\Sigma$ with variables $u_1, \dots, u_k$, let

$$A_i(\Sigma) = \Phi(T_i(\Sigma)) \text{ for } i = 1, \dots, k. \text{ Let also}$$

$$\vec{A}(\Sigma) = \langle A_1(\Sigma), \dots, A_k(\Sigma) \rangle \text{ and } \vec{T}(\Sigma) = \langle T_1(\Sigma), \dots, T_k(\Sigma) \rangle.$$

**An open decision problem:**

P1: Is $A_1(\Sigma) \approx A_1(\Sigma')$ decidable for systems $\Sigma$ and $\Sigma'$?

By restricting $X$ to be singleton, P1 becomes interreducible with the following:

P2: Is $<L, lex> \equiv <L', lex>$ for rational prefix-free languages $L$ and $L' \subset \{0,1\}^* ?$

But in fact:

(4.4) **Proposition**: P1 and P2 are interreducible.

**Proof**: We only sketch the proof. Formal details are left to the reader.

Assume that $X = \{x_1, \dots, x_k\}$. Let $Y = \{a\}$ be a new alphabet. We transform two given systems $\Sigma$ and $\Sigma'$ into $\bar{\Sigma}$ and $\bar{\Sigma}'$ by considering $x_1, \dots, x_k$ as variables and adding the following equations:
$x_1 = w_1 * w_2$ (w_1 and w_2 are two new variables)

$x_k = w_1 * (w_1' * (\cdots * w_2))$ (with k occurrences of w_1 and one of w_2)

$w_1 = w_1 * a$

$w_2 = a * w_2$

Then $A_1(\Sigma) \cong A_1(\Sigma')$ if and only if $A_1(\bar{\Sigma}) \cong A_1(\bar{\Sigma}')$.

Then P2 is the same as P1 with $W = \{a\}$ can be proved with the techniques of [C]. $\square$

We now give a sufficient condition under which two systems $\Sigma$ and $\Sigma'$ have exactly the same solutions in $\mathcal{A}(X)$.

Recall that $t \sim t'$ means that $t$ and $t' \in \mathcal{M}(\mathcal{FUV})$ are the same up to parentheses. This equivalence has been defined in (3.4).

For two systems $\Sigma = \langle u_i = t_i \rangle_{1 \le i \le k}$ and $\Sigma' = \langle u'_i = t'_i \rangle_{1 \le i \le k}$, let $\Sigma \sim \Sigma'$ mean that $t_i \sim t'_i$ for $1 \le i \le k$.

(4.5) **Proposition** : *let $\Sigma \sim \Sigma'$. Then*

1) $\Sigma$ and $\Sigma'$ have the same solutions in $\mathcal{A}(X)$ (up to isomorphism)

2) $A_i(\Sigma) \cong A_i(\Sigma')$ for $i=1, \dots, k$.

The proof needs a more precise definition of a solution of a system. A k-tuple $\langle A_1, \dots, A_k \rangle \in \mathcal{A}(X)^k$ is a solution of $\Sigma$ in $\mathcal{A}(X)$ if there exist isomorphisms :

$\alpha_i : A_i \to t_i[A_1, \dots, A_k]$.

where $t_i[A_1, \dots, A_k]$ is the value of the right handside of the ith equation for $u_1 = A_1, \dots, u_k = A_k$. Formally, for $t \in \mathcal{M}(\mathcal{FUV})$ (and $V = \{u_1, \dots, u_k\}$), the arrangement $t[A] = t[A_1, \dots, A_k]$ is defined inductively by :

$$ \left\{ \begin{array}{ll} t[A] = t_1[A] \cdot t_2[A] & \text{if } t = t_1 * t_2 \\ = A_i & \text{if } t = u_i \\ = a & \text{if } t = a \in X \end{array} \right. $$
But $t[A']$ is canonically isomorphic to $\sigma(\Phi(t))$ where $\sigma: t_{\#} \to A(X)$ is the substitution such that $\sigma(w)=A_i$. if $t(w)=u_i$, otherwise undefined. We will rather use this second definition for $t[A']$.

**Proof of (4.5) :**

1) Let $A'$ be a solution of $\Sigma$, hence $A_i = \sigma_i(\Phi(t_i))$ where $\sigma_i$ is the substitution $\sigma_i: t_{i\#} \to A(X)$ such that $\sigma_i(w)=A_j$ if $t_i(w)=u_j$.

Let $\sigma'_i: t'_{i\#} \to A(X)$ such that $\sigma'_i(w)=A_j$ if $t'_i(w)=u_j$. Then the (unique) isomorphism : $\Phi(t_i) \to \Phi(t'_i)$ defines an isomorphism $\gamma_i : \sigma_i(\Phi(t_i)) \to \sigma'_i(\Phi(t'_i))$ (by (1.2), taking for $\delta_w$ the identity on $A_j$ whenever $t_i(w)=u_j$).

Hence $A$ is also a solution of $\Sigma'$ since $A_i$ is isomorphic to $\sigma'_i(\Phi(t'_i)) = t'_i[A_1, \dots, A_k]$.

2) Will be proved as a corollary of (4.9) below. $\square$

It follows that stars and parentheses can be omitted in the writing of systems which are to be solved in $\tilde{A}(X)$. A system will be (sometimes) simply a list of equations, $\Sigma = \langle u_i = t_i \mid 1 \le i \le k \rangle$ where $t_i \in (X \cup \{u_1, \dots, u_k\})^*$ hence a context-free grammar with only one term in the right hand side of each equation.

(4.6) We now want to show that $A'(\Sigma)$ is in a certain sense *minimal* among all solutions of $\Sigma$.

It will not be possible to consider isomorphic arrangements as equal. Hence we must redefine our concept of a solution :

Let $\Sigma = \langle u_i = t_i \mid 1 \le i \le k \rangle$. A *solution* of $\Sigma$ is a k-tuple $\langle (A_1, \alpha_1), \dots, (A_k, \alpha_k) \rangle$ where $A_i \in A(X)$ and $\alpha_i$ is an isomorphism : $A_i \to t_i[A']$

A *morphism of solutions* of $\Sigma$ is a k-tuple $\beta = (\beta_1, \dots, \beta_n)$ : $\langle (A_1, \alpha_1), \dots, (A_k, \alpha_k) \rangle \to \langle (A'_1, \alpha'_1), \dots, (A'_k, \alpha'_k) \rangle$ such that

1) $\beta_i : A_i \to A'_i$ is a morphism,

2) if we denote by $t_i[A']$ the canonical morphism : $t_i[A'] \to t_i[A']$ then the following diagram is commutative :

<figure><img src="image_14.png" /></figure>
The canonical morphism $t_i[\beta] : \mathcal{B}(\beta(t_i)) \to \sigma'(\Phi(t_i))$ is defined in (1.2). The general definition of (1.2) reduces to the following one in this special case :

$$ (4.6.1) \quad t_i[\beta](w,x) = (w, \beta_j(x)) \quad \text{if } t_i(w) = u_j \quad (\text{which implies } x \in A_j^\omega) $$

$$ (4.6.2) \quad t_i[\beta](w,1) = (w,1) \quad \text{if } t_i(w) = a \in X. $$

(4.7) **Example** : let $\Sigma$ be the following equation :

$$ u = a * u $$

Two of its solutions are $(A,\alpha) = (a^\omega, \alpha)$ and $(A',\alpha') = (a^\omega a^\omega, \alpha')$.

The isomorphisms $\alpha$ and $\alpha'$ are best shown by the following diagrams :

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

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

Let us consider the following two morphisms $\beta, \beta'$ : $A \to A'$ :

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

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

It is not difficult to see that $\beta$ is a morphism of solutions : $(A,\alpha) \to (A',\alpha')$ but $\beta'$ is not since $\alpha' \circ \beta' \neq (a.\beta') \circ \alpha$ as shown by the following :

<figure><img src="image_19.png" /></figure>
(4.8) Going back to the general case we define morphisms $\gamma_i$, $1 \le i \le k$ such that $\langle (A_1(\Sigma), \gamma_1), \dots, (A_k(\Sigma), \gamma_k) \rangle$ is a solution of $\Sigma$ in the new sense of (4.6).

Let us recall that $A_i(\Sigma) = \Phi(T_i)$ where $T_i = T_i(\Sigma)$ and
$T_i = t_i[T_1/u_1, \dots, T_k/u_k]$ for all $i=1, \dots, k$.

It follows that :

$$
\begin{gather*}
(4.8.1) \quad T_{i\#} = t_{i\#}^{(1)} \cdot T_{1\#} \cdot \dots \cdot T_{i\#}^{(k)} \cdot T_{k\#} \cdot U^{(k)} \cdot U_{i\#}^{(x)} \\
\text{where } t_{i\#}^{(j)} = \{w \in \text{Dom}(t_i) / t_i(w) = u_j\} \\
t_{i\#}^{(x)} = \{w \in \text{Dom}(t_i) / t_i(w) \in X\}.
\end{gather*}
$$

There exists a bijection $\gamma_i : T_{i\#} \to t_{i\#}^{(1)} \times T_{1\#} \times \dots \times T_{i\#}^{(k)} \times T_{k\#} \times U_{i\#}^{(x)} \times \{1\}$ such that $\gamma_i(w) = w$ if $w \in t_{i\#}^{(x)}$ and $\gamma_i(w) = (w_1, w_2)$ if $w = w_1 w_2$ for some $w_1 \in t_{i\#}^{(j)}$ and $w_2 \in T_{j\#}$ (check that $\gamma_i$ is a well defined mapping).

But the codomain of $\gamma_i$ is nothing else than $|\sigma(t_i)|$ where $\sigma(w) = \Phi(T_j)$
if $t_i(w) = u_j$ and $w \in \text{Dom}(t_i)$.

That $\gamma_i$ is indeed an isomorphism : $\Phi(t_i) \to t_i[\Phi(T_1), \dots, \Phi(T_k)]$ is left to the reader.

We can now state :

(4.9) **Theorem** : $\langle (A_1(\Sigma), \gamma_1), \dots, (A_k(\Sigma), \gamma_k) \rangle$ is initial among the solutions of $\Sigma$.

Initial means that for every solution $\langle (D_1, \delta_1), \dots, (D_k, \delta_k) \rangle$ of $\Sigma$
there exists one and only one morphism $\beta$ from $\langle (A_1(\Sigma), \gamma_1), \dots, (A_k(\Sigma), \gamma_k) \rangle$ to it.

**Proof** : Let us assume first the existence of $\vec{\beta} = \langle \beta_1, \dots, \beta_k \rangle$ such that the following diagram commutes :

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

Then $\beta_i$ is a mapping : $T_{i\#} \to |D_i|$.
For $w \in t_{i\#}^{(x)}$, $\gamma_i(w) = w_i$ and $t_i[\beta](w_1) = (w_1)$ by (6.2)) whatever $\beta$ might be.
Hence, we must have $\beta_i(w) = \delta_i^{-1}((w_1))$.

If $w=w_1w_2$, $w_1 \in t_{i\#}^{(j)}$ and $w_2 \in t_{j\#}^{(k)}$, then $t_i[\beta](\gamma_i(w)) = t_i[\beta](w_1,w_2) = (w_1, \beta_j(w_2))$ by (4.6.1) and we must have $\beta_i(w) = \delta_i^{-1}((w_1, \beta_j(w_2)))$.

Let us now consider (4.8.1) : every $w \in T_{i\#}^{(x)}$ either belongs to $t_{i\#}^{(x)}$ or is $w_1w_2$ with $w_1 \in t_{i\#}^{(j)}$ and $w_2 \in t_{j\#}^{(k)}$ in a unique way and $|w_2|<|w|$. Every thing is in place for a proof by induction that the $\beta_i^{(j)}$'s are uniquely defined to make the diagrams commutative. Details are left to the reader. $\square$

In example (4.7), $(A,\alpha)$ is the initial solution, $(A',\alpha')$ is another solution and $\beta$ is the unique morphism : $(A,\alpha) \to (A',\alpha')$. As an application of this result, we can give a simple categorical proof of proposition (4.5.2), namely that the initial solutions of two schemes $\Sigma = \langle u_i=t_i \rangle_{1 \le i \le k}$ and $\Sigma' = \langle u'_i=t'_i \rangle_{1 \le i \le k}$ are isomorphic if $t_i \sim t'_i$ for all $i=1,\dots,k$ (i.e. $t_i$ and $t'_i$ are the same up to the associativity of $*$).

**Proof of (4.5.2) :** let $\langle A_i, \alpha_i \rangle_{1 \le i \le k}$ be the initial solution of $\Sigma$. Let $\gamma_i : t_i[\beta] \to t'_i[\beta]$ be as in the proof of (4.5.1) and $\alpha'_i = \gamma_i \circ \alpha_i$. We are to prove that $\langle A_i, \alpha'_i \rangle_{1 \le i \le k}$ is an initial solution of $\Sigma'$. It is clearly a solution. Let $\langle D'_i, \delta'_i \rangle_{1 \le i \le k}$ be an arbitrary solution of $\Sigma'$, let $\eta_i : t'_i[\beta'] \to t_i[\beta]$ be the canonical isomorphism of (4.5.1), then $\langle D'_i, \delta'_i \rangle_{1 \le i \le k}$ where $\delta'_i = \eta_i \circ \delta_i$ is a solution of $\Sigma$, hence there exists a unique $\beta_i : A_i \to D'_i$ such that

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

But also :

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

since $\gamma_i$ and $\eta_i$ are canonical (details are left to the reader) and $\beta_i$ is the
unique morphism : $A_i \to D'_i$ such that the following diagram commutes :

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

Hence $(A_i, \alpha'_i)$ is initial in the category of solutions of $\Sigma'$. Since initial elements in a category are isomorphic $A_i(\Sigma) \cong A'_i(\Sigma)$ for $i=1, \dots, k$. QED

# V - QUASI-RATIONAL SYSTEMS OF EQUATIONS

(5.1) Let $\Sigma$ be of the form :

$$ \left\{ \begin{array}{l} u_1 = t_1 \\ \cdot \\ \cdot \\ u_k = t_k \end{array} \right. $$

Then $\Sigma$ is said to be *quasi-rational* if for all $u_i$ and $t \in M(FUV)$ such that $u_i \xrightarrow{\Sigma} t$ then $u_i$ occurs at most once in $t$.

The system $\Sigma$ is *preordered* if there exists a preorder $\leq$ on $\{1, \dots, k\}$ such that for all $i$ and $j$ :

(i) if $u_j$ occurs in $t_i$ then $j \leq i$ (i.e. $j$ is less than $i$ w.r.t. $\leq$),

(ii) if $u_j$ and $u_l$ have distinct occurrences in $t_i$ (and possibly $j=l$) and $j \leq i$ and $l \leq i$ do not hold together.

**Remark :** Since we write the $t_i$'s without stars and parentheses, a quasi-rational system $\Sigma$ is also a quasi-rational context-free grammar, hence the terminology. But such systems, considered as tree grammars, to be solved in $M^\infty(F)$, are "less than rational", and they do not generate arbitrary rational infinite trees.

(5.2) **Proposition :** *A system $\Sigma$ is quasi-rational if and only if it is preordered.*

**Proof :** *Only if.* Let $\Sigma$ be quasi-rational. Take $j \leq i$ if $i=j$ or $u_i \xrightarrow{\Sigma} t$ for
some $t \in M(F, V)$ with at least one occurrence of $u_j$. Then $\theta$ is clearly a pre-order, (i) is satisfied; if $u_j$ and $u_\ell$ have distinct occurrences in $t_i$ and if $i\theta_j$ and $i\theta_\ell$ then one can find some $t \in M(F, V)$ such that:

$$u_i \to t_i \stackrel{*}{\to} t \text{ and } u_i \text{ occurs twice in } t.$$

Hence $\Sigma$ is not quasi-rational.

**If.** Let $\Sigma$ be preordered by $\theta$. By induction on the length of a derivation $u_i \stackrel{*}{\to} t$, one shows that if $u_j$ and $u_\ell$ have distinct occurrences in $t$ then $i\theta_j$ and $i\theta_\ell$ do not hold together. In particular, this implies that $\Sigma$ is quasi-rational. $\square$

(5.3) In order to solve explicitly quasi-rational systems, we define a certain kind of *regular expressions* (r.e.) involving exponentiation to $\omega$ and $-\omega$. Similar expressions are used in $\mathbb{M}$.

They are obtained by a finite number of applications of the following rules:

(i) every $a \in X$ is a r.e.,

(ii) $RR'$ is a r.e.,

(iii) $(R)^\omega$ is a r.e., and

(iv) $(R)^{-\omega}$ is a r.e., if R and $R'$ are r.e.

We also define *regular expressions with parameters* $U_1, \dots, U_k$ by adding following rule:

(v) $U_i$ is a r.e. for $i=1, \dots, k$.

By definitions (1.2) and proposition (3.1), every r.e. R has a well defined value in $A_\omega(X)$. A r.e. with parameters $U_1, \dots, U_k$ has a value in $A(X)$ for every assignment of values in $A(X)$ to the parameters. (The same symbol will denote a regular expression and its value).

An arrangement A is *quasi-rational* if $A = A_i(\Sigma)$ for some quasi-rational system $\Sigma$.

(5.4) **Theorem:*** *An arrangement is quasi-rational if and only if it is defined by some regular expression.*

**Proof:** We assume in this proof that systems are written without stars and parentheses. The "if" part is proved by induction on the structure of regular expressions:

(i) if $R = a \in X$, then $R = A_1(\Sigma)$ where $\Sigma = \langle u_1 = a \rangle$,

(ii) if $R = R_1 R_2$, one constructs $\Sigma_1 = \langle u_1 = t_1, \dots, u_k = t_k \rangle$,
$\Sigma_2 = \langle u_{k+1} = t_{k+1}, \dots, u_l = t_l \rangle$ such that $R_1 = A_1(\Sigma_1)$, $R_2 = A_{k+1}^{(\Sigma_2)}$, then
$R = A_{l+1}^{(\Sigma)}$ where $\Sigma = \Sigma_1 \cup \Sigma_2 \cup \langle u_{l+1} = u_1 u_{k+1} \rangle$

(iii) if $R = R_1^\omega$, where $R_1 = A_1(\Sigma_1)$, then $R = A_{k+1}^{(\Sigma)}$ where
$\Sigma = \Sigma_1 \cup \langle u_{k+1} = u_1 u_{k+1} \rangle$ (easy lemma left to the reader) and similarly :

(iv) if $R = R_1^{-\omega}$, then $R = A_{k+1}^{(\Sigma)}$ where $\Sigma = \Sigma_1 \cup \langle u_{k+1} = u_{k+1}^{\omega} \rangle$.

One easily checks at each step of this construction that one
gets preordered systems.

Let $\Sigma$ be preordered by $\leq_0$ and $A = A_1(\Sigma)$.

For each $i \in \{1, 2, \dots, k\}$ one can find $t_i' \in M(FUV)$ such that :

(1) $t_i \stackrel{*}{\to} t_i'$,

(2) if $u_j$ occurs in $t_i'$ then $j \le i$,

(3) if $u_j$ occurs in $t_i'$ and $i \le j$ then $i = j$,

(4) $u_i$ has at most one occurrence in $t_i'$.

Let $\Sigma' = \langle u_1 = t_1', \dots, u_k = t_k' \rangle$ ; then $T_i(\Sigma) = T_i(\Sigma')$ and $A_i(\Sigma) = A_i(\Sigma')$
for all $i=1, \dots, k$.

We now define $R_i$ such that $R_i = A_i(\Sigma')$ for $i=1, \dots, k$.

We define $R_i$ in terms of the $R_j$'s such that $j \le i$ and $i \ne j$.

(α) if $t_i'$ contains no occurrence of $u_i$, then by (2)
$t_i'$ contains only occurrences of $u_j$ such that $j \le i$ and $i \ne j$.
Then we take $R_i = t_i'[R_j/u_j]$, the substitution of $R_j$ to
each occurrence of $u_j$ in $t_i'$ for all $j$.

(β) if $t_i'$ contains an occurrence of $u_i$, then we obtain
three cases :

$$
(\beta.1) \quad t_i' = s u_i s'
$$

$$
(\beta.2) \quad t_i' = u_i s'
$$

$$
(\beta.3) \quad t_i' = s u_i
$$

where s and s' only contain occurrences of $u_j$ such that
$j \le i$ and $j \ne i$. Let $S = s[R_j/u_j]$ and $S' = s'[R_j/u_j]$ (same
notation than in case (α)). We then take $R_i = S^\omega S'^{-\omega}$ in
the first case, $R_i = S'^{-\omega}$ in the second and $R_i = S^\omega$ in
the third.

A formal proof that $R_i = A_i(\Sigma)$ for all $i=1, \dots, k$ is omitted. $\square$
(5.5) **Example**: Let us define $R_1 = A_1(\Sigma)$ where

$$ \Sigma \left\{ \begin{array}{l} u_1 = au_2 u_3 \\ u_2 = u_3 b u_1 \\ u_3 = u_4 u_3 b \\ u_4 = au_5 \\ u_5 = ab \end{array} \right. $$

$R_5 = ab$

$R_4 = aab$

$R_3 = (aab)^{\omega_b^{-\omega}}$

The first equation is transformed into

$u_1 = au_3 bu_1 u_3$

$$R_1 = (a(aab)^{\omega_b^{-\omega}})^{\omega_b^{\omega}} ((aab)^{\omega_b^{-\omega}})^{-\omega} = (a(aab)^{\omega_b^{-\omega}})^{\omega_b^{\omega}} ((aab)^{\omega_b^{-\omega}})^{-\omega}$$

$$R_2 = (aab)^{\omega_b^{-\omega}} (a(aab)^{\omega_b^{-\omega}})^{\omega_b^{\omega}} ((aab)^{\omega_b^{-\omega}})^{-\omega}.$$

By using regular expressions with parameters, we can also define *all* solutions of a given quasi-rational system $\Sigma$. In order to do so we state without proof the following :

(5.6) **Lemma**: Let $A, A' \in A(X)$. An arrangement $U$ satisfies the equation $U = AUA'$ (resp. $U = UA'$) (resp. $U = AU$) if and only if $U = A^{\omega}BA'^{-\omega}$ (resp. $U = BA'^{-\omega}$) (resp. $U = A^{\omega}B$) for some $B \in A(X)$.

Given $\Sigma$ as in the second part of the proof of (5.5), let $u_i$ be a parameter for all $i \in \{1, \dots, k\}$ such that $t_i'$ contains an occurrence of $u_i$ let $P$ be this set of parameters.

We define regular expressions $\bar{R}_i$ with parameters in $P$ in the same way as before except in case (β) where we take :

$$\bar{R}_i = S^{\omega} U_i S'^{-\omega} \quad \text{in subcase (β.1),}$$

$$\bar{R}_i = U_i S'^{-\omega} \quad \text{in subcase (β.2),}$$

$$\bar{R}_i = S^{\omega} U_i \quad \text{in subcase (β.3).}$$

We obtain with lemma (5.6) and the above notations :

(5.7) **Theorem**: The class of solutions of $\Sigma$ is exactly the class of values of $\langle \bar{R}_1, \dots, \bar{R}_k \rangle$ where parameters range over $A(X)$.
(5.8) **Example 5**: Let $\Sigma$ be defined in example (5.5):

$$R_5 = ab$$

$$R_4 = aab$$

$$R_3 = (aab)^{\omega} U_3 b^{-\omega}$$

$$R_1 = (a(aab)^{\omega} U_3 b^{-\omega})^{\omega} U_1 ((aab)^{\omega} U_3 b^{-\omega})^{-\omega}$$

$R_2$ is left to the reader.

Hence, the general solution of $\Sigma$ depends on two parameters, $U_1$ and $U_3$.

We conclude this section by another characterization of quasi-rational systems.

Let $T \in M^\infty(F)$. An *infinite branch* of $T$ is a word $w \in \{0,1\}^\omega$ such that $w[n]$ (i.e. the finite prefix of $w$ of length $n$) belongs to $\text{Dom}(T)$ for all $n \in \mathbb{N}$.

A tree is *sparse* if it has at most countably many infinite branches.

(5.9) **Proposition 6**: *A system $\Sigma$ is quasi-rational if and only if each* $T_i(\Sigma)$ *is sparse*.

**Proof 7**: Assume that $\Sigma$ is not quasi-rational. Then $u_i \xrightarrow{\ast} t$ with two occurrences of $u_i$ in $t$. Then $T_i(\Sigma)$ "contains as a subtree" the tree $W$ such that $W = W*W$. Its set of infinite branches is $\{0,1\}^\omega$ which is not countable.

Conversely, let $\Sigma$ be preordered. One shows that $T_i(\Sigma)$ is sparse by the same induction than for the construction of the $R_i$'s in the proof of (5.4) and the remark that if $T$ is the solution in $M^\infty(F)$ of an equation

$$T = t[T/v_0, T_1/v_1, \dots, T_n/v_n]$$

such that

$$ \begin{cases} T_1, \dots, T_k \text{ are sparse,} \\ t \in M(FU\{v_0, \dots, v_n\}), \ t \neq v_0 \text{ and } v_0 \text{ has one occurrence in } t, \end{cases} $$
then $T$ is sparse. $\square$
# VI. CONCLUSION :

Many problems are left open.

1. Deciding whether $A_1(\Sigma) \simeq A_1(\Sigma')$ for systems $\Sigma$ and $\Sigma'$.

2. Find a complete system of axioms and rules for the equality of regular expressions.

3. Extend regular expressions to represent the solutions of arbitrary systems.

4. What can be said of the set of arrangements $A(G)$ which are generated by a context-free grammar $\mathcal{G}$ of the equivalence relation on grammars defined by $A(G) = A(G')$ ? or $A(G) \simeq A(G')$ (is there any difference) ?

I thank J.M. Steyaert for his comments on a first draft of this paper and Chantal Le Moal for the typing.
References :

[C] B. Courcelle, "A representation of trees by languages", to appear in T.C.S. (also thèse d'Etat, (1976), Univ. Paris 7).

[C,N] B. Courcelle, M. Nivat : "Algebraic Families of Interpretations", 17<sup>th</sup> Symp. on F.O.C.S., 1976, Houston.

[L] D. Lehmann "Categories for fixpoint semantics", 17<sup>th</sup>, Symp. on F.O.C.S. (1976).

[M] R. McNaughton "Testing and generating infinite sequences by a finite automaton". Inf and Cont 9 (66) pp. 521-530.

[N] N. Nivat : "Mots infinis engendrés par une grammaire algébrique", to appear in RAIRO.

[T] J.W. Thatcher "Generalized<sup>2</sup> Sequential Machines Maps", JCSS4 (70), pp. 339-367.