RIA
laboria

laboratoire de recherche
en informatique
et automatique

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

Sur les relations rationnelles
fonctionnelles
entre monoïdes libres

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

M.P. Schützenberger

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

Rapport de Recherche n° 153

Janvier 1976
SUR LES RELATIONS RATIONNELLES FONCTIONNELLES
ENTRE MONOÏDES LIBRES

M.P. Schützenberger

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

Résumé :

On applique la théorie de S. Eilenberg au moyen de la méthode des transducteurs de M. Nivat pour caractériser les relations rationnelles dont le nombre des mots de l'image de chaque mot est bornée.

Abstract

Using Nivat's concept of transducer, one applies Eilenberg's theory to the special case of rational relations ρ such that $\text{Sup} \{\text{Card}(ap) : a \in A^*\}$ is bounded.
## Introduction

1. L'objectif du présent travail est de préciser un point de la théorie des relations rationnelles entre monoïdes libres développée par S. Eilenberg dans le chapitre IX de son traité [1] auquel nous ferons de larges emprunts et auquel nous nous permettons de renvoyer le lecteur pour la motivation et un historique du sujet.

On rappelle qu'étant donnés deux monoïdes libres $A^*$ et $B^*$ ( engendrés respectivement par les alphabets finis $A$ et $B$ ), une relation rationnelle $\rho : A^* \to B^*$ est une application de $A^*$ dans le semi-anneau $2^{B^*}$ des parties de $B^*$ dont le graphe est une partie *rationnelle* ( [1] chapitre VII ) du produit direct $A^* \times B^*$. Ces relations forment elles-même un semi-anneau si l'on définit la somme $\sigma = \rho + \rho'$ et le produit $\pi = \rho\rho'$ de deux d'entre elles par la condition que pour chaque mot $a$ de $A^*$ on ait :

$$ \sigma a = a\rho + a\rho' \text{ et } a\pi = \{(a'\rho)a''\rho' : a',a'' \in A^*, a = a'a''\} $$

( où $(a'\rho)(a''\rho')$ désigne le produit dans le semi-anneau $2^{B^*}$ des parties $a'\rho$ et $a''\rho'$ de $B^*$ ). La restriction d'une relation $\rho$ à une partie $D$ de $A^*$ est la relation $\rho' : A^* \to B^*$ telle que pour chaque mot $a$ on ait $a\rho' = a\rho$ ou $= 0$ selon que $a \in D$ ou non. Nous la désignerons par $D \cap \rho$ ce qui abrège sans risque la notation plus explicite $(D \times B^*)_{\rho}$. Quand $\rho$ est une relation rationnelle il en est de même de $D \cap \rho$ si $D$ est une partie *reconnaissable* ( [1] , chapitre IV et IX ), c'est à dire si il existe un morphisme $\phi$
de $A^*$ dans un monoïde fini pour lequel $D = D\phi\phi^{-1}$. Nous utiliserons constamment
le fait que les domaines des relations rationnelles sont des parties reconnais-
sables.

Pour toute partie X d'un monoïde nous poserons $||X|| = \text{Card}(X)$ et nous définirons
le norme $||\rho||$ d'une relation $\rho$ par $||\rho|| = \text{Sup} \{ ||a\rho|| : a \in A^* \}$.

Un role particulier est joué dans la théorie de Eilenberg par les relations
rationnelles de norme 1 que nous appelerons ici *fonctionnelles* puisqu'elles se ré-
duisent à des fonctions de $A^*$ dans $B^*$. Notre résultat principal peut s'énoncer ainsi
en désignant, comme d'usage, par $|a|$; la longueur d'un mot a.

**Propriété :** Toute relation rationnelle $\rho : A^* \to B^*$ satisfait l'une des trois conditions suivantes :

(i) Il existe trois mots, $a',p,a'' \in A^*$ tels que l'on ait $||(a'p^n p'')\rho|| \ge 2^n$ pour tout $n \in N$.

(ii) Il existe des entiers $d$ et $K$ tels que l'on ait $||a\rho|| \le K(1+|a|^d)$ pour tout mot $a$ de $A^+$ et trois mots tels que $||(a'p^n a'')\rho|| \ge n+1$ ($n \in N$).

(iii) $\rho$ est une somme finie de relations rationnelles fonctionnelles ( et a donc une norme finie ).

Nous dirons qu'une relation $\rho$ est *cyclique* ssi son image est contenue dans le sous monoïde $h^*$ de $B^*$ engendré par un seul mot $h$. Une telle relation peut aussi être considérée comme une relation de $A^*$ dans le semi groupe additif des entiers $N$. On constatera que les relations satisfaisant (ii) ou (iii) sont les polynomes ($=$ sommes finies de produits finis) en les relations fonctionnelles et cycliques. J'ignore si toute relation cyclique et un polynome en des relations fonctionnelles.

La distinction entre (i) et (ii) introduit une certaine complication
et la preuve de la Propriété ne se trouvera achevée qu'à la fin de la Section III.

Dans la section II on examinera préalablement les relations fonction-
nelles dont on retrouve après Nivat et Eilenberg une représentation maniable. Ces
résultats sont nécessaires pour la preuve de la Propriété. Ils sont repris dans
la Section IV où l'on montre notamment que quand $\rho$ a une norme finie, on peut la repré-
senter comme la somme d'une relation de domaine fini et de r relations fonction-
nelles où $r = \text{Min} \{ ||A^n A^x \rho|| : n \in N \} = \varliminf_{n \to \infty} \{ ||a\rho|| : |a| \ge n \}$.
2. Dans tout ce travail nous employerons la méthode des *transducteurs* de M. Nivat, [3] c'est à dire que nous supposerons que la relation considérée $\rho$ est donnée par :

- un ensemble fini $\mathcal{Q}$ et un morphisme $(\text{de semi-groupe}) : \mu \to A^*$ dans le monoïde multiplicatif des $\mathcal{Q} \times \mathcal{Q}$ matrices à entrées dans le semi-anneau $\mathbb{Z}^{B^*}$;

- deux éléments distingués $q_1$ et $q_m$ de $\mathcal{Q}$ et la prescription que l'image $\mathcal{a}\mu$ de chaque mot $a$ de $A^*$ est l'entrée $\mathcal{a}\mu(q_1, q_m)$ de la matrice $\mathcal{a}\mu$. Ceci sera noté $\rho = \mu(q_1, q_m)$ et on dira que $(\mu, q_1, q_m)$ est un *transducteur* de $\rho$.

Rappelons que le *support* d'une $\mathcal{Q} \times \mathcal{Q}$-matrice $\mathcal{m}$ est l'ensemble $\mathcal{m}^*$ des $(q, q') \in \mathcal{Q} \times \mathcal{Q}$ pour lesquels $\mathcal{m}(q, q') \neq 0$. Suivant Eilenberg ([1], p.23) un transducteur $(\mu, q_1, q_m)$ sera dit émondé ("trim") ssi pour chaque $q \in \mathcal{Q}$ il existe des mots $a, a'$ tels que $(q_1, q) \in \mathcal{a}\mu^*$ et $(q, q_m) \in \mathcal{a}\mu^*$. On pourra toujours se ramener au cas où cette condition est satisfaite. En effet, si elle ne l'était pas il existerait une partie propre $\mathcal{Q}'$ de $\mathcal{Q}$ contenant $q_1$ et $q_m$ telle que la restriction $\mu'$ de $\mu$ à $\mathcal{Q}' \times \mathcal{Q}'$ soit encore un morphisme et que $\rho = \mu'(q_1, q_m)$.

Supposant maintenant que $(\mu, q_1, q_m)$ est émondé, la relation $\rho=\mu(q_1, q_m)$ est rationnelle ssi chacune des entrées des matrices génératrices $\mathcal{a}\mu$ $(a \in A)$ est une partie rationnelle de $B^*$ ([1], chapitre VII). A son tour cette dernière condition est automatiquement remplie quand $\mu$ est un morphisme de $A^*$ dans le sous-semi anneau $\mathbb{F}_q = \mathbb{F}_q^*$ des $\mathcal{Q} \times \mathcal{Q}$ matrices dont les entrées sont des parties *finies* de $B^*$.

D'autre part, on sait qu'étant donnée une relation $\rho$ on peut toujours, choisir $\mu$ et deux états *distincts* $q_1$ et $q_m$ de telle sorte que $\rho = \mu(q_1, q_m)$. Si tel est le cas, on voit facilement qu'on peut prendre pour $\mu$ un *morphisme de monoïde* (et non pas seulement de semi-groupe) ssi $\rho = 0$ où $1 = \lambda^*$ désigne l'élément neutre de monoïde $A^*$ (ou de n'importe quel autre monoïde, d'ailleurs).

Nous nous ramenons au cas où ces hypothèses simplificatrices peuvent être faites au moyen de l'énoncé (connu) suivant (cf. [3] section 6). Comme d'usage $A^+ = A^* \setminus 1$ est le *semi-groupe libre* engendré par $A$.

I.1. Soit $\rho : A^* \to B^*$ une relation rationnelle et $D = \{ a \in A^+ : \|\rho a\| < \infty \}$.

On a $\rho = \rho_1 + \rho_+ + \rho_{inf}$ où les trois relations $\rho_1, \rho_+$ et $\rho_{inf}$ définies par $\rho_1 = \{1\} \cap \rho; \rho_+ = D \cap \rho; \rho_{inf} = (A^+ \setminus D) \cap \rho$ sont rationnelles.

*Preuve* : Le singolet $\{1\}$ et son complément $A^+$ sont des parties reconnaissables de $A^*$.
Donc $\rho_1 = \{1\} \cap \rho$ et $\rho' = \Lambda^+ \cap \rho$ sont deux relations rationnelles et nous pouvons supposer désormais que $\rho = \rho'$. Soit donc $\rho = \mu(q_1, q_m)$. A chaque lettre a de $A$ nous associons une $Q \times Q$ matrice $a_\mu$ par la condition que pour tout $q_1 q'_1 \in Q$ on ait :
$$a_\mu(q, q') = a_\mu(a, a') \quad \text{si} \quad \|a_\mu(q, q')\| < \infty;$$
$$= 0 \text{ sinon.}$$

Cette application $\mu' : A \to \tilde{\mathbb{F}}$ s'étend de façon naturelle à un morphisme $\mu$ de $A^*$ dans $\tilde{\mathbb{F}}$. Comme les parties infinies de $B^*$ forment un idéal tant pour la structure additive que pour la structure multiplicative du semi-anneau $\tilde{\mathbb{F}}^{B^*}$, la relation ci-dessus reste vraie pour tous..les mots de $A^*$ et par conséquent $\rho_+ = \mu'(q_1, q_m)$ est une relation rationnelle dont le domaine est $D$.

Notons enfin que l'appartenance d'un mot quelconque a à l'ensemble $D$, ne dépend que du support de la matrice $a_\mu'$. Comme l'application $a_\mu' \mapsto a_\mu'$# est un morphisme de $A^*$ dans le monoïde *fini* des relations binaires sur $Q$, on voit que $D$ donc $\Lambda^+ \setminus D$, est une partie reconnaissable et enfin que la relation $\rho_{inf} = (\Lambda^+ \setminus D) \cap \rho$ est rationnelle.

Q.E.D.

En raison du but poursuivi ici il sera loisible de supposer désormais que la relation étudiée $\rho$ se réduit à $\rho_+$ c'est à dire que $1_\rho = 0$ et que $a_\rho$ est toujours une partie finie de $B^*$. On pourra par conséquent la considérer comme donnée par un transducteur $\mu$ ($q_1, q_m$) où $\mu$ est un morphisme de monoïde de $A^*$ dans $\tilde{\mathbb{F}}$.

### I.2. Soit $\rho$ une relation rationnelle telle que $a_\rho$ soit fini pour tout mot $a$ et que $1_\rho = 0$. Il existe un entier $K$ tel que l'on ait identiquement

$$\|a_\rho\| \le K^{|a|} \quad (a \in A^*).$$

Si $\rho$ est cyclique cette inégalité peut être remplacée par

$$\|a_\rho\| \le K |a| \quad (a \in A^*).$$

Enfin si $\rho$ est un polynome en des relations cycliques ou fonctionnelles, il existe un $d \in \mathbb{N}$ pour lequel

$$\|a_\rho\| \le K |a|^d \quad (a \in A^*).$$

**Preuve** : On vient de voir que $\rho$ peut être définie par un morphisme $\mu$ de $A^*$ dans $\tilde{\mathbb{F}}$.
Soit L le maximum de la longueur des mots de $B^*$ figurant dans les entrées des matrices génératrices $a_\mu$ ($a \in A$). Pour chaque mot $a$ de $A^*$, tous les mots figurant dans $a_\mu$ sont de longueur au plus $|a|L$. Ceci établit la première inégalité puisque posant $m = \text{Card}(B)$, le monoïde $B^*$ a exactement $(m-1)^{-1}(m^{n+1}-1)$ mots de longueur au plus $n$ pour chaque $n \in N$. Le même argument donne la seconde inégalité puisque quand $\rho$ est cyclique son image est contenue dans un sous monoïde cyclique $h^*$ de $B^*$ qui contient au plus $n+1$ mots de longueur $\le n|h|$.

Considérons maintenant un produit $\rho = \rho_1\rho_2\cdots\rho_k$ où chaque $\rho_i$ est une relation cyclique ou fonctionnelle. L'image $a_\rho$ d'un mot quelconque est par définition la somme des produits $(a_1\rho_1)(a_2\rho_2)\cdots(a_k\rho_k)$. Le nombre de ces factorisations est borné par une fonction sur toutes les factorisations $a = a_1a_2\cdots a_k$ du mot $a$ polynomiale de degré $k-1$ en $|a|$ ce qui établit la dernière inégalité.

Q.E.D.
## II. Le cas fonctionnel

Nous considérons un morphisme de monoïde $\mu$ de $A^*$ dans le semi-anneau $E$ qui a été défini dans l'introduction et $q, q' \in Q$ étant une paire fixe quelconque, nous établissons d'abord le fait suivant :

II.1 On a $\|a\mu(q, q')\| \le 1$ pour tout $a \in A^*$ ssi cette inégalité est vérifiée par tous les mots de longueur au plus $1+2m$ ($m-1$) où $m = \text{Card}(Q)$.

**Preuve** : Il suffit de vérifier que si $a = a_1 a_2 \dots a_n$ ($a_1, a_2, \dots, a_n \in A$) est un mot de longueur minimum $|a| = n$ pour lequel $\|a\mu(q, q')\| \ge 2$, l'hypothèse $n > L = 1+2m$ ($m-1$) conduit à une contradiction.

Comme $|a|$ est minimum, il existe au moins une suite de $n-1$ paires $(q_j, q'_j)$ ($1 \le j \le n-1$ ; $q_j \ne q'_j$) telles que posant $q_0 = q'_0 = q$, $q_n = q'_n = q$ et $b_j = a_j \mu(q_{j-1}, q_j)$, $b'_j = a_j \mu(q'_{j-1}, q'_j)$, les produits $b = b_1 b_2 \dots b_n$ et $b' = b'_1 b'_2 \dots b'_n$ (qui sont des éléments de $a\mu(q, q')$) sont deux mots distincts.
Supposons $n > L$. Il existe trois indices $i < j < k$ tels que
$( q_i, q'_i ) = ( q_j, q'_j ) = ( q_k, q'_k )$ ce qui détermine une factorisation
$a = f_1 f_2 f_3 f_4 \quad \text{où} \quad f_1 = a_1 a_2 \cdots a_i ; f_2 = a_{i+1} \cdots a_j ; f_3 = a_{j+1} \cdots a_k ;
f_4 = a_{k+1} \cdots a_n$. Nous définissons de même les factorisations $b = g_1 g_2 g_3 g_4$
et $b' = g'_1 g'_2 g'_3 g'_4$ en remplaçant dans les expressions ci-dessus les $a_s$ par
les $b_s$ ou les $b'_s$. ( $1 \le s \le n$ )

Par construction on a les inclusions :
$g_1g_4, g'_1g'_4 \in ( f_1f_4)\mu(q,q') ; g_1g_2g_4, g'_1g'_2g'_4 \in ( f_1f_2f_4)\mu(q,q') ;$
$g_1g_3g_4, g'_1g'_3g'_4 \in ( f_1f_3f_4)\mu(q,q')$.

En raison du caractère minimal de $a$, on en déduit les équations
$$g_1 g_4 = g'_1 g'_4 ; g_1 g_2 g_4 = g'_1 g'_2 g'_4 ; g_1 g_3 g_4 = g'_1 g'_3 g'_4 ;$$
où l'on peut supposer que, par exemple, $|g_1| \le |g'_1|$.

La première équation équivaut alors à l'existence d'un mot h tel que
$g'_1 = g_1h$ et $g_4 = hg'_4$. En reportant ceci dans les deux autres, on obtient après
simplification, $hg_2 = g'_2h$ et $hg_3 = g'_3h$.

Par conséquent $b = g_1g_2g_3g_4 = g_1g_2g_3hg'_4 = g_1g_2hg'_3g'_4 = g_1hg'_2g'_3g'_4 =$
$g'_1g'_2g'_3g'_4 = b'$ en contradiction avec $b \neq b'$.

Q.E.D.

2. Nous dirons qu'un morphisme $\mu$ est *fonctionnel* ssi la norme
$$ \|a\mu\| = \operatorname{Max} \{ \|a\mu(q,q')\| : (q,q') \in Q \times Q \} $$ de toutes les matrices $a\mu$ ($a \in A^*$)
est au plus 1. c'est à dire ssi toutes les entrées non nulles des matrices $a$ sont
des mots. On voit facilement que si $\mu$ est émondé et $\rho = \mu(q_1,q_m)$ l'hypothèse que
$\rho$ est fonctionnelle entraine qu'il en soit de même de $\mu$.

Nous nous proposons ici de déduire d'un morphisme fonctionnel $\mu$ un autre
morphisme $\lambda$, qui soit aussi un transducteur pour $\rho$ et qui possède la propriété supplé-
mentaire que son caractère fonctionnel résulte a priori de la structure des supports
$a\lambda#$ des matrices $a\lambda$ ($a \in A^*$) et des conditions initiales $\|a\lambda\| \le 1$ ($a \in A$).
C'est à quelques détails près la théorie développée par M. Nivat
([3], section 7). Au moyen d'une construction plus compliquée, nous re-
trouvons les *bimachines* de Eilenberg ([1], chapitre XI, 7) et une partie de
son théorème 7.1. Tout ceci sera utilisé pour étudier la norme d'un poly-
nome en des relations fonctionnelles dans les sections II.3 et IV.

Considérons d'abord un monoïde M de Q x Q matrices sur un semi-anneau
unitaire quelconque $\mathbb{B}$. Suivant M. Nivat ([3], section 7) nous dirons que M est
un *monoïde* $\{0,1\}$ ssi les supports $m#$ de ses éléments satifont la condition :
(ZU). Pour chaque paire $m,m' \in M$ et chaque entrée $(q,q') \in (mm')#$, il existe
exactement un $q'' \in Q$ pour lequel $(q,q'') \in m#$ et $(q'',q') \in m''$#.

La condition (ZU) a pour conséquence que seule la structure multipli-
cative de $\mathbb{B}$ (et le fait que O soit un élément neutre additif) interviennent dans
le calcul du produit de deux matrices de M. Il en résulte que si $\mu$ est un morphisme
de $A^*$ dans un sous monoïde $\{0,1\}$ de $\mathbb{F}$ il est fonctionnel ssi chacune des matrices
génératrices $a_\mu$ ($a \in A$) a norme au plus 1.

La condition ( ZU ) est satisfaite en particulier par les matrices dites
*monomiales* ( resp. *monomiales par colonne* ) caractérisées par la propriété que chaque
ligne ( resp. colonne ) a au plus une entrée non nulle. Nous aurons besoin de la géné-
ralisation suivante de cette notion. Disons qu'une matrice m est *semi-monomiale* ssi
son ensemble d'indice est un produit direct $I \times J$ et si en outre :

- Il existe une application partielle $i \to i.m$ de $I$ dans lui-même ;

- pour chaque $(i,i') \in I \times I$, la $J \times J$- sous matrice bloc $m_{ii'} = (m( ij,i'j' ))$ $(j,j' \in J)$ est une matrice monomiale par colonne quand $i' = i$.$m$ est nulle sinon.

Il est clair que l'ensemble des $(I \times J) \times (J \times I)$ matrices semi-monomiales
à entrées dans $\mathbb{B}$ forme un monoïde de matrices $\{0,1\}$.

Il en est de même dans le cas encore plus particulier où toutes les $J \times J$ sous-matrices blocs non nulles $m_{ii'}$ de chaque matrice $m$ ont le même support et où nous dirons alors qu'il s'agit d'un *semi-groupe de matrices de bimachines*. De façon équivalente, une $(I \times J) \times (I \times J)$ matrice $m$ est semi-monomiale ( resp. de bimachine ) ssi
elle appartient au produit en couronne ( resp. kroneckerien ) des J×J-matrices monomiales par colonne dans les I×I matrices monomiales.

Pour abréger, si Ket K' sont deux parties de I×J,nous désignons par
m ( K,K' ) pour chaque ( I×J ) × ( 1×J ) matrice m, la somme des entrées m ( ij,i'j' )
pour ( i,j ) ∈ K, ( i',j' ) ∈ K'.

II.2. Soit ρ = µ( q₁, q_m ) une relation rationnelle fonctionnelle. Il existe un ensemble fini V, un morphisme fonctionnel λ de A* dans le monoïde des ( V×Q ) × ( V×Q ) matrices semi-monomiales, un v₁ ∈ V et une partie V_m de V tels que l'on ait identiquement ap = aλ (v₁q₁, V_m q_m).

**Preuve :** En raison de l'hypothèse faite dans l'introduction que µ est émondé, le caractère fonctionnel de ρ implique que toutes les matrices aµ ( a ∈ A* ) soient de norme au plus 1.

Soient u le Q-vecteur égal à la ligne q₁ de la matrice 1µ et v₁ = u#
son support. Nous désignons par V l'ensemble des supports non nuls des lignes q₁ des
matrices aµ ( a ∈ A* ) ( c'est à dire des vecteurs u.aµ ) et nous introduisons une
action partielle V × A → V en définissant v'.a comme le support commun des vecteurs
u. ( a'aµ ) pour tous les mots a' tels que u ( a'aµ ) = v'. ( v' ∈ V ).

Nous construisons maintenant le morphisme λ en deux étapes. Tout d'abord
pour chaque lettre a ∈ A, v ∈ V et q ∈ Q tels que v,a(q) = 0, on peut choisir
arbitrairement un q' pour lequel on a à la fois v(q') ≠ 0 et aµ(q',q) ≠ 0. Ceci
permet de définir la Q × Q matrice aµ'v en posant aµ'(q'',q) = aµ(q'',q) ou = 0
selon que q'' = q' ou non.

Il est clair que toutes ces matrices $a\mu'_v$ sont monomiales par colonne et
de norme $\le 1$.

Ensuite nous définissons pour chaque lettre a la ( V × Q ) × ( V × Q )
matrice aλ par la condition que chacun de ses ( v,v' ) blocs aλ_{v,v'} ( v,v' ∈ V )
soit égal à aµ'_v où à 0 selon que v' = v.a ou non. Comme v → v.a est une action
partielle, les matrices aλ sont bien semi-monomiales et de norme au plus 1.
On vérifie directement ( par induction sur la longueur du mot ) que
pour chaque $a \in A^*$, la ligne $v_1q_1$ de la matrice $a\lambda$ est un vecteur dont les coordonnées non nulles ont pour index les paires $(v_1,a, q)$ où $v_1 \cdot a(q) \neq 0$.

Comme le vecteur $u.a\mu$ est par hypothèse un vecteur de norme au plus 1,
il en résulte instantanément que la ligne $v_1q_1$ de $a$ est le $V \times Q$ vecteur dont
chaque coordonnée ($v,q$) est égal à la coordonnée $q$ du vecteur $u.a$ quand
$v = v_1a$ et à 0 sinon.

Q.E.D.

3. Venons en aux bimachines. Modifiant très légèrement la définition de Eilenberg ([1], XI, 7) nous appelerons *bimachine* toute application partielle $v : A^* \times A^* \times A^* \to B^*$ satisfaisant les deux conditions suivantes :
(i) Pour tout $a_1, a_2, a_3, a_4 \in A^*$ on a $(a_1; a_2 a_3; a_4)v = (a_1; a_2; a_3 a_4)v$. $(a_1 a_2; a_3; a_4)v$.
(ii) Il existe un morphisme $\phi$ de $A^*$ dans un monoïde fini tel que pour tout $a, a_1, a_2, a_3, a_4 \in A^*$, les équations $a_1\phi = a_3\phi$ et $a_2\phi = a_4\phi$ impliquent $(a_1; a; a_2)v = (a_3; a; a_4)v$.

La relation définie par la bimachine $v$ est l'application partielle $\bar{v}$
envoyant chaque mot $a$ sur $(1,a,1)v$.

On vérifie facilement que, réciproquement, étant donné un morphisme $\phi$ de $A^*$
dans un monoïde fini $S$, toute application partielle $v' : S \times A \times S \to B^*$ définit la
restriction à $A^+$ d'une bimachine. En effet, l'identité (i) équivaut à la condition que
pour chaque mot $a = a_1 a_2 \dots a_n$ ($n \ge 1$, $a_1, a_2, \dots a_n \in A$) la valeur de $\bar{a}$ soit le
produit sur $i = 1,2,\dots,n$ des termes
$$ (( a_1 \dots a_{i=1} )\phi ; a_i ; ( a_{i+1} \dots a_n )\phi )v' $$
( avec la convention habituelle que pour $i=1$ ou $i=n$, le produit vide vaut 1).

La même identité détermine presque complètement les valeurs des $(a; 1; a)v$ qui ne peuvent être que $1 = l_{B^*}$ ou 0. Si ( comme on peut toujours le supposer ) $l_{\phi\phi}^{-1} = 1$, on peut choisir arbitrairement $\bar{l_v} = 1$ ou $\bar{l_{\bar{v}}} = 0$.

Enfin nous réserverons le nom de *morphisme de la bimachine* $v$ aux morphismes $\phi$ de $A^*$ dans un monoïde fini qui, en plus de (ii) satisfont $l_{\phi\phi}^{-1} = 1$ et la condition que pour chaque paire de mots $a_1, a_2 \in A^*$, le domaine $D'$ de la relation $\rho' \mapsto (a_1; a; a_2)v$ soit reconnaissable par $\phi$
( c'est à dire que $D' = D'\phi\phi^{-1}$). Comme $\rho'$ ne dépend que de $a_1$ et $a_2$ il n'existe qu'un nombre fini de tels domaines $D'$ et chacun d'eux est reconnaissable. Comme en outre $\{1\}$ est reconnaissable, on peut définir de façon naturelle pour tout morphisme $\phi' : A^* \to S'$ satisfaisant (ii) un morphisme $\phi = \phi' \times \psi : A^* \to S = S' \times T$ qui soit un morphisme de $\nu$.

### II.3.
Soit $\rho : A^* \to B^*$ une relation rationnelle fonctionnelle. Il existe un morphisme $\mu$ de $A^*$ dans un monoïde fini $S$ tel que $\rho$ puisse être définie par l'un quelconque des trois objets suivants :

- un morphisme $\mu$ de $A^*$ dans un monoïde $\{0,1\}$ de matrices tel que $\mu# = \phi$;

- une bimachine $\nu$ dont $\phi$ est un morphisme;

- un morphisme $\pi$ de $A^*$ dans un monoïde de bimachine de $(S \times S) \times (S \times S)$ matrices tel que $\phi = \pi#$.

**Preuve** : Nous partons d'un morphisme $\mu$ de $A^*$ dans un monoïde $\{0,1\}$ de $Q \times Q$ matrices de nome $\le 1$ telle que l'on ait identiquement $\alpha_0 = \alpha_\mu(q_1, q')$ pour une certaine paire $q_1 \in Q, q' \in Q$. Pour abréger nous désignons par $\phi$ le morphisme $\mu#$ envoyant chaque mot sur le support de la matrice $\alpha_\mu$.

Soient $a, a'$, et $a''$ trois mots dont le produit $aa'a''$ est dans le domaine de $\rho$. En raison de la propriété (ZU) et du caractère fonctionnel de $\rho$ il existe un et un seul triple $(q, q', q'') \subset Q \times Q \times Q'$ pour lequel les trois entrées $b = \alpha_\mu(q_1, q)$, $b' = a'\mu(q'_1, q')$ et $b'' = a''\mu(q'', q'')$ sont simultanément non nulles. On a alors $(aa'a'')\rho = bb'b'$. Il est clair que le mot $b'$ ne dépend que de la matrice $a'\mu$ et des supports $s = a\phi$ et $s'' = a''\phi$ des matrices $\alpha_\mu$ et $a''\mu$. Nous pouvons donc définir une application partielle $\nu'$ de $S \times A^* \times S$ dans $B^* (S = A^*\phi)$ en posant $b = (s;a';s'')\nu'$. Renant $a = a'' = 1$, le calcul précédent montre que $a'\rho = (1;a',1)\nu'$ pour tout mot $a'$ de $A^*$. Prenons maintenant $a$ et $a''$ quelconques et supposons $a' = a_2a_3 (a_2, a_3 \in A^*)$. On vérifie l'identité

$$ ( a\phi;a_2a_3;a''\phi )\nu' = ( a\phi;a_2 ; ( a_3a''\phi )\nu' . (( aa_2 )\phi;a_3;a''\phi )\nu' ) $$

qui montre que $\nu = (\phi^{-1}; \phi^{-1})\nu'$ est une bimachine dont $\phi$ est un morphisme.
Supposons maintenant donnés $v$ et $\phi$. Pour chaque $s,s'' \in S$, $a' \in A^*$ nous désignons par $(s;a';s'')v'$ la valeur commune de $(a;a';a'')v$ pour n'importe quels mots $a \in s\phi^{-1}$ et $a'' \in s''\phi^{-1}$. Nous associons à chaque mot à la $(S \times S) \times (S \times S)$ matrice $a\pi$ par la condition que pour tout $s_1,s',s_2,s'_2 \in S$ on ait $a\pi(s_1,s_2;s'_1s'_2) = (s_1;a;s'_2)v'$ ou $0$ selon que la double condition $s'_1 = s_1$, $(a\phi)$ et $s_2 = (a\phi).s'_2$ est ou non satisfaite.

On vérifie facilement que $\pi$ est un morphisme de $A^*$ dans un monoïde de bimachine (de norme $\le 1$) tel que $a\phi$ soit identiquement égal à $a\pi(1,S;S,1)$ et plus précisément à l'entrée $(1,s;1,1)$ où $s = a\phi$.

Le morphisme $\pi#$ coincide avec $\phi$ puisque l'on peut considérer $a \to a\pi#$ comme le produit kronekerien des représentations régulières gauches et droites de $A^*$ sur $S = A^*\phi$.

Ceci achève la preuve puisque tout monoïde de bimachine est un monoïde $\{0,1\}$.

Q.E.D.

On en déduit :

**Théorème (S. Eilenberg)** : Toute relation rationnelle fonctionnelle peut être réalisée par une bimachine.

**Preuve** : Ceci découle immédiatement de II.2. et de l'énoncé précédent.

Q.E.D.

4. Nous terminons cette section en considérant les produits de relations fonctionnelles.

II.4. Soit $\pi : A^* \to B^*$ un produit de relations rationnelles fonctionnelles. S'il n'est pas une somme finie de relations rationnelles fonctionnelles, il existe trois mots $a',p,a'' \in A^*$ tels que $\|(a'p^n a'')\pi\| \ge n+1$ pour tout entier positif $n$.
**Preuve :** Par induction sur le nombre de facteurs de produit, il suffit de considérer le cas de $\pi = \bar{\mu}.\bar{\nu}$ où $\bar{\mu}$ et $\bar{\nu}$ sont les relations fonctionnelles définies respectivement par les bimachines $\mu$ et $\nu$. Nous pouvons construire un morphisme $\phi$ de $A^*$ dans un monoïde fini S qui est simultanément un morphisme de $\mu$ et de $\nu$.
Soit $s \in S$ quelconque. Nous engendrons une bimachine $\mu_S$ en posant pour chaque $a \in A$ et $a_1, a_2 \in A^* : (a_1, a, a_2)_{\mu_S} = 0$ si $(a_1 a) \phi \neq s$ et $a_1 = 1 = (a_1, a_2, a_2)_{\mu}$ sinon.

Par définition, le domaine de la relation $\bar{\mu}_S$ est contenu dans $s\phi^{-1}$ et $\bar{\mu}_S$ est égale à $\bar{\mu}$ sur son domaine. La même construction s'applique à $\nu$ et nous avons donc que $\pi$ est égale à la somme finie des produits de relation $\bar{\mu}_S \bar{\nu}_S$, $(s,s' \in S)$. Nous pouvons donc supposer pour simplifier que $\mu = \mu_S$ et $\nu = \nu_T$ pour une certaine paire $s,t \in S \setminus 1$.

Si chacun des mots du domaine de $\pi = \mu\nu$ admet exactement une factorisation comme produit d'un mot de $s\phi^{-1}$ par un mot de $t\phi^{-1}$, le résultat est établi puisqu'alors $\pi$ est fonctionnelle. Dans le cas contraire, soit a un mot du domaine de $\pi$ ne satisfaisant pas les conditions d'unicité ci-dessus. Il admet une factorisation maximale unique

$$ a = a'p_1p_2 \dots p_n a'' \quad (p, \dots, p_n \in A^+, n \ge 1) $$

telle que l'on ait identiquement

$$ a'p_1 \dots p_i \in s\phi^{-1}, p_{i+1} \dots p_n a'' \in t\phi^{-1} \quad (0 \le i \le n). $$

Son image par $\pi$ est constituée par les $n+1$ mots

$$ b'q_1 \dots q_i r_{i+1} \dots r_n b'' \quad \text{où pour abréger on a posé } b' = (1;a';a'')_{\mu};b'' = (a';a'';1). $$

$$ q_j = (a';p_j;a'')_{\mu};r_j = (a';p_j;1)_{\nu} \quad (1 \le i \le n). $$

Désignons par $P^*$ le sous monoïde de $A^*$ formé des mots p tels que $s.p\phi = s$ et $p\phi$. $t = t$. C'est une partie reconnaissable de $A^*$ et nous pouvons tester si les relations rationnelles fonctionnelles

$\bar{\mu}' : p \mapsto (a'; p; a'')_{\mu}$ et $\bar{\nu} : p \mapsto (a'; p; a'')_{\nu}$ sont ou non égales sur $P^*$.
Dans le premier cas on a évidemment $q_i = r_i$ ( $1 \le i \le n$ ) et par conséquent $\pi$ est fonctionnelle. Dans le second cas soit $p \in P^*$ tel que $q = p\bar{u}' \ne p\bar{v}'$
L'image par $\pi$ du mot $a^p q^n a^n$ est formée des $n+1$ mots $b^p q^m r^n s^m b^m$ ( $0 \le m \le n$ ) que
l'on vérifie immédiatement être distincts puisque toute égalité entre deux
d'entre eux entrainerait une équation de la forme $q^k = r^k$ ($k \ge 1$) en con-
tradiction avec $q \ne r$,

### III. Le cas général

Q.E.D.

Nous continuons à faire tacitement l'hypothèse que chaque relation con-
sidérée donne une image *finie* à chaque mot de son domaine.

1. Une relation $\rho : A^* \to B^*$ sera dite _minimale_ ssi son domaine est $\{1\}$ ou une lettre de $A$. Elle sera dite _unitaire_ ssi elle peut être mise sous la forme $\rho = \mu(q,q)$ où $\mu$ est un morphisme de monoïde de $A^*$ dans un semi-anneau de $Q\times Q$ matrices et $q$ un élément quelconque de $Q$.

Il est clair que chaque relation unitaire $\rho$ satisfait $\ell\rho = 1$ et est sous-multiplicative en ce sens que $(\ell\rho)(\alpha'\rho) \subset (\alpha\rho)\rho$ pour tout $\alpha, \alpha' \in A^*$. Son domaine est donc un sous monoïde $P^*$ de $A^*$ (engendré par un ensemble minimal $P \subset A^+$, qui est vide ssi $\rho$ est _triviale_). On rappelle qu'un morphisme $\mu$ de $A^*$ dans un anneau de $Q\times Q$ matrices est _irréductible_ ssi $Q\times Q$ est l'union sur tous les mots a des supports des matrices $a\mu$. Par conséquent si $\rho = \mu(q,q)$ où $\mu$ est émondé au sens donné à ce terme dans l'introduction, le morphisme $\mu$ est irréductible, puisque pour tout $q' \in Q$ il doit exister $\alpha, \alpha' \in A^*$ tels que $(q,\alpha'q') \in a\mu\#$ et $(\alpha',q) \in a'\mu\#$.

Un produit $\rho = \rho_1 \rho_2 \cdots \rho_k$ de relations est _non ambigu_ ssi tout mot a de son domaine admet exactement une factorisation $a = a_1 a_2 \cdots a_k$ où chaque $a_i$ est dans le domaine de $\rho_i$. Plus généralement, un polynome $p = \rho'_1 + \rho'_2 + \cdots + \rho'_k$, est _non ambigu_ ssi tous les produits $\rho'_j$ sont non ambigu et ont des domaines deux à deux disjoints.

III.1. Soit $\rho = \mu(q_1, q_m)$ une relation rationnelle. Il existe un algorithme ne dépendant que du morphisme $\mu\#$ dans le monoïde des relations binaires sur $Q$ qui permet d'exprimer $\rho$ comme un polynome en des relations rationnelles minimales ou unitaires. Quand $\mu$ est un morphisme dans un monoïde $\{0,1\}$, le polynome obtenu est non ambigu.
**Preuve** : Nous pouvons supposer que $\mu$ est un morphisme de monoïde dans le semi-anneau $\mathbb{F}$ (de $Q \times Q$ matrices) et que $q_1 \neq q_m$. Soit $\rho_1$ la relation rationnelle unitaire $\mu(q_1, q_1)$.

Nous considérons d'abord le cas où $\rho_1$ est triviale (en ce sens que son domaine est $\{1\}$). Ceci équivaut à l'hypothèse que toutes les colonnes $q_1$ des matrices $a\mu$ ($a \in A^+$) sont nulles.

Soit $Q' = Q \backslash q_1$. Pour chaque $q \in Q'$, $a \in A$ nous posons $\rho_q' = \mu(q, q_m)$ et $\rho_{a,q} = \text{la relation de domaine } \{a\} \text{ égale à } a\mu(q_1, q)$ sur celui-ci. La relation $\rho$ est la somme sur tous les $q \in Q'$, $a \in A$ des produits non ambiguïs $\rho_{a,q} \rho_q'$ et chaque $\rho_{a,q}$ est une somme de relations minimales. Soit maintenant $\mu'$ la restriction de $\mu$ à $Q' \times Q'$, c'est à dire soit $a\mu'(q, q') = a\mu(q, q')$ pour chaque $a \in A^*, q, q' \in Q'$. En raison de l'hypothèse faite sur $\mu$ c'est un morphisme de $A^*$ dans un semi-anneau de $Q' \times Q'$ matrice et l'on a $\rho_q' = \mu'(q, q_m)$ pour chacun des $q$ de $Q'$.

Ceci conclut la preuve par induction sur $Card(Q)$ dans ce cas. En effet, quand $\mu$ est un morphisme dans un monoïde $\{0,1\}$ il en est encore de même de $\mu'$, chaque $\rho_{a,q}$ est minimale et la condition (ZU) montre que les produits $\rho_{a,q} \rho_{q'}^*$ ont des domaines disjoints.

Supposons maintenant que $\rho_1$ n'est pas triviale et définissons un morphisme $\mu''$ de $A^*$ dans $\mathbb{F}$ par sa restriction à $A$ en remplaçant par 0 toutes les entrées de la colonne $q_1$ de chaque matrice $a\mu$ ($a \in A$). La relation rationnelle $\rho'' = \mu''(q_1, q_m)$ satisfait les hypothèses du premier cas traité et il nous suffit donc de montrer que l'on a $\rho = \rho_1 \rho''$ où le produit est non ambigu quand $\rho$ est fonctionnelle puisque $A^* \mu''$ et un monoïde $\{0,1\}$ quand $\mu$ a la même propriété.

Soit donc $a = a_1 \cdots a_n$ ($n \ge 1$, $a_1, a_2, \cdots, a_n \in A$) un mot du domaine de $\rho$. L'entrée $a\mu(a_1, q_m)$ est la somme du produit des entrées $a_i(q_i', q_{i+1}')$ ($1 \le i \le n$) sur toutes les suites $(q_1' = q_1, q_2', \cdots, q_{n+1}' = q_m)$ de $n+1$ états $q_j'$ pour lesquelles
ces entrées sont toutes non nulles. Pour chaque telle suite il existe un plus grand indice $j$ ($1 \le j \le n$) tel que $q_j' = q_1$. Le produit correspondant est contenu dans le produit des deux entrées $(a_1, ..., a_j), \mu(q_1, q_j)$ et $(a_{j+1}, ..., a_n), \mu''(q_1, q_m)$. Donc $\rho_1\rho'' \subset \rho$, d'où l'égalité cherchée puisque réciproquement toute relation $a'\rho_1 \ne 0$, $a''\rho'' \ne 0$ implique ($a'a''\rho \ne 0$). Dans le cas fonctionnel, $a(q_1, q_m)$ est de façon unique un produit d'entrées non nulles et la factorisation $\rho = \rho_1\rho'$ est donc non ambigue.

Q.E.D.

On notera que la construction précédente de la suite $(q_1', ..., q_{n+1}')$ montre que quand $\rho$ est fonctionnelle le domaine $P^*$ de $\rho_1$ est engendré librement par l'ensemble générateur minimal $P$ de $P^*$.

2. Nous aurons besoin en outre de quelques résultats propres au semi-anneau $\mathbb{Z}^{B^*}$. Nous les extrayons sans démonstration du livre de A. Lentin ([2]).

Pour chaque mot $b \in B^*$ soit $\sqrt{b}$ le plus court mot $h \in B^*$ tel que $b$ soit contenu dans le monoïde cyclique $h^* = \sum_{0 \le n \le h} h^n$. On a évidemment $h = \sqrt{h}$, c'est à dire que $h$ est un mot *primitif*. Plus généralement, nous dirons qu'une partie $P$ de $B^*$ est *cyclique* ssi il existe un mot $h$ ( que l'on peut supposer primitif et noter $\sqrt{h}$) tel que $P \subset h^*$. Donc toute partie $P'$ d'une partie cyclique $P$ est aussi cyclique et $\sqrt{P'} = \sqrt{h}$ sauf si $P' \setminus 1 = \emptyset$.

Soit $P = \{b,c\}$ où $b,c \ne 1$. On sait que les assertions suivantes sont équivalentes :

- $P$ n'est pas cyclique ;

- $\sqrt{b} \ne \sqrt{c}$ ;

- $b^* \cap c^* = \{1\}$ ;

- $P^*$ est isomorphe au monoïde libre à deux générateurs.

Nous utiliserons plus loin la remarque suivante :

III.2. Soient $b \in B^+$ et $P$ une partie cyclique de $B^*$ qui n'est pas un singolet. Les parties $b+P$ et $bP$ sont simultanément cycliques ou non.
**Preuve** : Il est clair que $b+P$ est cyclique ssi $\sqrt{b} = \sqrt{P}$ et que ceci entraîne que $\sqrt{bP} = \sqrt{P}$. Réciproquement, supposons que $bP$ soit cyclique. Comme $P$ n'est pas un singolet, $P$ contient $h^r$ et $h^s$ où $h = \sqrt{P}$, $0 \le r < s$ et $bP$ contient les mots $bh^r = g^{r'}$, $bh^s = g^{s'}$ où $g = \sqrt{bP}$. On a $r' < s'$. Par conséquent $h^{r-1} = g^{r'-s'}$ ce qui entraîne $h = g$ puisque ces deux mots sont primitifs et enfin $b = h^{r'-r}$.

Q.E.D.

3. Pour alléger l'écriture nous supposons ici que $Q = \{1,2,...,m\}$.
Un morphisme $\mu$ de $A^*$ dans $F$ sera dit de **type cyclique** ssi il est possible de réindexer les éléments de $Q$ de telle sorte que la matrice $A^*\mu$ ( somme des matrices $a\mu$ pour $a \in A^*$ ) soit contenue dans une $Q \times Q$ matrice $H$ satisfaisant les conditions suivantes :

Il existe m mots $b_j \in B^*$ tels que, posant $h_j = b_j b_{j+1} \cdots b_m b_1 \cdots b_{j-1} (1 \le j \le m)$, on ait pour tout $i,j$ :

$$H(i,i) = h_i^* \quad \text{et pour } i \neq j$$

$$H(i,j) = h_i^* H'(i,j)$$

avec $H'(i,j) = b_i b_{i+1} \cdots b_{j-1}$ si $i<j$ ou si $i<j$ et $h_i = h_j$ et $H'(i,j) = b_i b_{i+1} \cdots b_m b_1 \cdots b_{j-1}$ sinon.

On vérifie directement que $H(i,j) = H'(i,j)h_j^*$ et que par conséquent $HH = H$.

Soit maintenant $\mu$ un morphisme irréductible au sens donné à ce terme à la fin de III.1. Nous posons $A_\mu = \sum \{ a_\mu = a \in A \}, A_\mu^* = \sum \{ a_\mu : a \in A^* \}, \bar{M} = A_\mu + A_\mu^2 + \dots + A_\mu^{2m-1} \text{ et } P = \bar{M}(1,1)$. Il est clair que $P$ est une partie cyclique de $B^*$ quand $\mu$ est de type cyclique.

Réciproquement :

III.3. Une condition suffisante pour que le morphisme irréductible $\mu$ soit de type cyclique est que $P$ soit une partie cyclique de $B^*$.

**Preuve** : L'énoncé est trivial si aucune des entrées de $A_\mu$, (donc de $A_\mu^*$) ne rencontre $B^+$ car il suffit de prendre alors tous les $b_j$ égaux à 1 dans la définition de $H$. Nous supposons donc ces cas écartés.

Soient $q$ et $q'$ deux états **distincts** de $Q$. Comme $\mu$ est irréductible,
la paire $(q, q')$ est dans le support de la matrice $A_{\mu}^{*}$, ce qui signifie qu'il existe une suite $(q'_1, q'_2, \dots, q'_n = q')$ et n lettre $a_i \in A$ tels que les entrées $a_i^{\mu}(q'_i, q'_{i+1})$ ($1 \le i \le n-1$) sont non nulles. On peut choisir les $q'_i$ distincts et, puisque $m = \text{Card}(Q)$, ceci montre que la matrice $M' = A_{\mu} + A_{\mu+1}^2 + \dots + A_{\mu+n-1}^{m-1}$ a toutes ses entrées non diagonales non nulles. Comme au moins une des entrées de $A_{\mu}$ rencontre $B^+$ il en résulte que la même chose est vraie de l'entrée $(1,1)$ de $\bar{M} = M'(A_{\mu})M'$ et que le mot $h = \sqrt{p}$ appartient à $B^+$.

Considérons un état $q \neq 1$. On a l'inclusion :

$$M'(1,q). M'(q,1) \subset \bar{M}(1,1) \subset h^*.$$

Si $M'(1,q)$ n'est pas contenue dans $h^*$, ceci implique l'existence d'une factorisation bien définie $h = g'_q g''_q$ pour laquelle $M'(1,q) \subset h^* g'_q$ et $M'(q,1) \subset g''_q h^*$. Dans le cas contraire, on doit avoir aussi $M'(q,1) \subset h^*$ et nous posons $g'_q = g''_q = 1$.

Nous choisissons maintenant un indexage de $Q$ tel que la suite des longueurs des mots $g'_q$ soit non décroissante.

Les $m-1$ équations $g'_q g''_q = h$ ($ou = 1$) déterminent sans ambiguïté m mots $b_j$ tels que $g'_j = b_1 \dots b_{j-1}$ ($2 \le j \le m$) maintenant.

Pour chaque $(i,j)$ $(i,j \neq 1)$ on a l'inclusion :

$M'(1,i). A_{\mu}(i,j). M'(j,1) \subset \bar{M}(1,1) \subset h^*$

où $M'(1,i)$ et $M'(j,1)$ sont des parties non vides de $h^* g'_i$ et de $g''_j h^*$ respectivement. Exprimant ceci en fonction des mots $b_n$, on obtient la relation :

$A(i,j) \subset H(i,j)$ d'où le résultat puisque $HH = H$.

Q.E.D.

**III.4.** Soit $\mu : A^* \to \mathbb{F}$ un morphisme irréductible qui n'est pas fonctionnel. Il existe trois mots $p, a', a''$ tels que l'on ait $\|(a'p^nq'')\mu\| \ge \alpha(n)$ ($n \in N$) avec $\alpha(n) = n+1$ ou $= 2^n$ selon que $\mu$ est ou non de type cylcique.

**Preuve** : L'hypothèse que $\mu$ n'est pas fonctionnelle implique l'existence d'un
mot p et d'états q,q' tels que $P = a_\mu(q,q')$ contienne au moins deux mots distincts b et c. D'autre part quelques soient $q_1$ et $q'_1$ l'hypothèse que $\mu$ est irréductible implique l'existence de mots a' et a'' tels $a'_\mu(q_1,q)$ et $a''\mu(q',q'_1)$ ne soient pas nuls et que par conséquent

$$ \|(a'pa'\)\mu(q_1,q'_1)\| \ge \|P\|. $$

Il suffit donc de considérer une seule paire $(q,q')$ et on peut même supposer que $q = q'$ ce que nous ferons désormais.

Pour chaque entier $n$ on a $\{b,c\}^n \subset P^n \subset a_\mu^n(q,q)$.

Ceci établit l'inégalité cherchée quand $P$ n'est pas cyclique puisque l'on peut alors prendre $b,c \in P$ tels que $\{b,c\}^*$ soit isomorphe au monoïde libre à deux générateurs, c'est à dire que $\|\{b,c\}^n\| = 2^n$ identiquement.

Si $P$ est cyclique mais que $\mu$ ne l'est pas, nous pouvons trouver deux mots $a_1$ et $a_2$ tels que $\{d_1 = a_1\mu(q,q), d_2 = a_2\mu(q,q)\}$ ne soit pas cyclique. On a $d_i P \subset (a_i P)\mu(q,q), i = 1,2$ et d'après III.2. l'un au moins de ces deux ensembles n'est pas cyclique. Ceci achève la preuve quand $\mu$ n'est pas cyclique.

Supposons maintenant $P$ cyclique c'est à dire $b = h^r, c = h^s (r,s \in \mathbb{N})$ où $h = \sqrt{P}$. Pour chaque $n \in \mathbb{N}$, $P^n$ contient les $n+1$ mots distincts $h^{n_1}$ où $n_1 = i+r+(n-i)s (0 \le i \le n)$ concluant la preuve.

Q.E.D.

Ceci achève d'établir la Propriété énoncée dans l'introduction.

En effet, soit $\rho : A^* \to B^*$ une relation rationnelle. S'il existe un mot de $A^*$ dont l'image par $\rho$ est infinie, l'eventualité (i) est réalisée (avec $\rho = 1$). Sinon, (comme nous le supposons désormais), nous savons d'après (I.1) que $\rho$ est un polynôme en des relations fonctionnelles ou unitaires (III.1) et nous distinguons deux cas selon que ces dernières sont toutes fonctionnelles ou que l'une au moins ne l'est pas.
Compte tenu de (I.2.), l'énoncé (II.4.) (resp. III.4.) montre
alors que dans le premier (resp. second) cas l'une des éventualités (i) ou (ii)
ou (iii) est réalisée.

Nous terminons la discussion dans la section suivante, en utilisant le
résultat ( qui vient d'être établi ) qu'une relation rationnelle a une nomre finie
ssi elle est la somme d'un nombre fini de relations rationnelles fonctionnelles.

IV. Les relations de norme finie

1. Faisant référence à la terminologie introduite au début de la section III, nous considerons une relation rationnelle fonctionnelle $\rho$ de domaine infini qui est un produit non ambigu de relations minimales ou unitaires. Regroupant les termes et mettant ceux qui sont triviaux, on en déduit de façon unique une expression de $\rho$ comme un produit non ambigu $p = \tau_0 \sigma_1 \tau_1 \cdots \tau_{k-1} \sigma_k \tau_k (k \ge 1)$ où chaque $\tau_i$ est une relation dont le domaine est un mot $y_i \in A^*$ et chaque $\sigma_i$ une relation fonctionnelle unitaire dont le domaine est le sous-monoïde $X_i^*$ engendré librement par la partie non vide $X_i$ de $A^*$.

Nous appelerons (X) = (y₀, x₁, y₁, ..., xₙ, yₙ) (h ≥ 1) un *monome*.
Son *domaine* sera la partie infinie y₀xᵢ yᵢ ... xᵣ yₙ = x de A* et nous dirons que la
relation ρ est *compatible* avec (X). La suite (σ) = (τ₀, σ₁, ..., σₖ, τₖ) sera dite
*induite* par (X) sur ρ.

Nous montrons d'abord qu'étant donnés (X) et ρ compatibles, on peut
choisir une suite distinguée unique parmi toutes les suites induites par (X) sur ρ.

IV.1. Etant donnés (X) et ρ compatibles, il existe exactement une suite induite (σ) tel que pour chaque i = 1,2,... k les mots de l'ensemble

$$
\{ y_i - 1 \tau_{i-1} \} \cup \{ x \sigma_i \neq 1. x \in X_i^* \}
$$

n'aient pas de facteur droit commun dans $\mathbb{B}^+$.

Preuve : Soient (σ) et (σ') deux suites induites par (X) sur ρ. Prenant x ∈ X₁
et n ∈ N quelconques, la double équation

$(y_0 x^n y_1 y_2 \cdots y_k) \rho$
$$ 
\begin{aligned}
&= ( y_0 \tau_0 ) ( x \sigma_1 )^n ( y_1 \tau_1 ) ( y_2 \tau_2 ) \dots ( y_k \tau_k ) \\
&= ( y_0 \tau'_0 ) ( x \sigma'_1 )^n ( y_1 \tau'_1 ) ( y_2 \tau'_2 ) \dots ( y_k \tau'_k )
\end{aligned}
$$

montre l'un des mots $y_0 \tau_0$ et $y_0 \tau'_0$ est facteur gauche de l'autre. Supposons par exemple $y_0 \tau'_0 = ( y_0 \tau_0 ) c ( c \in B^* )$. Prenant l'équation précédente pour $n=0$ et $n=1$ on voit que $x_1$ et $x \tau'_1$ ont même longueur et prenant n assez grand pour que

$$ | ( y_0 \sigma_0 ) ( x \sigma_1 )^n | \ge | ( y_0 \tau'_0 ) ( x \sigma'_1 ) | $$

on en déduit l'existence de mots $c', c''$ tels que $x\sigma_1 = c'c'', x\sigma'_1 = c''c', c \in c' (c''c')^*$ quand $x\sigma_1 \ne 1$. Donc tous les mots $y_0 \tau'_0$ et $x\sigma'_1 \ne 1$ ($x \in X_1^*$) ont le facteur droit $c'$. Il en résulte que la suite cherchée se trouve parmi celles pour lesquelles la longueur $|y_0 \tau_0|$ est minimum. Supposons donc cette condition remplie par $(\sigma)$ et supposons qu'il existe un mot $c \in B^*$ qui soit facteur commun de $y_0 \tau_0$ et des $x\sigma_0 \ne 1$ ($x \in X_1^*$).

Chacun de ces dernières aurait la forme $x\sigma_0 = c_x c ( c_x \in B^*)$ et, posant $y_0 \tau_0 = ( y_0 \tau'_0 ) c ; x\sigma'_0 = c c_x ; y_1 \tau'_1 = c ( y_1 \tau'_1 )$, la suite $( \tau'_0, \sigma'_0, \tau'_1, \sigma'_1, \dots, \tau'_k )$ serait encore une suite induite. Comme $|y_0 \tau'_0| = |y_0 \tau_0| - |c|$, l'hypothèse faite ci-dessus montre que $c=1$. Le résultat s'en déduit par induction sur $k$ en considérant le monome $( y_1, x_1, \dots, y_k )$ et la suite induite $( \tau'_1, \sigma'_1, \dots, \tau'_k )$.

Q.E.D.

Ceci nous permettra une économie de notations puisque, pour tout segment $X_i^* Y_i^* \dots X_j^* Y_j^*$ (ou $Y_{i-1}^* X_i^* Y_i^* \dots X_j^* Y_j^*$ ou $X_i^* Y_i^* \dots X_j^* Y_j^*$ etc.) du domaine $X$ et tout mot $x$ de celui-ci nous pourrons sans ambiguïté désigner par $x\sigma$ le produit correspondant des images de ses facteurs par les relations $(\sigma_i, \dots, \sigma_j)$ de la suite distinguée que l'on vient de définir.

2. Nous vérifions d'abord un résultat technique.
IV.2. Soit $\rho = \rho_1 + \rho_2 + \dots + \rho_d$ une somme finie de relations rationnelles fonctionnelles $\rho_i$. Il existe une relation $\rho_0$ de domaine fini et un système fini de monomes disjoints ($X^{(j)}$) et de relations rationnelles $\rho_{ji}$ telles que chaque paire $(X^{(j)}, \rho_{ji})$ soit compatible et que $\rho$ soit la somme de $\rho_0$ et des $\rho_{ji}$.

**Preuve** : Chacune des relations initiales $\rho_i$ peut être définie par une bimachine $v_i$. Celles-ci étant en nombre fini, on peut choisir un morphisme $\phi$ de $A^*$ dans un monoïde fini $S$ qui en soit simultanément un morphisme. Donc pour tout $\rho_i$ et $s \in S$ la partie $s\phi^{-1}$ est contenue dans le domaine de $\rho_i$ ou dans son complément.

On définit maintenant la relation $\rho_0$ comme la restriction de $\rho$ à l'union $D$ des parties $s\phi^{-1}$ ($s \in S$) qui sont finies. Remplaçant $\rho$ par sa restriction au complément de $D$, on peut désormais supposer $\rho_0 = 0$ et même, pour simplifier, que toutes les relation $\rho_i$ ont le même domaine $s\phi^{-1}$ pour un certain $s \in S$.

D'après II.3. et ses corollaires, on peut trouver des morphismes $\mu_i$ dans des monoïdes $\{0,1\}$ de $Q \times Q$ matrices ($Q = S \times S$) qui définissent les $\rho_i$ et satisfaisant identiquement $\mu_i \# = \phi$.

Appliquons maintenant la construction de III.1. à l'une quelconque $\rho_1$, des relations $\rho_i$. Elle permet d'exprimer cette relation comme une somme finie de produits $\rho_{ji}$ ($j = 1, 2, \dots, h$) de relations et chacun de ceux-ci donne de façon unique une paire compatible $(X^{(j)}, \rho_{ji})$. Par construction les domaines des monomes $(X^{(j)})$ sont deux à deux disjoints. En vertu des égalités $\phi = \mu_i \#$, les mêmes monomes $(X^{(j)})$ auraient été obtenus si cette construction avait été effectuée à partir de l'une quelconque des relations $\rho_i$.

Q.E.D.

Nous considérons désormais un monome fixe $(X)$ avec lequel toutes les relations considérées seront supposées compatibles. Puisque chaque segment $X_i^*$ de $(X)$ est engendré librement par $X_i$, le monoïde $M = X_1^* \times X_2^* \times \dots \times X_k^*$ est isomorphe à
un produit direct de monoides libres et il existe une bijection $\eta$ de $M$ sur le domaine de $(X)$ envoyant chaque $m = (x_1, x_2, \dots, x_k)$ sur le mot $y_0 x_1 y_1 \cdots y_{k-1} x_k y_k$ ; en particulier $\ln = y_0 y_1 \cdots y_k$. Etant donnée une relation $\rho$ nous désignerons par $\hat{\rho}$ le morphisme de $M$ dans $N$ tel que $m\hat{\rho} = |mn\rho| - |\ln\rho|$.

On a donc identiquement

$$ (x) \qquad |m^n w m^{n'} n\rho| = |w n\rho| + (n+n') (m\hat{\rho}) $$

pour tout $m, w \in M$ et $n, n' \in N$.

On peut tester au moyen de l'énoncé II.4. si une autre relation $\rho'$ satis-
fait ou non $\hat{\rho} = \rho'$. Il suffit pour cela de prendre un morphisme $\beta$ de $B^*$ dans
lui-même en voyant tout l'alphabet $B$ sur une seule lettre $b$ et de vérifier pour
$i = 1,2,\dots,k$ l'égalité des relations induites $\rho\beta$ et $\rho'b$ de $X_i^*$ dans $b^*$.

IV. 3. Soient $\rho$ et $\rho'$ deux relations *distinctes* compatibles avec $(X)$ et telles que $\hat{\rho} = \rho'$, . Il existe un idéal ( non vide ) $W$ de $M$ tel que $w\rho \neq w\rho'$ pour chacun de ses mots.

**Preuve** : Puisque $\hat{\rho} = \rho'$ on a pour tout $m \in M$, $|mn\rho| - |mn\rho'| = |\ln\rho| - |\ln\rho'|$ donc $mn\rho \neq mn\rho'$ sauf si cette différence est identiquement nulle ainsi que nous le supposerons désormais. Supposant aussi que par exemple $|y_0\rho'| \le |y_0\rho|$, on voit que les idéaux à droite $(y_0\rho')B^*$ et $(y_0\rho)B^*$ ont une intersection vide ( et que par conséquent $mn\rho \neq mn\rho'$ pour tout $m$ ) sauf si $y_0\rho'$ est un facteur gauche de $y_0\rho$. Dans ce cas on peut simplifier à gauche par le mot $y_0\rho'$, ce qui revient à supposer $y_0\rho' = 1$, $y_0\rho = b$.

Soit V le sous semi groupe de $X_1^*$ formé des mots v tels que $|v\rho| \ge |b|$. Nous définissons les relations $\rho_2, \rho_3, \rho_1', \rho_2'$ de domaine V par les conditions $v\rho = (v\rho_2)(v\rho_3)$ ; $v\rho' = (v\rho_1')(v\rho_2')$ ; $|v\rho_3| = |v\rho_1'| = |b|$.

On vérifie que V est une partie reconnaissable et que ces quatre relations sont rationnelles en même temps que $\rho$ et $\rho'$. Supposons qu'il existe un mot $w \in V$ pour lequel $w\rho_2 \neq w\rho_2'$. Quelque soit $x \in X_1^*$ l'égalité des longueurs de $x\rho$ et $x\rho'$ entraine que les mots

$$ b(x\rho)(w\rho_2) \text{ et } (x\rho')(w\rho_1')(w\rho_2') $$

aient même longueur et soient différents. Ceci entraine qu'ils engendrent des
idéaux à droite disjoints, donc que $m\rho \neq m\rho'$ pour tout m appartenant à l'idéal de M engendré par w.

Supposons au contraire que $\rho_2 = \rho'_2$. Quelque soient $x \in X_1$ et $v \in V$ les mots $b((vx)\rho_2), (vx)\rho_3)$ et $((vx)\rho'_1), (vx)\rho'_2)$ ($v\rho'_1$) sont égaux.

Si donc on avait $(vx)\rho_3 \neq 1$, la dernière lettre à droite de ce mot serait la même que celle du mot $v\rho'_1$ donc aussi, en considérant le facteur gauche de longueur $|b|$ de $f$, que celle du mot $b$. Ceci contredit les conventions faites à la suite de IV.1.

Par conséquent $\rho_2 = \rho'_2$ implique que $b = 1$ et que $\rho_2 = \rho'_2$ soit la relation commune induite par $X_1$ sur $\rho$ et $\rho'$.

Le résultat en découle par induction sur $k$. En effet, si l'on avait $(y_0x_1... x_k)\rho = (y_0x_1... x_k)\rho'$ identiquement, les hypothèses $\rho \neq \rho'$, $\hat{\rho} = \hat{\rho}'$ impliqueraient que $y_k\rho$ et $y_k\rho'$ soient deux mots distincts mais de même longueur, donc que $m\rho \neq m\rho'$ pour tous les $m \in M$.

Q.E.D.

Soit maintenant $R$ un ensemble fini de relations rationnelles fonctionnelles deux à deux distinctes et toutes compatibles avec le monome $(X)$ et soit $\sigma$ la somme des $\rho \in R$.

IV.4. Le monoïde $M$ contient un sous semi groupe non vide $S$ tel que $||S\cap\sigma|| = d$ pour chacun de ses éléments.

**Preuve** : Puisque l'ensemble des idéaux de $M$ contient l'intersection de deux quelconques de ses membres, l'énoncé IV.2 permet de construire un idéal $W$ tel que pour chaque $\rho, \rho' \in R$ et $w \in W$ on ait $w\rho = w\rho'$ seulement si $\hat{\rho} = \hat{\rho}'$.

Considérons maintenant pour chaque sous ensemble $\bar{R}$ de $R \times R$ l'ensemble $W(\bar{R})$ des $w \in W$ qui satisfont la condition supplémentaire que $|w\rho| \neq |w\rho'|$ pour chaque $(\rho, \rho') \in \bar{R}$ tels que $\hat{\rho} \neq \hat{\rho}'$.
Etant donné un tel $W(\bar{R})$, soient $\rho, \rho' \in R$ et $m \in M$ tels que $\mathfrak{m}\rho \neq \mathfrak{m}\rho'$. Utilisant l'identité (*) mentionnée avant IV.3 on voit que $m^{\frac{n}{n'}}_{\mathfrak{w}m}$ appartient à l'ensemble $W(\bar{R} \cup \{\rho, \rho'\})$ pour tout $n, n' \in N$ tels que $n+n'$ soit assez grand. Considérant successivement toutes les paires $(\rho, \rho') \in \mathcal{R}\mathcal{R}$ on en conclut que $W = W(\mathcal{R}\mathcal{R})$ n'est pas vide. Par définition on a $\|s\sigma\| = d$ pour chaque $s \in W$.

Considérons enfin un $s \in W$. Il existe une permutation de $R$ telle que l'on ait

$$s\rho_1 \leq s\rho_2 \leq \dots \leq s\rho_d.$$ pour un indexage convenable des $\rho \in R$.

Les éléments $m \in M$ pour lesquelles ces mêmes inégalités sont satisfaits forment un sous monoïde $M_s$ de $M$ qui admet comme idéal son intersection $S$ avec $W$. Donc $S$ est un semi groupe, qui est non vide puisqu'il contient $s$.

Q.E.D.

Nous avons terminé la preuve des propriétés énoncées dans l'introduction.

En effet si la relation rationnelle $\rho$ n'admet aucun triple de mots $a', \rho, a''$ pour lequel $\|(a'p^n a'')\rho\| \ge n+1$ identiquement, la première partie de la preuve montre quelle est la somme d'un nombre fini de relations rationnelles fonctionnelles.
D'après IV.2 nous pouvons représenter $\rho$ comme la somme d'une relation $\rho_0$ de domaine fini et de relations fonctionnelles $\rho_{ji}$ dont les domaines sont ceux de monomes disjoints $(x^{(j)})$. Sur chacun de ceux-ci, le dernier énoncé montre que la norme de $\rho$ est la même que celle de la restriction de $\rho$ à tous les mots de longueur supérieure à une valeur finie arbitraire. Si donc $d$ est le maximum de la norme de $x^{(j)}_{n\rho}$ sur tous les domaines $(x^{(j)})$ on peut regrouper ceux-ci et exprimer $\rho$ comme somme de $\rho_0$ et d'exactement d relations fonctionnelles.

On notera que les constructions effectuées permettraient de vérifier si une relation rationnelle $\rho'$ de norme finie satisfait ou non $a_0 \subset a_0'$ pour tous les mots appartenant au complément d'un sous ensemble fini de $A^*$. Il serait curieux que ceci ne reste pas vrai pour des relations rationnelles $\rho$ et $\rho'$ satisfaisant seulement la condition (ii) de la Propriété.
Références :

[1] S. Eilenberg. " Automata, Languages and machines ". Vol A. Academic Press. N.Y. 1974.

[2] A. Lentin. " Equations dans les monoides libres ". Gauthiers Villars Paris 1972.

[3] M. Nivat ( 1968 ) " Transductions des langages de Chomsky ". Ann. Institut Fourier XVIII. pp. 335-455.