# Une caractérisation des parties reconnaissables

Marcel-Paul Schützenberger

► To cite this version:

Marcel-Paul Schützenberger. Une caractérisation des parties reconnaissables. [Rapport de recherche] IRIA-RR-107, IRIA. 1975, pp.6. hal-04716111

HAL Id: hal-04716111

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

Submitted on 1 Oct 2024

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
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

Une caractérisation
des parties reconnaissables

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

M.P. Schützenberger

Rapport de Recherche n° 107.

Mars 1975
# UNE CARACTÉRISATION DES PARTIES RECONNAISSABLES

M.P. Schützenberger

## Résumé :

On donne une caractérisation des parties reconnaissables d'un semi-groupe inspirée des méthodes de Hankel.

## Abstract :

A characterisation of the family of recognisable subsets in semi-groups is given which derives from Hankel's matrices.
Dans la théorie de S. Eilenberg ([1], p.68), une partie X d'un semi-groupe S est dite *reconnaissable* ssi il existe un morphisme de S dans un semi-groupe *fini* pour lequel $X = X\phi\phi^{-1}$.

La méthode des matrices de Hankel introduite par M. Fliess et en particulier le théorème 2.11 de cet auteur ([2]), suggèrent les caractérisations suivantes des parties reconnaissables du semi-groupe S voisine de la Propriété 12.2 de [1] chapitre IV. On suppose donné un corps commutatif K et on rappelle que la *fonction caractéristique* $\chi = \chi_X$ d'une partie X de S est l'application de S dans K telle que pour chaque élément s de S on ait $\chi_s = 1$ ou $= 0$ selon que s appartient ou non à X.

**Propriété :** Une condition nécessaire et suffisante pour que la partie X du semi-groupe S soit reconnaissable est qu'il existe une famille finie $\{\lambda_i, \rho_i\}$ ($1 \le i \le n < \infty$) de paires d'applications de S dans K telles que sa fonction caractéristique $\chi$ satisfasse l'identité suivante pour tout $s, s' \in X$ :

$$ (*) \quad (ss')\chi = \sum_{1 \le i \le n} (s\lambda_i) (s'\rho_i). $$
Un cas typique où une telle identité est satisfaite est celui où il existe un morphisme $\mu$ de $S$ dans un monoïde de $n \times n$ matrices $(n<\infty)$ sur le corps $K$ et deux indices distingués $i_1, i_n$ tels que l'entrée $(i_1, i_n)$ de chaque matrice $s_\mu$, soit $s_\chi$, ne prenne que les valeurs 1 ou 0. On obtient alors $(*)$ en prenant le produit scalaire de la ligne $i_1$ de la matrice $s_\mu$ par la colonne $i_n$ de $s_\mu$.

Nous établissons maintenant cette propriété.

## I. La condition est suffisante.

Supposons que l'on ait $X = X\phi\phi^{-1}$ où $\phi$ est un morphisme de $S$ dans un semi-groupe fini $M$. Soit $Q$ l'ensemble des paires $(m, m') \in M \times M$ telles que $mm' \in X\phi$. C'est un ensemble fini et pour chaque $s, s' \in S$ les relations $(ss')\chi = 1$ ; $ss' \in X$ ; $(ss')\phi = (s\phi)(s'\phi) \in X\phi$ et $(s\phi, s'\phi) \in Q$ sont équivalentes.

Pour chaque $q = (m, m') \in Q$ nous considérons maintenant la fonction caractéristique $\lambda_q$ (resp. $\rho_q$) de la partie $m\phi^{-1}$ (resp. $m'\phi^{-1}$) de $S$. Si $s$ et $s'$ sont deux éléments quelconques de $S$, le produit $(s\lambda_q)(s'\rho_q)$ est égal à 1 si $(s\phi, s'\phi) = q$ et à 0, sinon. Par conséquent la somme finie $\sum_{q \in Q} (s\lambda_q)(s'\rho_q)$ est égale à 1 ou 0 selon que $ss' \in X$ ou non, ce qui établit le résultat cherché.

Q.E.D.

## II. La condition est nécessaire.

Nous considérons le cas un peu plus général où sont données deux familles $\{\lambda_q\}$, $\{\rho_q\}$ d'applications de $S$ dans $K$ indexées par les éléments d'un ensemble *fini* $Q$ et une application $\chi$ satisfaisant la condition
que l'identité (*) soit vraie et que l'image { sχ : s ∈ S } de χ soit
une partie *finie* I du corps K.

Nous nous proposons de vérifier que chaque partie donnée J de I
définit une partie reconnaissable.

$$
X_J = J \chi^{-1} = \{ s \in S : s \chi \in J \}
$$

de S.

Nous cœmençons par trois remarques introduisant des hypothèses supplémentaires qui allègent la preuve proprement dite.

(1). S est un semi-groupe infini et X = X_J n'est ni vide ni égal à S.

**Preuve** : En effet, dans le cas contraire, le résultat est déjà établi car, par définition, toute partie X d'un semi-groupe fini est reconnaissable et la partie X = ∅ ou X = S de tout semi-groupe S est une partie reconnaissable de ce dernier.

Q.E.D.

(2). J est le singleton formé de l'élément unité 1 du corps K. De plus il n'existe aucun q ∈ Q pour lequel λ_q ou ρ_q soit identiquement nulle.

**Preuve** : Toute partie X de S est reconnaissable en même temps que son complément S\X. On peut donc supposer O ∉ J en remplaçant au besoin J par son complément dans l'image I de χ puisque cette dernière est supposée être finie.

D'autre part, si pour chaque k ∈ J, il existe un morphisme φ_k de S
d'image finie tel que $X_k \phi_k \phi_k^{-1} = X_k \text{ où } X_k = k\chi^{-1}$, on a $X\phi\phi^{-1} = X \text{ où } \phi \text{ est}$
le morphisme évident de $S$ dans le produit direct des semi-groupes $S\phi_k$.
Il suffit donc d'établir que chaque $X_k$ est reconnaissable. On se ramène
au cas où $k=1$ en remplaçant chaque $\rho_q$ par $\rho_q k^{-1}$ et $\chi$ par $\chi k^{-1}$.

Enfin si $\lambda_q$ ou $\rho_q$ était identiquement nulle, il en serait de
même de chaque terme $s_{\lambda_q} \cdot s'_{\rho_q}$ dans (*) et celui-ci pourrait être omis
dans la somme.

Q.E.D.

Nous supposons donc désormais $\{1\} = J \subset I$.
(3). $S$ est un monoïde.

Preuve : S'il n'est est pas ainsi, nous adjoignons à S un nouvel élément neutre 1, obtenant ainsi un monoïde $\bar{S} = \{1\} \cup S$.

Nous définissons $1_\lambda = 1_\rho = 0$ pour chaque $q \in Q$. Nous ajoutons
aussi deux nouveaux éléments $r$ et $r'$ à $Q$ et nous définissons les applications
$\lambda_r = \rho_r'$ et $\lambda_{r'} = \rho_{r'}$ comme étant respectivement les fonctions caractéristiques des parties $X$ et $\{1\}$ de $\bar{S}$. On a donc que pour chaque $s,s' \in S$ le nouveau
terme $(s\lambda_r)(s'\rho_r') + (s\lambda_{r'})(s'\rho_{r'})$ de la somme est égal à 1 ou à 0 selon que
$(s,s')$ appartient ou non à l'union de $X \times \{1\}$ et de $\{1\} \times X$, ce qui montre
que l'identité (*) ( et les autres hypothèses ) sont encore satisfaites.

Il est clair que $X$ est reconnaissable à la fois comme partie de $\bar{S}$
et comme partie de $S$. En effet si $X\phi\phi^{-1} = X \text{ où } \phi$ est un morphisme d'image
finie du monoïde $\bar{S}$, on a aussi $X\psi\psi^{-1} = X \text{ où } \psi$ est la restriction de $\phi$ à $S$
puisque, par construction, le nouvel élément $1$ n'appartient pas à $X$

Q.E.D.
Nous en venons maintenant à la preuve que X est reconnaissable.
Nous désignons par $s\lambda$ ( resp. $s\rho$ ) pour chaque $s \in S$, le (0-vecteur ligne
( resp. colonne ) dont les coordonnées sont les $s\lambda_q$ ( resp. $s\rho_q$ ) ce qui
fait que le membre de droite de (1) est simplement le produit scalaire $s\lambda.s'\rho$.

Soit $d( \leq \mathrm{Card}(Q) )$ la dimension du $K$-module $R$ sous-tendu par tous
les vecteurs $\mathrm{sp}(s \in S)$. On peut trouver une partie $T$ de $d$ éléments de $S$
et une $Q \times Q$ matrice inversible $M$ telles que, posant $s\lambda' = s\lambda \cdot M^{-1}$ $\mathrm{sp}' = M \cdot \mathrm{sp}(s \in S)$,
les vecteurs $t\rho$ ($t \in T$) forment une base de $R$ constituée de vecteurs ayant
toutes leurs coordonnées nulles sauf une égale à 1.

On a identiquement $s\lambda \cdot s'\rho = s\lambda' \cdot s'\rho'$ et nous pourrons donc désormais
supposer que $\lambda = \lambda'$, $\rho = \rho'$.

D'après l'hypothèse (2), on a donc $d = \mathrm{Card}(Q)$. En raison de notre
choix des vecteurs $t\rho$ ($t \in T$), l'hypothèse que $s\lambda \cdot t\rho$ soit identiquement
contenu dans la partie $I$ de $K$ implique que toutes les coordonnées non nulles
des vecteurs $s\lambda$ ($s \in S$) soient aussi dans $I$.

Nous en concluons que la relation d'équivalence $\approx$ sur $S$ définie
par $\lambda^{-1}(s_1 \approx s_2 \text{ssi } s_1^\lambda = s_2^\lambda)$ n'a qu'un nombre *fini* ($\le (1+\mathrm{Card}(I))^d$) de classes.

Posons $X_k = k\chi^{-1}$ et $s^{-1}X_k = \{ s' \in S : ss' \in X_k \}$ pour chaque $k \in I$
et $s \in S$ et désignons par $\sim$ la relation d'équivalence sur $S$ définie par
$s_1 \sim s_2 \text{ ssi } s_1^{-1}X_k = s_2^{-1}X_k$ pour chaque $k \in I$. Il est clair que $s_1 \approx s_2$
implique $s_1 \sim s_2$ et que, réciproquement, d'après notre choix de vecteurs
$t\rho$ ($t \in T$) on ne peut avoir $s_1 \approx s_2$ que si $s_1 \sim s_2$.

De plus, chaque $X_k$ est une union de $\sim$-classes puisque, S étant un
monodée, on a :

$$
X_k = \{ s \in S : 1 \in s^{-1} X_k \}.
$$
Ceci permettrait d'achever la preuve en utilisant la Proposition 12.1
de [1] . Par souci d'être complet, nous en reproduisons la partie pertinente.

Soient $s, s_1, s_2 \in s_2 \in S, k \in I$ tels que $s_1^{-1} X_k = s_2^{-1} X_k$. L'ensemble $(s_1 s)^{-1} X_k$ est égal à $s^{-1}(s_1^{-1} X)$ puisque $1 \in S$, et il est par conséquent égal à $(s_2 s)^{-1} X_k$ ce qui montre que l'équivalence $\sim \approx$ admet la multipli-cation à droite.

Il existe donc un morphisme $\phi$ de $S$ dans le monoïde *fini* des applica-
tions dans lui-même de l'ensemble $S/\sim$ qui est en bijection avec $\{ s\lambda : s \in S \}$.
Comme $S$ est un monoïde, on a $Y\phi\phi^{-1} = Y$ pour chaque $\sim$-classe ou union de
$\sim$-classes $Y \subset S$. Donc en particulier $X = X\phi\phi^{-1}$ est reconnaissable.

Q.E.D.

Références :

[1] S. Eilenberg. Automata, languages and machines. ( vol A ).
Academie Press. New-York 1974.

[2] M. Fliess ( 1974 ). Matrices de Hankel. J.Math. Pures et Appli.53 pp. 197 - 222.