# Sur une caractérisation des fonctions séquentielles

Marcel-Paul Schützenberger

► To cite this version:

Marcel-Paul Schützenberger. Sur une caractérisation des fonctions séquentielles. [Rapport de recherche] IRIA-RR-176, IRIA. 1976, pp.7. hal-04716386

HAL Id: hal-04716386

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

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
IRIA

laboria

Institut de Recherche
d'Informatique
et d'Automatique

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

laboratoire de recherche
en informatique
et automatique

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

SUR UNE CARACTÉRISATION
DES FONCTIONS SÉQUENTIELLES

Marc Paul SCHÜTZENBERGER

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

Rapport de Recherche N° 176

Juin 1976
# SUR UNE CARACTÉRISATION DES FONCTIONS SÉQUENTIELLES

M.P. Schützenberger

## Résumé :

On donne une caractérisation des fonctions (partielles) séquentielles généralisées qui étend légèrement les théorèmes classiques de Ginsburg et Rose et de Eilenberg au moyen des transducteurs monomiaux de M. Nivat.

## Abstract :

Ones characterizes the q.s.p. by a slight extension of the classical theorems of Ginsburg - Rose and Eilenberg with the help of Nivat's monomial transducers.
# SUR UNE CARACTERISATION DES FONCTIONS SEQUENTIELLES

M. P. Schützenberger

## 1. Introduction.

On se propose d'établir la Proposition 1 ci-dessous qui dérive du Théorème 4.2 du chapitre XII (Vol. A) du Traité de S. Eilenberg, "Automata, Languages and Machines" ([S.E]). Dans ce qui suit $A^*$ et $B^*$ sont les monoïdes libres engendrés respectivement par les alphabets finis A et B et, pour chaque partie X de $A^*$, $H(X)$ désigne la famille des applications de X dans l'union $B^* \cup O$ de $B^*$ et du zéro, O, de son algébre sur $Z$. Pour abrèger, une telle application sera appelée une **fonction de X** (dans $B^*$). Nous faisons faisons référence à [S.E] pour la définition et la théorie de la sous-famille des fonctions séquentielles ($= \text{gsp} = \text{"generalized sequential partial functions"}$).

Soit maintenant k un entier (fini) fixe. Pour chaque entier n on note $F_n$ l'ensemble $A^h A^* \setminus A^{k+n+1} A^*$ des mots de $A^*$ dont la longueur est comprise entre k et $k+n$ et $H^n$ la famille des fonctions de $H(A^h A^*)$ qui jouissent de la propriété suivante :
(Det). Il existe une fonction $\beta$ de $H(A^*)$ et une application $a \to \rho_a$ de $A^*$ dans un ensemble $R$ de n fonctions de $H(F_n)$ telles que l'on ait identiqueMENT :

$$ (1) \quad (\text{af}) \alpha = (a\beta)(\rho_a) \quad (a \in A^*, f \in F_n). $$

Le théorème 4.2 de [S.E.] Vol. A, chap. XII, montre que toute fonction séquentielle (généralisée) $\alpha$ satisfait ces conditions pour n (fini) assez grand, $k=0$ et $\beta=\alpha$ et donne une réciproque de cette propriété. La considération du cas où $\beta$ n'est pas nécessairement égal à $\alpha$ est motivée par divers cas particuliers, tels que les fonctions ayant un domaine fini, les restrictions de fonctions séquentielles à un domaine (reconnaissable) arbitraire ou bien l'Exemple 8.2. de [S.E.], vol. A, chap. XI.

**Proposition 1.** Supposant A fini, une condition suffisante pour qu'une fonction $\alpha$ de $H^n$ ait même restriction à $A^{k+1} A^*$ qu'une fonction séquentielle (généralisée) est que l'on ait identiquement :
$$
(2) \quad (\text{fa}) \quad \alpha = 0 \text{ ou } (\text{fa}) \quad \alpha \in (\text{fa}) \, B^* \quad (f \in F_{n-1}, a \in A).
$$

On notera que la restriction $\tilde{\quad}$ à des alphabets $\underline{\quad}$ finis A et B n'intervient
que dans la définition des fonctions séquentielles.

2. *Remarques préliminaires.*

Il sera commode de considérer $B^*$ comme un sous-monoïde du groupe libre $B^{(*)}$
engendré par $B$ et d'employer $Q$ pour désigner n'importe quelle fonction dont
la valeur est $0$ pour chaque élément de son domaine.

Soient maintenant, k, n, $\alpha \in H^n$ fixes et $F = F_n$. Les fonctions $\beta$ et $\rho_a$
$(a \in A^*)$ ne sont pas entièrement déterminées par l'identité (1) et la donnée de
$\alpha$. On peut cependant supposer n minimum ($\alpha \notin H^n$ pour $m < n$) et la condition :
(0). Pour tout mot $a$ de $A^*$ on a :

$$
a\beta = 0 \quad \text{ssi} \quad \rho_a = 0.
$$

En effet, l'identité (1) montre que chacune de ces deux relations équivaut
à (aF)α (= {(af)α : f ∈ F}) = 0 et qu'on peut donc supposer qu'elles sont tou-
jours simultanément vérifiées ou non.

Pour $\rho \in R$, on pose $D_{\rho} = \{a \in A^* : \rho = \rho_a\}$ et, si $b$ est un élément du groupe libre $B^{(*)}$, on note $b[\rho]$ la fonction (dans $B^{(*)} \cup 0$) envoyant chaque $f \in F$ sur $b(f\rho)$.

2.1. On peut choisir $\beta$ et les $\rho_a$ de telle sorte que :

(Min). Pour chaque $\rho$ de $R$ les mots de $(D_{\rho})\beta$ n'ont pas le facteur droit commun dans $BB^* (= B^* \setminus I)$.

Il en est de même pour la condition :

(Max). Pour chaque mot $a$ de $A^*$, $a \beta$ est le plus long facteur droit commun des mots de $(aF)\alpha$.

Sous cette deuxième hypothèse, les mots de $F_{\rho_a}$ n'ont pas de facteur gauche commun dans $BB^* (a \in A^*)$.
**Preuve.** Considérons par exemple la condition (Max) et supposons qu'elle n'est pas satisfaite en a. Comme $(aF)\alpha \subset a\beta.B^*$ d'après l'identité (1), ceci signifie qu'il existe un mot b de $BB^*$ tel que $a\beta b$ est le plus long facteur droit commun de $(aF)\alpha$. Toujours d'après (1), on peut aussi bien définir b comme le plus long facteur gauche commun des mots de $F_{\rho_a}$. On peut donc remplacer la valeur de $\beta$ en a par $a\beta.b$ en substituant à $\rho_a$ la fonction $b^{-1}[\rho_a]$ de $H(F)$ sans altérer la validité de l'identité (1).

Une discussion analogue s'applique à la condition (Min).

Q.E.D.

Une conséquence utile de cette remarque est :

2.2. On a $\rho = \lambda$ si $\rho, \lambda \in R$ sont tels que $\lambda = b[\rho]$ pour un $b \in B^{(*)}$.

**Preuve.** Supposons en effet que $\rho$ et $\lambda = b[\rho]$ ($b \in B^{(*)}$) sont dans $R$. Si $\rho = 0$ on a $\lambda = 0 = \rho$. Sinon, soit $d = f\rho \in B^*$ ($f \in F$). On a $fd = e = bd \in B^*$, c'est-à-dire $b = e d^{-1}$.

Cette dernière relation entraîne que, si $c \in B^*$ est le plus long facteur droit commun de d et de e, $d = d'c$, $e = e'c$ ($d', e' \in B^*$), on ait $b = (e'c)(cd')^{-1} = e'd^{-1}$. Comme la même chose est vraie de tous les mots de $F\rho$, d'après $e'$ est un facteur gauche commun de tous les mots de $F\rho$ (resp. $F\lambda$) et puisque l'on peut supposer que la condition (Max) est remplie, on a :
$$d' = e' = b = 1, \text{c'est-à-dire } \rho = \lambda.$$

Q.E.D.

Soit $K$ l'algèbre sur $Z$ du groupe libre $B^{(*)}$ et, pour chaque $F_j = A^h A^* \setminus A^{h+j+1} A^*$ ($0 \le j \le n$), soit $K^{F_j}$ le $K$-module des $F_j$-vecteurs à coordonnées dans $K$. Soit aussi $\pi_j$ la projection de $K^F = K^{F_n} \times_{F_j} F_j$.

A chaque mot $a$ de $A^*$ on associe le $F$-vecteur $av$ de $K^F$ dont la coordonnée $f$, $av(f)$, est égale à $(af)\alpha$ ($f \in F$) et on désigne par $V$ le sous $K$-module de $K^F$ sous-tendu par les vecteurs $av$ ($a \in A^*$).

2.3. Soit $w$ un $F$-vecteur de la forme $w = x[hv] - x'[h'v]$ où $x, x' \in B^{(*)} \cup 0$ et $h, h' \in A^*$. Si $w \pi_{n-1} = 0$ on a $w = 0$.
**Preuve.** D'après l'hypothèse (0) et la minimalité de $n$, il existe un ensemble $C$ de n mots de $A^*$ tels que $R = \{\rho_c : c \in C\}$ avec $c\beta \neq 0$ pour $\rho_c \neq 0$. Donc $\dim V \leq n$ puisqu'en raison de l'identité (1), $V$ est engendré en tant que K-module par les $n$ vecteurs $cv(c \in C)$.

Il suffit donc de supposer $w_{\pi_{n-1}} = 0$ et $w \neq 0$ et de vérifier que ceci permet de construire $n+1$ vecteurs $w_j$ ($0 \le j \le n$) de $V$ **indépendants** en contradiction avec la dimension de $V$.

Soient $w = w_n$ et $f$ un mot de $F$ pour lequel $w(f) \neq 0$. On a $f \in F_n \setminus F_{n-1} = A^{k+n+1}$ ce qui permet d'écrire $f = f_n = a_1 a_2 \dots a_n f_h$ avec $a_1, a_2, \dots, a_n \in A$ et $f_h \in A^h$. Posons $d_{n-j} = a_1 \dots a_{n-j}$ ($= 1$ pour $j=n$), $f_j = a_{n-j+1} \dots a_n f_h \in F_j$ et enfin $w_j = x[(h d_{n-j}) v] - x'[(h'd_{n-j})v] \in V$ pour $j=n, n-1, \dots, 1, 0$.

Puisque $f = f_n = d_{n-j} f_j$ on a : $w_j(f_j) = x[(hd_{n-j})v(f_j)] - x'[(h'd_{n-j})v(f_j)] = x[(hf)\alpha] - x'[(h'f)\alpha] = w(f) \neq 0$ ce qui montre que $w_j \pi_j \neq 0$ ($0 \le j \le n$).

Nous vérifions maintenant que $w_j \pi_{j-1} = 0$ ($1 \le j \le n$) ce qui achève de montrer que les vecteurs sont indépendants.

Soit donc $f' \in F_{j-1}$. Comme ci-dessus, on a $w_j(f') = x[(hf'')\alpha] - x'[(h'f'')\alpha] = w(f'')$ où $f'' = a_1 \dots a_{n-j} f' \in F_{n-1}$ et où par conséquent $w_j(f') = w(f'') = 0$ en raison de $w_{\pi_{n-1}} = 0$.

Q.E.D.

Nous supposons désormais que $\beta$ et les $\rho_a$ ont été choisis de façon à satisfaire la condition (Min).

2.4. Il existe une application $(\rho, a) \to (\rho \perp a, a \otimes \rho)$ de $R \times A$ dans $R \times (B^* \cup 0)$ ayant les deux propriétés suivantes dans lesquelles $\lambda = \rho \perp a$ et $b = a \otimes \rho$ :

(24+). Si $\rho \neq 0$ et $g \in D_\rho$ on a $ga \in D_\lambda$ et $(ga)\beta = g\beta.b$ où, de plus $b=0$ si $\lambda=0$.

(240). $\lambda = 0$ et $b=0$ si $\rho=0$.

**Preuve.** Supposons d'abord $\rho \neq 0$ et soient $g, g' \in D_\rho$.

D'après la condition (0) on a $g\beta = y \neq 0$ et $g'\beta = y' \neq 0$ et, d'après l'identité (1), $(gf)\alpha = y.f\rho$ ; $(g'f)\alpha = y'.f\rho$ pour tous les mots $f$ de $F = F_n$ et en
particulier pour tous ceux de la forme $f = af'$ où $f' \in F_{n-1}$. Donc le F-vecteur
$w = y^{-1}[(ga)v] - y'^{-1}[(g'a)v]$ satisfait $w\pi_{n-1} = 0$ ce qui entraîne $w = 0$ selon
la remarque précédente. On a donc :

$$
y^{-1}((gaf)\alpha) = y'^{-1}((g'af)\alpha)
$$

pour tous les mots $f$ de $F = F_n$ et non pas seulement pour ceux de $F_{n-1}$.

Utilisant (1), cette relation peut aussi s'écrire :

$$
y^{-1}((ga)\beta.f\rho_{ga}) = y'^{-1}((g'a)\beta.f\rho_{g'a}) \quad (f \in F)
$$

c'est-à-dire $\rho_{g'a} = b[\rho_{ga}]$ où $b$ est égal à $((g'a)\beta)^{-1}y'^{-1}((ga)\beta) \in B^{(*)}$ ce
qui entraîne $\rho_{g'a} = \rho_{ga}$ d'après 2.2 et, enfin, l'existence de l'application
$\rho \mapsto \rho \land a$ pour $\rho \neq \emptyset$.

Gardant les mêmes notations, nous prenons un mot $f' \in F_{n-1}$ et nous posons
$z = (ga)\beta$. D'après (1) on a $(gaf')\alpha = y.(af')\rho = z.f'\lambda(\lambda = \rho\land a)$ ce qui montre
que $z = 0$ ssi $y = 0$ et, d'après (0), que $\lambda = 0$ ssi $(ga)\beta = 0$. Supposant
maintenant ce cas particulier écarté, on peut écrire l'équation précédente sous
la forme :

$$
(g\beta)^{-1} \cdot ((ga)\beta) = (af')\rho \cdot (f'\lambda)^{-1}
$$

où le membre de droite est indépendant de choix de $g$ dans $D_\rho$ et peut être
noté $a_\theta_\rho$ puisque, comme on vient de le voir, $\lambda$ ne dépend que de $\rho$ et de $a$.
Il nous reste à vérifier que, de fait, $a_\theta_\rho$ est un mot du monoïde $B^*$.

L'égalité $y.(af')\rho = z.f'\lambda$ où tous les termes sont dans $B^*$ entraîne
l'existence d'un mot $t$ de $B^*$ tel que l'on ait :

soit $z = yt$ et $(af')\rho = t.(f'\lambda)$ ;

soit $y = zt$ et $f'\lambda = t((af')\rho)$.

Dans le premier cas $t = a_\theta_\rho$ et la conclusion souhaitée est obtenue. Dans le
second $t = (a_\theta_\rho)^{-1}$ et, comme $a_\theta_\rho$ est indépendant de $g \in D_\rho$, la relation
$y(= g\beta) = zt (= (ga)\beta.t)$ est vraie pour tous les $g \in D_\rho$. Ceci implique que $t$
soit un facteur commun droit de $(D_\rho)\beta$ donc que $t = 1$ d'après l'hypothèse (Min)
sur le choix de $\beta$ et montre que $a_\theta_\rho \in B^*$ dans tous les cas.

Il reste à traiter le cas où $\rho = \emptyset$. Prenant $g \in D_\rho$ on a $(gf)\alpha = g\beta.f\rho = 0$
pour tout $f$ dans $F$ et en particulier dans $aF_{n-1}$. Ceci équivaut à $w\pi_{n-1} = 0$
où cette fois $w$ est le F-vecteur $w = x[(ga)v] - x'[(ga)v]$ de $V$ avec
x = 1 et x' = 0. Appliquant la remarque 2.3, on obtient w = 0, c'est-à-dire
(gaF)α = 0, ce qui en raison de la convention (0) signifie que (ga)β = 0, et
λ = 0.

Q.E.D.

On observera que comme l'hypothèse (Min) implique que 1 β = 1, l'énoncé
précédent signifie qu'avec ce choix la fonction β est séquentielle (généralisée)
puisque l'alphabet A est fini.

3. Fin de la vérification de la Propriété 1.

On suppose désormais que la fonction α de Hⁿ satisfait la condition (2).
Nous vérifions d'abord qu'il existe une application (ρ, f, a) → ατ<sub>ρ,f</sub> de
(R × A<sup>k</sup>) × A dans B<sup>*</sup> × 0 telle que l'on ait :

$$
(2') \quad (gfa)\alpha = (gf)\alpha. \alpha_{\tau_{\rho,f}}
$$

pour tout mot g de D_p.

Pour cela, utilisant l'existence de l'application $R \times A \to R$ établie dans
2.4 (et le caractère minimal de n), nous observons que l'on peut trouver un
mot g dans $D_p$ dont la longueur est au plus $n-1$. En vertu de la condition
(2) on a $(gfa)\alpha = 0$ ou $(gfa)\alpha \in (gf)\alpha.B^*$, ce qui équivaut à l'existence d'un
élément b de $B^* \cup 0$ pour lequel $(gfa)\alpha = (gf)\alpha.b$. On conviendra de poser
$b=0$ quand $(gf)\alpha = 0$.

Maintenant l'identité (1) montre que (g'f)α = g'β.fρ et (g'fa)α =
g'β.(fa)ρ quelque soit g' dans Dρ. Comme gβ ≠ 0 quand ρ ≠ Q d'après (0),
on en déduit que (fa)ρ = fρ.b et que, par conséquent, (g'fa)α = (g'f)α.b pour
tout g' ∈ Dρ. Il en résulte que b est bien une fonction ατρ,f de ρ,f et
a seulement.

Il nous reste à construire un ensemble fini Q et une application de Q × A
dans Q × (B* ∪ 0) telle que la fonction séquentielle résultante σ (d'après
la méthode du chapitre XI de [S.E]) coïncide avec α sur A<sup>k+1</sup> A*.

Soit $Q = \mathbb{R}^{k+1}$, l'ensemble des suites de $k+1$ fonctions de $R$. On note
$q_1$ la suite $(Q, Q, \dots, Q, \rho_1)$ où $\rho_1$ est la fonction de $R$ associée à l'élé-
ment neutre de $A^*$.
Si $a \in A$ et $q = (\rho_{i_1}, \rho_{i_2}, \dots, \rho_{i_{k+1}}) \in Q$, on définit :
$$ q.a = (\rho_{i_2}, \dots, \rho_{i_{k+1}}, \rho') \text{ avec } \rho' = \rho_{i_{k+1}} \quad \text{la si cette dernière fonction} $$
$$ \text{n'est pas } Q \text{ et } q.a = (0, 0, \dots, 0) \text{ (= } q_0\text{) sinon.} $$

Cette application $Q \times A \to Q$ s'étend de façon naturelle à une action
$Q \times A^* \to Q$. On pose : $Q' = \{q_1.a : a \in A^* \setminus A^h A^*\}$ et $Q'' = \{q_1.a : a \in A^h A^*\}$.
Comme chaque $q \in Q'' \setminus q_0$ a toutes ses composantes différentes de $0$ par cons-
truction, les ensembles $Q'$ et $Q'' \setminus q_0$ sont disjoints.

Nous construisons maintenant $\tau : Q \times A \to B^* \cup 0$ en posant $a_\tau = 0$ si
$q = q_0$ ou si $q$ n'appartient pas à $Q' \cup Q''$ ($a \in A$). Soit $q \in Q'' \setminus q_0$. On
peut écrire $q = q_1$. gf où $g \in A^*$ et $f \in A^k$ et on pose $a_\tau = a_\rho, f$ où
$\rho = \rho_g$. Pour $q = q_1.g \in Q' \setminus q_0$ et $a \in A$, on pose $a_\tau = (ga)\alpha$ ou $= 1$ selon
que $ga \in A^k$ ou $\in A^* \setminus A^h A^*$.

Cette dernière convention entraîne, pour $k$ positif, que l'on ait
$h\sigma = h\alpha$ ou $= 1$ selon que le mot $h$ de longueur au plus $k$ appartient ou
non au domaine $A^k A^*$ de $\alpha$. Ceci fixe les conditions initiales et on vérifie
aisément d'après (2') que $\sigma$ coïncide bien avec $\alpha$ sur ce domaine.

Si $k=0$, on voit de même que $1\sigma = 1$ et $h\sigma = h\alpha$ pour tout
$h \in A A^* = A^{h+1} A^*.$

Q.E.D.