# Sur le produit de concatenation non ambigue

Marcel-Paul Schützenberger

► To cite this version:

Marcel-Paul Schützenberger. Sur le produit de concatenation non ambigue. [Rapport de recherche] IRIA-RR-181, IRIA. 1976, pp.30. hal-04716347

HAL Id: hal-04716347

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

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
RR181

RIA

laboria

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

Institut de Recherche
d'Informatique
et d'Automatique
(Code 115)

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

Dnr: 02045.

laboratoire de recherche
en informatique
et automatique

SUR LE PRODUIT
DE CONCATENATION NON AMBIGU

Marc Paul SCHÜTZENBERGER

30p.

Rapport de Recherche N° 181

Juillet 1976
SUR LE PRODUIT DE CONCATENATION NON AMBIGU

M.P. Schützenberger

Résumé :

On étudie les implications syntaxiques du produit de concaténation non ambigu.

Abstract :

One studies syntactical implications of non ambiguous concatenation product.
# I. INTRODUCTION

Cet article est une application des méthodes développées par S. Eilenberg [5, Vol B] pour caractériser certaines familles de semi-groupes au moyen de constructions sur les parties de semi-groupes ou de monoïdes libres. Nous nous permettrons dans cette introduction de rappeler quelques éléments des concepts et des notations de ce traité plutôt que d'y multiplier les références.

Une variété (de semi-groupes ou de monoïdes) est une famille d'objets contenant chaque *diviseur* (= objet quotient d'un sous objet) du produit direct de deux quelconques de ses membres. On notera la différence entre ce concept et celui de "variété au sens de Birkhoff". Pour nous limiter à des exemples qui interviendront par la suite, citons la variété des semi-groupes commutatifs, et celle des semi-groupes idempotents (qui sont toutes les deux des variétés au sens de Birkhoff), la variété de semi-groupes union de groupes finis (qui n'en n'est pas une), celle des semi-groupes finis *G*-triviaux (c'est-à-dire dans lesquels chaque *G*-classe est un singolet) en prenant pour *G* l'une quelconque des relations *J*, *R*, *L* ou *H* de Green.

La variété des semi-groupes *J*-triviaux est caractérisée par un théorème profond de I. Simon [14] ; celles des semi-groupes *R* ou *L* triviaux jouent un rôle dans la théorie de la hiérarchie de J. Brzozowski ([1], [2]). Les semi-groupes *H*-triviaux ont été introduits par R. Mc Naughton (cf. [8]). Nous suivrons S. Eilenberg qui les nomme *apériodiques*. L'objet du présent article sera la variété, notée $\mathcal{D}_f$, des semi-groupes *finis* dont chaque *J*-classe contenant un idempotent est un semi-groupe. Elle contient évidemment celle des semi-groupes *finis* dont chaque idéal principal idempotent est un idéal principal
à gauche (ou à droite) qui se rencontre dans la théorie de la complexité ([14]), et qui a été récemment étudiée par G. Lallemend [6], [7].

Dans la première partie de cet article on examine quelques propriétés formelles des monoïdes de $\mathcal{D}_f$. En particulier on vérifie que $\mathcal{D}_f$ est l'ensemble des monoïdes *finis* d'une famille plus générale $\mathcal{D}$ qui, de façon intuitive, est constituée par les semi-groupes dont la structure des idéaux n'est pas complètement oblitérée par passage à leur quotient commutatif (ou idempotent). Pour être plus précis, disons qu'un morphisme $\phi$ d'un semi-groupe $S$ dans un semi-groupe $T$ est *injectif* sur les idéaux principaux idempotents ssi deux tels idéaux de $S$ sont égaux quand leurs images par $\phi$ engendrent le même idéal de $T$. On a alors la :

**DEFINITION.** $\mathcal{D}$ est la famille des semi-groupes tels que le morphisme naturel sur leur plus grand quotient commutatif et idempotent soit injectif sur les idéaux principaux idempotents.

Cette condition est trivialment satisfaite par les semi-groupes idempotents et des théorèmes classiques de Clifford montrent que tous les semi-groupes commutatifs de même que les semi-groupes union de groupes appartiennent à $\mathcal{D}$.

On distinguera dans $\mathcal{D}$ la sous-famille $\mathcal{D}_1$ (resp. $\mathcal{D}$, resp. $\mathcal{D}_1\mathfrak{r}$) des semi-groupes dont la $J$-classe de chaque idéal idempotent est une $L$-classe (resp. $R$-classe, resp. un groupe). Un autre cas particulier sera la famille $\mathcal{D}^0$ des semi-groupes ayant un et un seul idéal idempotent qui est leur idéal minimum.

Ces considérations dépendent de façon essentielle de la théorie de la décomposition en semi-treillis de Tamura et Kimura [15], Yamada [20] et M. Petrich [10] à laquelle nous avons fait de larges emprunts Venons-en aux monoïdes libres.

Rappelons que si $X, Y, \dots$ sont des parties d'un semi-groupe $S$ on note $X^+$ (resp. $X^* = \{1\} \cup X^+$) le sous-semi groupe (resp. sous-monoïde) engendré par $X$ ; $XY = \{xy \in S : x \in X, y \in Y\}$, $X^{-1}YZ^{-1} = \{s \in S : Y \cap XsZ \neq \emptyset\}$. Suivant Eilenberg, un sous semi-groupe $P$ de $S$ sera dit *unitaire* (en symbole $P \in \mathcal{U}(S)$) ssi $P^{-1}P = P \neq \emptyset$ ; nous l'appellerons *bi-complet* ($P \in \mathcal{B}(S)$) ssi de plus $S = S^{-1}P$.

Enfin on sait qu'étant donnée une collection $\{X_i : i \in I\}$ de parties de $S$, il existe une congruence maximale sur $S$ dont chaque $X_i$ est une union de classes ; le quotient correspondant de $S$ est le semi-groupe syntaxique $\text{Synt}(X_i : i \in I)$ de la collection. Une partie $X$
est dite reconnaissable ssi $\text{Synt}(X)$ est fini.

**PROPRIETE 1.** $\mathcal{D}_f$ est la plus petite variété $\mathcal{V}$ qui contienne pour chaque alphabet fini $A$ le semi-groupe syntaxique de tout sous semigroupe reconnaissable unitaire bi-complet $P \in \mathcal{B}(A^+)$ satisfaisant la condition supplémentaire :

(#). Chaque sous semi-groupe unitaire $Q$ contenu dans $P$ et tel que $\text{Synt}(Q)$ soit un quotient de $\text{Synt}(P)$ vérifie $(A^+)^{-1}Q \subset Q(A^+)^{-1}$.

On notera que si l'on remplace la condition $(A^+)^{-1}Q \subset Q(A^+)^{-1}$ par $A^+ = Q(A^+)^{-1}$ (resp. par $A^+ = (A^+)^{-1}Q$) on caractérise de la même façon la sous variété $\mathcal{D}_f^0$ (resp. $\mathcal{D}_f^01$) des semi-groupes finis dont tous les idempotents sont dans l'idéal minimum (resp. dans un idéal à gauche principal minimum).

Comme le semi-groupe syntaxique d'une partie d'un monoïde libre $A^*$ est automatiquement un monoïde, on obtient une caractérisation des monoïdes de $\mathcal{D}_f$ en remplaçant partout $A^+$ par $A^*$ dans l'énoncé précédent. En particulier la variété des groupes finis est obtenue en imposant la condition $A^* = Q(A^*)^{-1}$ dans (#), ainsi qu'on le vérifie facilement en prenant $Q = \{1\}$.

D'autre part, en utilisant les travaux de Y. Cesari [3] et de D. Perrin [8], on pourrait montrer que $\mathcal{D}_f^0$ contient la variété engendrée par les semi-groupes syntaxiques des sous semi-groupes $P$ de $\mathcal{B}(A^+)$ qui sont finiment engendrés et que cette dernière contient la variété des semi-groupes union de groupes de $\mathcal{D}_f^0$.

La sous variété $\mathcal{D}_f \cap \mathcal{A}_P$ des semi-groupes de $\mathcal{D}_f$ qui sont apériodiques (c'est-à-dire dont tous les groupes sont triviaux) admet une caractérisation plus immédiate. Il en est de même de la famille des monoïdes finis $\mathbb{R}$ (resp. $\mathbb{L}$) triviaux (qui sont les monoïdes apériodiques finis de $\mathbb{D}_1$ (resp. $\mathbb{D}_1\mathbb{r}$)).

Les énoncés de cette partie du travail sont indépendants des résultats obtenus au cours de la preuve de la Propriété 1. Suivant S. Eilenberg nous employons la notation $A^* \cong \mathcal{V}$ pour désigner la famille des parties du monoïde libre $A^*$ dont le monoïde syntaxique appartient à un ensemble donné $\mathcal{V}$ de monoïdes.

Rappelons qu'un produit $XY$ de deux parties d'un monoïde libre $A^*$ est non ambigu ssi chaque $A$ de $A^*$ admet au plus une factorisation $a = xy$ avec $x \in X$ et $y \in Y$ et appelons completion polynomialie non ambiguë $\text{UPol}(X)$ d'une famille $\mathcal{X}$ de parties de $A^*$ la plus petite famille $\mathcal{Y}$ qui contienne $\mathcal{X}$ et les parties suivantes :
(i) Chaque lettre a de A et chaque sousmonoïde $B^*$ où $B \subset A$;

(ii) Chaque union *disjointe* $Y_1 \cup Y_2$ et chaque produit *non ambigu* $Y_1 Y_2$ où $Y_1, Y_2 \in \mathcal{Y}$.

Nous établirons la :

**PROPRIETE 2.** Pour chaque alphabet A, la famille $A^* = (D_f \cap A_p)$ est la plus petite famille de parties de $A^*$ égale à sa complétion polynomiale non ambiguë.

On peut imposer au produit XY des conditions plus strictes que d'être non ambigu. Nous introduirons ainsi sans la section IV un "produit déterministe" et un "produit bidéterministe" et les complétions polynomiales correspondantes.

En application directe de la théorie des produits en couronne de J. Rhodes et de Bret Tilson ([14] [12], [13], [16], [17]) on obtiendra l'énoncé suivant dans lequel $\mathcal{G}$ est une variété donnée de groupes finis et, où par abus de notations, $\mathcal{G} \subset \mathcal{D}1$ (resp. $\mathcal{G} \subset \mathcal{D}1r$) désigne la famille des monoïdes finis de $\mathcal{D}1$ (resp. de $\mathcal{D}1r$) dont tous les groupes appartiennent à $\mathcal{G}$.

**PROPRIETE 3.** Pour chaque alphabet A, $A^* - \mathcal{G} \subset \mathcal{D}1$ (resp. $A^* - \mathcal{G} \subset \mathcal{D}1r$) est la plus petite famille $\mathcal{X}$ de parties de $A^*$ qui soit égale à sa complétion polynomiale déterministe (resp. bidéterministe) et qui contienne chaque intersection de la forme $X \cap Y$ où $X \in \mathcal{X}$ et $Y \in A^* - \mathcal{G}$.

Ceci suggère la question plus intéressante suivante qui se rattachante à la théorie des semi-groupes orthodoxes de Clifford. Dans celle-ci $\text{Pol}(A^* - \mathcal{G})$ désigne la plus petite algèbre booléene de parties de $A^*$ contenant le produit (de concaténation) de deux de ses membres et chaque partie *finie* ou dont le monoïde syntaxique est un groupe de la variété $\mathcal{G}$.

Est-ce que $\text{Pol}(A^* - \mathcal{G}) = A^* - \mathcal{G} \subset \mathcal{E}$ où $\mathcal{G} \subset \mathcal{E}$ désigne la variété des monoïdes finis dont les groupes sont dans $\mathcal{G}$ et dont les idempotents engendrent un sous monoïde apériodique ?

## II. GENERALITES

Pour des raisons de commodité typographiques tous les énoncés de cette section sont formulés dans le langage des monoïdes. Ils s'appliquent aussi bien à un semi-groupe quelconque en considérant celui-ci comme l'idéal propre maximal du monoïde formé en lui adjoignant un
un élément neutre.

Nous réservons la notation $\xi = \xi_S$ pour désigner pour chaque semi-groupe $S$ le morphisme naturel de celui-ci sur son plus grand quotient commutatif et idempotent, c'est-à-dire sur $S/\equiv \text{où } \equiv$ est la plus petite congruence sur $S$ telle que l'on ait identiquement $s's' \equiv s's$ et $s \equiv s^2$ ($s,s' \in S$).

Une partie $X$ d'un monoïde $M$ est dite consistante ssi $M^{-1}XM^{-1} \subset X$ c'est-à-dire ssi toute relation $mm'm'' \in X$ implique $\{m,m',m''\} \subset X$ ($m,m',m'' \in M$) ; elle est dite fermée par conjugaison (ou "reflexive" selon Clifford) ssi pour chaque $m \in M$ on a $m^{-1}X = Xm^{-1}$ ; enfin on pose $\sqrt[X]{X} = \{m \in M : X \cap m^+ \neq \emptyset\}$ où, on le rappelle, $m^+ = \{m, m^2, \dots, m^n, \dots\}$ est le sous semi-groupe engendré par $m$.

L'énoncé suivant résume les propriétés du morphisme $\xi = \xi_M$ qui nous serviront par la suite. Dans celui-ci $M$ est un monoïde quelconque. De fait, toute cette partie.

II.1. (1) Chaque classe d'équivalence $E$ de la congruence $\equiv$ est un semi-groupe $E = \sqrt[E]{E}$, fermé par conjugaison et contenant chaque $J$-classe qu'il rencontre ;

(2) Un sous-monoïde unitaire $P$ de $M$ est une union de classes ssi il est consistant.

**PREUVE.** (1) Comme $m \equiv m^2$ identiquement, chaque classe $E$ est égale à $\sqrt[E]{E}$ ; en outre $m \equiv m'$ implique $m \equiv m^2 \equiv mm'$ et $E$ est donc un semi-groupe ; enfin $E$ est fermé par conjugaison d'après l'identité $mm' \equiv m'm$.

Il est trivial que les $J$-classes de $M\xi = M/\equiv$ sont précisément les éléments de ce monoïde. Comme tout morphisme de $M$ envoye chaque $J$-classe $D$ de $M$ dans une partie d'une $J$-classe de l'image, il en résulte que $D\xi$ est un élément de $M\xi$ ce qui achève la preuve de (1).

(2) Soit $P$ un sous-monoïde unitaire de $M$. S'il est une union de classes, chaque relation $m'm \in P$ implique que $m'mm \in P$ donc que $m \in (m'm)^{-1}(m'mm) \subset P^{-1}P$ appartienne à $P$. On a de même $mm' \in P$ d'où $m' \in m^{-1}P \subset P$ ce qui montre que $P$ est consistant. Réciproquement si $P$ est consistant et si $m_1m_2m_3m_4 \in P$ on a $m_1, m_2, m_3, m_4 \in P$, d'où $m_1m_3m_2m_4 \in P$. On vérifie de même que $m_1m_2m_3 \in P$ ssi $m_1m_2m_2m_3 \in P$ ce qui montre que $P$ contient chaque
≡ -classe qu'il rencontre.

Q.E.D.

Nous désignons par $Jid = Jid(M)$ la famille des $J$-classes $D$ de $M$ qui engendrent un idéal idempotent. En application des remarques précédentes on a :

II.2. Deux conditions nécessaires et suffisantes équivalentes pour que $M$ appartienne à la famille $\mathcal{D}$ sont :

(1). $D \to \mathcal{D}\xi$ est une injection de $Jid(M)$ dans $M\xi$ :

(2). Il existe un semi-groupe $T$ de $\mathcal{D}$ et un morphisme $\phi : M \to T$ qui est injectif sur les idéaux idempotents.

**PREUVE.** (1) Résulte immédiatement de l'énoncé précédent puisque $Jid(M\xi) = M\xi$. Pour vérifier (2) rappelons qu'un idéal principal est idempotent ssi sa $J$-classe $\mathcal{D}$ satisfait $\mathcal{D} \cap \mathcal{D} \neq \emptyset$, ce qui montre que tout morphisme $\phi : M \to T$ induit une application de $Jid(M)$ dans $Jid(T)$. D'autre part le caractère naturel des morphismes $\xi_M$ et $\xi_T$ fait qu'il existe un morphisme $\Psi$ de $M\xi_M$ dans $T\xi_T$ tel que $\phi\xi_T = \xi_M\Psi$. Par conséquent si $T \in \mathcal{D}$ et si $\phi$ est injectif sur les idéaux principaux idempotents, le morphisme $\xi_M$ doit être une injection de $Jid(M)$ dans $M\xi_M$ et par conséquent $M$ appartient à $\mathcal{D}$. La condition (2) est donc suffisante. On vérifie qu'elle est trivlement nécessaire en prenant $T = M\xi_M$ et $\phi = \xi_M$.

Q.E.D.

II.3. Une condition nécessaire et suffisante pour qu'une partie non vide $\mathcal{D}$ de $M$ soit l'idéal minimum d'un sous monoïde consistant de $M$ est qu'elle soit à la fois une $J$-classe et un semi-groupe. On a alors $P = \mathcal{D}^{-1}$, $\mathcal{D} = \mathcal{D}\mathcal{D}^{-1}$.

**PREUVE.** (1). La condition est nécessaire car, d'une part chaque idéal minimum d'un sous monoïde de $M$ est un semi-groupe, et d'autre part, d'après II.1(2), chaque $J$-classe d'un sous monoïde consistant de $M$ est une $J$-classe de $M$.

(2) Réciproquement, soit $\mathcal{D}$ une $J$-classe de $M$. $\mathcal{D}$ est l'intersection de l'idéal MDM avec l'ensemble $C = M^{-1}\mathcal{D} M^{-1}$ des éléments de $M$ qui engendrent un idéal contenant MDM. Ce deuxième ensemble $C$ est consistant.

Posons $P = \mathcal{D}^{-1}\mathcal{D}$ et soit $p \in P$. Il existe $d \in \mathcal{D}$ pour lequel $dp \in \mathcal{D}$. Si $p = \text{mm}'$ on a $(\text{dm}) m' \in \mathcal{D}$ donc $\text{dm} \in \text{MDM} \cap \mathcal{C} = \mathcal{D}$ ce qui montre que $m \in P$ et $m' \in (\text{dm})^{-1}\mathcal{D} \subset \mathcal{D}^{-1}\mathcal{D}$, établissant ainsi que
P est consistant.

Supposons désormais que la J-classe D est un semi-groupe. On a $D \subset P$ puisque $DD \subset D$. De plus chaque relation $dp \in D$ ($d \in D$) entraîne $dpD \subset DD \subset D$ donc $pD \subset MDM \cap C = D$ et l'on a donc la double inclusion $PD \subset D \subset P$.

Il en résulte que P est un semi-groupe car si $p, p' \in P$, $d \in D$ et $dp \in D$, on a $dpp'D = (dp)(p'D) \subset DD \subset D$ d'où $pp'D \subset d^{-1}D \subset P$ et enfin $pp' \in P$ puisque P est consistant.

Maintenant, le fait que D soit une J-classe dans M et que $P \subset M^{-1}DM^{-1}$ entraîne qu'elle soit une J-classe dans P. Comme $DD \subset PD \subset D$, D est l'idéal minimum de P et la relation $P = DD^{-1}$ découle de $PD \subset D$, par symétrie gauche-droite.

Q.E.D.

II.4. Soit M un monoïde tel que chaque $m^+$ ($m \in M$) rencontre au moins une classe de Jid(M). Chacune des deux conditions suivantes est nécessaire et suffisante pour que $M \in D$.

(1) $D \to D\xi$ est une bijection de Jid(M) sur $M\xi$.

(2) Chaque classe de Jid(M) est un semi-groupe.

**PREUVE.** (1) Ceci résulte immédiatement de II.2(1) et de l'hypothèse supplémentaire sur M, puisque cette dernière entraîne que l'image inverse de chaque élément de M rencontre au moins une classe de Jid(M).

(2) Si $D \in Jid(M)$ n'est pas un semi-groupe, il existe $d, d' \in D$ tels que pour chaque $n \ge 1$ l'idéal principal $M(dd')^n M$ soit une partie propre de MDM. Comme $(dd')^n \xi = D\xi$, on en déduit immédiatement que sous l'hypothèse supplémentaire faite sur M, la condition (2) est nécessaire pour que M appartienne à D. Réciproquement, si chaque classe D de Jid(M) est un semi-groupe, l'énoncé précédent montre que $D \to D^{-1}D$ est une injection de Jid(M) dans la famille des sous-monoïdes consistant de M, donc d'après II.1.2., que $D \to (D^{-1}D)\xi \cap D\xi = D\xi$ est une injection de Jid(M) dans Mξ et par conséquent que M appartient à D.

Q.E.D.

Comme les J-classes des idéaux idempotents des semi-groupes commutatifs sont des groupes, ainsi qu'il est bien connu, l'énoncé précédent montre que D contient tous ces semi-groupes. Il en est de même pour les autres familles mentionnées dans l'introduction.
Nous considérons maintenant exclusivement les semi-groupes $S$ satisfaisant la condition suivante :
(Gp) Chaque semi-groupe $s^+$ ($s \in S$) rencontre un groupe dans $S$.

Les théorèmes classiques de Clifford prouvent que chaque $J$-classe $D$ d'un tel semi-groupe et une $\mathcal{D}$-classe complètement $0$-simple. En particulier $DD \cap D \neq \emptyset$ (resp. $DD \subset D$) ssi $D$ contient un groupe (resp. est une union de groupes).

Pour chaque $s \in S$ nous désignerons par $s^\omega$ l'idempotent du groupe (nécessairement unique) rencontrant $s^+$. Il est clair que $s^\omega = s^n$ pour tout $n \in \mathbb{N}$ assez grand quand tous les éléments des groupes dans $S$ ont un ordre fini.

Nous rappelons la notation $\underline{D}^\circ$ pour désigner la famille des semi-groupes dont tous les idempotents sont contenus dans l'idéal minimum.

II.5. Soit $M$ un semi-groupe satisfaisant (Gp). Il appartient à $\underline{D}$ ssi il admet une partition en semi-groupes fermés par conjugaison, satisfaisant (Gp) et appartenant à $\underline{\mathcal{D}}^\circ$. Ces semi-groupes sont alors les classes de la congruence $\equiv$.

**PREUVE.** (1). Soit $E$ une classe de $\equiv$. On a vu dans II.1(1) que $E = \sqrt{E}$ est un semi-groupe fermé par conjugaison qui contient chaque $J$-classe de $M$ qu'il rencontre. Il satisfait donc (Gp) en même temps que $M$. Comme cette condition implique l'hypothèse supplémentaire de l'énoncé précédent et comme, triviallement, chaque idempotent est contenu dans la $J$-classe d'un idéal idempotent, ce même énoncé montre que si $M \in \underline{D}$, il existe exactement une classe $D$ de $\mathrm{Jid}(M)$ qui soit contenue dans $E$ et que tous les idempotents de $E$ se trouvent dans $D$. D'après II.3. $D$ est l'idéal minimum de $P = \underline{D}^{-1}D$ donc de $E$ puisque $D \subset E \subset P$.

La condition énoncée est donc nécessaire.

(2) Réciproquement soit $E$ un composant d'une partition $\{E_i : i \in I\}$ de $M$ en semi-groupes. Ceci implique que $E = \sqrt{E}$. Si de plus chaque $E_i$ satisfait (Gp) chaque élément $m$ de $M$ appartient au composant $E_i$ qui contient l'idempotent $m^\omega$. Donc $E$ contient $\sqrt{\underline{G}}$ pour chaque groupe $G$ qui le rencontre.

Introduisons l'hypothèse que $E$ est fermé par conjugaison et soient $u = u^2 \in E$ et $D$ la $J$-classe de $M$ contenant $u$. En raison de l'hypothèse que $M$ satisfait (Gp), $D$ est une $\mathcal{D}$-classe. Par conséquent pour chaque idempotent $v \in D$ on peut trouver $x \in uM \cap Mv$
et $y \in Mu \cap vM$ tels que $xy = u$, $yx = v$, donc $v \in E$ montrant que $E$ contient tous les groupes dans $D$.

Faisant jouer la dernière condition que $E \in D^0$, on vérifie que l'union des groupes dans $D$ est contenue dans l'idéal minimum de $E$. Donc $D$ est cet idéal minimum (et par conséquent un semi-groupe). En outre $E$ ne peut rencontrer aucune autre classe de Jid(M) puisque chaque $J$-classe d'un sous semi-groupe de $M$ est contenue dans une $J$-classe de $M$.

Supposons pour finir que ces deux conditions de fermeture par conjugaison et d'appartenance à $D^0$ sont satisfaites par chacun des composants $E_i$. Le raisonnement précédent montre que toutes les classes de Jid(M) sont des semi-groupes, donc que $M \in D$.

(3) La construction qui vient d'être effectuée établit une bijection à travers Jid(M) entre les $E_i$ et les classes de la congruence $\equiv$. Comme tous les composants de ces deux partitions sont des semi-groupes fermés par $m \to m^\omega$ d'après l'hypothèse (Gp), on voit facilement que les $E_i$ sont les classes de $\equiv$.

Q.E.D.

II.6. Soit $M$ un semi-groupe satisfaisant (Gp). Il appartient à $D^0$ si il satisfait l'identité

$$((xy)^\omega (yx)^\omega (xy)^\omega)^\omega = (xy)^\omega \quad (x,y \in M).$$

Donc quand $M \in D^0$ tout semi-groupe quotient de $M$ appartient aussi à $D^0$ et il en est de même de ceux de ses sous semi-groupes qui satisfont (Gp).

**PREUVE.** (1). Supposons que $M$ appartient à $D^0$. Les deux idempotents $u = (xy)^\omega$ et $v = (yx)^\omega$ sont dans une même $J$-classe $D$. Comme celle-ci est une $D$-classe complètement simple, le produit uvu appartient à la même $R$-classe et à la même $L$-classe que $u$, c'est-à-dire au groupe dont $u$ est l'idempotent, ce qui établit l'identité.

(2). Réciproquement, supposons que celle-ci est satisfaite par $M$. Soit $x$ un élément quelconque d'une classe $D$ de Jid(M). En raison de l'hypothèse (Gp), $D$ est une $D$-classe contenant des idempotents et d'après un théorème classique de Clifford on peut trouver $y \in D$ tel que $xy = u$ et $yx = v$ soient deux idempotents de $D$. On a donc $(xy)^\omega = u$ ; $(yx)^\omega = v$. L'identité entraîne que le produit $xy.yx.xy$, donc $xx$, soient contenus dans $D$. Puisque les conditions de Green sont satisfaites par $M$, les relations $x,x^2 \in D$ impliquent que $x$ soit un élément d'un groupe. Donc $D$ est une union
de groupes. La théorie classique de Clifford montre alors que $D$ est un semi-groupe ce qui donne la conclusion cherchée que $M \in D$.

(3). Chaque identité satisfaite par $M$ est aussi satisfaite par chaque quotient et chaque sous semi-groupe de $M$. Comme il est trivial que les quotients de $M$ satisfont $(Gp)$ la dernière partie de l'énoncé découle directement de la première.

Q.E.D.

Il est clair que le produit direct de deux semi-groupes de $D$ satisfaisant $(Gp)$ a aussi ces deux propriétés.

C'est un théorème connu ([5]) que les semi-groupes de $D_1$ (resp. de $D_1r$), satisfaisant $(Gp)$ sont caractérisés par l'identité $(xy)^{\overline{w}x^w} = (xy)^w$ (resp. $(xy)^w = (yx)^w$). Par conséquent les familles $D_f, D_f^1$ et $D_{f1r}$ sont des variétés.

Les énoncés suivants sont des cas particuliers de théorèmes beaucoup plus généraux dus à J. Rhodes [13] et développés par B. Tilson [17]. Nous rappelons la notation $D^1$ pour la sous-famille des semi-groupes de $D$ dont tous les idempotents sont dans un idéal à gauche minimum et nous notons $\text{Lid}(M)$ la famille des $L$-classes de $M$ qui engendrent un idéal à gauche idempotent.

II.7. Soient $P$ un semi-groupe satisfaisant $(Gp)$ et $\pi : P \to M$ un morphisme surjectif tel que $u\pi^{-1} \in D^0$ (resp. $\in D^1$) pour chaque idempotent $u$ de $M$. Le morphisme $\pi$ induit une application bijective de $\text{Jid}(P)$ sur $\text{Jid}(M)$ (resp. $\text{Lid}(P)$ sur $\text{Lid}(M)$). Donc $P \in D$ quand $M \in D$.

**PREUVE.** Il est clair que l'application induite par $\pi$ est surjective. Il suffit donc de montrer que si les idempotents $r$ et $s$ de $P$ sont tels que leurs images $u = r\pi$ et $s\pi$ appartiennent à la même $J$-classe $D$ (resp. $L$-classe $L$) de $M$ on a $r \in \text{PsP}$ (resp. $r \in \text{Ps}$) puisque, par symétrie entre $r$ et $s$ ceci entraînera que ces deux éléments appartiennent à la même $J$-classe (resp. $L$-classe) de $P$.

Soit $E$ la $J$-classe de $r = r^2$. Comme $r \in u\pi^{-1}$ où $u = u^2$, $E$ est l'idéal minimum du semi-groupe $u\pi^{-1}$ puisque celui-ci appartient à $D^0$ par hypothèse. Donc $r \in \text{PtP}$ pour chaque $t \in u\pi^{-1}$. Si de plus, $u\pi^{-1} \in D^1$ on a de même $r \in \text{Pt}$.

Si $s\pi$ est dans la même $J$-classe (resp. $L$-classe) que $u$ il existe $m, m' \in M$ tels que $u = m \cdot s\pi \cdot m'$ (resp. $u = m \cdot l\pi \cdot m'$). Comme $\pi$ est surjectif on peut prendre des éléments quelconques $p \in m^{-1}$ et
$p' \in m'\pi^{-1}$ et l'on obtient l'élément $t = p \cdot s \cdot p' \in u\pi^{-1} \cap p\S P$ (resp. $= p \cdot s \in u\pi^{-1} \cap p\S S$) ce qui achève la preuve.

Q.E.D.

Nous rappelons enfin le cas particulier suivant des théorèmes généraux sur le produit en couronne.

II.8. Soient $M$ un semi-groupe, $S$ un semi-groupe de $D^0$ (resp. de $D_1^0$) satisfaisant (Gp) et $\pi$ le morphisme naturel sur $M$ du produit en couronne $P$ de $S$ dans $M$. Pour chaque idempotent $u$ de $M$ le semi-groupe $P_u = u\pi^{-1}$ appartient à $D^0$ (resp. à $D_1^0$).

**PREUVE.** Il suffit de vérifier que $p \in pp'P$ (resp. $p = pp'$) pour deux idempotents quelconques $p$ et $p'$ de $P_u$.

Soit $F$ l'ensemble des applications de $M$ dans $S$. Par définition $P$ est l'ensemble $F \times M$ muni du produit $(f,m)(f',m') = (f'',mm')$ où, à son tour, l'application $f''$ est définie par la condition que pour chaque $m'' \in M$ on ait $m''f'' = (m''f)((m''m)f')$. Les idempotents de $P$ sont donc les paires $(f,m)$ dans lesquelles $m$ est un idempotent et $f$ satisfait $m''f = (m''f)((m''m)f)$ pour tout $m'' \in M$. Supposant $m = m^2$, on note que cette dernière condition implique que $m''f$ soit un idempotent pour chaque $m'' \in M$ puisque $m'' = m''m = m''mm$ quand $m'' \in M$.

Donc, d'après l'hypothèse $S \in D^0$ qui implique que chaque idempotent de $S$ soit contenu dans son idéal minimum $D$, une condition nécessaire pour que $(f,u)$ soit idempotent est que $f$ envoie $M_u$ sur le sous-ensemble $D_1$ des idempotents de $D$. De plus, comme $S$ satisfait (Gp), $D$ est un semi-groupe union de groupe et pour chaque $s \in S$ on a $s = se$ $(e \in D_1)$ ssi $s$ appartient à la $L$-classe de $e$. Soient maintenant $p = (f,u)$ et $p' = (f',u)$ deux idempotents. Pour chaque $m$ de $M_u$ les éléments $mf$ et $mf'$ sont des idempotents de $D$. Donc $(mf)(mf')(mf) = \bar{h}_m$ est un élément du groupe contenant $mf$ et l'on peut trouver dans ce dernier un élément $\bar{h}_m$ tel que $\bar{h}_m\bar{h}_m = mf$. Nous définissons l'élément $\bar{p} = (\bar{f},u)$ de $P_u$ par la condition que $\bar{m}\bar{f} = \bar{h}_{mu}$ pour chaque $m$ de $M$. Soit $p'' = (f'',u) = pp'\bar{p}$. Pour chaque $m \in M$, $mf = s$ est égal à se où $e = (mu)f$ et on calcule directement que $mf'' = s.(mu)f'.\bar{h}_{mu} = s.e = s$. Donc $p'' = p \in pp'P$.

Dans le cas particulier où $S \in D_1^0$, l'idéal $D$ se réduit à une seule $L$-classe. Donc si $p'' = pp' = (f'',u)$, on a pour chaque
$m \in M$ que $mf = s$ ; $muf = e = e^2$ ; $muf' = e' = e'^2$ où $s = e$ et où $e'e' = e$, $se' = see' = e$ ce qui donne directement $p'' = pp' = p$.

Q.E.D.

### III. LA PROPRIETE 1.

Nous commençons par rappeler quelques faits concernant la famille $U(S)$ des sous semi-groupes unitaires de $S$ c'est-à-dire, on le rapporte des sous semi-groupes $T$ tels que $T = T^{-1}T$. Dans ce qui suit $G$ est un groupe maximal dans $S$, $L$ sa $L$-classe et $L'$ le sous semi-groupe $L$-simple union des groupes dans $L$.

III.1. (1) Si $T \in U(S)$ rencontre $G$, l'intersection $T \cap G$ est un groupe de $T \cap L'$ est un semi-groupe $L$-simple contenant tous les idempotents dans $L$.

(2) Réciproquement, si $H$ est un sous groupe de $G$, l'intersection $T$ de tous les $T' \in U(S)$ contenant $H$ est un sous semi-groupe de $U(S)$ tel que $T \cap G = H$. Si la $J$-classe de $G$ est complètement $O$-simple on a de plus $T \cap MGM = T \cap L'$.

**PREUVE.** (1). Soient $g \in T \cap G$ et $h \in \text{l'inverse de } g$ dans $G$. L'idempotent $u = hg$ appartient à $T$ puisque $ghg = g$ implique $hg \in \{g\}^{-1}\{g\} \subset T^{-1}T \subset T$. Comme $u = gh$ on obtient $h \in \{g\}^{-1}\{u\} = T^{-1}T \subset T$ ce qui montre que $T \cap G = H$ est un sous groupe de $G$ puisque $T$, donc $T \cap G$ est un semi-groupe.

Si $v$ est un autre idempotent dans $L$ on a $uv = u$, donc, comme ci-dessus, $v \in T$. Par conséquent, puisque $T$ est un semi-groupe, son intersection avec $L$ contient le semi-groupe $L$-simple $V$ formé par l'union des groupes $vH$ où $v$ parcourt l'ensemble des idempotents dans $L$.

(2). Réciproquement, étant donné le sous-groupe $H$ de $G$, posons $T = H^{-1}H$. Tout sous semi-groupe unitaire de $S$ contenant $H$ doit contenir $T$. Soit $t \in T$. Il existe $h \in H$ tel que $ht = h' \in H$. Multipliant à gauche par $H$ on obtient $Ht = H$, puisque $H$ est un groupe. On a donc d'une part $TT \subset T$ (puisque $Ht' = Ht' = H$ pour chaque $t' \in T$), et, d'autre part $T^{-1}T \subset T$ (puisque, si $s \in S$ et $ts \in T$, on a $Hts = Hs = H$ d'où $s \in T$). Par conséquent $T$ est bien le plus petit sous semi-groupe unitaire contenant $H$.

Le reste de la preuve découle de la première partie qui montre
que T contient le semi-groupe *L*-simple $V = Tn L'$ et des résultats classiques sur les *J*-classes complètement *O*-simples qui impliquent $Hx \cap H = \emptyset$ donc $x \notin T$ pour tout $x \in MGM\backslash V$.

Q.E.D.

Nous désignons par $U^1(S)$ la famille des sous semi-groupes unitaires de la forme $H^{-1}H$ où $H = \{u\}$ est un groupe trivial (c'est-à-dire réduit à un idempotent $u$) dans $S$. On rappelle que $\mathfrak{B}(S)$ désigne la sous famille des sous semi-groupes unitaires $T$ qui sont *bi-complets* en ce sens que $S \subset S^{-1}T$. Cette sous famille n'est pas vide car elle contient toujours au moins $S$ lui-même. Nous utiliserons le fait que chaque $T \in \mathfrak{B}(S)$ contient tous les $Q \in U^1(S)$. En effet, si $u$ est un idempotent dans $S$, l'hypothèse que $T$ est bicomplet implique $su = t \in T$ pour au moins un $s \in S$. Comme $tu = suu = su = t$ et comme $T$ est unitaire, ceci implique $u \in T$ donc $u^{-1}u \in T$.

### III.2. Soit $M$ un semi-groupe satisfaisant (Gp).

(1) Si $M \in \mathcal{D}$ on a $M^{-1}Q \subset QM^{-1}$ pour tout $Q \in U(M)$.

(2) Si $M^{-1}Q \subset QM^{-1}$ pour chaque $Q \in U^1(M)$ on a $M \in \mathcal{D}$.

**PREUVE.** (1). Supposons ces hypothèses satisfaites et soit $x \in M^{-1}Q$, c'est-à-dire $mx \in Q$ pour un certain $m \in M$. Puisque $M$ satisfait (Gp), une puissance positive $q = (mx)^n$ ($n \ge 1$) de $mx$ appartient à un groupe dans $M$. Comme $Q$ est un semi-groupe il contient $q$, donc, ainsi qu'on l'a vu en III.1., un groupe $H$ dans lequel se trouve l'élément $q$.

D'autre part puisque $M$ appartient à $\mathcal{D}$, il existe un sous semi-groupe premier $R$ dont l'idéal minimum est la *J*-classe $\mathcal{D}$ contenant $H$. On a $x \in R$ puisque $R$ est premier et $(mx)^n \in H \subset R$.

De plus, $\mathcal{D}$ est un semi-groupe union de groupes. Prenons $h \in H$ quelconque. On a $x \in \mathcal{D}$ ce qui signifie que $xh = vg$ où $v$ est un idempotent dans la *L*-classe $L$ de $H$ et où $g$ est un élément du groupe maximal $G$ contenant $H$. On a vu dans III.1. que $v \in Q$. Prenant l'inverse $g'$ de $g$ dans $G$, on a $xhg' = v \in Q$, ce qui est la conclusion cherchée $x \in QM^{-1}$.

(2). Supposons inversement que $M$ n'appartienne pas à $\mathcal{D}$. C'est-à-dire en raison de l'hypothèse (Gp) qu'il existe une classe $\mathcal{D} \in \text{Jid}(M)$ qui ne soit pas un semi-groupe. D'après un théorème classique de Clifford $\mathcal{D}$ a une *L*-classe $L$ qui contient à la fois un idempotent $u$ et un élément $x$ n'appartenant pas à un groupe dans
M. Plus précisément l'idéal à droite $xM$ ne rencontre aucun des groupes dans L. Considérons $Q = u^{-1}u$. D'après III.1., c'est un semi-groupe unitaire dont l'intersection avec MLM est formée des idempotents dans L. De nouveau d'après la théorie des inverses de Clifford on peut trouver un élément $y \in D$ pour lequel $yx = u$. On a par conséquent $x \in M^{-1}Q\backslash QM^{-1}$ prouvant que la condition (2) est suffisante pour que $M \in D$.

Q.E.D.

III.3. Tout semi-groupe $S'$ est contenu dans un semi-groupe $T$ admettant un sous semi-groupe $R \in B(T)$ pour lequel $T = \text{Synt}(R)$. Quand $S'$ $S' \in D_f$ on peut choisir un tel $T$ dans $D_f$.

**PREUVE.** (1). Nous transformons $S'$ en un monoïde $S$ en lui ajoutant un élément neutre $e$. Nous prenons un groupe $G$ et un sous-groupe $H \neq G$ de $G$ ayant au moins autant d'éléments que $S$ et ne contenant aucun sous-groupe invariant $\neq \{1\}$ de $G$. Il est clair que quand $S$ est fini on peut prendre un groupe $G$ fini. Nous considérons le monoïde $M$ des $S \times S$ matrices à entrées dans l'algèbre de $G$ ayant exactement une entrée non nulle par colonne, celle-ci appartenant de plus à $G$ lui-même. Soit $\mu$ le morphisme injectif de $S$ dans $M$ envoyant chaque $s \in S$ sur la matrice $s\mu$ telle que chacune de ses entrées $s\mu(s,s')$ soit égale à $1$ ($=1_G$) ou $0$ selon que $s' = ss'$ ou non. Nous notons $M_e$ le sous semi-groupe des matrices de $M$ dont toutes les entrées non nulles sont dans la ligne $e$. A chaque $g \in G$ nous associons la matrice $u^g \in M_e$ telle que $u(e,s) = g$ pour tout $s \in S$. Enfin, nous choisissons arbitrairement une matrice $v$ $v \in M_e$ telle que ses entrées $v(e,s)(s \in S)$ soient des éléments de $H$ tous distincts, ce qui est possible puisque $\text{Card}(H) \geq \text{Card}(S)$ par hypothèse.

Ceci fait $T$ est défini comme le sous semi-groupe de $M$ engendré par les $s$ ($s \in S$), les $u^g$ ($g \in G$) et $v$ et son semi-groupe $R$ comme celui des matrices de $T$ dont toutes les entrées non nulles sont dans $H$.

(2). Il est clair que $T$ est fini quand $S$ est fini. Montrons que $T \in D$ quand $S \in D$. Pour cela il suffit de vérifier que toutes les classes de $\text{Jid}(T)$ sont des sous semi-groupes. Comme $T$ est l'union de $S$ et d'un ensemble $D$ de matrices lignes, il suffit de montrer que $D$ est l'idéal minimum de $T$ c'est-à-dire, par exemple
que $u^1d = d$ (pour tout $d \in D$) ce qui est trivial, et que $u^1$ ap-
partient à tous les idéaux de $T$, ce qui résulte du calcul immédiat
$u^1 = ug.t.s.u^1$ pour chaque $t \in T$ en prenant une de ses entrées
non nulles quelconque $t(s;s) = g'$ et pour $g$ l'inverse de $g'$ dans
$G$.

(2). Nous vérifions $R \in B(T)$. Tout d'abord c'est un semi-groupe puisque $HH \subset H$. Il est unitaire car si $t \in T$ et $p \in R$ sont tels que $q = pt \in T$ on a $pt \in R$ puisqu'à chaque entrée non nulle $t(s;s)$ correspond au moins une entrée non nulle $p(s;s')$, qui est dans $H$, par hypothèse de même que le produit $q(s;s') = p(s;s')$ $t(s;s)$ ce qui implique $t(s;s) \in H^{-1}H \subset H$.

Pour montrer que $R$ est bi-complet nous considérons un $t$ de $T$
quelconque et une de ses entrées non nulles $t(s;s) = g'$. Si $g = g'^{-1}$
la matrice $s\mu.u^g$ a toutes ses entrées non nulles dans la ligne $s$.
On vérifie facilement que $t.s\mu.u^g = s'\mu.u^1$ où ce dernier produit ap-
partient à $R$ puisque $s'\mu$ et $u^1$ appartiennent à $R$ par défini-
tion. Donc $tT \cap R \neq \emptyset$ pour tout $t \in T$ et $T = T^{-1}R$.

(4). Il reste à établir $T = \text{Synt}(R)$, c'est-à-dire qu'étant donnés deux éléments distincts $t$ et $t' \neq t$ de $T$ on peut trouver $t_1, t_2 \in T$ tels que $t_1 \leq t_2 \in R$ et $t_1, t_2 \notin R$.

Par hypothèse on a $0 \neq t(s;s) \neq t'(s;s)$ pour au moins une paire
$(s;s)$. D'après notre choix de $v$ une relation analogue est encore
vraie pour $u^1t$ et $u^1t'$ et pour $vt$ et $vt'$. Ceci permet désormais
de supposer que $t,t' \in M_e$ et que l'on a $f = t(e,s) \neq f' = t'(e,s)$
$(f,f' \in G)$. Comme $H$ ne contient pas de sous-groupe normal non tri-
vial de $G$, on peut trouver au moins un $g \in G$ tel que $f^{-1}f' \notin g^{-1}Hg$.
Par conséquent $gf^{-1}fg^{-1} = 1 \in H$, $gf^{-1}f'g^{-1} \notin H$.

Un calcul direct donne alors $u^x t u^y \in R$, $u^x t' u^y \notin R$ en prenant
$x = gf^{-1}, y = g^{-1}$.

Q.E.D.

PREUVE DE LA PROPRIETE 1. Il sera commode de dire qu'un morphisme
$\phi : S \to T$ reconnait une partie X d'un semi-groupe Sssi $X\phi\phi^{-1} = X$,
c'est-à-dire, de façon équivalente, ssi il existe un morphisme de
l'image Sphi sur le semi-groupe syntaxique de X.

Nous utiliserons couramment la remarque que quand $\phi$ est un mor-
phisme surjectif qui reconnaît les parties X et Y de S on a
$(Y^{-1}X)\phi = (Y\phi)^{-1}(X\phi)$ et $(Xy^{-1})\phi = (X\phi)(Y\phi)^{-1}$. Par conséquent, suppo-
sant toujours $\phi$ surjectif, les relations $P \in U(S)$ et $P\phi \in U(S\phi)$
sont équivalentes pour chaque sous semi-groupe P reconnu par $\phi$.
Il en est de même pour la condition d'être bi-complet ou de satisfaire
la relation $S^{-1}P \subset PS^{-1}$.

Nous prions le lecteur de se rapporter à l'énoncé de la Proprié-
té I donné dans l'introduction. Comme tous les semi-groupes finis sa-
tisfont (Gp), il résulte immédiatement de II.6 que $Df$ est une variété.
Par conséquent, pour établir l'égalité $Df = V$ qui constitue la Pro-
priété I il suffit de vérifier les deux assertions (1) et (2) ci-des-
sous. On rappelle que P est reconnaissable si son semi-groupe syn-
taxique est fini.

(1). Soient A un alphabet fini et P ∈ B(A<sup>+</sup>) reconnaissable et sa-
tisfaisant la condition supplémentaire (#). Son semi-groupe synta-
xique M = Synt(P) est dans D.

PREUVE. Soit $\phi : A^+ \to M$ le morphisme syntaxique de P. Ainsi qu'on vient de le dire, P$\phi$ appartient à B(M). Chacun des sous semi-groupes Q ∈ U<sup>1</sup>(M) est reconnu par $\phi$, par définition, et par conséquent chaque semi-groupe syntaxique Synt(Q$\phi^{-1}$) est un quotient de M = A<sup>+</sup>$\phi$ = Synt(P). Donc en raison de la condition (#) chaque Q (qui est égal à Q$\phi^{-1}\phi$) satisfait M<sup>-1</sup>Q ⊂ QM<sup>-1</sup>. La conclusion désirée M ⊂ D résulte alors de II.2.(2).

Q.E.D.

(2). Soit S' ∈ Df. Il existe un alphabet fini A et un semi-groupe
reconnaissable P ∈ B(A<sup>+</sup>) satisfaisant la condition (#) tel que S'
divise Synt(P).

PREUVE. Nous appliquons à S' la construction décrite dans
III.3. Le semi-groupe obtenu T est fini et appartient à D. On
peut donc prendre un ensemble fini A et étendre une surjection
$\phi : A \to T$ à un morphisme $\phi$ de $A^+$ sur T. Soit $P = R\phi^{-1}$. Le
morphisme $\phi$ reconnaît P, par construction et, d'autre part,
d'après l'hypothèse $T = \text{Synt}(R)$ on a $P \neq P\Psi\Psi^{-1}$ pour tout morphisme
$\Psi$ de la forme $\phi\tau$ où $\tau$ est un morphisme de T sur un de ses
quotients propres. Donc $T = \text{Synt}(P)$.

En raison de $R \in B(T)$ on a $P \in B(A^+)$. En outre chaque sous
semi-groupe $Q \subset P$, $Q \in U(A^+)$ tel que $\text{Synt}(Q)$ soit un quotient de
$\text{Synt}(P)$ vérifie $Q = Q\phi\phi^{-1}$, donc $Q\phi \subset R$, $Q\phi \in U(T)$, ce qui implique
$T^{-1} \cdot Q\phi \subset Q\phi \cdot T^{-1}$ d'après III.2.(1) et, par conséquent,
$(A^+)^{-1}Q \subset Q(A^+)^{-1}$. Donc P satisfait (#) et comme S' est un sous
semi-groupe de $T$ le résultat est prouvé.

Q.E.D.

#### IV. LES PROPRIETES 2 ET 3.

Nous commençons par préciser une construction connue. Si $X$ et $Y$ sont deux parties d'un monoïde libre $A^*$, le produit $XY$ est d'ambiguïté bornée ssi il existe un entier $k$ tel que chaque mot de $A^*$ admette au plus $k$ factorisations distinctes comme produit d'un mot de $X$ par un mot de $Y$. Une partie $X$ est dite préfixe ssi elle est contenue dans le semi-groupe libre $A^+$ et si $XA^+ \cap X = \emptyset$, c'est-à-dire, de façon équivalente, ssi $X'Y$ est un produit non ambigu différent de $Y$ pour tout $X' \cup X$ et $Y \subset A^*$. De façon symétrique, $X$ est suffixe (ou préfixe opposé) ssi $X \subset A^+$ et $A^+X \cap X = \emptyset$.

Nous considérons maintenant un monoïde fini $M$ et deux de ses éléments $x$ et $y$. Soient $T (= T_{x,y})$ l'ensemble des paires $(m,m') \in M \times M$ telles que $x \in M_m$ et $y \in M'_m$ et $2^T$ le monoïde commutatif des parties de $T$ par rapport à l'union. Nous définissons selon [5] une action bilatère $M \times 2^T \times M \to 2^T$ en posant pour chaque $m_1, m_2 \in M$ ; $q \in T$ et $t = (m, m') \in T$ :

$$m_1 \times m_2 = (m_1, m, m_2) \quad \text{si cette paire est dans } T ; = \emptyset \text{ sinon.}$$

Comme d'usage $m_1 q m_2 = \{m_1 \mid t' m_2 : t' \in q\}$ et $mq$ et $qm$ sont des abréviations pour $mq_1$ et $lqm$. L'union est notée $+$ par commodité. Ceci permet de définir un produit sur $M \times 2^T$ par l'identité $(m,q)(m';q') = (mm;mq' + qm')((m,q), (m;q') \in M \times 2^T)$ dont on vérifie immédiatement l'associativité en calculant

$$(m,q)(m;q)(m;q'') = (mm'm''mm'q'' + mq'm'' + qm'm'').$$

On désignera par $\pi$ et $\tau$ les projections naturelles de $M \times 2^m$ sur $M$ et sur $2^T$ respectivement.

**IV.1.** Soit $\mu : A^* \to M$ un morphisme. Le produit $E = x_\mu^{-1} \cdot y_\mu^{-1}$ est reconnu par un morphisme $\phi$ sur un monoïde $P$ contenu dans $M \times 2^T$.

Pour chaque idempotent $u$ de $M$ le semi-groupe $u\pi^{-1} \cap P$ est apériodique. De plus, il appartient à $D^\circ$ quand $E$ est d'ambiguïté bornée. Quand $x_\mu^{-1}$ est préfice, il appartient à $D^{\circ 1}$. Enfin, quand $E$ est préfixe et $y_\mu^{-1} \subset A$ il se réduit à $\{u\}$.

**PREUVE.** (1). L'application de $A$ dans $M \times 2^T$ envoyant chaque lettre $a$ sur $(a\mu, (a\mu, 1) + (1, a\mu))$ se prolonge en un morphisme $\phi$ de $A^*$ sur un monoïde $P$ contenu dans $M \times 2^T$ dont l'élément neutre
est (1, (1,1)). Pour chaque mot $b$ on a $b\phi = (b\mu, b\phi\tau)$ où :
$$b\phi\tau = \sum \{(b'\mu, b''\mu) \in T : b', b'' \in A^* ; b = b'b''\}.$$

Donc $b \in E = x\mu^{-1} \cdot y\mu^{-1}$ ssi $(x,y) \in b\phi\tau$ ce qui montre que $\phi$ reconnaît $E$.

(2). Soient maintenant $u$ un idempotent de $M$ et $V = u\mu^{-1} \cap P$.

Si $P = (u,q) \in V$, on a $p^2 = (u,uq + qu)$ et $p^n = (u,uq + uqu + qu)$ pour chaque $n \ge 3$ ce qui montre que $V$ est apériodique.

Soit $T_u$ l'ensemble des $t \in T$ tels que $t \in q$ pour au moins un $(u,q) \in V$. Supposons qu'il existe un $t = (m,m') \in T$ tel que $utu = t$, c'est-à-dire tel que $um = n$ et $m'u = m'$. Cette hypothèse est satisfaite si $u = l$ ou si $ut'u \ne \emptyset$ pour un $t' \in T_u$ puisqu'il suffit alors de prendre $t = ut'u$. Prenons $c \in m\mu^{-1}$, $d \in m'\mu^{-1}$.
D'après la définition $T = (M^{-1}x) \times (yM^{-1})$ il existe $f,g \in A^*$ tel que $fc \in x\mu^{-1}$ et $dg \in y\mu^{-1}$ et $mm' = u$ on a $f(cd)^i c \in x\mu^{-1}$, $d(cg)^j g \in y\mu^{-1}$ pour tout $i,j \ge 0$ ce qui montre que $f(cd)^n g$ a $n+1$ factorisations distinctes comme produit d'un mot de $x\mu^{-1}$ et d'un mot de $y\mu^{-1}$ quand $cd \in A^+$.

Par conséquent, quand $E$ est un produit d'ambiguïté bornée on a $uT_u = \emptyset$ pour chaque idempotent $u \in A^+\mu$, ce qui entraîne en particulier que le sous monoïde $A^+\mu$ de $M$ soit l'union d'un élément neutre $l = l\mu$ et d'un semi-groupe $A^+\mu$. On en déduit immédiatement que $V \in D^0$ ouisque si $p = (u,q)$, $p' = (u,q')$ et $p'' = (u,q'')$ sont trois éléments de $V$, le produit $pp'p'' = (u,uq'' + uq'u + qu)$ est égal à $pp'' = (u,uq'' + qu)$ en raison de $uq'u \subset u.T_u \cdot u = \emptyset$, ce qui montre que $pVp'' = pp'' (p,p'' \in V)$ identiquement.

(3). Gardant les mêmes notations, supposons que $t = (m,m') \in T_u$ soit tel que $ut = t$. On a $(f(cd)^i c \in x\mu^{-1}$ pour tout $i \ge 0$ et par conséquent la partie $X = x\mu^{-1}$ est telle que $X^{-1}X$ contient le semi-groupe $(dc)^+$ ce qui est impossible quand $cd \in A^+$ et quand $X$ est une partie préfixe, comme nous le supposons maintenant. On a donc $uT_u = \emptyset$ pour chaque idempotent $u \in A^+\mu$. Sous cette hypothèse, prenant $p,p'' \in V$ comme ci-dessus, on trouve que $pp'' = (u,qu) = p^2$, c'est-à-dire que $pV = p^2$ identiquement ce qui établit que $V \in D^01$.

(4). Supposons enfin que $Y = y\mu^{-1}$ est une partie de $A$. On a donc $y \inym'M$ pour tout $m' \ne l$ et, en revenant à la définition
de morphisme $\phi$, on voit que si $b \neq 1$ est tel que $E \cap A^*bA^* \neq \emptyset$, il n'y a que deux cas possibles, à savoir : $b\phi = (b\mu, (b\mu, 1))$ et $b\phi = (b\mu, (b\mu, 1) + (b'\mu, y))$ selon que $b \notin A^*Y$ ou que $b = b'a \in A^*Y$ ($a \in Y \subset A$) où, dans le second cas, $b\mu = b'\mu.y$. Si l'on introduit l'hypothèse supplémentaire que $E = XY$ est une partie préfixe, il est exclus que $b\mu$ soit un idempotent dans le deuxième cas puisque ceci impliquerait $fb^+ \subset E$ pour au moins un mot $f$. Par conséquent les seuls idempotents de $P = A^*\phi$ sont $(1, (1,1)) = 1\phi$ et les $(u, (u\mu, 1))$ ($u = u^2 \in M$) d'où l'on conclut que $u\pi^{-1} \cap P = \{u\}$ ce qui achève la vérification de l'énoncé.

Q.E.D.

G. Lallemend m'a fait observer que les calculs ci-dessus équivalent à l'usage des identités $x^\omega y^\omega z^\omega = x^\omega z^\omega$ et $x^\omega y = x^\omega$ pour caractériser les variétés des semi-groupes apériodiques de $D_f^0$ et $D_f^1$ respectivement.

Nous dirons que le produit $XY$ est déterministe ssi $X$ est préfixe ou si $XY$ est préfixe et $Y \subset A$. Symétriquement, $YX$ est déterministe opposé ssi $X$ est suffixe ou si $YX$ est suffixe et $Y \subset A$. Plus généralement, un produit $X_1 X_2 \dots X_k$ sera déterministe (resp. déterministe opposé) ssi ceci est vrai de chacun des produits $X_1 X_2, (X_1 X_2) X_3, (X_1 X_2 X_3) X_4, \dots$ etc. (resp. $X_{k-1} X_k, K_{k-2}(X_{k-1} X_k), \dots$ etc). Ces conditions impliquent trivalement que ce produit soit non ambigu.

Nous rappelons que nous avons défini dans l'introduction la complétion polynomiale non ambiguë UPol($X$) d'une famille $\tilde{X}$ de partie de $A^*$ comme la plus petite famille $\tilde{Y}$ contenant $\tilde{X}$ telle que :
(i) $\tilde{Y}$ contient chaque lettre de l'alphabet $A$ et chaque sous-monoide $B^*$ engendré par une partie $B$ de $A$.

(ii) $\tilde{Y}$ contient l'union disjointe de deux de ses membres.

(iii) $\tilde{Y}$ contient tout produit non ambigu de ses membres.

On définit de même la complétion polynomiale déterministe DPol($X$) en remplaçant dans (iii) l'adjectif non ambigu par déterministe. Enfin on aura la complétion polynomiale bidéterministe BDPol($\tilde{X}$) en remplaçant (iii) par :

(iii B). $\tilde{Y}$ contient chaque partie de $A^*$ qui est à la fois une union disjointe finie de produits déterministes de parties de $\tilde{X}$ et
une union disjointe finie de produits déterministes opposés de par-
ties de $\mathbb{Y}$. (On a par conséquent les inclusions
$\mathcal{X} \subset \text{BDPol}(\mathcal{X}) \subset \text{DPol}(\mathcal{X}) \subset \text{UPol}(\mathcal{X})$.

D'autre part, afin d'unifier les preuves des Propriétés 2 et 3,
nous considérons comme dans l'introduction une variété $\mathcal{G}$ de groupes
finis et nous notons $\mathcal{G} \underset{\mathcal{D}_f}{\overset{\mathcal{D}}{\subset}}$ la famille des monoïdes finis de $\mathcal{D}$ dont
tous les groupes appartiennent à $\mathcal{G}$ et qui satisfont l'identité :
(\#) $(x^\omega y^\omega)^\omega = (x^\omega y^\omega)(x^\omega y^\omega)^\omega$.

(avec $\omega$ comme dans l'énoncé II.6). D'après la théorie de
S. Eilenberg, $\mathcal{G} \underset{\mathcal{D}_f}{\overset{\mathcal{D}}{\subset}}$ est une variété. De façon plus explicite, la con-
dition exprimée par l'identité supplémentaire (\#) signifie que le sous-
monoïde engendré par deux idempotents est apériodique. Elle est donc
trivialement satisfaite par les monoïdes finis apériodiques et la va-
riété $\mathcal{D}_f \cap A_p$ de la Propriété 2 est la variété $\mathcal{G} \underset{\mathcal{D}_f}{\overset{\mathcal{D}}{\subset}}$ correspondant
au cas où $\mathcal{G}$ est la variété triviale de groupes formés du seul groupe
$\{1\}$.

IV.2. Pour tout alphabet fini $A$, chacune des familles $\mathbb{Y} = A^* - \mathcal{D}_f$ ou $A^* - \mathcal{G} \mathcal{D}_f$ (resp. $= A^* - \mathcal{G} \mathcal{D}_f$ ; resp. $= A^* - \mathcal{G} \mathcal{D}_f$lt) est égale à sa complé-
tion polynomiale non ambiguë (resp. déterministe ; resp. bidétermi-
niste) et contient les intersections de ses membres avec les parties
de $A^* - \mathcal{G}$.

PREUVE. (1) C'est un théorème de S. Eilenberg [5] que pour chaque variété $\mathcal{V}$ la famille $A^* - \mathcal{V}$ est une algèbre booléenne : en effet le monoïde syntaxique de toute partie $X$ de $A$ est égal à celui de son complément $A^\setminus X$ et celui d'une union $X \cup Y$ divise le produit direct des monoïdes syntaxiques de $X$ et de $Y$. Comme la variété $\mathcal{G}$ est contenue dans $\mathcal{D}^{1r}$ (et que tous les groupes satisfont trivlement l'identité (#)), ceci prouve que $\mathbb{Y}$ contient l'union disjointe de deux de ses membres et l'intersection de chacun de ceux-ci avec une partie quelconque de $A^* - \mathcal{G}$.

(2) Chaque partie de $A^*$ formée d'une seule lettre ou
égale au sous monoïde engendré par un sous alphabet possède un monoïde
syntaxique qui divise le monoïde à trois éléments $\{1, m, m^2 = m^3\}$.
Ce dernier est apériodique et appartient à $\mathcal{D}^\circ_{\mathcal{f}}lr$. Par conséquent $\mathbb{Y}$
contient toutes les parties de $A^*$ de cette forme.

(3) Soient $X$ et $Y$ deux parties de $\mathbb{Y}$. Elles sont re-
connues par un morphisme $\mu$ de $A^*$ dans un sous monoïde $M$ du pro-
duit direct de leurs monoïdes syntaxiques. Le produit XY est une somme disjointe de produits de la forme $(x\mu^{-1})(y\mu^{-1}) = E (x \in X_\mu, y \in Y_\mu)$ dont chacun est non ambigu (resp. déterministe ; resp. déterministe opposé) quand $E$ lui-même a cette propriété. D'après IV.1, $E$ est reconnu par un morphisme $\phi : A^* \to P$ où la projection $\pi : P \to M$ est telle que $u\pi^{-1}$ soit un semi-groupe apériodique de $D_f^0$ (resp. de $D_f^1$ pour chaque idempotent $u$ de $M$ quand le produit est non ambigu (resp. déterministe).

Le fait que $u\pi^{-1}$ soit apériodique implique que chaque groupe dans $P$ soit isomorphe à un groupe dans $M$ donc qu'il appartienne à la variété $\mathcal{G}$. Elle entraîne aussi que $P$ satisfasse l'identité (#) quand celle-ci est satisfaite par $M$.

Le second fait que $u\pi^{-1} \in D_f^0$ (resp. $\in D_f^{01}$) entraîne d'après II. 7, que l'on ait $P \in D_f$ (resp. $\in D_f^1$) quand $M$ appartient à cette variété.

Procédant par induction sur le nombre des produits de concatenation effectués, ceci établit l'énoncé en ce qui concerne les familles $A^* - \mathcal{D}_f$, $A^* - \mathcal{G} \mathcal{D}_f$ et $A^* - \mathcal{G} \mathcal{D}_f^1$ et il nous reste seulement à examiner le cas de $\mathcal{D}_f^1 \mathcal{r}$.

(4) Soit donc $F$ une partie de $A^*$ satisfaisant les hypothèses de (iii B) c'est-à-dire telle que $F = F^1 = F^r$ où $F^1$ (resp. $F^r$) est une union disjointe finie de produits déterministes de termes $X_i^1 \in A^* - \mathcal{D}_f \mathcal{l} \mathcal{r}$, ($i \in I$) (resp. de produits déterministes opposés de termes $X_j^r \in A^* - \mathcal{D}_f \mathcal{l} \mathcal{r}$ ($j \in J$)).

Soit $N$ le monoïde syntaxique simultané de toutes les parties $X_i^1$ et $X_j^r$ ($i \in I, j \in J$), c'est-à-dire le quotient de $A^*$ par la plus grande congruence pour laquelle chacune de ces parties est une union de classes. $N$ est un monoïde fini appartenant à $\mathcal{D} \mathcal{l} \mathcal{r}$.

Utilisant l'expression $F = F^1$, il résulte de (3) qu'il existe un morphisme $\lambda : A^* \to Q^1$ reconnaissant $F$ où $Q^1$ appartient à la variété $\mathcal{D}_f^1$. Symétriquement, utilisant $F = F^r$, on vérifie que $F$ est reconnu par un morphisme $\rho$ de $A^*$ dans un monoïde $Q^r$ de la variété $\mathcal{D}_f^r$ des semi-groupes finis dont chaque $J$-classe contenant un idempotent est une $R$-classe.

Par conséquent, le monoïde syntaxique de $F$ appartient à l'intersection de $D_f^{11}$ et $\mathcal{D}_f^{rr}$ c'est-à-dire à $\mathcal{D}_f^{1r}$.

Q.E.D.
Le même énoncé IV.1 permet facilement de vérifier que la famille des parties reconnaissables de $A^*$ dont le monoïde syntaxique n'admet aucun diviseur égal au monoïde à trois éléments $\{1, u = u^2 = vu ; v = v^2 = uv\}$ (resp. ni au monoïde symétrique $\{1, u = u^2 = uv, v = v^2 = vu\}$) est égale à sa complétion polynomiale déterministe (resp. bidéterministe) (Cf. [5] Chap. VI).

Nous considérons maintenant un alphabet (fini) $A$, un monoïde fini fixe $M \neq \{1\}$, l'ensemble $\Delta M$ de ses diviseurs propres (c'est-à-dire $\neq M$) et la famille $A^* - \Delta M$ des parties de $A^*$ dont le monoïde syntaxique appartient à $\Delta M$. Nous considérons aussi la complétion polynomiale non ambiguë UPol (resp. déterministe, DPol ; resp. bidéterministe, BDPol) de $A^* - \Delta M$ et nous notons PolB la famille des unions finies de parties de $A^*$ de la forme $X, A^*X$ ou $X\Y$ avec $X \in UPol$ et $Y \in PolB$.

Dans l'énoncé suivant l'idéal $0$-minimal $K$ de $M$ est l'intersection de tous les idéaux de $M$ ayant deux éléments ou plus. Comme $M \neq \{1\}$ est fini, $K$ est un idéal non vide qui peut être réduit au zéro, $0$, de $M$.

Dans le cas contraire $K\O = D (=K$ si $M$ n'a pas de zéro)$ est une $J$-classe. On sait que si $K \neq 0$ chaque élément $k \in K\O$ engendre un idéal à droite $kM$ (resp. à gauche $Mk$) qui est $0$-minimal en ce sens que $kM = k'M$ (resp. $Mk = Mk'$) pour chacun de ses éléments $k' \neq 0$. Si de plus $K$ est apériodique, on a $kM \cap Mk = \{k,0\}$ ou $K = k$ selon que $M$ a ou non un zéro. Enfin dans le cas particulier où $K$ est apériodique et où $D$ est réduit à une seule $L$-classe (resp. $H$-classe) on a $kM = \{k,0\}$ ou $=k$ dans les mêmes conditions (resp. $D = kM\O = Mk\O = \{k\}$).

IV.3. Soit $\mu$ un morphisme du monoïde libre $A^*$ dans un monoïde fini $M \neq \{1\}$, $K$ l'idéal $0$-minimal de $M$, $x \in M$ et $X = x\mu^{-1}$.

On a les relations suivantes :

(i) $X \in A^* - \Delta M$ pour chaque $x \in M\K$.
Soit désormais $x \in K$.

(ii) $X \in BDPol$ si $K^2 = 0$ ou si $x = 0$ et $D^2 = D (\neq \O)$.
Soit désormais $K$ apériodique.

(iii) $X \in UPol$ si $D^2 = D$ avec, plus précisément, $X \in DPol$ (resp. $\in BDPol$) quand $D$ est réduit à une seule $L$-classe (resp. $H$-classe).

(iv) $X \in PolB$ pour chaque $x \in K$ dans le cas restant, l'hypothèse
K apériodique n'étant pas requise pour $x = 0$.

### PREUVE.
Elle requiert la considération de cas particuliers dont l'ordre ne coincide pas exactement avec celui de l'énoncé.

(1). Soit d'abord $x \in M \setminus K$. Par hypothèse il existe un idéal W ne contenant pas $x$ qui a deux éléments ou plus. Par conséquent, il existe un morphisme $\rho$ de $M$ sur un monoïde quotient qui reconnaît $x$ et envoie $W$ sur un zéro. On a donc $X = \rho(\mu\rho)^{-1}$ où $\mu\rho \in \Delta M$ ce qui établit l'assertion (i).

Nous supposons donc toujours désormais que $x \in K$ et nous posons $\overline{M} = M \setminus M \times M$.

(2). Soit $K = 0$ et $x = 0$.

On a $1 \notin X$ puisque $M \neq \{1\}$. Soit $f$ un mot de $X$. Il admet un plus long facteur gauche $g$ tel que $g\mu = m \in \overline{M}$, donc une facturation $f = gag'$ où $a \in A$, $g' \in A^*$ et $(ga)\mu = x = 0$. Si $E = (m\mu^{-1})a$ on a $EA^* \subset X$ puisque $x = xM$. Puisque $m \in \overline{M} = M\setminus M \times M$ et $E\mu = x$, $E$ est une partie préfixe. Donc $EA^*$ est un produit déterministe appartenant à DPol. Il est clair que $X$ est l'union disjointe finie de tels produits $(m'\mu^{-1})$.a'.A* étendue à toutes les paires $(m', a') \in \overline{M} \times A$ telles que $x = m'.a'\mu$.

Une construction symétrique à partir des plus longs facteurs droits dans $\overline{M}\mu^{-1}$ des mots de $X$ montre que $X$ est aussi une union disjointe finie de produits déterministes opposés. Par conséquent $X \in BDPol$.

Nous supposons désormais $K \neq 0$.

(3). Soit $K^2 = 0$ et $x \in D = K \setminus 0$.

Comme dans (2) on a $1 \notin X$. Soient $f$ un mot de $X$, et $g$ son plus long facteur gauche dans $\overline{M}\mu^{-1}$. On a encore $f = gag'$ ($a \in A$, $g' \in A^*$) où $(ga)\mu \in K$. Comme $(gag')\mu = x \neq 0$ et $K^2 = 0$ on a aussi $g' \in \overline{M}\mu^{-1}$. De la même manière que dans (2) on voit que si $g\mu = m$, $g'\mu = m'$, le produit $(m\mu^{-1})a$ est une partie préfixe et que le produit $(m\mu^{-1})a$ $(m'\mu^{-1})$ est une partie déterministe contenue dans $X$. On en déduit $X \in DPol$ et, comme la construction est symétrique $X \in BDPol$.

(4). $K^2 = 0$ et $x = 0$.

La vérification que $X \in BDPol$ se fait comme dans (2) puisque l'on vient de voir que cette famille contient toutes les parties de la
forme $k\mu^{-1}$ où $k \in K\backslash O$.

Nous supposons désormais $K^2 \neq 0$ et par conséquent $D = K\backslash O \neq \emptyset$. Les arguments sont différents selon que $D$ est un semi-groupe ($D^2 = D$) ou non. Nous considérons d'abord le premier cas.

D'après II.3., $D^{-1}D$ est un sous semi-groupe premier $P$ de $M$. Soit $B = A \cap P\mu^{-1}$. Puisque $P$ est premier on a $P \subset B\mu = M'$ et puisque $P$ est un monoïde $P = M'$. Par conséquent $D$ est l'idéal minimum de $M'$.

(5). $D^2 = D$ et $x = 0$.

Comme $O \neq P$, ces hypothèses impliquent que $C = A\backslash B$ ne soit pas vide. Soit $Q = (A^*C A^*)\mu$. $Q$ est un idéal de $M$ qui contient $x$ et d'après la définition du sous monoïde premier $P$, son intersection avec $P$ est vide. Donc $Q \cap D = \emptyset$. Puisque $D = K\backslash O$ où $K$ est l'intersection de tous les idéaux de $M$ ayant deux éléments ou plus, ceci entraîne que $Q$ soit un singolet, c'est-à-dire que $Q = 0 = x$. Donc $X = A^*C A^*$. On peut écrire $X$ comme un produit déterministe, $B^*C A^*$, ou déterministe opposé, $A^*C B^*$, et par conséquent $X \in \text{BDPol}$ ce qui termine la preuve de l'assertion (ii).

Nous supposons toujours désormais que $K$ est apériodique.

(6). $D^2 = D$ et $x \in D$.

Si $l \in X$ on a $x = l$ c'est-à-dire que $x$ appartient au sous-groupe de $M$. Comme $K$ est apériodique, ce dernier est réduit à $l$ et l'on a $X = B^*$ pour un sous alphabet $B$ de $A$. Donc dans ce cas $X \in \text{BDPol}$.

Supposons désormais $l \notin X$ et soit $f$ un mot de $X$. Il admet un plus long facteur gauche $g$ tel que $g\mu = m \in \bar{M}$ et une factorisation $f = gag'$ avec $a \in A$, $g' \in A^*$. De fait, $g,g' \in B^*$ et $a \in B$ d'après les remarques faites au début de la discussion du cas $D^2 = D$.

Si $D$ est réduit à une seule $l$-classe le produit déterministe $(m\mu^{-1})a B^*$ est contenu dans $X$ et $X \in \text{DPol}$ puisque $X$ est une union disjointe finie de tels produits. Si $D$ est réduit à une seule $h$-classe, c'est-à-dire ssi. $D = \{x\}$, on conclut $X \in \text{BDPol}$ par symétrie.

Revenant au cas général et au même mot $f$, il se peut que $m'' = g'\mu$ appartienne à $\bar{M}$. Dans ce cas $f$ appartient au produit déterministe $(m\mu^{-1})a (m''\mu^{-1}) \in \text{DPol}$. Si cette circonstance particulière n'est pas réalisée, c'est-à-dire si $g'\mu \in K$, le mot $g'$ a un plus long facteur droit $h$ tel que $h\mu = m' \in \bar{M}$, donc une factorisation $g = f'a'h$ avec $a' \in B$, $f' \in B$ et $(a'h)\mu \in K$.
Comme D est l'idéal minimal du sous monoïde $B^*\mu = M'$, tous les mots de $m.a\mu.M'$ (resp. de $M'.a'\mu.m'$) appartiennent à l'idéal à droite minimum $xM'$ de $M'$ (resp. à l'idéal minimum à gauche $M'x$). Comme K est apériodique, l'intersection de ces deux idéaux se réduit à x ce qui montre que le produit $X' = (m\mu^{-1}).a.B^* \cdot a' \cdot (m'\mu^{-1})$ est contenu dans X. Par construction le produit $m\mu^{-1} \cdot a$ est une partie préfixe. Donc le produit $(m\mu^{-1}) \cdot a.B^*$ est déterministe. Comme la partie $a' \cdot (m'\mu^{-1})$ est suffixe (par construction), le produit $X'$ est non ambigu.

Il est clair que X est une union disjointe finie de tels produits et de produits décrits au début de la discussion ce qui achève la prüve de l'assertion (iii) que $X \in \text{UPol}$.

Nous supposons désormais que $D^2 \neq D$, ce qui entraîne que M ait un zéro.

(7). $D^2 \neq D$ et $x=0$.

Soit $C = X \cap A$. Si C n'est pas vide, X contient la partie $A^*CA^*$ qui appartient à BDPol par définition. Considérons un mot $f \in X\A^*CA^*$. Il admet un plus long facteur gauche $g \in \bar{M}\mu^{-1}$, donc une factorisation $f = \text{gag}'$ avec $a \in A$, $g' \in A^*$ et $0 = x$ (ga)μ. Comme $a \notin C$, le mot $g$ admet un plus long facteur droit h tel que $(ha)\mu \in \bar{M}$ et une factorisation $g = f'a'h$ où $f' \in A^*$, $a' \in A$, $(a'ha)\mu = x = 0$.

Nous vérifions que $h\mu = p$ n'appartient pas à K. Pour cela, supposons le contraire et posons $m = a\mu, m' = a'\mu$. Comme $pm \neq 0$, p et pm engendrent le même idéal à droite 0-minimum de M. Il existe donc $m'' \in M$ tel que $p = \text{pmm''}$. Comme $m'p \neq 0$ par hypothèse, on obtient les relations contradictoires $0 = m'pm = m'\text{pmm''}$ et $0 \neq m'\text{pmm''} = m'p$.

Par conséquent le produit $a' \cdot (p\mu^{-1}) \cdot a$ (qui est non ambigu puisque $a,a' \in A$) appartient à UPol et le produit $Y = A^* \cdot a' \cdot (p\mu^{-1}) \cdot a.A^*$ appartient à PolB par construction puisque $a' \cdot (p\mu^{-1}) \cdot a.A^* \in \text{UPol}$. Il est clair que $X \setminus A^*CA^*$ est une union finie (non nécessairement disjointe) de tels produits et nous avons donc établi $X \in \text{PolB}$ pour $X = O\mu^{-1}$.

Le lecteur notera que l'hypothèse que K est apériodique n'a pas été utilisée. Bien plus, quand K n'est pas apériodique, un théorème classique de J. Rhodes et B. Tilson montre qu'il existe un morphisme $\chi$ de M sur un monoïde quotient propre $M' \in \Delta M$ pour lequel $O_{XX}^{-1} = 0$ et que l'on a donc alors $X = O\mu^{-1} \in A^* - \Delta M$.
Nous supposons de nouveau K apériodique.

(8). $D^2 \neq D$ et $x \in D$.

L'hypothèse que K est apériodique entraîne que $xM \cap Mx = \{x,0\}$,
Reprenant la discussion de (6) et remplaçant partout B par A on
obtient une partie X' de $X \cup O\mu^{-1}$ contenant X comme union fine
de produits $(m\mu^{-1})$ a $(m'\mu^{-1})$ ($a \in A$ ; m, m' $\in \bar{M}$, $m(a\mu)$ $m' = x$) et
de produits $(m\mu^{-1})$ a $A^*$ a' $(m'\mu^{-1}) \in \text{UPol}(a, a' \in A$ ; m, m' $\in \bar{M}$ ;
m $(a\mu)$, $(a'\mu)$ $m' \in K$). On en déduit $X = X' \setminus O\mu^{-1}$ par complémentation,
d'où $\bar{X} \in \text{PolB}$ d'après (7) et la définition de cette famille.

Q.E.D.

Nous avons encore besoin d'une remarque qui est un corollaire des théorèmes fondamentaux de la théorie moderne des semi-groupes finis de J. Rhodes et B. Tilson et nous faisons référence aux travaux de ces auteurs pour la preuve de la plupart des faits utilisés ci-dessous.

IV.4. Soient $M \in \underline{G_D}_f \cup \underline{G_D}_f^1$ un monoïde sans zéro et $G$ un groupe maximal dans son idéal $\mathcal{O}$-minimal $K$. M admet un monoïde quotient $M'$ dont l'idéal $\mathcal{O}$-minimal est apériodique qui est tel que $M$ soit un sous-monoïde du produit direct $M' \times G$.

PREUVE. (1). L'hypothèse que $M$ n'a pas de zéro entraîne que $K = D = D^2$ dans les notations de IV.3. D'après J. Rhodes et B. Tilson il existe un morphisme de $M$ sur un monoïde quotient $M'$ dont la restriction à $M \setminus K$ est bijective et dont la à K envoit bijective-ment chaque $H$-classe sur un idempotent. $M'$ a un idéal $\mathcal{O}$-minimal apé-riodique (qui est l'image de $K$). C'est le monoïde mentionné dans l'énoncé.

Soit d'autre part {$L^1 : i \in I$} l'ensemble des idéaux à gauche
minimaux de M, leur union est K. D'après les mêmes auteurs il existe
un monoïde P d'applications de I dans lui-même, un sous-monoïde Q
du produit en couronne GoP et un morphisme surjectif $\rho$ de M sur
Q dont la restriction à chaque idéal minimal à droite de M est bi-
jective. Ceci entraîne que M soit isomorphe à un sous-monoïde du
produit direct $M' \times Q$. Comme P est un monoïde quotient de M' il
suffit donc de montrer que sous l'hypothèse $M \in \underline{G_D}_f \cup \underline{G_D}_f^1$, Q se
trouve être un sous-monoïde du produit direct $G \times P$ (qui est lui-même
un sous-monoïde de GoP).

(2). Ceci est trivial quand M appartient à $\underline{D_f^1}$ car cette hypothèse implique que J soit un singolet et que par conséquent
P soit le monoïde trivial {1}.

Nous supposons donc désormais $M \in \underline{G \ D}_f$.

(3). Soit $\bar{e}_1 = (f_1, e_1)$ un idempotent fixe dans l'idéal minimum $K'$ de $Q$. Son support $e \in P$ est une application de $I$ sur un élément $i_1$ de cet ensemble et $f_1$ est une application de $S$ dans $G$ telle que $i_1 f_1 = 1 (= 1_G)$. On peut supposer que $\text{if}_{i_1} = 1$ pour chaque $i \in I$ car sinon on se ramenerait à ce cas en prenant deux éléments convenablement choisis $(d,1)$ et $(d',1)$ du sous-groupe de $GoP$ et en effectuant l'isomorphisme interne $p \to (d,1)p (d',1) (p \in GoP)$.

Supposons qu'il existe un autre idempotent $\bar{e}_2$ dans l'idéal à gauche engendré par $\bar{e}_1$. On a $\bar{e}_2 = (f_2, e_1)$ et, si $\bar{e}_2 \neq \bar{e}_1$, il existe un $i \in I$ pour lequel $\text{if}_i = g \neq 1$. Soit $\bar{e}_3$ l'idempotent du groupe $H_1^i$ intersection de $L^i$ et de l'idéal à droite $R_1$ engendré par $\bar{e}_1$. On a que $\bar{e}_3 \bar{e}_2$ est l'élément $g$ du groupe $L^i \cap R_1$.

Ceci est impossible quand $M$ appartient à $\underline{G \ D}_f$ puisque l'idéité (#) implique que le produit de deux idempotents soit apériodique, et on en conclut que sous cette hypothèse $K'$ est constitué par l'idéal minimum à droite $R_1$. Par conséquent, $K'$ est l'ensemble des paires $(f, e_j)$ où $e_j$ est l'application de $J$ sur $j$ ($j \in J$) et où chaque application $f$ envoie $J$ sur un seul élément du groupe $G$.

Considérant un élément quelconque $\bar{q} = (f, p) \in Q$ et calculant $\bar{q} \bar{e}_1$ on en déduit que l'image de son application $f$ est encore un élément unique $\bar{q}Y \in G$. Il est clair que $Y$ est un morphisme ce qui conclut la preuve.

Q.E.D.

Il résulte de la preuve que l'on a les inclusions :

$$ \underline{G} \subset \underline{G \ D}_f 1r \subset \underline{G \ D}_f 1 \subset \underline{D}_f $$

### PREUVE DES PROPRIETES 2 ET 3.

Ainsi qu'on l'a dit plus haut elle résultera de celle de l'énoncé suivant.

IV.5. Soit $\underline{G}$ une variété de groupes finis. Pour chaque alphabet $A$, la famille $A^*-\underline{G \ D}_f$ (resp. $A^*-\underline{G \ D}_f 1$ ; resp. $A^*-\underline{G \ D}_f 1r$) est la plus petite famille de parties des $A^*$ égale à sa complétion polynomiale non ambiguë (resp. déterministe ; resp. bi-déterministe) qui contienne les intersections de ses membres avec les parties de $A^*-\underline{G}$.

**PREUVE.** En raison de IV.2. il reste seulement à vérifier que si
une partie $X$ de $A^*$ a son monoïde syntaxique $M = A^*\mu$ dans les variétés mentionnées dans l'énoncé on peut l'obtenir par les opérations permises. Ceci est trivial quand $M = \{1\}$ puisque dans ce cas $X=A^*$ et on peut donc procéder par induction sur le nombre d'éléments de $M$, De plus, comme les complétions polynomiales sont fermées par union disjointe finie on peut supposer que $X\mu = X$ où, d'après IV.3 (i), cet élément appartient à l'idéal 0-minimal $K$ de $M$. Si $K$ est apériodique (et en particulier si $K^2 = 0$) le résultat découle de IV.3 (ii) et (iii) puisque l'hypothèse $M \in D_f$ implique que $D$ soit un semi-groupe quand $K^2 \neq 0$. Sinon, d'après IV.4., il existe un morphisme $\gamma$ de $A^*$ dans un groupe $G$ de $\mathcal{G}$ et un élément $g \in G$ tel que $X = X' \cap g\gamma^{-1}$ où $X'$ a pour monoïde syntaxique un quotient du monoïde $M' \in \Delta M$ et ou par conséquent il satisfait les conditions requises en vertu de l'hypothèse d'induction.

Q.E.D.

## REFERENCES

1. Brozozowski, J.A., Culik II, K. and Gabriellian A, *Classification of non counting events*. J. of Computer and System Sci, 5 (1971) 41-53.

2. Brzozowski J., *Run languages* à paraître dans Discrete Maths.

3. Césari Y., *Sur un algorithme donnant les codes bipréfixes finis*, Math. Syst. Theory 6 (1972) 221-223.

4. Clifford A.H., et G.B. Preston, *The algebraic theory of semi-groups*, American Math. Soc. (1961).

5. Eilenberg S., *Automata, languages and Machines*. Vol. B. Academic Press (sous presses).

6. Lallemend G., *Regular semi-groups with $D=R$ as syntactic monoids of finite prefix codes*, à paraître dans *Theoretical Computer Science*.

7. Lallemend G., et E. Milito, *Recognizable Languages and finite semi-lattice of groups*. Semi-Group Forum II (1975) 181-184.

8. Mc Naughton R. and S. Pappert., *Counter free automata*. MIT Press (1971).

9. Perrin D., *Codes bipréfixes et groupes de permutations*. Thèse Paris (1975).
10. Petrich M., *The maximal semilattice decomposition of semi-groups*. Math. Zeit 85 (1964) 68-82.

11. Rhode J.L., *Algebraic Theory of finite semi-groups in Semi-groups*, K.W. Folley Ed. Academic Press (1969).

12. Rhode J.L. and Bret R. Tilson, *Local Structure Theorems for finite semi-groups in Algebraic Theory of machine, languages and Semi-groups*, M.A. Arbib Ed. Academic Press (1968).

13. Rhodes J. and Denis Alfen J.L., *Synthesis of the Classical and Modern theory of finite semi-groups*. Advances in Math. 11 (1973) 238-266.

14. Simon I., *Picewice testable events 2nd Conf. on Automata Theory Kaiserlautern* (1975), à paraître dans les "lectures notes in Computer Science". (Springer Verlag).

15. Tamura T. and N. Kimura, *Existence of greatest decomposition of semi-groups*, Kodai Math. Sem. Rep. 7 (1955) 83-84.

16. Tilson B., *Decomposition and Complexity of finite semi-groups* Semi-group form. 3 (1971) 189-250.

17. Tilson B., *Depth Decomposition Theorems in 8*. Eilenberg. Automata languages and Machines Vol. B. Academic Press (sous presses).

18. Tilson B., *Complexity of two J-class semi-groups*. Adv. in Math. II (1973) 215-237.

19. Tilson B., *On the p-length of p-solvable semi-groups in Semi-groups* in Semi-groups, Academic Press N.Y. (1969).

20. Yamada M., *On the greatest semi lattice decomposition of semi-groups*. Kodai. Math. Sem. Rep. 7 (1955) 59-62.