IRIA
laboria

laboratoire de recherche
en informatique
et automatique

Sur la traduction
des schémas récursifs
monadiques
en schémas itératifs.

B.Courcelle,

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

Institut de Recherche
d'Informatique
et d'Automatique

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

Rapport de Recherche n° 69

avril 1974
SUR LA TRADUCTION DES SCHÉMAS RÉCURSIFS MONADIQUES
EN SCHÉMAS ITÉRATIFS

B. Courcelle

**Résumé** : Il est toujours possible de traduire un schéma récursif monadique en un schéma de Ianov augmenté de deux compteurs.

Nous caractérisons ici la sous classe stricte de ceux qui sont traductibles en schémas de Ianov à un compteur. D'après Plaisted, ces derniers schémas de Ianov sont traductibles en "flow-charts" à plusieurs registres et sans compteur.

**Abstract** : We know that functional monadic schemata are translatable into Ianov-schemata with two counters.

We determine here the strict subclass of monadic functional schemata that are translatable into Ianov schemata with one counter. According to D. Plaisted, these schemata are translatable into flow-charts with several registers and no counter.
## Introduction :

Le lecteur trouvera les preuves des résultats de base de la théorie des schémas de programme que nous allons rappeler dans *Ashcroft*, *Manna* et *Pnueli* [1], *Cousineau* et *Rifflet* [3] et *Luckham* et *Garland* [7].

Un ensemble $F = \{f_1, \dots, f_r\}$ de fonctions de base monadiques,

un ensemble $P = \{p_1, \dots, p_n\}$ de prédicats monadiques ainsi

qu'un ensemble $V = \{F_0, \dots, F_m\}$ de variables fonctionnelles étant donnés, on définit :

1) les **termes** : expressions de la forme $mf(x)$ où $m \in (\mathbb{F}_U \cup \mathbb{V})^*$ et $f \in F$,

2) les **termes linéaires** : termes ayant au plus une variable fonctionnelle,

3) les **termes réguliers** : termes linéaires de la forme $Fm(x)$ ou $m(x)$ avec $F \in V$ et $m \in \mathbb{F}^+$,

4) les **termes conditionnels** : expressions finies définies inductivement par :

i) tout terme est un terme conditionnel,

ii) si $\tau_1$ et $\tau_2$ sont des termes conditionnels et $p \in P$, si $p(x)$ alors $\tau_1$ sinon $\tau_2$ est un terme conditionnel,

5) les **termes conditionnels linéaires** (resp. **réguliers**) en remplaçant "terme" par "terme linéaire" (resp. "terme régulier") dans la définition précédente.

6) Les classes $S$ (resp. $L$), (resp. $R$) de **schémas récursifs monadiques** (resp. **linéaires**) (resp. **réguliers**) sont les systèmes de la forme

$$ \begin{cases} F_0(x) \leftarrow T_0 \\ \vdots \\ F_m(x) \leftarrow T_m \end{cases} $$

où les $T_i$ sont des termes conditionnels (resp. t.c. linéaires) (resp. t.c. réguliers)

**Exemple** : le schéma suivant est linéaire.

$$ \begin{cases} F_0(x) \leftarrow \underline{\text{si}} \ p_2(x) \ \underline{\text{alors}} \ (\underline{\text{si}} \ p_1(x) \ \underline{\text{alors}} \ f_1 F_1 f_2(x) \ \underline{\text{sinon}} \ f_1(x) ) \ \underline{\text{sinon}} \ f_3 f_4(x) \\ F_1(x) \leftarrow \underline{\text{si}} \ p_2(x) \ \underline{\text{alors}} \ F_0 f_3(x) \ \underline{\text{sinon}} \ f_4 F_1 f_2(x) \end{cases} $$
Une *interprétation* d'un schéma est la fonnée $I = <D^I, p_i^I, f_i^I>$

i) d'un ensemble $D^I$ ou *domaine* de $I$,

ii) de prédicats totaux $p_i^I$ sur $D^I$ pour tout $p_i \in P$,

iii) de fonctions partielles $f_i^I : D^I \to D^I$ pour tout $f_i \in F$.

Le quadruple $\langle S, I, F_i, \xi \rangle$ où $S$ est un schéma, $I$ une interprétation, $F_i$ une variable fonctionnelle et $\xi$ un élément de $D^I$ est alors un programme *récursif interprété*. Nous prendrons comme règle d'évaluation celle de la sémantique Algol. Le résultat du calcul, si celui-ci se termine, est alors noté $\underline{\mathrm{Val}}(F_i, S, I)(\xi)$.

$\underline{\mathrm{Val}}(F_i, S, I)$ est donc une fonction partielle $D^I \to D^I$.

$\underline{\mathrm{Val}}(F_0, S, I)$ est la fonction calculée par le schéma $S$ ; on la notera aussi $\underline{\mathrm{Val}}(S, I)$. Deux schémas $S$ et $S'$ sont dits *équivalents* s'ils calculent la même fonction, c'est à dire si $\underline{\mathrm{Val}}(S, I)=\underline{\mathrm{Val}}(S', I)$ pour toute interprétation $I$.

**Remarque** : On peut convenir qu'un symbole de fonction de base, par exemple $f_1$, est toujours interprété par la fonction identité $D^I \to D^I$. Ce point de vue est adopté dans [1] et [3] et modifie sensiblement la situation : en particulier, l'équivalence des schémas est décidable pour la classe $S$ alors que ce problème est ouvert si on adopte cette dernière définition. Les problèmes sont donc tous plus difficiles, et sans grande justification en fait : si l'on choisit d'étudier des programmes ininterprétés, autant ne rien interpréter du tout.

Nous allons introduire maintenant différentes classes de schémas itératifs. $F$ et $P$ étant donnés comme plus haut, $V=\{x_0, \dots, x_m\}$ étant un ensemble de variables individuelles, définissons les ensembles suivants d'instructions :

$$A_0 = \{x_0 := f_1(x_0) / f_1 \in F\},$$

$$A_1 = A_0 \cup \{c_1 := 0, c_1 := c_1+1, c_1 := c_1^2, \dots\},$$

$$A_2 = A_1 \cup \{c_2 := 0, c_2 := c_2+1, c_2 := c_2^2, \dots\},$$

$$B = \{x_i := x_j, x_i := f_k(x_j) / x_i, x_j \in V, f_k \in F\}$$

ainsi que les ensembles de tests :

$$T_0 = \{p_i(x) / p_i \in P\},$$
$T_1 = T_0 \cup \{c_1=0\},$

$T_2 = T_1 \cup \{c_1=0\},$

$T' = \{p_i(x_j) / p_i \in P \text{ et } x_j \in V\},$

Les **schémas de Ianov** (resp. **schémas à un compteur**) (resp. **schémas à deux compteurs**) (resp. "flowcharts") sont les schémas itératifs écrits avec les instructions de $A_0$(resp. $A_1$) (resp. $A_2$) (resp. B) et les tests de $T_0$(resp. $T_1$) (resp. $T_2$) (resp. $T'$). Nous désignerons respectivement ces classes de schémas par $I_0, I_1, I_2, \dots, I_n$.

Le schéma suivant appartient à $I_1$:

<figure><img src="image_2.png" /></figure>
Il est clair qu'à toute interprétation $I = <D^I, p_i^I, f_i^I>$, à tout schéma (resp. "flowchart") $S$, on sait associer une fonction calculée $\underline{Val}(S,I) : D^I \to D^I$ (resp. $D^{Ik} \to D^{Ik}$ si $k$ est le nombre de variables du "flowchart" $S$).

En interprétant toujours les variables $c_i$ par des entiers positifs ou nuls et l'opération $\oplus$1 par $\lambda n(\underline{si} n=0 \ \underline{alors} \ 0 \ \underline{sinon} \ n-1)$, on peut définir l'in- terprétation $\underline{Val}(S,I)$ d'un schéma à un compteur (resp. à deux compteurs).

**Convention** : Pour tout "flow-chart" $S$ à $k$ variables $x_0, \dots, x_{k-1}$, nous désignons désormais par $\underline{Val}(S,I)$ la fonction monadique $D^I \to D^I$ définie par $\underline{Val}(S,I)(\xi)=\text{première composante de } \underline{Val}(S,I)(\xi, \dots, \xi)$.

**Définition** : Etant données deux classes de schémas $C$ et $C'$, et $S$ un schéma de $C$, on dit que $S$ est traductible en un schéma de $C'$ si on peut construire $S' \in C'$ tel que $S \equiv S'$, (c'est à dire $\underline{Val}(S,I) = \underline{Val}(S',I)$ pour toute interprétation $I$).

D'après la convention que nous venons de faire, si $S$ est un schéma monadique, cela a un sens de dire que $S$ est traductible en un "flow-chart". Soit $F$ la classe des schémas récursifs monadiques traductibles en schémas à un compteur.

Le tableau suivant résume les propriétés de traductibilité des classes $S$, $L, F, R, I_0, I_1, I_2, \dots, FC$ que nous avons introduites :

Schémas Récursifs

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

Schémas Itératifs

Dans ce tableau, $C \to C'$ signifie que tout schéma de $C$ est traductible
en un schéma de C' et C $---->C'$ signifie $C \subset C'$. (Remarquons que $C \----> C'$ implique $C \to C'$). Toute flèche non écrite et ne se déduisant pas par transïtivité de celles écrites est fausse. Le lecteur trouvera des contre exemples dans Luckham et Garland [7]. Les résultats sont tous énoncés dans [7] ainsi que Plaisted [11]. Le lecteur en trouvera aussi les preuves dans Cousineau et Rifflet [3] et Guessarian [5].

Les résultats essentiels de ce travail sont les suivants :

1) *On peut décider pour tout schéma S<sub>∈S</sub> si S appartient à F.*

2) *Si S<sub>∈F</sub>, on peut construire un schéma équivalent S' appartenant à I<sub>1</sub>.*

Nous allons maintenant donner un aperçu des méthodes utilisées pour les prouver.

*Trace d'un schéma.*

Luckham, Park et Paterson ont introduit dans [8] une classe parti-
culière d'interprétations, les *interprétations libres* définies par les condi-
tions suivantes :

1) $D^I = F^*$ (dont le mot vide sera désigné par $\xi_O$),

2) pour tout $d \in D^I$, tout $f \in F$, $f^I(d) = df$.

Soient F et G deux schémas appartenant à SuI<sub>2</sub>.

**Proposition 1 :** $F \equiv G \text{ ssi, pour toute interprétation libre I} \\
\underline{Val(F,I)}(\xi_O) = \underline{Val(G,I)}(\xi_O).$

Soit I une interprétation libre telle que $F(\xi_O) = m \in F^*$.

Soit n le nombre de prédicats du schéma et $\Sigma = \{0,1\}^n \times F$ ; associons à m le mot $\bar{m} \in \Sigma^*$, $\bar{m} = (n_o, f_{i_o}) (n_1, f_{i_1}) \dots (n_k, f_{i_k})$ où

(1) $m = f_{i_o} \dots f_{i_k}$

(2) $n_o$ (resp. $n_j$) représente la valeur des n prédicats sur $\xi_O$ (resp. $f_{i_o}, \dots, f_{i_{j-1}}$). Remarquons qu'au cours du calcul

de F(ξ₀), les seuls tests effectués sont ceux dont on a "enregistré" la valeur
sur le mot m. Donc, pour toute interprétation libre I telle que m = (n₀, fᵢ₀) ... (nₖ, fᵢₖ)
satisfait la condition (2) ci-dessus, F(ξ₀) = fᵢ₀ ... fᵢₖ.
Appelons *trace* de $F_i$ le langage sur $\Sigma$ constitué des mots m associés à toutes les interprétations libres. (Ce langage est noté $\text{Tr}(F)$). Ceci montre que

**Proposition 2** : $F \equiv G \quad \text{ssi} \quad \text{Tr}(F) = \text{Tr}(G)$.

La proposition suivante permet de caractériser certaines classes de
schémas par leur trace et démontre une partie du tableau de la page 4 :

**Proposition 3** : *Soit $L \subset \Sigma^*$ la trace d'un schéma monadique S. Ce schéma est traductible en un schéma de la classe*

$\mathrel{\text{I}}_2 \text{ ssi } L \text{ est récursivement énumérable,}$

$\mathrel{\text{I}}_1 \text{ ssi } L \text{ est déterministe à compteur,}$

$\mathrel{\text{I}}_0 \text{ ssi } L \text{ est régulier,}$

$\mathcal{S} \text{ ssi } L \text{ est simple déterministe,}$

$\mathcal{R} \text{ ssi } L \text{ est régulier.}$

(Ces trois propositions sont démontrées dans [3] et [7]).

Rappelons que les langages déterministes à compteur sont les langages
reconnus par les automates à mémoire-pile déterministes ayant un seul symbole de
pile (voir page 14 et [6]) et que les langages simples sont les langages reconnus
par arrêt sur pile vide des automates à un seul état, et sans $\epsilon$-transition (voir
page 14 et [2]). Il résulte de cette proposition que le problème de déterminer la
classe F se ramène à celui de décider si un langage simple est un langage déter-
ministe à compteur.

Nous allons en fait chercher à déterminer les automates déterministes
qui reconnaissent des langages déterministes à compteur.

Afin de présenter la méthode que nous utilisons, donnons quelques définitions relatives aux automates déterministes à pile. Soit $\mathcal{A}$ un automate :

1) *le langage de pile* $P(\mathcal{A})$ est l'ensemble des mots $mq$ tels que $m \in \mathbb{N}^*, q \in K$ ($\mathbb{N}$ est l'alphabet de pile et $K$ l'ensemble des états) et $(q,m)$ est une configuration que l'automate atteint au cours de la reconnaissance d'un mot. Ce langage est un langage régulier dont on peut construire une grammaire.

2) Deux configurations sont *équivalentes* (relation notée $(q,m) \equiv (q',m')$)
ssi les langages reconnus en les prenant comme configuration initiale de leur
automate respectif sont les mêmes.
3) Un automate $\mathcal{A}$ est normal si il existe un entier $k$ tel que toute configuration est équivalente à au plus $k$ configurations de $P(d)$.

4) Etant donnés deux automates $a_1$ et $a_2$, $m_1,q_1 \in P(a_1)$ et $(m_2q_2) \in P(a_2)$, ces configurations sont conjuguées ssi elles sont atteintes par $a_1$ et $a_2$ après lecture d'un même mot sur l'alphabet d'entrée.

Enumerons les propositions-clef :

1) Un langage régulier sur $\mathcal{X}$ est de la forme $\bigcup_{i=1}^{r} \alpha_i \beta_i^* \gamma_i$ avec $\alpha_i, \beta_i, \gamma_i \in \mathcal{X}^*$ si et seulement si il est image de $\{\mathcal{x}^*\}$ par une transduction rationnelle d'image bornée (voir page 9). Nous appelons quasi-périodiques ces langages. On peut décider si une grammaire régulière engendre un langage quasi-périodique.

2) Si le langage de pile $P(d)$ d'un automate $\mathcal{A}$ est quasi-périodique, $L(\mathcal{A})$ est un langage déterministe à compteur.

3) La réciproque est vraie pour les automates normaux ce que nous montrons en prouvant :

4) que la conjugaison entre configurations d'un automate normal et d'un automate à compteur équivalents est une transduction rationnelle (d'image bornée) et en appliquant 1).

5) Pour tout langage simple, on peut construire un automate (simple déterministe) normal le reconnaissant. Il en résulte un algorithme pour décider si un langage simple est un langage déterministe à compteur et donc, grâce aux propositions 2 et 3, une caractérisation effective de la classe F.

Pour décider par cette méthode si un langage déterministe est un langage déterministe à compteur, il faudrait pouvoir construire un automate normal équivalent à un automate donné, ce que nous ne savons pas faire. Ce problème est lié au problème ouvert de décider l'équivalence de deux automates déterministes.

Ce travail est extrait de la thèse de troisième cycle de l'auteur (Université PARIS VII).
# 1. Langages Réguliers Quasi-périodiques :

Un mot $\alpha \in \Sigma^*$ est dit *périodique* s'il s'écrit $\alpha=\beta^k$, $k \ge 2$ et $\beta \in \Sigma^*$. Nous appelerons *périodiques* les langages $\beta^*$ pour $\beta \in \Sigma^*$ et *quasi-périodiques* les langages de la forme $\bigcup_{i=1}^k \alpha_i \beta_i^{\gamma_i}$ où $\alpha_i, \beta_i, \gamma_i \in \Sigma^*$. Ce sont des langages réguliers que l'on peut caractériser comme les images par transduction rationnelle bijective des langages réguliers sur $\{x\}$, i.e des ensembles d'entiers ultimement périodiques.

## Langages sur $\{x\}$.

Nous identifierons le monoïde $\{x\}^*$ à N au moyen de l'isomorphisme de monoïde $h: \langle\{x\}^*, 0, 1\rangle \to \langle N, +, 0\rangle$, défini par $h(x)=1$. Nous parlerons donc de langages sur N et de langages sur $\{x\}$ indifféremment.

**Définition** : Un ensemble $L \subset N$ est dit *ultimement périodique de période $\pi \in N$* si il existe $\ell \in N$ tel que pour tout $x>\ell$ $x \in L$ ssi $x+\pi \in L$.

**Lemme 1** : Si $(L, \pi)_{1 \le i \le k}$ est une famille finie d'ensembles U.P. de période $\pi$, alors $\bigcup_{i=1}^k L_i$ et $\bigcap_{i=1}^k L_i$ sont des ensembles U.P. de période $\pi$ = p.p.c.m. $(\pi_1, \dots, \pi_k)$.

**Lemme 2** : Si $\alpha, \beta_1, \dots, \beta_k \in N$, alors l'ensemble $L=\{\alpha+n_1\beta_1 + \dots + n_k\beta_k \mid n_1, \dots, n_k \in N\}$ est un ensemble U.P. de période $\pi=p.p.c.m.(\beta_1, \dots, \beta_k)$.

**Démonstration** : Soit $\ell = \alpha + (k-1)\pi$. Si $x \in L$ alors $x + \pi \in L$. Si $x > \alpha + (k-1)\pi$ et $x + \pi \in L$ alors $x + \pi = \alpha + n_1\beta_1 + \dots + n_k\beta_k$. Ruisque $x + \pi > \alpha + k\pi$ il existe $i, 1 \le i \le k$ et tel que $n_i > \pi$ donc $x = \alpha + n_1\beta_1 + \dots + (n_i - \pi)\beta_i + \dots + n_k\beta_k \in L$. CQFD.

Parikh [10] a démontré le résultat suivant : Si L est un langage algébrique sur N, alors L est une réunion finie d'ensembles linéaires d'entiers (i.e les ensembles intervenant dans le lemme 2). Réciproque-tout ensemble linéaire est régulier. D'où la :

**Proposition 1** : La classe des ensembles U.P., la classe des langages réguliers sur N et la classe des langages algébriques sur N coïncident.

## La famille des langages quasi-périodiques

Rappelons tout d'abord quelques définitions (Nivat [9]). Une transduction rationnelle de $X^* \to Y^*$ est une relation $\tau \subset X^* \times Y^*$ telle qu'il existe $Z$ et $R$, langage régulier sur $Z^*$ et deux homomorphismes $\phi: Z^* \to X^*$ et $\Psi: Z^* \to Y^*$
tels que $\{(x,y) \in \tau\} = \{\phi(h), \Psi(h) | h \in R\}$. Nous aurons besoin de distinguer
des classes particulières de transductions rationnelles.

-les *transductions bijectives*

-les *transductions d'image finie* (i.e. $\forall x \in X^* \{y \in Y^* | (x,y) \in \tau\}$ est fini.

-les *transductions d'image bornée*. Il existe un entier $k_+$ plus grand que le cardinal de $\{y \in Y^* | (x,y) \in \tau\}$ pour tout $x \in X^*$.

Nous appelerons dans ce qui suit *grammaire régulière* une *grammaire régulière droite* $G(N, \Sigma)$ (i.e dont les équations sont de la forme
$S_i = \sum_{j=1}^{r} a_j S_j + \sum_{j=1}^{r'} a'_j S_j$ réduite (i.e dont tout non-terminal $S$ engendre
un langage non vide).

Soit $R$ un langage régulier sur $\Sigma$ et $\beta \in \Sigma^+$. On notera $R\beta \{r \in \Sigma^* | \exists k \ge 0, r \beta^k \in R \text{ et } \beta \text{ n'est pas facteur droit de } r\}$. $R\beta$ est un langage régulier dont on sait calculer une grammaire.

On appelle *langage quasi-périodique* un langage fini ou un langage régulier
satisfaisant l'une des conditions (i)-(v) de la :

**Proposition 2** : *Pour tout langage régulier infini $R \in \Sigma^*$ les conditions (i) à (v) sont équivalentes :*

(i) $R = \bigcup_{i=1}^{r} \alpha_i \beta_i^* \gamma_i \quad \text{où } \alpha_i, \beta_i, \gamma_i \in \Sigma^*$

(ii) (i) est vrai et de plus pour $i \neq j, \alpha_i \beta_i^* \gamma_i \alpha_j \beta_j \gamma_j \in \Sigma^*$

(iii) R est l'image de N par une transduction rationnelle bijective.

(iv) R est l'image d'un langage régulier de N par une transduction rationnelle d'image bornée.

(v) Si $G$ est une grammaire régulière et $R=L(G,S_0)$, si $S$ est un non-terminal de $G$ tel que pour un $\beta$ primitif $S \to^{\beta^k} S'$ et $k>0$ alors $\{m \in \Sigma^* | S \to^{\beta^k} m S\} \cap \beta$ est fini.

**Corollaire 1** : *On peut décider si une grammaire régulière donnée engendre un langage quasi-périodique.*

**Démonstration** : On peut vérifier si (v) est satisfaite. Pour chaque non-terminal $S$, calculons un $\beta$ s'il en existe. On sait décider si le langage régulier $\{m \in \Sigma^* | S_0 \to^m S\} \cap \beta$ est fini.
Rappelons [14] quelques définitions et propriétés de $\Sigma^*$. Un mot $u \in \Sigma^*$ est dit *primitif* s'il n'est pas $v^h$ pour $h \ge 2$ et $v \ne 1$. Deux mots u et v sont *conjugués* si $u=u_1u_2$ et $v=u_2u_1$. Cette relation est une relation d'équivalence. Si $u^x$ et $v^y$ sont conjugués, il existe deux mots primitifs et conjugués $u_0$ et $v_0$ tels que $u=u_0^s$ et $v=v_0^t$.

**Lemme 3 :** Si $\alpha\beta^*\gamma\alpha'\beta'^*\gamma'$ est infini, il existe un mot primitif $\beta_0, \alpha_0$ et $\gamma_0$ tels que $\alpha\beta^*\gamma\alpha'\beta'^*\gamma' \subset \alpha_0\beta_0^*\gamma_0$. $\beta$ et $\beta'$ sont conjugués d'une puissance de $\beta_0$.

**Démonstration :** Il existe $w \in \alpha\beta^*\gamma\alpha'\beta'^*\gamma'$ tel que $w=\alpha\beta^y\gamma=\alpha'\beta'^y\gamma'$, $|\alpha\beta^y|>|\alpha'|$ et $|\beta'^y\gamma'|>|\gamma|$. Soit $\delta$ tel que $\alpha\beta^y=\alpha'\delta$. On a aussi $\delta\gamma=\beta'^y\gamma'$. Puisque $\alpha\beta^*\gamma\alpha'\beta'^*\gamma'$ est infini, il existe $x$ et $x'$ tels que $|\beta^x|>\delta$ et $\alpha\beta^{y+x}=\alpha'\beta'^{y+x'}\gamma'$. Soit encore $\alpha'\delta\beta^x=\alpha'\beta'^x\delta\gamma$ et donc $\delta\beta^x=\beta'^x\delta$. Alors il existe $\eta$ tel que $\beta^x=\eta\delta$ et $\beta'^x=\delta\eta$. Il existe donc $\beta_0$ tel que $\beta=\beta_0^s$, $\beta_0^s=\beta_1^s\beta_2^s\beta_0^s=\beta_2^s\beta_1^s$ et $\beta'=\beta'^s$. Il en résulte que $\alpha\beta^*\gamma\alpha\beta_0^*\gamma$ et $\alpha'\beta_0^*\gamma'\subset\alpha'\beta_0^*\gamma'$. Si $\alpha$ est plus court que $\alpha'$, on prend $\alpha_0=\alpha$ et $\alpha'\beta_0^*\gamma'\subset\alpha\beta_0^*\beta_1\gamma'$. On prend alors pour $\gamma_0$ le plus court des deux mots $\gamma$ et $\beta_1\gamma'$. Si $\alpha$ est plus long que $\alpha'$, on prend $\alpha_0=\alpha'$ et $\alpha\beta_0^*\gamma\alpha'\beta_0^*\beta_2\gamma$. On prend alors pour $\gamma_0$ le plus court des mots $\gamma'$ et $\beta_2\gamma$. Dans tout les cas on a $\alpha\beta^*\gamma\alpha'\beta'^*\gamma' \subset \alpha_0\beta_0^*\gamma_0$. CQFD.

**Corollaire 2 :** *La relation $(\alpha,\beta,\gamma)\bowtie(\alpha',\beta',\gamma')$ définie entre éléments de $(\Sigma^*)^3$ par "$\alpha\beta^*\gamma\alpha'\beta'^*\gamma'$ est un langage infini," est une relation d'équivalence.*

**Démonstration de la proposition 2 :**

(i) $\Rightarrow$ (ii)

Soit $R = \bigsqcup_{i=1}^r \alpha_i \beta_i^* \gamma_i$. Si il existe $h$ et $j \ne h$ tels que $(\alpha_h, \beta_h, \gamma_h)^\infty (\alpha_j, \beta_j, \gamma_j)$, soit $\alpha^* \gamma \supset \alpha_h \beta_h^* \gamma_h \supset \alpha_j \beta_j^* \gamma_j$ (lemme 3) et $R_1 = \bigsqcup_{i \ne h, j} \alpha_i \beta_i^* \gamma_i \cup \alpha \beta^* \gamma$. $R \in R_1$ et $R_1$ à $r-1$ "composantes" au lieu de $r$.

Par itération, on construit $R \subset R_1 \subset R_2 \subset \dots \subset R_k = R'$, chaine finie de langages vérifiant (i) et telle que les composantes de $R_k$ sont deux à deux d'in-tersection finie.

Il existe donc un entier $M$ plus grand que la longueur des mots $x$ appartenaant à deux composantes de $R'$. Posons $R' = \bigsqcup_{i=1}^r \alpha_i' \beta_i'^* \gamma_i'$. Pour tout $i \in [1, r']$, $\{x \in N | \alpha_i' \beta_i'^* \gamma_i' \in R \text{ et } |\alpha_i' \beta_i'^* \gamma_i'| \ge M\}$ est un ensemble régulier de $N$, donc un ensemble ultimement périodique de période $\pi$. C'est la réunion d'une
famille finie d'ensembles disjoints deux à deux de la forme {$\rho+\lambda\pi | \lambda \in N$} et d'un ensemble fini disjoint de ceux-ci. R est donc la réunion disjointe d'une famille finie d'ensembles $\alpha_i!\beta_i!\rho_i!(\beta_i!n_i!)^*\gamma_i'$ et d'un ensemble fini disjoint de ceux-ci.

L'ensemble des mots de R de longueur >M a donc été mis sous la forme requise par (ii). On peut alors ajouter l'ensemble fini des mots de R de longueur $\le M$.

$$
(ii) \Rightarrow (iii) : \quad R = R_0 \cup \left[ \bigcup_{i=1}^{r} \alpha_i! \beta_i! \gamma_i' \right]. \quad \text{Pour } 1 \le i \le j \le r \text{ et } \beta_i \neq 1, \alpha_i! \beta_i! \gamma_i' \cap R_0 = \emptyset \text{ et } \alpha_i! \beta_i! \gamma_i' \cap \alpha_j! \beta_j! \gamma_j' = \emptyset.
$$

Numérotons de 0 à N₀⁻¹ les éléments de R₀ : ($\delta_i$)₀≤i≤N₀⁻¹.

Soit $Z=\{d_i|0\le i\le N_0-1\}\cup\{a_i,b_i,c_i|1\le i\le r\}$ et $H\subset Z^*$ le langage régulier $\{d_i|0\le i\le N_0-1\}\cup\bigcup_{i=1}^r a_i b_i^* c_i$. Soit $\Phi$ le morphisme $Z^*\to \Sigma^*$ défini par $\Phi(a_i)=\alpha_i$, $\Phi(b_i)=\beta_i$, $\Phi(c_i)=\gamma_i$, $\Phi(d_i)=\delta_i$.

Soit $\Psi$ le morphisme $Z^* \to N$ défini par $\Psi(d_i)=i, \Psi(a_i)=N_0+i-1, \Psi(b_i)=r, \Psi(c_i)=0$. Nous avons défini une transduction rationnelle $\tau=\{(\Phi(h),\Psi(h)|h\in H)\}$ Elle réalise une bijection entre $R$ et $N$: $(x,y)\in\tau$ ssi $y<N_0$ et $x=\delta_i$ ou bien $y=N_0+(i-1)+\lambda r$ pour $1\le i\le r, \lambda\ge 0$ et $x=\alpha_i, \beta_i, \gamma_i$. L'hypothèse sur $R$ montre que c'est une bijection.

$$
(iii) \Rightarrow (iv) \text{ Résulte des définitions.}
$$

$$
(iv) \implies (v) : \text{Soit } \tau \text{ une transduction rationnelle d'image bornée, } \tau:N \to \Sigma^* \text{ et définie par } H \subset Z^*, \Psi: Z^* \to N \text{ et } \ell: Z^* \to \Sigma^*. \text{ Supposons que } R=\tau(N) \text{ ne vérifie pas } (v) \text{ ; il existe } G(W,\Sigma), \text{ grammaire régulière telle que } R=L(G,S_0) \text{ et } \{m \in \Sigma^* | S_0^* \supset mS\} \square \beta \text{ est infini. Il existe alors } f \text{ et } g \in \Sigma^+, R_0 \text{ partie infinie de } \Sigma^* \text{ tels pour tous } r \text{ et } r' \text{ dans } R_0, r \neq r' \Rightarrow rf^* \cap r!f^* = \emptyset. \text{ Il suffit de prendref}=\beta^k, g \in L(G,S) \text{ et une partie } R_0 \text{ convenable de } \{m \in \Sigma^* | S_0^* \supset mS\}.
$$

Nous allons en déduire une contradiction. Admettons d'abord que l'on puisse "remonter" $R_0 f^* g$, c'est à dire trouver $\bar{R}_0 \subset Z^*$, $\bar{f}$ et $\bar{g} \in Z^*$ dont les images $\ell(\bar{R}_0)$, $\ell(\bar{f}) \in f^*$ et $\ell(\bar{g}) \in f^*$ g satisfont les mêmes propriétés que le triplet $\langle R_0, f, g \rangle$. Puisque $\tau: N \to \Sigma^*$ est d'image finie $\Psi(\bar{f}) \neq 0$, sinon pour un $r \in \bar{R}_0$, $\tau(\psi(r)+\psi(\bar{g}))$ serait l'ensemble infini $\ell(r) f^* g$. Donc pour tout $r$ dans $R_0$, $\Psi(\bar{r}f^*\bar{g})$ est une partie périodique de $N$ de période $\Psi(\bar{f})=\pi$. Puisqu'il n'y a qu'un nombre fini de classes d'équivalence modulo $\pi$, l'une au moins de ces classes contient une infinité de parties $\Psi(\bar{r}f^*\bar{g})$. Si k majore le nombre d'éléments de chaque $\tau(x) \subset \Sigma^*$, alors il existe un $x \in N$ appartenant à $k+1$ parties $\Psi(r_i \bar{f}^* \bar{g})$, $1 \le i \le k+1$. Donc il existe $(y_i)_{1 \le i \le k+1}$ tel que $\tau(x) \supset \{\ell(r_i) f^{y_i} g\}$. Puisque $\tau(x)$ a au plus k éléments il existe i et j tels que $\ell(r_i) \neq \ell(r_j)$
et $l(r_i)f^*g=l(r_j)f^*g$ donc $l(r_i)f^*n(l(r_j)f^*g) \neq \emptyset$ contrairement à l'hypothèse sur $l(\bar{R}_0)$.

Il reste à montrer comment "remonter" $\bar{R}_0 f^* g$. Soit $G_1(W_1, Z)$ une grammaire régulière telle que $H=L(G_1, S'_0)$. Pour tout $(r,x) \in \bar{R}_0 \times N$ il existe $uv_1...v_x w \in H$ tel que $l(u)=r, l(v_i)=f$ pour $1 \le i \le x$, $l(w)=g$. Si $x> |W_1|+1$ aors il existe un $S \in W_1$ tel que $S'_0 \xrightarrow{\bar{G}_1} uv_1...v_x S, S \xrightarrow{\bar{G}_1} v_{\ell+1}...v_k S$ et $S \xrightarrow{\bar{G}_1} v_{k+1}...v_x w$.

Posons alors $\theta(r,x)=(S,uv_1...v_\ell,v_{\ell+1}...v_k,v_{k+1}...v_x w)$. Puisque $W_1$ est fini et que $\bar{R}_0$ est infini, il existe une infinité de $r \in \bar{R}_0$ et un $S_1 \in W_1$ tels que $\theta(r, |W_1|+1)=(S_1,r',f',g')$. Prenons pour $\bar{R}_0$ l'ensemble des $r'$ correspondants, $\bar{f}$ l'un quelconque des $f'$, $\bar{g}$ l'un quelconque des $g'$. Il est clair alors que $\bar{R}_0 \bar{f}^* \bar{g} \subset H$ et que $(l(\bar{R}_0), l(\bar{f}), l(\bar{g}))$ vérifie les propriétés souhaitées.

$(v) \implies (i)$: Soit $G(W, \Sigma)$ une grammaire

régulière telle que $L(G, S_0)=R$ pour $S_0 \in W$. Soit $W_0$ l'ensemble des non-terminaux de $G$ t.q. pour un $m \in \Sigma^*, S \xrightarrow{m} S$. Pour tout $S \in W_0$ il existe un mot $\beta_S$ primitif tel que $S \xrightarrow{\beta_S} S^* \subset G$ et le langage régulier $D(\beta) = \{ u \in \Sigma^* | S_0 \xrightarrow{\beta} u S \} \subset \beta_S$ est fini (hypothèse de (V)). Pour tout non-terminal $S \in W$ soit $F(S)$ l'ensemble des mots m de $\Sigma^*$ tels que $S \xrightarrow{m} W$ par une dérivation n'utilisant que des non-terminaux de $W-W_0$. L'ensemble des telles dérivations est fini et donc $F(S)$ est fini.

Il en résulte que $R \subset F(S_0) \cup \bigcup_{S \in W_0} D(S) \beta_S^* F(S)$. Puisque $F(S), D(S), W_0$ sont finis $R$ est contenu dans un langage vérifiant (i). La technique utilisée au cours de la preuve de $i \implies ii$ montre que $R$ lui-même vérifie (i).

Au cours de la partie $(i) \implies ii$ de la démonstration, nous avons démontré le :

**Corollaire 3** : *Tout langage régulier contenu dans un langage quasi-périodique est quasi-périodique.*

Tous ces résultats peuvent se reformuler ainsi :

**Théorème :** *L'ensemble des langages quasi-périodiques est la plus petite famille de langages réguliers contenant les langages finis et N et close par union, intersection, transductions rationnelles d'image bornée (resp. transductions rationnelles bijectives).*

**Démonstration :** Soit $L$ la famille des langages réguliers quasi-périodiques sur $\Sigma$.

Il est clair qu'elle est close par union (proposition 2 (i)), contient $N$ et les langages finis (proposition 2 (iii)). Soit $\tau X^* \to Y^*$ une transduction d'image bornée et $R$ l'image par $\tau$ d'un langage quasi-périodique $R$. $R$ est l'image par $\tau_0 : N \to X^*$, transduction bijective. $\tau_0 \tau_0$ est une
transduction rationnelle (Nivat [9]), d'image bornée. Donc $R' \in L$
(proposition 2 (iv)). Par les corollaires 2 et 3, $\alpha\beta^{*\gamma\alpha'}\beta'^{*\gamma'}$ est
quasi-périodique. $L$ est donc close par intersection. Puisque tout lang-
age de cette famille est l'image de $N$ par une transduction ration-
nelle, elle est contenue dans toute famille satisfaisant ces conditions.
C'est donc bien la plus petite. CQFD.

Exemples de langages non quasi-périodiques :

1) {a,b}* et a*b* ne sont pas quasi-périodiques. Le critère (v) de la proposition 1 n'est pas satisfait.

2) La famille des langages quasi-périodiques sur Σ n'est pas close par complémentation : {a,b}*-b*={a,b}*a{a,b}* et contient le langage régulier a*ab* qui n'est pas quasi-périodique.
## 2. Langages de Pile des Automates

Rappelons les définitions relatives aux **automates à mémoire pile déterministes** (AMPD ou tout simplement **automates**) (voir aussi [6]).

Un AMPD $\mathfrak{a}$ est un 7-uplet $<\Sigma, K, \Gamma, \delta, q^0, Z^0, F>$ où :

(i) $\Sigma$ est **l'alphabet d'entrée** (fini),

(ii) $K$ l'ensemble fini des **états**,

(iii) $\Gamma$ **l'alphabet de pile**, ($K \Gamma = \emptyset$)

(iv) $q^0 \in K$ **l'état initial**,

(v) $Z^0 \in \Gamma$ **le symbole de pile initial**,

(vi) $F \subset K$ l'ensemble des **états terminaux**

(vii) $\delta: K_x(\Sigma \cup \{\epsilon\}) \times \Gamma \rightarrow K_x\Gamma^*$, est une application non partout définie, telle que pour tout $(q,a,Z) \in K_x\Sigma x\Gamma$ $\delta(q,a,Z)$ et $\delta(q,\epsilon,Z)$ ne sont pas simultanément définis.

Une **configuration** est un couple $(q,m) \in K_x\Gamma^*$ que l'on notera aussi sans ambiguïté possible mq. Pour tout $a \in \Sigma \cup \{\epsilon\}$ nous écrirons

$a : (q_1, m_1 Z_1) \underset{a}{\vdash} (q_2, m_1 m_2)$ ssi $\delta(q_1, a, Z_1) = (q_2, m_2)$.

Pour tout $w \in (\Sigma \cup \{\epsilon\})^* = a_1 a_2 \cdots a_n$ nous écrirons $w : (q,m) \stackrel{a}{\vdash} (q',m')$ ssi il existe une suite $(q_i, m_i)$ de configurations telle que $(q_0, m_0) = (q,m)$, $(q_n, m_n) = (q',m')$ et pour $0 < i \le n$ $a_i : (q_{i-1}, m_{i-1}) \stackrel{a}{\vdash} (q_i, m_i)$. Nous écrirons aussi $w' : (q,m) \stackrel{a}{\vdash} (q',m')$ où $w'$ est déduit de $w$ en effaçant les $\epsilon$.

Les langages reconnus par $\mathfrak{a}$ par **arrêt sur état final** et **arrêt sur pile vide** respectivement notés $T(\mathfrak{a})$ et $N(\mathfrak{a})$ sont définis par $N(\mathfrak{a}) = \{u \in \Sigma^* | u : (q^0, Z^0) \stackrel{a}{\vdash} (q, 1)\}$ et $\tau(\mathfrak{a}) = \{u \in \Sigma^* | \exists q \in F \exists m \in \Gamma^* u : (q^0, Z^0) \stackrel{a}{\vdash} (q, m)\}$.

Rappelons que les $N(\mathfrak{a})$ sont l'ensemble des **langages algébriques déterministes préfixes** et les $T(\mathfrak{a})$ l'ensemble des **langages déterministes** [6].

Nous allons étudier une classe particulière d'automates :

Les **automates à compteur déterministes** (ACD) :

Un automate à compteur est un AMPD $<\Sigma, K, \Gamma, \delta, q^0, Z^0, F>$ vérifiant les conditions supplémentaires suivantes :

(iii bis) $\Gamma = \{Z^0, Z\}$

(vii bis) Si $\delta(q,a,Z)$ est définie, $\delta(q,a,Z) \in K_x\{Z\}^*$
Si $\delta(q,a,Z^0)$ est définie, $\delta(q,a,Z^0) \in K_x(Z^0\{Z\}^*)$.

Donc toute configuration est de la forme $(q, Z^0 Z^n)$. On l'identifiera à un élément de $K_x N$. Ceci nous permet de définir plus simplement un ACD
comme un 5-uplet $\langle\Sigma, K, \delta, q^0, F\rangle$ pour lequel les définitions (i), (ii), (iv), (vi) sont valables et dont la fonction de transition $\delta$ vérifie :
(vii) : $\delta$ est une application partiellement définie de $K_x\{\Sigma|\{e\}\}|x\{0,1\} \rightarrow Kx\Gamma{-1,+\delta}[\text{telle que } \delta(q,ay) \text{ et } \delta(q,\epsilon,y) \text{ ne sont pas simultanément définies (si } a\in\Sigma\text{)}$.

Les transitions élémentaires se définissent ainsi :

$a : (q, x) \stackrel{\delta}{\rightarrow} a$ (q', x+k) ssi $(\delta(q, a, 0) = (q', k)$ et $x=0$) ou bien $(\delta(q, a, 1) = (q', k)$ et $x\neq 0)$.

Nous avons identifié les configurations d'un automate $a$ à des mots de $(\Gamma\cup K)^*$Nous allons montrer que l'ensemble des configurations intervenant au cours de la reconnaissance d'un mot du langage de pile de $a$, forment un langage régulier sur $\Gamma\cup K$ dont on peut déterminer une grammaire.

Soit $a = \langle\Sigma, K, \Gamma, \delta, q^0, Z^0, F\rangle$ un AMPD. Pour tous $q\in K$ et $Z\in\Gamma$ définissons les langages auxiliaires :

$$R(q, Z) = \{m'q'\epsilon(K\cup\Gamma)^* \mid \exists u\in\Sigma^* \ u: (q, Z)\stackrel{\delta}{\rightarrow} (q', m')\}, (1)$$

$$F(q) = \{m'q'\epsilon(K\cup\Gamma)^* \mid \exists u\in\Sigma^* \ \exists m\in\Gamma^* \ u: (q', m')\stackrel{\delta}{\rightarrow} (q, m)\},$$

$$N(q) = \{m'q'\epsilon(K\cup\Gamma)^* \mid \exists u\in\Sigma^* \ u: (q', m')\stackrel{\delta}{\rightarrow} (q, 1)\}.$$

Les langages de pile d'un automate, correspondant respectivement aux langages reconnus par arrêt sur état final et pile vide sont :

(i) $P^F(a) \in \Gamma^*K$ défini par :
$$mq\in P^F(a) \quad \text{ssi il existe } u, v\in\Sigma^*, q'\in F \text{ et } m'\in\Gamma^* \text{ tels que } u: (q^0, Z^0)\stackrel{\delta}{\rightarrow} (q, m) \text{ et } v: (q, m)\stackrel{\delta}{\rightarrow} (q', m').$$

(ii) $P^N(a) \in \Gamma^*K$ défini par :
$$mq\in P^N(a) \quad \text{ssi il existe } u, v\in\Sigma^*, q\in K \text{ tels que } u: (q^0, Z^0)\stackrel{\delta}{\rightarrow} (q, m) \text{ et } v: (q, m)\stackrel{\delta}{\rightarrow} (q, 1).$$

**Lemme 1 :** *Pour tout couple $(\gamma, \gamma')$ de configurations de $a$, on peut décider si il existe $u\in\Sigma^*$ tel que $u:\gamma\stackrel{\delta}{\rightarrow}\gamma'$.*

**Démonstration :** En utilisant les méthodes classiques de [6] , on construit une grammaire algébrique engendrant $\{u\in\Sigma^* \mid u:\gamma\stackrel{\delta}{\rightarrow}\gamma'\}$. On sait décider si une grammaire donnée engendre un langage vide. CQFD.

---

<footnote>(1) On écrit partout $\mid$ au lieu de $\stackrel{\delta}{\rightarrow}$ car il n'y a pas d'ambiguïté.</footnote>
**Théorème 1 :** *Pour tout automate $a$, on peut déterminer des grammaires régulières engendrant $P^F(a)$ et $P^N(a)$.*

**Démonstration :** Il résulte des définitions que

$$P^F(a) = \bigcup_{q \in F} F(q),$$

et $P^N(a) = \bigcup_{q \in K} N(q)$. Il suffit donc de savoir calculer des grammaires régulières engendrant les langages $R(q,Z),F(q)$ et $N(q)$, ce qui est l'objet des lemmes 2 et 3 pour avoir démontré ce théorème.

**Lemme 2 :** *Etant donné un automate $a$, on peut construire une grammaire régulière*

**Démonstration :** Il résulte du lemme 1 que l'on peut calculer l'ensemble fini $W_0$ des $(q,Z,q',m')$ tels que :

(i) Il existe $a \in \Sigma \cup \{\epsilon\}$, et $(q',m) \in Kx[\cdot]^*$ tels que $\delta(q,aZ)=(q'',m)$,

(ii) Il existe $u \in \Sigma^*$ tel que $u:(q'',m) \stackrel{*}{\Rightarrow} (q',m')$,

(iii) $m'=1$ ou $m'=m'_1Z'$ et $m'_1$ est facteur gauche de $m$.

Définissons alors $G_0$ par les équations :

$$[q,Z]=Zq + \sum q' + \sum m'[q',Z'] \quad \text{où le premier } \Sigma \text{ est étendu aux } q' \text{ tels que}$$
$$ (q,Z,q',1) \in W_0 \text{ et le second aux } q',Z',m' \text{ tels que } (q,Z,q',m'Z') \in W_0. \text{ Nous allons montrer que pour tous } q,Z,q',m',Z', \text{ il existe } u \in \Sigma^* \text{ tel que} $$
$$ u:(q,Z) \stackrel{*}{=} (q',m'Z') \text{ ssi } [q,Z] \stackrel{*}{\subset} G_0 m'[q',Z'] \quad \text{Avec les règles terminales} $$
$$ [q',Z'] \to Z'q' \text{ et } [q',Z'] \to q'' \quad \text{pour } (q',Z',q'',1) \in W_0 \text{ la conclusion du lemme en résultera.} $$

Il est clair que si $(q,Z,q',Z') \in W_0$ il existe $u \in \Sigma^*$ tel que $u:(q,Z) \stackrel{*}{=} (q',m'Z')$. Il en résulte que si $[q,Z] \stackrel{*}{\subset} G_0 m'[q',Z']$ alors il existe $u \in \Sigma^*$ tel que $u:(q,Z) \stackrel{*}{=} (q',m'Z')$. Montrons la réciproque par récurrence sur le nombre $n$ de transitions élémentaires d'une suite $u:(q,Z) \stackrel{*}{=} (q',m'Z')$ :

si $n=1$, $[q,Z] \to m'[q',Z']$ par définition de $W_0$;

si $n>1$ soit $u:(q,Z) \stackrel{*}{=} (q'',m''Z'') \to (q',m'Z')$:

si $|m'Z'| \ge |m''Z''|$ la dernière transition résulte de $(q'',Z'') \to (q',m'_1Z')$ et $m'=m''m'_1$. Alors $[q,Z] \stackrel{*}{\to} m''[q'',Z''] \to m''m'_1[q',Z']$
si $|m'Z'| < |m''Z''|$ la suite de transitions se décompose en
$(q,Z) \stackrel{*}{\longmapsto} (q_1,m_1Z_1) \longmapsto (q_2,m_1m_2Z_2) \stackrel{*}{\longmapsto} (q',m_1m_3Z')$ avec $m'=m_1m_3$ et
$m_3$ facteur gauche de $m_2$. $[q_1,Z_1] \stackrel{G_0}{\rightarrow} m_3[q',Z']$ par définition
de $W_0$ et avec l'hypothèse de récurrence, $[q,Z] \stackrel{*}{\rightarrow} m_1[q_1,Z_1] \rightarrow
m_1m_3[q',Z']$.

Dans chacun de ces deux cas $[q,Z] \xrightarrow[G_0]{} m'[q',Z']$. CQFD.

**Lemme 3 :** *Etant donné un automate a, on peut construire deux grammaires régulières $G_1$ $((Kx\Gamma)UK,\Gamma UK)$ et $G_2$ $((Kx\Gamma)UK,\Gamma UK)$ telles que pour tout $q\in K, L(G_1,[q])=N(q)$ et $L(G_2,[q])=F(q)$.*

**Démonstration :** Pour tous $q$ et $q' \in K$ soit $W(q,q')$ l'ensemble des $(m,m') \in \Gamma^* \times \Gamma^*$ tels que pour un $u \in \Sigma^*$ $u: (q,m) \stackrel{*}{\longmapsto} (q',m')$. Cet ensemble est récursif (lemme 1). Soit $W_1$ l'ensemble fini et calculable des $(q',Z',q)$ tels que pour un $u \in \Sigma^*$ et un $m \in \Gamma^*$ $u: (q',Z') \stackrel{*}{\longmapsto} (q,m)$.

Définissons $G_1((Kx\Gamma)UK,\Gamma UK)$ par les équations :

$$[q'] = \sum [q,Z] \quad (\text{pour } (Z,1) \in W(q,q')), $$

$$[q',Z'] = Z'q' + \sum_{(Z_1,Z,Z') \in W(q,q')} Z_1 [q,Z] + \sum_{(Z,Z') \in W(q,q')} [q,Z]$$

Soit $G_2$ la grammaire ayant les mêmes équations relatives aux $[q,Z]$ ainsi que les équations :

$$[q'] = \sum_{(q,Z,q') \in W_1} [q,Z] + \sum_{Z \in \Gamma} Z[q']$$

Nous allons montrer que $L(G_1,[q])=N(q)$ et $L(G_2,[q])=F(q)$.

a) Il existe $u \in \Sigma^*$ tel que $u:(q,mZ) \stackrel{*}{\longmapsto} (q',Z')$ ssi $[q',Z'] \xrightarrow[G_1]{} m[q,Z]$.

Démontrons, par récurrence sur la longueur de $m$ que la condition est nécessaire si $|m|=0$ alors $(q,Z) \stackrel{*}{\longmapsto} (q',Z')$ et donc $[q',Z'] \xrightarrow[G_1]{} [q,Z]$,
si $m=Z_1m_1$ la suite de transitions se décompose en $u_1u_2:(q,Z_1m_1\tilde{Z}) \stackrel{*}{\longmapsto} (q'',Z_1Z'') \stackrel{*}{\longmapsto} (q',Z')$ avec $u_1: (q,m_1Z) \stackrel{*}{\longmapsto} (q'',Z'')$. Donc $[q'',Z''] \xrightarrow[G_1]{} m_1[q,Z]$ et $[q',Z'] \xrightarrow[G_1]{} Z_1[q'',Z'']$. Finalement $[q',Z'] \xrightarrow[G_1]{} Z_1m_1[q,Z]$. CQFD.
Si $[q',Z'] \stackrel{*}{\overline{G}_1} m[q,Z]$ avec $m \in \mathbb{U}\{1\}$, $(q,mZ) \stackrel{*}{=} (q',Z')$. Il en résulte que $[q',Z'] \stackrel{*}{\overline{G}_1} m[q,Z]$ avec $m \in F^*$ implique $(q,mZ) \stackrel{*}{=} (q',Z')$.

b) $N(q)=L(G_1;[q])$ pour tout $q \in K$: pour tous $m',Z',q'$, $m'Z'q' \in L(G_1,[q])$ ssi il existe une dérivation de la forme $[q] \stackrel{*}{\overline{G}_1} [q_1,Z_1] \stackrel{*}{\overline{G}_1} m'[q',Z'] \stackrel{*}{\overline{G}_1} m'Z'q'$ ssi, compte tenu de a) et des définitions, $(q',m'Z') \stackrel{*}{=} (q_1,Z_1) \stackrel{*}{=} (q,1)$, i.e si et seulement si $m'Z'q' \in N(q)$.

c) $F(q)=L(G_2,[q])$ pour tout $q \in K$: pour tous $m',Z',q',m'Z'q' \in L(G_2,[q])$ ssi il existe dans $G_2$ une dérivation $[q] \stackrel{*}{\overline{G}_2} m'_1[q] \stackrel{*}{\overline{G}_2} m'_1[q_1,Z_1] \stackrel{*}{\overline{G}_1} m'_1 m'_2[q,Z'] \rightarrow m'_1 m'_2 Z'q'$ et $m'=m'_1 m'_2$, $ssi^2(q',m'_1 m'_2 Z') \stackrel{*}{=} (q,m'_1)$, i.e si et seulement si $m'Z'q' \in F(q)$.

**Remarques :** Ces résultats sont valables sans changement pour les automates à mémoire-pile non déterministes.
### 3. Condition suffisante pour qu'un AMPD engendre un langage à compteur déterministe

Les AMPD et les automates finis sont un cas particulier de la notion suivante d'automate :

Un automate est un 5-uplet $a<\Sigma, \bar{K}, \bar{\delta}, \bar{q}^o, \bar{F} > \bar{\delta}$ est une application non partout définie $\bar{K} \times \Sigma \to \bar{K}$ que l'on étend canoniquement en une application $\bar{\delta}^*: \bar{K} \times \Sigma \to \bar{K}$ en posant $\bar{\delta}^*(q, m_a) = \bar{\delta}(\bar{\delta}^*(q, m), a)$. $L(a) \subset \Sigma^*$ est alors l'ensemble des $m \in \Sigma^*$ tels que $\bar{\delta}^*(\bar{q}^o, m) \in \bar{F}$.

La proposition suivante est un critère d'égalité des langages reconnus par deux automates :

**Proposition 1** : Soit $\mathcal{A}$ et $\mathcal{A}'$ deux automates sur le même alphabet $\Sigma$, $\ell$ une injection $\bar{K} \to \bar{K}'$ telle que $\ell(\bar{q}^o) = \bar{q}'^o$, $\ell(\bar{F}) = \bar{F}' \cap \ell(\bar{K})$ et pour tous $a \in \Sigma$ et $q \in \bar{K}$, $\bar{\delta}'(\ell(q), a) = \ell(\bar{\delta}(q, a))$ alors $L(\bar{a}) = L(a)$.

**Démonstration** : Les prolongements canoniques $\bar{\delta}$ et $\bar{\delta}'$ vérifient $\forall q \forall m \bar{\delta}'^*(\ell(q), m) = \ell(\bar{\delta}^*(q, m))$. Donc $\bar{\delta}'^*(\bar{q}'^o, m) = \ell(\bar{\delta}^*(q^o, m))$ et $L(\bar{a}) = L(a)$ puisque $\bar{F}' \cap \ell(\bar{K}) = \ell(\bar{F})$.

Soit alors un AMPD $\mathcal{A} = <\Sigma, K, \Gamma, \delta, q^o, F>$. On peut le considérer comme un automate au sens précédent où $\bar{K} = P^F(\mathcal{A})$, $\bar{q}^o = Z^o q^o$, $\bar{F} = P^F(\mathcal{A}) \cap \{mq/m \in \Gamma^* \text{ et } q \in F\}$ et nous laisserons le lecteur définir précisément $\bar{\delta}$ en fonction de $\delta$. Alors $L(\bar{\mathcal{A}}) = T(\mathcal{A})$. On a un résultat analogue pour $N(\mathcal{A})$.

On en déduit le

**Critère 1** : Soient $\mathcal{A}$ et $\mathcal{A}'$ deux AMPD sur $\Sigma$.

Soit $\ell$ une injection $P(\mathcal{A}) \to \Gamma^* K'$ telle que $\ell(Z^o q^o) = Z^o q^o$, $p$ est une configuration terminale de $\mathcal{O}$ si $\ell(p)$ est une configuration terminale de $\mathcal{A}'$, pour tous $a \in \Sigma \cup \{\epsilon\}$, tout $p \in P(\mathcal{A})$ il existe $p' \in P(\mathcal{A}')$ tel que $a:p|_a p'$ ssi il existe $p'' \in P(\mathcal{A}')$ tel que $a:\ell(p)|_{\ell(p')} p''$ et dans ce cas $\ell(p') = p''$.

Nous allons utiliser ce critère pour démontrer le

**Théorème 1** : Soit un AMPD $\mathcal{A}$ dont le langage de pile $P^F(\mathcal{A})$ (resp. $P^N(\mathcal{A})$) est quasi-périodique. On peut construire un ACD reconnaissant $T(\mathcal{A})$ (resp. $N(\mathcal{A})$).

Nous allons construire un automate à compteur $B=<\Sigma, H, \gamma, h^o, G>$ (voir définition au §2.1) reconnaissant $T(\mathcal{A})$ pour $\mathcal{A} = <\Sigma, K, \Gamma, \delta, q^o, F> \text{ à l'aide d'une application } \ell P^F(\mathcal{A}) \to H \times N \text{ telle que :}$

(α) $\ell$ est injective,

(β) $\ell(Z^o q^o)=(h^o, 0)$,

(γ) si $\ell(mq)=(h, x)$ alors $q \in F$ ssi $h \in G$,

(δ) $\ell$ respecte les fonctions de transition $\delta$ et $\gamma$ des deux automates.

Ceci est suffisant grâce au critère 1.
**Remarque 1 :** La construction est la même pour $P^N(a)$ et $N(a)$ en remplaçant $(\gamma)$ par $(\gamma')$: $\ell(mq)=(h,x)$ et $h \in G$ ssi $(x=0 \text{ et } m=1)$.

Afin de définir $B$ et $\ell$ nous allons faire sur $P(a)$ les hypothèses suivantes : (nous traiterons en même temps les cas $P^F(a)$ et $P^N(a)$).

(i) $P(a) \subset R_0 \cup \bigcup_{i=1}^{l} \alpha_i \beta_i^* \gamma_i = R$, $R_0 = \{\delta_i / r+1 \le i \le r+t\}$,

(ii) $R_0 \subset P(a)$,

(iii) $\forall i \le j \le r$, $\alpha_i \beta_i^* \gamma_i \cap P(a)$ est infini,

(iv) pour $1 \le i < j \le r$ $R_0 \cap \alpha_i \beta_i^* \gamma_i = \emptyset$ et $\alpha_i \beta_i^* \gamma_i \cap \alpha_j \beta_j^* \gamma_j = \emptyset$,

(v) Si pour $a \in \Sigma u\{\epsilon\}$, il existe $x>0$ et $p \in P(a)$ tels que $a : \alpha_i \beta_i^* \gamma_i \rhd_a P$ alors il existe $j \in [1, r]$ et $k \ge -1$ tels que pour tout $x>0$ $a : \alpha_i \beta_i^x \gamma_i \rhd_a \alpha_j \beta_j^{x+k} \gamma_j$

Définissons alors $B=\langle \Sigma, H, \gamma, h^\circ, G \rangle$ et $\ell : R \to H \times N$ en prenant :

1) $H = \{h_i / 1 \le i \le r+t\}$,

2) $\ell(\alpha_i \beta_i^x \gamma_i) = (h_i, x)$ et $\ell(\delta_i) = (h_i, 0)$. Ceci est bien une définition grâce à (iv) et $\ell$ est injective.

3) $h^\circ = h_i$ si $Z^\circ q^\circ = \delta_i$ et $r+1 \le i \le r+t$ ou bien $Z^\circ q^\circ = \alpha_i \gamma_i$ et $1 \le i \le r$. (On peut supposer que l'on ne peut avoir $Z^\circ q^\circ = \alpha_i \beta_i^x \gamma_i$ pour $x \ge 1$).

4) $G = \{h_i / 1 \le i \le r \text{ et } \gamma_i = mq \text{ pour } m \in \Gamma^* \text{ et } q \in F\}$
$$ U \{h_i / r+1 \le i \le r+t \text{ et } \delta_i = mq \text{ pour } m \in \Gamma^* \text{ et } q \in F\} $$

Il est clair que la restriction de $\ell$ à $P(a)$ vérifie les conditions $(\alpha)$ à $(\gamma)$ page 43.

5) Il reste à définir $\gamma$: $Hx(\Sigma u\{\epsilon\})x\{0,1\} \to Hx[-1, +\infty[$

**Cas I :** Pour $a \in \Sigma u\{\epsilon\}$, pour $r+1 \le i \le r+t$ soit $mq \in P(a)$ si elle existe telle que $a : \delta_i \rhd_a mq$. On pose alors $\gamma(h_i, a, 0) = (h_j, k)$ si $(j, k) = \ell(mq)$.

**Cas II :** Pour $a \in \Sigma u\{\epsilon\}$, pour $1 \le i \le r$ soit $mq \in P^F(a)$ si elle existe telle que $a : \delta_i \rhd_a mq$ et $(j,k) = \ell(mq)$. On pose alors $\gamma(h_i, a, 0) = (h_j, k)$.

**Cas III :** Pour $a \in \Sigma u\{\epsilon\}$, pour $1 \le i \le r$ si il existe $x>0$ et $mq \in P(a)$ tels que $a : \alpha_i \beta_i^x \gamma_i \rhd_a mq$, on sait (v) ci-dessus) qu'il existe $(j,k)$ tels que pour tout $x>0$ $a : \alpha_i \beta_i^x \gamma_i \rhd_a \alpha_j \beta_j^{x+k} \gamma_j$. On pose alors $\gamma(h_i, a, 1) = (h_j, k)$.

Vérifions maintenant que $\ell$ respecte $\delta$ et $\gamma$ :
Soit $\alpha \in \Sigma U\{\epsilon\}$, $mq \in P(a)$ et $a : mq \underset{a}{\vdash} m'q'$.

Par construction de $ℓ$, on peut vérifier que dans chacun des trois cas I, II, III $a : ℓ(mq) \underset{B}{\vdash} ℓ(m'q')$. Si il existe $(j, x)$ tel que $a : ℓ(mq) \underset{a}{\vdash} B (j, x)$, il existe $m'q'$ tel que $mq \underset{a}{\vdash} m'q'$ c'est évident dans les cas I et II. Cela résulte de l'hypothèse (v) dans le cas III.

Il ne reste plus qu'à écrire $P(a)$ comme $R_0 \cup \bigcup_{i=1}^r \alpha_i \beta_i^* \gamma_i$ d'une manière qui satisfasse les conditions (i) à (v) de la page 44.

**Définition :** Un triplet $(\alpha, \beta, \gamma) \in X^{*3}, \beta \neq 1$ est dit *maximal* si $\beta$ est primitif, s'il n'existe pas $\beta_1, \beta_0$ tels que $\beta=\beta_0\beta_1$, $\alpha=\alpha'\beta_1$ et si $\beta$ n'est pas un segment initial de $\gamma$. *A tout $(\alpha, \beta, \gamma)$ on peut associer un triplet maximal $(\alpha', \beta', \gamma')$ tel que $\alpha\beta^* \subset \alpha'\beta'^* \gamma'$. Il résulte de la démonstration du lemme 1(§1) qu'un tel triplet est unique si $\beta \neq 1$. (Pour le construire, on remplace $\beta$ par une racine primitive $\beta_1$, puis $\beta_1$ par un conjugué $\beta_2\beta_3$ tel que $\alpha=\alpha'\beta_2(\beta_3\beta_2)^k$ puis on cherche un $\gamma'$ et un $k'$ maximal tel que $\beta_2\gamma=(\beta_2\beta_3)^{k'}\gamma'$).

**Remarque 2 :** Si $((\alpha_i, \beta_i, \gamma_i))_{1 \le i \le r}$ est une suite finie de triplets maximaux, si $(\alpha, \beta, \gamma)$ est maximal et si $\alpha\beta^*\gamma$ rencontre une infinité de fois $\bigcup_{i=1}^r \alpha_i \beta_i^* \gamma_i$ alors il existe $1 \le i \le r$ tel que $\alpha=\alpha_i, \beta=\beta_i$, et $k \neq r$ tel que $\gamma=\beta_i^k \gamma_i$.

Si $P(a)=P_0 \cup \bigcup_{i=1}^r \alpha_i \beta_i^{*,*} \gamma_i$ (où $P_0$ est fini et si $1 \le i \le r \beta_i \neq 1$)

Soit $(\alpha_i, \beta_i, \gamma_i)$ le triplet maximal associé à $(\alpha_i^{,\prime}, \beta_i^{,\prime}, \gamma_i^{,\prime})$. Alors $P(a) \subset P_0 \cup \bigcup_{i=1}^r \alpha_i \beta_i^{*,*} \gamma_i = P_0 \cup \bigcup_{j=1}^r \alpha_j \beta_j^{*,*} \gamma_j$ où pour $j \neq j'$ $(\alpha_j, \beta_j) \neq (\alpha_j^{,\prime}, \beta_j^{,\prime}, \gamma_j^{,\prime})$, et $\Gamma_j = \{\gamma_{ji} / 1 \le i \le r (j)\}$ est un ensemble fini.

Il existe sûrement un entier $h$ possédant les propriétés suivantes :

- si $x \ge h \ge 1$ alors $\alpha_i \beta_i^x \gamma_{ij} \in P_0$ et $\alpha_i \beta_i^* \gamma_{ij} \in \alpha_i \beta_i^* \gamma_{i',j'}$ sauf si $i=i'$ et $j=j'$.

- si $x \ge h$ et $a: \alpha_i \beta_i^x \gamma_{ij} \vdash p \in P(a)$, alors il existe une infinité de $y \in N$ et pour chacun d'eux une configuration $p(y) \in P(a)$ tels que $a: \alpha_i \beta_i^* \gamma_{ij} \vdash p(y)$.
Remarquons alors qu'une transition modifie seulement le facteur
droit $\beta_i \gamma_{ij}$ de $\alpha_i \beta_i^y \gamma_{ij}$. Les $p(y)$ sont donc de la forme $\alpha_i \beta_i^{y-1} \gamma'$
pour un $\gamma' \in \Gamma^*K$. Il résulte de la remarque 2 que pour un certain
$k' \in N$ $\gamma'=\beta_i^{k'} \gamma_{ij}'$. Posons $k=k'-1$. Nous venons de démontrer que
pour tout $x \ge h$ $a: \alpha_i \beta_i^x \gamma_{ij} \vdash \alpha_i \beta_i^{x+k'} \gamma_{ij}'$, et $k \in [-1, +\infty[$.

La preuve est alors terminée : il suffit de prendre $R_1 = \bigsqcup_{i=1}^r (\alpha_i \beta_i^h)^{\beta_i^* \Gamma_i}$ et $R_0 = P(\alpha) - R_1$. Alors $P(\alpha) = R_0 \cup R_1$ satisfait les conditions (i) à (v) énoncées au début.

**Exemple :** Soit $G_0$ la grammaire simple

$$
G_0 = \begin{cases}
S = a & ST + b \\
T = a & + b ST^2
\end{cases}
$$

et $L_0 = L(G_0, S)$.

Soit $a_0 = \langle\{a,b\}, \{S,T\}, \delta, S\rangle$ l'automate simple (i.e à un seul état qu'on ne notera pas, sans $\epsilon$-transitions et s'arrêtant sur pile vide), dont la fonction de transition $\delta$ est définie par :

$\delta (a, S) = TS$

$\delta (b, S) = 1$

$\delta (a, T) = 1$

$\delta (b, T) = T^2 S$

Il est clair que $L_0=N(a_0)$ et que $P^N(a_0)=T^*SUT^*$, $L_0$ est donc un langage à compteur, reconnu par l'automate suivant $B=\langle\{a,b\},\{q^0,q^1,qf\},\gamma, q^0,\{qf\}\rangle$. Plutôt que d'écrire explicitement $\gamma$, nous représenterons par les dessins suivants les structures de $a_0$ et $B$.

<figure><img src="image_4.png" /></figure>
La condition du théorème 1 est suffisante mais non nécessaire comme le montre le contre exemple suivant :

Soit $\Sigma=\{a,b,c\}$ et $L_1=\{wc^{n+1}/w \in \{a,b\}^+ \text{ et } |w|=n\}$. $L_1$ est visiblement un langage à compteur reconnu par l'AMPD suivant :

$$a_1 = <\Sigma, K, \Gamma, \delta, q^0, Z^0> \text{ où}$$

$$K = \{q^0, q^1\},$$

$$\Gamma = \{Z^0, A, B\},$$

$$\delta(q^0, a, Z^0) = (q^1, AZ^0),$$

$$\delta(q^0, b, Z^0) = (q^1, BZ^0),$$

$$\delta(q^1, c, Z^0) = \delta(q^1, c, A) = \delta(q^1, c, B) = (q^1, 1).$$

Il est clair que $N(a_1) = L_1$.

Pour tout $w \in \{a,b\}^+$, w:(q°,Z°)[a(q¹,WZ°) où W est l'image de w par le morphisme $\Psi(a)=A, \Psi(b)=B$. On voit aussi que $P(a_1)=\{Z^0q^0\} \cup \{A,B\}^*\{Z^0q^1,q^1\}$ et ce langage n'est pas quasi-périodique (voir fin du §1).
Il est clair que la pile enregistre de "l'information inutile" qu'un automate à compteur ne pourrait pas enregistrer, bien qu'il reconnaisse le même langage. En généralisant légèrement la notion d'*automate minimal* (i.e deux configurations différentes n'engendrent pas le même langage) on obtient la classe des automates *normaux* (§4) pour lesquels la condition du théorème 1 devient nécessaire.
### 4. Automates Minimaux-Automates Normaux.

Soit $\mathfrak{a}$ un AMPD. Pour tout $mq \in \Gamma^*K$ on note $L(\mathfrak{a}(q,m))$ le langage engendré en prenant $(q,m)$ comme configuration initiale.

Deux *configurations sont équivalentes*, $mq \equiv m'q'$, si $L(\mathfrak{a}(q,m))=L(\mathfrak{a}(q',m'))$.

$\mathfrak{a}$ est *minimal* si pour tout $L \subseteq \Sigma^*$, $L \neq \emptyset$, il existe au plus une configuration $(q,m)$ telle que $L=L(\mathfrak{a}(q,m))$. $\mathfrak{a}$ est *w-normal* si l'ensemble de telles configurations est fini et *normal* s'il est de cardinalité bornée par un entier $K$ ne dépendant que de $\mathfrak{a}$.

**Exemple 1 :** L'automate $a_0$ défini page 23, est *w-normal mais non-normal*: Pour tout $W \in \{A,B\}^*$ les configurations équivalentes à $WZ^\circ q^1$ sont les $W'Z^\circ q^1$ telles que $W' \in \{A,B\}^+$ et $|W|=|W'|$. Il y en a donc $2^{|W|}$ et $a_0$ n'est pas normal. Le même argument montre que $a_0$ est w-normal.

**Exemple 2 :** Le langage $L_1=\{a^n b^m c^2 | m \le n\}$ est un *langage à compteur non w-normal* (i.e qui ne peut être reconnu par un automate w-normal). Soit $\mathfrak{a}$ un AMPD tel que $L_1=L(\mathfrak{a})$ et pour tout $n \ge 1$ soit $p_n$ la configuration telle que $a^n b^n: (q^1, Z^0) \stackrel{*}{\longmapsto} a^n p_n$ et qui n'est suivie d'aucune $\epsilon$-transition. Si $n \ne n'$ alors $p_n \not\equiv p_{n'}$. Il existe donc des $p_n$ de longueur arbitrairement grande. Soit $q_n$ défini par $c:p_n \stackrel{*}{\longmapsto} q_n$. Les $q_n$ sont toutes équivalentes mais de longueur arbitrairement grande puisqu'elles se déduisent des $p_n$ par une seule transition. Elles sont en nombre infini et $\mathfrak{a}$ n'est pas w-normal$^1$.

**Exemple 3 :** De manière analogue, $L_2=\{wc^{n+1} | w \in \{a,b\}^+ \text{ et } n=|w| \} \cup \{\tilde{w} | w \in \{a,b\}^+\}$ est w-normal mais non-normal.

**Proposition 1 :** *Un AMPD $\mathfrak{a}$ s'arrêtant sur pile vide est w-normal ssi pour tout $m_0 \in \Gamma^* l'ensemble des $(q,m,q')$ tels que $m_0 mq \in P(\mathfrak{a})$ et $\epsilon:=(q,m) \stackrel{*}{\longmapsto} (q',1)$ est fini*

*Ce dernier critère est décidable.*

**Démonstration :** *Le critère est nécessaire* : s'il n'est pas satisfait, il existe $q' \in L$ et une infinité de $(q,m)$ tels que $m_0 mq \in P(\mathfrak{a})$, $\epsilon:=(q,m) \stackrel{*}{\longmapsto} (q',1)$. Alors $L(\mathfrak{a}(m_0 q'))=L(\mathfrak{a}(m_0 mq))$ pour tout ces $(q,m)$ et $\mathfrak{a}$ n'est pas w-normal.

*Le critère est suffisant* : Parmi tous les langages $L$ égaux à $L(\mathfrak{a}(mq))$ pour une infinité de $(q,m)$ s'il en existe, choisissons en un, $L_0$, tel que $\tau(L_0)$ soit minimal. Si $\tau(L_0)=0$, il existe une infinité de $(q,m)$ tels que $1 \in L(\mathfrak{a}(mq))$ i.e $\epsilon:=(q,m) \stackrel{*}{\longmapsto} (q',1)$ pour un $q'$ contrairement à l'hypothèse. Si $\tau(L_0) \ge 1$, soit $a \in L_0$ tel que $|a|=\tau(L_0)-1$, $a \in \Sigma$ et $a \in \Sigma^*$. (Pour tout $L \subseteq \Sigma^*$ et $a \in \Sigma$, soit $L|a=\{u \in \Sigma^* | au \in L\}$).
Puisque $\tau(L_0|a) < \tau(L_0)$, l'ensemble des configurations p telles que $L_0|a=L(a(p))$ est fini. Nous les désignerons par $p_1, \dots, p_K$. Soient $p'_1, \dots, p'_K$, les configurations telles que pour un $i \in [1,k]$, $a:p'_i-p_i$. Elles sont bien en nombre fini puisque $p_i$ se déduit de $p'$ par une seule transition. Soit mq telle que $L_0=L(a(q,m))$. Il existe $1 \le i \le k$ tel que $\epsilon: (q,m) \stackrel{*}{\longmapsto} p'_i$. Il existe donc $i$ et une infinité de $(q,m)$ tels que $\epsilon: (q,m) \stackrel{*}{\longmapsto} p'_i=(q',m_0)$. Les $(q,m)$ sont donc de la forme $(q,m_0 m_1)$ et on a contrairement à l'hypothèse une infinité de $(q,m_1,q')$ tels que $\epsilon: (q,m_1) \stackrel{*}{\longmapsto} (q',1)$.

**Le critère est décidable :** L'ensemble $R$ des mq tels que pour un $q'$ $\epsilon: (q,m) \stackrel{*}{\longmapsto} (q',1)$ est un langage régulier dont on peut construire une grammaire avec les techniques du §2. L'ensemble des facteurs droits des mots de $P(a)$ est aussi un langage régulier $H$. Tout revient à décider si $H \cap H$ est fini.

On appelle *pseudo-simple* un automate sans $\epsilon$-transition.

**Corollaire :** Les langages reconnus par arrêt sur pile vide par les automates pseudo-simples et les automates $\omega$-normaux sont les mêmes.

**Démonstration :** Il résulte de la proposition 1 que tout automate pseudo-simple est $\omega$-normal (pour l'arrêt sur pile vide). Réciproquement, si un automate est $\omega$-normal, il existe une borne au nombre maximum $d' \in \mathbb{N}$ -transitions successives intervenant au cours de la reconnaissance d'un mot. Cette borne peut être calculée au moyen de l'algorithme de la proposition 1 et on peut construire un automate pseudo-simple équivalent (Valiant [15] §1.4).

Valiant [15] introduit sous le nom de *non-singulier* les automates s'arrêtant sur pile vide et satisfaisant la condition suivante :
$$ \exists k \in \mathbb{N} \ \forall m; m' \in \Gamma^* \ \forall q, q' \in K \ \text{si } |m| > k \text{ et } L(q', m') \neq \emptyset \text{ alors } (q', m') \neq (q, m') $$

Il est clair, compte tenu de la proposition 1 que tout automate non-singulier est $\omega$-normal. La réciproque est fausse car les langages non-singuliers forment une partie stricte de l'ensemble des langages pseudo-simples [V], i.e des langages $\omega$-normaux.

Le langage $L_2$ défini comme exemple est non-singulier mais ne peut être reconnu par un automate normal. D'autre part, il est facile de construire un automate normal qui n'est pas non-singulier : il suffit que $L(q^1, S^n) = \{a^m / \text{pour } n=2m \text{ ou } n=2m-1\}$ et $L(q^2, S^n) = \{a^n\}$ et on peut s'arranger pour qu'il soit normal.
Alors que l'ω-normalité dépend essentiellement des ε-transitions,
la normalité dépend de l'équivalence des configurations, et de même
que Valiant ne sait sans doute pas décider si un AMPD donné est non-
singulier, nous ne savons pas décider si un AMPD est normal.

**Remarque :** *Tout algorithme décidant la normalité d'un AMPD permettrait de décider l'équivalence de deux AMPD normaux.*

**Démonstration :** Soient $a_0$ et $a_1$ deux AMPD sur un même alphabet d'entrée $\Sigma_0$ tels que $\Gamma_0 \cap \Gamma_1 = \emptyset$ et $K_0 \cap K_1 = \emptyset$. Construisons un AMPD B sur l'alphabet $\Sigma=\Sigma_0 \cup \{a_0, a_1, \emptyset\}$, qui reconnaît le langage $L=\bigcup_{i_1} a_{i_1} a_{i_2} \cdots a_{i_k} \notin L_{i_k} \cdots \notin L_{i_1} \subset \emptyset$ la réunion est prise sur les suites $i_1 \cdots i_k \in \{0,1\}^+$ et où $L_i=L(a_i)$. Nous prendrons comme ensemble d'états $K_0 \cup K_1$ comme alphabet de pile $\Gamma_0 \cup \Gamma_1 \cup \{A_0, A_1\}$. La configuration courante sera $p=A_{i_1} A_{i_2} \cdots A_{i_\ell} \text{mq où } \text{mq} \in P(a_0) \cup P(a_1)$ et $L(B(p))=L(a_i(q,m)) \notin L_{i_1} \cdots \notin L_{i_k}$. Il est clair que si $L_0=L_1, B$ n'est pas normal car la configuration p est équivalente à au moins $2^\ell$ configurations distinctes.

Si $L_0 \neq L_1$ et si $a_0$ et $a_1$ sont normaux (bornes $k_0$ et $k_1$) alors B est normal (borne $k_0 + k_1$). Notre connaissance de la structure des grammaires simples (lère partie) permet de démontrer la :

**Proposition 3** : *Etant donnée une grammaire simple G, on peut construire un automate simple normal reconnaissant L(G).*

**Démonstration :** L'auteur a montré ailleurs [2] que pour toute grammaire simple G, on peut construire une grammaire $G_0(N, \Sigma, \sigma)$ simple, équivalente à G et telle que pour tous m et $m' \in N^*$, $L(G_0,m)=L(G_0,m')$ implique $m=m'$. L'automate simple déterministe $a_0$ canoniquement associé à $G_0$ est normal (rappelons que $a_0=<\Sigma, N, \delta, \sigma>$ dont l'ensemble des états n'a qu'un élément et tel que $\delta(S,a)=m$ ssi $S \to \tilde{a}_m$ est une règle de $G_0$, alors $N(a_0)=L(G_0,\sigma)$ et pour tout $m \in N^*$, $N(a_0(m))=L(G_0,\tilde{m})$ ; la proposition en résulte).

**Conjecture 1** : La proposition 3 est vraie pour les langages LL(k).
5. Configurations équivalentes et configurations conjuguées de deux AMPD équivalents. Application aux langages normaux.

**Définition** : Soient $\mathfrak{a}$ et $\mathfrak{a}'$ deux AMPD, mq et $m'q'$ des configurations de $\mathfrak{a}$ et de $\mathfrak{a}'$ respectivement. Nous dirons qu'elles sont **équivalentes** (bien que ce ne soit pas une relation d'équivalence) si $L(\mathfrak{a}(q,m))=L(\mathfrak{a}'(q',m'))$ et nous noterons cela $\equiv$. Elles sont conjuguées s'il existe $u \in \Sigma^*$ tel que $u: (q^0, Z^0) \stackrel{*}{\to}_{\mathfrak{a}} (q, m)$ et $u: (q'^0, Z'^0) \stackrel{*}{\to}_{\mathfrak{a}} (q', m')$. Cette relation est notée $//$.

**Proposition 1** : Si $\mathfrak{a} \equiv \mathfrak{a}'$, $mq \in P(\mathfrak{a})$ et $mq // m'q'$ alors $m'q' \in P(\mathfrak{a}')$ et $mq \equiv m'q'$. $\equiv$ et $//$ définissent une relation entre les deux langages réguliers $P(\mathfrak{a})$ et $P(\mathfrak{a}')$ (§1) :

**Conjecture 2** : Si $\mathfrak{a} \equiv \mathfrak{a}'$, $\equiv$ et $//$ sont des transductions rationnelles.

Nous l'avons démontré dans les cas suivants :

**Proposition 2** : Si $\mathfrak{a}$ et $\mathfrak{a}'$ sont des automates simples équivalents, $\equiv$ et $//$ sont des transductions rationnelles.

**Proposition 3** : Si $\mathfrak{a}$ est $\omega$-normal, si $\mathfrak{a}'$ est à compteur $//$ est une transduction rationnelle.

**Démonstration de la proposition 2** :

1) grâce à la bijection canonique établie en démontrant la proposition 3 du §4) entre les automates simples et les grammaires simples engendrant le même langage, la relation $m \equiv m'$ sur $\Gamma^*x\Gamma'^*$ n'est autre que la relation $L(G, \tilde{m})=L(G', \tilde{m}')$ Si $\mathfrak{a}''$ est canonique (i.e associé canoniquement à la grammaire canonique de $N(\mathfrak{a}')$) et $\mathfrak{a} \equiv \mathfrak{a}'$, alors $\equiv$ est un homomorphisme $\Gamma^* \to \Gamma'^*$ (voir [2]) est donc une transduction rationnelle. La transduction $\equiv : \Gamma'^* \to \Gamma^*$ est donc rationnelle et il en est de même de leur composée soit $\equiv : \Gamma^* \to \Gamma'^*$. (Voir [9]).

2) Soient $\mathfrak{a}$ et $\mathfrak{a}'$ deux automates simples, $\Gamma$ et $\Gamma'$ leurs alphabets de pile et $L=N(\mathfrak{a})=L(\mathfrak{a}') \subset \Sigma^*$. Nous allons montrer que $//$ est une transduction rationnelle $\Gamma^* \to \Gamma'^*$.
Nous allons utiliser la méthode de [13] pour décider l'équivalence de deux grammaires LL(k) (ou de [1] pour deux schémas récursifs monadiques libres) : on peut construire un AMPD $\mathfrak{a}''$ dont la pile enregistre à la fois les contenus des piles de $\mathfrak{a}$ et $\mathfrak{a}'$ après lecture d'un
même mot $u \in \Sigma^*$. Nous laisserons le lecteur construire de façon détaillée un AMPD $a''=<\Sigma, \Gamma'', K'', \delta'', q''^\circ, Z''^\circ>$ (dont K'' contient un état particulier $q_1^1$) et deux homomorphismes $\Psi_1 : (\Gamma'' \cup K'')^* \to (\Gamma \cup K)^*$ et $\Psi_2 : (\Gamma'' \cup K'')^* \to (\Gamma' \cup K')^*$ tels que

1) $u \in \Sigma^*$ n'est pas facteur gauche d'un mot de L ssi il existe $m_1 \in \Gamma''^+$ tel que $u : (q''^\circ, Z''^\circ) \stackrel{*}{\underset{a''}{\rightleftharpoons}} (q^1, m_1)$,

2) $L=\mathcal{N}(a'')$,

3) si $u : Z^\circ \stackrel{*}{\underset{a}{\rightleftharpoons}} m$ alors il existe $(q', m')$ tel que $u : (q''^\circ, Z''^\circ) \stackrel{*}{\underset{a}{\rightleftharpoons}} (q', m')$ et $\Psi_1(m'q')=m$.

4) condition analogue à 3) pour $a'$ et $\Psi_2$.

Il est clair alors que $m//m'$ si et seulement si il existe $m''q'' \in P(a'')$ telque $\Psi_1(m''q'')=m$, $\Psi_2(m''q'')=m'$. Puisque $P(a'')$ est un langage régulier, $(P(a'), \Psi_1, \Psi_2)$ définit une transduction rationnelle. CQFD.

La démonstration de la proposition 3 est très technique. Nous en démontrerons une forme plus faible suffisante pour les applications que nous avons en vue.

La définition suivante est tirée de Paterson et Valiant [12]
Un automate à compteur $a'$ est dit _semi-canonique_ si, pour tout $q \in K'$
ou bien $\forall x \forall y \in N(q,x) \in P(a')$ et $y \neq x \Rightarrow (q,x) // (q,y)$
ou bien $\forall x \in N \in (q,x) \stackrel{*}{\rightarrow} (q,0)$.

Les configurations $(q,x)$ du deuxième type sont dites *impropres*.
Le langage de pile $P^*(a')$ d'un ACD semi-canonique sera défini comme
$P(a') - \{(q,x)/(q,x) \text{ est impropre et } x \neq 0\}$.

Démonstration de la proposition 3 : Si $a$ isomega-normal est équivalent à $a$'semi-canonique,
// est une transduction rationnelle $P(a) \to P^*(a')$.

Remarquons que $a'$ est normal pour cette notion de langage de pile. Pour
simplifier la démonstration, et sans perte de généralité, nous suppo-
serons que $a$ est un automate simple.

1) Il existe un entier $H$ tel que si $m \in \Gamma^*$, $q' \in K'$, $m // (q', \emptyset)$ alors $|m| < H$.
Cela résulte de ce que $m // (q', 0)$ et $m' // (q', 0)$ impliquent
$L(a, (q', 0)) = L(a, m) = L(a, m')$ et donc $m \equiv m'$, et de ce que $a$ est isomega-normal.
2) Soit $R_0 \subset \Gamma^*(K' \times N)$ l'ensemble (fini car $a'$ est normal) des (m, (q, x)) tels que $m// (q, x)$ et $|m| \le H$. Soit $R_1 = // - R_0$. Si $m// (q, x)$ et $|m| \not\le H$ alors il existe $(m_0 Z'_0, (q'_0, x_0)) \in R_0$ tel que $|m_0 Z'_0| = H$, une suite $(u_i)_{0 \le i \le k}$ d'éléments de $\Sigma^*$ et $(k_i)_{0 \le i \le k}$ d'éléments de Z tels que :

$$
\alpha) \quad u_i : Z'_i \stackrel{*}{\vert} a_i Z'_i \quad \text{pour } 0 \le i \le k,
$$

$$
\beta) u_i : (q'_i, x_i)^* \ni a' (q'_i, x_{i+1}) \text{ et } x_{i+1} = x_i + k_i,
$$

$$
\gamma) \dot{m} = m_0 z_0 \dots z_k z'_{k+1},
$$

$$
\delta) x = x_{k+1} = x_{0+} \sum_{i=0}^{k} k_i,
$$

Il suffit donc de montrer que pour chaque $(m_0 Z'_0, (q'_0, x_0)) \in R_0$, la relation $(m, (q, x)) \in R$ définie par $\exists u \in \Sigma^* u : m_0 Z'_0 \stackrel{*}{\vert} a$, $\dot{m}$ et $u : (q'_0, x_0)^* \stackrel{*}{\vert} a$, $(q, x)$ est une t.r., car R est la réunion d'une relation finie $R_0$ et d'un nombre fini de transductions rationnelles.

3) Soit Z l'ensemble fini des quadruplets $\tilde{3}=(Z'_i, Z_i Z'_i, \dots, Z_i q'_i, q_i) \in \mathbb{Z}^k$
intervenant dans $\alpha$) et $\beta$). A chacun d'eux est associé un $k_i \in \mathbb{Z}$
que l'on notera $\Psi(\tilde{3})$. Il est unique à cause de l'hypothèse sur $a'$
et de ce que $x_i$ n'est pas nul $(m_0 Z_0 \dots Z'_i \equiv (q'_i, x_i) \text{ et } |m_0 Z_0 \dots Z'_i| > H)$
Les séquences $(u_i)_{0 \le i \le k}$ conduisant de $(m_0 Z'_0, (q'_0, x_0)) \text{ à } (m, (q, x))$
sont donc en fait les mots d'un langage régulier $K \subset \mathbb{Z}^*$, local, dont
les transitions acceptables sont les $(Z_1, Z_2 Z_3, q_1, q_2), (Z_4, Z_5 Z_6, q_3, q_4)$
pour lesquelles $Z_3=Z_4$ et $q_2=q_3$. Il est clair d'autre part que
$x-x_0 = \sum_{i=1}^k \Psi(\tilde{3}_i)$.

En ajoutant à Z des symboles supplémentaires représentant le début
et la fin d'une séquence $(u_i)$ on peut définir $\ell : \mathbb{Z}^* \to \Gamma^*$ tel que
$\ell(\tilde{3}_0 \dots \tilde{3}_k) = m$. Si pour tout $\mathfrak{Z} \in \mathfrak{Z}^*$ tel que
$(\mathfrak{Z}, \ell, \Psi)$ définit la transduction rationnelle cherchée. Sinon on
terme la démonstration en utilisant le

**Lemme :**

Soit X un alphabet fini, Ψ une application de X → Z. R est un langage régulier sur X tel que pour tout facteur gauche u = x₁...xₙ d'un mot de R, Ψ(u) = Σn Ψ(xi) ≥ 0. Alors, Ψ est une transduction rationnelle R → N.
**Démonstration** : Il existe un entier $A$ tel que si $uvw \in R$ alors $\Psi(v)>A$. Sinon, soit $v_n$ une suite infinie de facteurs de $R$ tels que $\Psi(v_{n+1})<\Psi(v_n)$. Puisque le monoïde syntaxique de $R$ est fini [14] il existe une sous-suite infinie $v'_n$ et $(u,w)$ tels que $uv'_n \in R$ pour tout $n$. Mais dès que $\Psi(v'_n)<\Psi(u)$ $\Psi(uv'_n)<0$ contrairement à la l'hypothèse. La remarque préliminaire est donc démontrée.

On peut alors construire un g.s.m. [4] qui définit la transduction $\Psi : R \to N$. C'est donc une transduction rationnelle.

**Proposition 4** : *Soit $c'$ un automate à compteur. Il existe un automate semi-canonique équivalent à $a'$.*

**Démonstration** : Soient $M,Z,z$ trois entiers. Désignons par $A(M,Z,z)$ l'ensemble $\{M+z+\lambda Z/\lambda \ge 0\}$.

Le lemme suivant n'est autre que le lemme 5.4 de Valiant [15]

**Lemme** : *Soit $a'$ un automate à compteur. Il existe deux entiers positifs $M$ et $Z$ tels que pour tout $(q,z) \in K' \times [0,z-1]$,*

a) *ou bien* $\forall x \forall y \in A(M,Z,z) (q,x) \equiv (q,y),$

b) *ou bien* $\forall x \forall y \in A(M,Z,z), x \neq y \text{ et } L(q,x) \neq \emptyset \Rightarrow L(q,y) \neq \emptyset.$

Les configurations $(q,M+z+\lambda Z)$ pour $\lambda \ge 0$ et $(q,z)$ vérifiant $\alpha$ sont dites *impropres*.

Ce lemme va nous permettre de montrer l'existence d'un automate semi-canonique équivalent à $a'$. Soient $M$ et $Z$ les entiers associés à $a'$ par le lemme.

1) En introduisant des états nouveaux pour chaque configuration $(q,x)$ où $x \le M$ on peut "diminuer de $M$" chaque configuration. Le nouvel automate à compteur $a'_1$ sera équivalent à $\sigma'$ et tel que $M(a'_1)=0$.

2) On peut d'autre part enregistrer sur le symbole d'état la classe résiduelle modulo $Z$ dans laquelle se trouve la valeur du compteur. L'impropriété d'une configuration ne dépendra donc que de l'état.

3) On peut s'arranger pour que les seules configurations impropres soient $(q,\lambda R)$ (i.e $z(a')=0$), et par des $\epsilon$-transitions, vider la pile d'une configuration impropre.

L'automate $a''$ ainsi construit est semi-canonique et équivalent à $a'$.
**Théorème :** *Pour qu'un AMPD normal reconnaisse un langage déterministe à compteur, il faut et il suffit que son langage de pile soit quasi-périodique.*

**Démonstration :** Nous avons montré au §3, théorème 1 que la condition était suffisante pour tout AMPD. Soit $\mathcal{A}$ un automate normal et $\mathcal{A}'$ un automate à compteur équivalent semi-canonique (proposition 4). Il résulte de la proposition 3 que // est une transduction rationnelle $P^*(\mathcal{A}') \to P(\mathcal{A})$. Elle est d'image bornée car $\gamma//\gamma'$ et $\gamma//\gamma''$ impliquent $\gamma' \equiv \gamma''$ et $\mathcal{A}$ est normal. Soit $\tau$ cette transduction.

Si $P(\mathcal{A}') \subset K' \times N$ alors, pour tout $q' \in K'$, $\tau_{q'}(x) = \tau(q', x)$ est encore une transduction rationnelle bornée et $\tau_{q'}(N)$ est un langage quasi-périodique (§1). Il en est de même de $P(\mathcal{A}) = \bigcup_{q' \in K'} \tau_{q'}(N)$.

**Corollaire :** *On peut décider si un langage normal ou un langage simple donné est un langage à compteur.*

**Démonstration :** Pour tout langage simple, on sait construire un automate normal qui le reconnait (§4). On sait calculer une grammaire régulière engendrant le langage de pile d'un automate (§2) et décider si une telle grammaire engendre un langage quasi-périodique (§1) donc décider si l'automate reconnait un langage à compteur. CQFD.

Les hypothèses du théorème ne peuvent pas être affaiblies comme le montre le contre exemple du §3.

On ne peut pas d'autre part caractériser les images par transductions rationnelles d'image finie des ensembles U.P de $N$: pour tout langage régulier $R \subset \Sigma^*$, la transduction $\tau_N \to \Sigma^*$ définie par $\tau=\{x,w\}/w \in R$ et $x=|w|)$ est une transduction rationnelle d'image finie et $\tau(N)=R$.

L'étude du langage de pile ne permettra donc pas d'étendre à des automates non normaux cet algorithme de décision.
## 6. Application aux Schémas récursifs monadiques et exemples.

Soit S un schéma récursif monadique dont l'ensemble des variables est $\{F_0, \dots, F_m\}$.

Le calcul de $F_0(\xi)$ dans une interprétation donnée I est une suite d'évaluation de termes $m_n(x_n)$ où $x_n \in D^I$ et $m_n \in \{F_0, \dots, F_m\}^*$. Soit P(S), le langage de pile du schéma, l'ensemble de tous les $m_n$ inter- venant dans un calcul fini, pour toutes les interprétations. Il ré- sulte de [3] que $P(S) = P(a)$ où $a$ est l'AMPD qui reconnaît Tr(S). Un schéma est normal si il existe $k \in N$ tel que pour tout $m \in P(S)$, l'en- semble des $m' \in P(S)$ tels que $m \equiv m'$ a de moins k éléments, autrement dit, si l'automate $a$ associé est normal.

Il en résulte avec les résultats rappelés dans l'introduction, le Théorème 1 : (i) *Tout schéma récursif monadique dont le langage de pile est quasi-périodique est traductible en un schéma à 1 compteur.*

(ii) Cette condition est nécessaire pour un schéma récursif monadique normal.

(iii) On peut décider si un schéma récursif monadique est traductible en un schéma à 1 compteur.

**Application :** Il est montré dans [7] que le schéma $F(x) \Leftarrow si p(x) \text{ alors } g(F(F(f(x)))) \text{ sinon } h(x)$ n'est pas traductible en un schéma à 1 compteur. Nous allons démontrer ce résultat en appliquant notre méthode.

Il est clair que $P(S)$ est l'ensemble des mots sur $\{g,F\}$ de la forme $n_1 n_2 \dots n_k m$ $g^1 F^g F^{g_1} \dots F^{g_{n_1}}$ avec $n_i \ge 1$, $m \in \{0,1,2\}$. Puisque $g \neq F, S$ est un schéma normal et le langage de pile n'est pas quasi-périodique (sinon $g^1 F^g F^{g_1} \dots | n_i \ge 1$) le serait contrairement à $1$, contre exemples). Le schéma n'est pas traductible en un schéma à un compteur.

**Exemple :**

$F_0(x) \Leftarrow si p(x) \text{ alors } f(x) \text{ sinon } F_0 F_1 F_1 (g(x))$
$F_1(x) \Leftarrow si p(x) \text{ alors } f(x) \text{ sinon } F_2(g(x))$
$F_2(x) \Leftarrow si p(x) \text{ alors } f(x) \text{ sinon } F_1 F_2(g(x))$

Son langage de pile est $P(F_0) = F_0 F_1^* F_2 \cup F_0 F_1^*$

$F_0$ est équivalent au schéma à un compteur suivant :
<figure><img src="image_5.png" /></figure>
Références :

[1] E. Ashcroft, Z. Manna, A. Pnueli "Decidable Properties of Monadic Functional Schemes" in Theory of Machines and computations (Eds : Kohavi and Paz), New-York 1971,3-17.

[2] B. Courcelle "Grammaires canoniques des Langages Simples", revue de l'Association pour l'Informatique et la Recherche Opérationnelle, 1974, n°1.

[3] G. Cousineau, J.M. Rifflet "Schémas de Programme : Problèmes d'Equivalence et Complexité", Thèse de 3ème cycle, Paris 1974.

[4] S. Ginsburg et S. Greibach "Mappings which preserve Context sensitive Languages". Inf et Cont. 9 (1966) pp 563-582.

[5] I. Guessarian "Sur une réduction des schémas de programmes polya-diques à des schémas monadiques et ses applications". Mémoire n°5 du groupe d'Informatique Théorique de l'Université Paris VII 1973.

[6] J. Hopcroft et J. Ullmann "Formal languages and these relation to automata". Addison-Wesley 1969.

[7] D. Luckham et S. Garland. "Program Schemes, recursion schemes and formal languages". J.C.S.S. Vol 7 pp 119-160 (1973).

[8] D. Luckham, D. Park, M. Paterson. "On Formalized Computer Programs". J.C.S.S. Vol 4, pp 220-249.

[9] M. Nivat. "Transductions des langages de Chomsky". Annales de l'Institut Fourier, Grenoble 1968.
[10] R. Parikh. "On context-free languages". JACM 13-4 pp 570-581.

[11] D. Plaisted. "Flowchart Schemata with counters" 1972.
4th ACM Symposium pp 44-51.

[12] M. Paterson et L. Valiant. "Deterministic One-Counter Automata".
Lecture Notes in Computer Science Vol 2 (1973)
Springer Verlag.

[13] D. Rosenkrantz et R. Stearns. "Properties of Deterministic
Top-Down grammars". Inf. et Contr. 17 p 226-256 (1970).

[14] M.P. Schützenberger. "Quelques problèmes combinatoires de la
Théorie des automates". Institut de Programmation.
Paris 1967.

[15] L. Valiant. "Decision Procedures for Families of DPDA". Report n°7,
Computer Centre (1973) Warwick University
Table des matières.

Introduction page 1

1. Langages Réguliers Quasi-périodiques. page 8

2. Langages de Pile des Automates page 14

3. Condition suffisante pour qu'un AMPD engendre un langage à compteur déterministe. page 19

4. Automates Minimaux-Automates Normaux. page 24

5. Configurations équivalentes et configurations con- juguées de deux AMPD équivalents. Application aux langages normaux. page 27

6. Application aux Schémas récursifs monadiques et exemples. page 31

Références. page 33