RIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

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

laboratoire de recherche
en informatique
et automatique

Sur une propriété syntactique
des relations rationnelles

M.P Schützenberger

Rapport de Recherche n° 67

avril 1974
SUR UNE PROPRIÉTÉ SYNTACTIQUE DES RELATIONS RATIONNELLES

M.P. Schutzenberger

Résumé :

On examine dans un cas particulier l'effet d'une relation
rationnelle sur les monoïdes syntactiques.

Abstract :

One studies in a special case connections between rational
relations and syntactic monoïdes.
# I - INTRODUCTION :

Une relation rationnelle $\theta : A^* \to B^*$ entre monoïdes libre associe à chaque partie reconnaissable F de $B^*$ la partie reconnaissable $F^{\theta^{-1}}$ de $A^*$.

Le problème des *invariants syntactiques* de $\theta$, c'est à dire des propriétés du monoïde syntactique $\text{Synt}(F^{\theta^{-1}})$ qui sont fonction de celles de $\text{Synt}(F)$ a été posé par S. Eilenberg qui l'a complètement résolu dans les cas fondamentaux où $\theta$ est fonctionnelle ($\text{Card}(a\theta) \le 1$ pour chaque $a \in A^*$) et en particulier quand $\theta$ est un morphisme. Nous nous proposons ici d'appliquer la théorie générale de la factorisation des morphismes et des cascades de produits en couronne de J.P. Rhodes et BR. Tilson (dont un bon exposé se trouve dans 'Algebraic Theory of Machines, Languages and Semi-groups, M.A. Arbib. Ed (1968)) pour borner superieurement pour certaines parties F les groupes dans $\text{Synt}(F^{\theta^{-1}})$ au moyen de ce qu'après M. Nivat nous appelerons un *transducteur pour θ*.

Dans cette définition, nous notons $2^{B^*}$ le semi-anneau des parties du monoïde libre $B^*$ (plus généralement $2^S$ sera le semi-anneau des parties de tout semi-groupe $S$).

## Définition :

$\mu$ est un *transducteur pour θ* ssi il existe un ensemble *fini* $Q$ et deux éléments $q_0, q_1 \in Q$ tel que $\mu$ soit un morphisme de $A^*$ dans le semi-anneau $\Gamma_B$ des $Q \times Q$ matrices à entrées dans $2^{B^*}$ satisfaisant la condition que $a\theta$ soit, pour chaque mot $a \in A^*$, l'entrée $(q_0, q_1)$ de la matrice $a\mu$.

La donnée de $\theta$ comme partie rationnelle de $A^* \times B^*$ implique celle d'au moins un de ses transducteurs.
Soient maintenant Γ le semi-anneau des relations dans $QxQ$, $\Gamma_B$ celui des $QxQ$ matrices à entrées dans $2^G$ et enfin $\beta$ le morphisme de $\Gamma_B$ dans Γ envoyant chaque matrice $m$ sur son *support*

$$m\beta = \{ (q, q') \in QxQ : m_{q, q'} \neq \emptyset \}.$$

Nous appelerons *monoïde des supports* du transducteur $\mu$ le monoïde (nécessairement fini) $M_\mu = A_\mu^* \mu_\beta$ formé des supports de toutes les matrices $a_\mu$ ($a \in A_\mu^*$).

Le résultat principal de ce travail est la propriété ci-dessous dans laquelle la partie $F$ de $B^*$ est supposée être reconnaissable dans un groupe $G$, c'est à dire satisfaire $F = F_{\rho\rho}^{-1}$ où $\rho$ est un morphisme de $B^*$ dans un groupe *fini* $G$.

Dans la section III on donne une application de cette propriété.

**Propriété :** Soient $\theta : A^* \to B^*$ une relation rationnelle et $F \subset B^*$ une partie reconnaissable dans un groupe fini $G$. Quelque soit le transducteur $\mu$ pour $\theta$, tout groupe dans $\text{Synt}(F^\theta)$ divise un produit en couronne $G \circ G'$ où $G'$ est un groupe dans le monoïde $M_\mu$ des supports du transducteur.

Montrons pour terminer comment la vérification de cet énoncé se ramène à l'application d'un lemme qui sera établi dans la section II.

Étant donnés $Q$ et le morphisme $\rho : B^* \to G$, nous pouvons prolonger ce dernier à un morphisme (de semi-anneau) de $2^{B^*}$ dans $2^G$ puis à un morphisme de $\Gamma_B$ dans le semi-anneau $\Gamma_G$ des $QxQ$ matrices à entrées dans $G$.

Gardant la notation $\beta$ pour les supports de tous les semi-anneaux considérés, il est clair que $m_\beta = m_\beta$ pour toute matrice $m$. Donc si $M' = A_\mu^* \mu_\rho \subset \Gamma_G$, on a $M'_\beta = M_\mu = A_\mu^* \mu_\beta$. Comme $F^\theta^{-1}$ est par définition l'ensemble des mots $a \in A_\mu^*$ tels que $a \in F^\theta \setminus \emptyset$, nous avons la relation $F^\theta^{-1} = \{a \in A_\mu^* : (a \in \rho) q_0, q_+ \in F^\rho \neq \emptyset\}$, qui montre que $F' = F^\theta^{-1}$ satisfait $F'(\mu_\rho)(\mu_\rho)^{-1}$. Ceci équivaut à ce que le monoïde syntactique de $F^\theta^{-1}$ soit une image homomorphe du monoïde *fini* $M' = A_\mu^* \mu_\rho$.

Il suffit donc d'établir le lemme énoncé ci-dessous.
## II. UN LEMME TECHNIQUE.

Nous gardons les mêmes notations.

**Lemme** : Soit $M'$ un monoïde de $Q \times Q$ matrices à entrées dans $\text{GL}_2$ où $G$ est un groupe fini. Tout groupe $H$ dans $M'$ divise un produit en couronne $G \circ H_\beta$ où $H_\beta$ est un groupe dans $M'_{\beta}$.

Nous désignons par $u$ l'idempotent de $H$ et nous montrons que la preuve se ramène par des méthodes standard (c'est à dire sans utiliser l'hypothèse que $G$ est un groupe) au cas que nous appelerons *positif* : c'est à dire, à celui où le support de $u$ est une classe d'équivalence $Q' \times Q'$ ($Q' \subsetneq Q$).

II.1. Le groupe $H$ divise le produit en couronne $N \circ H_\beta$ où $H_\beta$ est un groupe et où : $N = \{h \in H : h_\beta = u_\beta\}$.

*Preuve* : $H_\beta$ est un groupe puisque $H$ est un groupe et $\beta$ un morphisme.

De plus $N$ est le noyeau de $\beta$ et la formule est un cas particulier des théorèmes de base des produits en couronne.

Q.E.D.

Etant données une relation quelconque $R \subsetneq Q \times Q$ et une matrice $m \in M'$, nous désignons par $m \circ r$ la matrice $m' \in \text{GL}_2$ telle que l'on ait identiquement $m'_{q,q'} = m_{q,q'}$ ou $= \emptyset$ selon que $(q,q') \in r$ ou non.

II.2. Il existe une famille $\{\epsilon_i : i \in I\}$ de morphismes de $N$ tels que d'une part chaque $N_{\epsilon_i}$ soit positif, d'autre part $N$ soit un sous-groupe du produit direct des groupes $N_{\epsilon_i}$.

*Preuve* : Comme le support de $u$ est une relation idempotente, il
existe une famille de parties de Q non vides disjointes, $Q_i$ ($i \in I$) et une relation $v$ telles que $u_\beta$ soit l'union disjointe de $e=\bigcup_{i} Q_i \times Q_i$ et de $v$ et que $v=ev+ve+v^2$. Ceci entraîne que $\epsilon_i : h \to h_n(Q_i \times Q_i)$ soit un morphisme de N pour chaque $i \in I$. et que $\epsilon : h \to \Sigma h_{\epsilon_i}$ soit un morphisme de N sur un sous-groupe $N_\epsilon$ du produit direct des groupes positifs $N_{\epsilon_i}$. Il suffit donc de montrer que le noyeau $E = \{h \in N : h_\epsilon = u_\epsilon\}$ de $\epsilon$ est réduit à $\{u\}$ puisque N divise $E \circ N_\epsilon$.

Ceci est trivial quand $u_\beta=Q \times Q$. Comme ce cas couvre celui où $Q$ est un singleton, nous pouvons donc procéder par induction sur $\text{Card}(Q) \ge 2$ en supposant $e \neq Q \times Q$. Cette dernière hypothèse implique l'existence d'une partition propre $Q=Q'+Q''$ telle que $h_n(Q''xQ')=\emptyset$ pour chaque $h \in N$ et que, par conséquent $h \to h_n(Q'xQ'+Q''xQ'')$ soit un morphisme de $N$. Ceci permet d'écrire $u=\begin{pmatrix} a & c \\ \emptyset & b \end{pmatrix}$ où $a$ et $b$ sont respectivement une $Q'xQ'$ et une $Q''xQ''$ matrice *idempotente*. Soit $h \in E$. D'après l'hypothèse d'induction, $h=\begin{pmatrix} a & x \\ \emptyset & b \end{pmatrix}$, $h^{-1}=\begin{pmatrix} a & y \\ \emptyset & b \end{pmatrix}$.

Les identités $u=u^2=uhh^{-1}$ et $h=uhu$ donnent les relations :

$$c=ac+cb \quad \text{axb+ay+cb et}$$

$$x=axb+ax+bc.$$

Donc $x=axb+c=axb+ay+cb=c$ montrant que $h=u$ et $E=\{u\}$.

Q.E.D.

Il suffit donc maintenant de vérifier le lemme dans le cas particulier où $H=N$ est positif et l'on peut même supposer pour simplifier $u_\beta=Q \times Q$.
II.3. Tout groupe H dans M' tel que $h\beta=QxQ$ pour chaque $h\in H$ divise le groupe G.

*Preuve* : D'après la relation $u^2=u$ on a $(u_{q,q})^2\subset u_{q,q}$ pour chaque $q\in Q$, donc $u_{q,q}$ est un sous semi-groupe de G. Comme il est non vide et que G est un groupe fini, c'est un sous-groupe $G_q$ de G.

Soit $h\in H$. La relation $uh=h$ montre que $G_q h_{q,q'} = u_{q,q} h_{q,q'} c_{q,q'}^h$, pour chaque $q'\in Q$, c'est à dire que $h_{q,q'}$ est une union de cosets de $G_q$. La même chose vaut pour les entrées $h_{q',q}^{-1}$ de $h^{-1}$ et la relation $hh^{-1}=u$ qui implique $h_{q,q'} h_{q',q}^{-1} = u_{q,q'}$. Montre que de fait chacune de ces entrées de $h$ et de $h^{-1}$ est un coset unique (non vide) de $G_q$.

Ceci s'applique en particulier à la matrice $u$ elle-même et à chacune de ses entrées, $u_{q',q}''$ qui est donc à la fois un coset à droite de $G_{q'}$ et un coset à gauche de $G_{q''}$. ($q',q''\in Q$).

Prenons maintenant un $q_0\in Q$ fixe et posons pour chaque $h\in H$, $h_0=h_{n}({\{q_0\},{q_0\}})$ = la matrice obtenue en remplaçant toutes les entrées par $\emptyset$, sauf $h_{q_0,q_0}$. L'identité $h=uh_u$ et les relations précédentes montrent que l'on a identiquement $h=uh_0u$.

Comme $\emptyset \neq h_0 h'_0 c(hh')_0$ pour tout $h,h'\in H$, l'application $h \to h_0$ est un morphisme injectif. Donc, enfin, H est isomorphe au groupe $G'_0/G_0$ où le sous-groupe $G'_0$ de G est l'union des cosets $H_0(h\in H)$ de $G_0$.

Q.E.D.

Ceci achève la preuve du lemme, donc aussi de la propriété.

Les techniques restent appliquables quand H est un groupe de matrices à entrées dans $\mathbb{Z}^S$ où S est un semi-groupe sans idéaux propres (G est alors son groupe de *Suschkewitsch*). Ceci donnerait une générali-
sation assez immédiate de la propriété au cas où F est reconnaissable
dans S à condition de considérer suelement les semi-groupes libres $A^+$ et $B^+$.

D'autres cas particuliers (par exemple celui des monoïdes union
de groupes) permettent aussi des énoncés relativement simples ; ce sont
ceux où le monoïde syntactique S de F à la propriété (évidente dans le
cas où S est un groupe) que tout groupe dans le monoïde $2^S$ divise S.
Dans le cas général, les groupes dans $\text{Synt}(F\theta^{-1})$ sont soumis à des con-
traintes (assez peu strictes, et de nature quasiment numérique) que je
n'ai pas réussi à formuler de façon raisonnablement simple (ou non triviale).
Par exemple, si S est le monoïde booleane $\{0,1\}$ (qui est union de groupes!),
le monoïde des $QxQ$ matrices *positives* à entrées dans $2^S$ contient le groupe
symétrique sur Q : il suffit pour cela de représenter ce dernier par le
monoïde des bijections et de remplacer chaque entrée vide par $\{0\}$ et chaque
entrée non vide par $\{1,0\}$.

### III. UNE APPLICATION.

Revenant aux notations de l'introduction, nous considérons désor-
mais le cas où la relation $\theta$ est l'inverse d'une substitution (rationnelle)
$\theta^{-1}: B^* \to A^*$, c'est à dire d'un morphisme de $B^*$ dans $2^{A^*}$, donné par les
parties reconnaissables $b_\theta^{-1} \subset A^*$ (b$\in B$ où l'alphabet B est évidemment sup-
posé fini). Pour simplifier nous ferons l'hypothèse summlémentaire que
$b_\theta^{-1}$ est contenu dans le semi-groupe $A^+ (=A^*\setminus\{1\})$, c'est à dire que
$1=1\theta=1\theta^{-1}$.

Nous désignerons par $M_2=A^*\tau_2$ le monoïde syntactique simultané des
parties $b_\theta^{-1}$ ($b\in B$), par $M_1=A^*\tau_1$ celui de $B^*\theta^{-1}$, et par $M_3$ le produit direct
$M_1 \times 2^{M_1 \times M_2} \times M_2$.
D'après la théorie générale des produits en couronne, il est possible de munir $M_3$ d'une structure de monoïde ayant les deux propriétés suivantes :

(i) Tout groupe dans $M_3$ est produit sous-direct d'un groupe dans $M_1$ et d'un groupe dans $M_2$;

(ii) Si $\sigma'$ est l'application envoyant chaque mot $a \in A^*$ sur $a\sigma'_3 = \{(a'\sigma_1, a''\sigma_2) \in M_1 \times M_2 : a', a'' \in A^*, a'a''=a\}$, l'application $\sigma_3 : a \to (a\sigma_1, a\sigma'_3, a\sigma_2)$ est un morphisme (de semi-groupe) de $A^*$ dans $M_3$.

Rappelant que $F$ est une partie de $B$ reconnaissable dans le groupe fini $G$, nous nous proposons d'établir :

III.1. Tout groupe dans le monoïde syntactique de $F\theta^{-1}$ divise le produit en couronne de $G$ dans un groupe dans $M_3$.

Nous construisons d'abord en application immédiate de la théorie générale des relations rationnelles, un transducteur (standard) $\mu$ pour $\theta$, et, d'après la propriété, il suffira de vérifier que son monoïde des supports $M_\mu$ divise $M_3$.

### Construction du transducteur.

La donnée des parties $b\theta^{-1} (b \in B)$ implique celle d'un ensemble minimal fini $Q'$, d'une action $Q' \times A^* \to Q'$, de parties $Q_b$ de $Q'$ ($b \in B$) et d'un élément distingué $q_0 \in Q'$ tels que pour chaque lettre $b$ de $B$ on ait
$$b\theta^{-1} = q_0^{-1} Q_b (=\{a \in A^* : q_0 a \in Q_b\}).$$

Nous adjoignons un nouvel élément $q_+$ à $Q'$ et nous étendons l'action précédente à $Q=\{q_+\} \times Q'$ en posant $q_+ a = \emptyset$ pour chaque $a \in A^+$.
Nous définissons maintenant pour chaque lettre $a$ deux $Q \times Q$ matrices $a_\mu$ et $a_{\mu''}$ (à entrées dans le semi-anneau des parties de $B^*$) par les conditions suivantes :

Pour tout $q, q' \in Q$ :

$a_\mu'_{q', q} = 1$ ou $\emptyset$ selon que $q'a=q$ ou non ;

$a_{\mu''}''_{q', q} = \emptyset$ pour $q \neq q_0, q_+$ et, sinon,

$=b$ si $q=q_0$ ou $q_+$ et $q'a \in Q_b$.

De plus nous définissons les deux matrices $l_\mu'$ et $l_\mu''$ par les conditions :

$l_\mu'_{q', q} = 1$ si $q'=q \neq q_+$ ;

$=\emptyset$ sinon.

$l_\mu''_{q', q} = 1$ si $q'=q_0, q=q_+$ ;

$=\emptyset$ sinon.

L'application $\mu=\mu'+\mu''$, s'étend à un morphisme (de semi-groupe) de $A^*$ dans le semi-anneau $\Gamma_B$.

### III.2. $\mu$ est un transducteur pour $\theta$.

*Preuve* : Notons $\mathfrak{a}$ le $Q$-vecteur égal à la ligne $q_0$ de $a_\mu$ ($\emptyset \subsetneq A^*$).

Pour $a=1$, toutes ces coordonnées sont $\emptyset$ sauf la dernière, c'est à dire qui est égale à $1=1\theta^{-1}$ d'après l'hypothèse $B_\theta^{-1} \subsetneq A^+$.

Ceci permet de procéder par induction sur la longueur des mots et il suffit de vérifier les deux formules suivantes pour $a'$ : $a' \in A^*$, $a \in A$ en les supposant établis pour $a'$ :

(21). Pour tout $q \in Q$ :

$$a' \mathfrak{a}v_q = \sum_{b \in B^*} : a' a \epsilon b \theta^{-1} q_0^{-1} q ;$$
$$
(22). \quad a'\overline{av}_{q_+} = \Sigma \{b \in B^* : a'a\overline{b\theta}^{-1} \} = a\theta.
$$

Nous utilisons le fait que par construction, la ligne $q_+$ de $a_\mu$
est vide et nous observons que les mots $b \in B^*$ qui apparaissent dans (21)
le font d'au moins l'une des deux manières suivantes :

(i) Il existe un $q' \in Q'$ et une factorisation $a=a_1a_2(a_1, a_2 \in A^*)$ tels que :
$$ a_1 \in b \theta^{-1} ; q_0 a_2 = q' ; q' \in q. $$

On vérifie directement que la contribution de ces mots est pour
$q \in Q'$, la coordonnée $q$ du produit $a'v.a\mu'$ et pour $q=q_+$ celle de
$a'v.a\mu''$.

(ii) On a $aa' \in b\theta^{-1}$ et $q=q_0$. Comme $b\theta^{-1} \subset A^+$, il existe un $q' \in Q'$ et des factorisations $b=b_1b'$ ($b_1 \in B^*, b' \in B$) $a=a_1a_2$ ($a_1, a_2 \in A^*$) tels que :
$$ a_1 \in b_1 \theta^{-1} ; q_0 a_2 = q' ; q' \in q_0. $$

Comme ci-dessus la contribution correspondante est la coordonnée $q_0$ du produit $a'v.a\mu''$.

La formule (21) résulte immédiatement de ce deuxième cas et de
la définition de $\mu''$.

Q.E.D.

III.3. Le monoïde $M_\mu = A^* \mu_\beta$ est une image homomorphe de $M_3$.

Preuve : Il suffit de vérifier que pour deux mots $a$ et $a'$ quelconques, $a\mu\beta \neq a'\mu\beta$ implique $a\sigma_3 \neq a'\sigma_3$.

La première relation signifie que les entrées $(q',q)$ des deux
matrices sont différentes pour au moins une paire $q',q \in Q$. On peut prendre
$a'' \in q_0^{-1}q'$ et, posant $a_1=a''a$, $a_1'=a''a_1'$, on a que les coordonnées $q$ des sup-
ports des vecteurs $a_1v$ et $a_1'v$ sont différentes. Ceci entraîne $a_1\sigma_3 \neq a_1'\sigma_3$
(donc le résultat cherché) d'après la formule (21) et la définition
de $\sigma_3:A^* \to 2^{M_1 \times M_2}$ si $q \neq q_+$ et d'après la formule (22) et
$\sigma_3 = \sigma_1 \times \sigma_3' \times \sigma_2$ si $q=q_+$.

Q.E.D.

Ceci conclut la preuve de II.1. A titre d'exemple, nous consi-
dérons le cas particulier suivant.

III.4. Soient $r \ge 1$ et P l'ensemble générateur minimum d'un sous-monoïde de $P^* \in \text{Rat}(A^*)$ de $A^*$. Tout groupe dans le monoïde syntactique de $(P^r)^*$ divise le produit en couronne du groupe cyclique $Z_{(r)}$ dans un produit direct de groupes dans le monoïde syntactique de $P^*$.

Preuve : Prenons $B=\{b\}$. et $\rho:B^* \to G = Z_{(r)}$ tel que $b_\rho$ soit un générateur de ce groupe. Si $\theta^{-1}$ est la substitution telle que $b\theta^{-1}=P$, on a $(P^r)^* = \rho^{-1}\theta^{-1}$ et le résultat est encore une conséquence de la théorie des produits en couronne puisque d'après celle-ci chaque groupe dans le monoïde syntactique de P divise un groupe dans $\text{Synt}(P^*)$ quand P est l'ensemble générateur minimum.

Q.E.D.

En particulier tout groupe dans $\text{Synt}(P^r)^*$ est résoluble quand ceci est vrai pour $\text{Synt}(P^*)$.