Lemme d'échange

Modèle:Confusion En informatique théorique, le lemme d'échange, en anglais Modèle:Citation étrangère est un résultat de théorie des langages utilisé principalement pour démontrer que certains langages ne sont pas algébriques. Il est nommé interchange lemma par ses auteurs William F. Ogden, Rockford J. Ross et Karl Winklmann, des informaticiens théoriciens qui l’ont publié en 1985^[1].

Le lemme d'échange fait partie de la famille des propriétés nécessaires d'un langage algébrique. Contrairement aux lemmes d'itérations pour les langages algébriques comme le lemme de Bar-Hillel, Perles et Shamir, le lemme d'itération d'Ogden ou le lemme d'itération de Bader et Moura, le lemme d'échange montre que, dans certaines conditions, des groupes entiers de mots d'un langage algébrique peuvent être modifiés en échangeant des facteurs particuliers. Ainsi, le lemme d’échange impose une contrainte d’une autre nature aux langages algébriques : à la place d’une itération, la propriété qu’un langage algébrique doit satisfaire concerne la possibilité d’échanger des facteurs de mots dans certaines positions sans sortir du langage. Un aspect intéressant de ce lemme est qu’il est valable pour des langages qui ont « beaucoup » des mots, des langages qui justement se soustraient aux lemmes d’itération usuels^[2].

Le lemme d'échange a notamment été utilisé — par ses inventeurs — pour démontrer que le langage complémentaire du langage des mots sans carré n'est pas algébrique. Une variante plus forte a été décrite pour démontrer, mais sans succès, que le langage des mots primitifs n'est pas algébrique.

Le lemme d'échange, comme les autres lemmes, formule une condition nécessaire, mais pas suffisante, pour l'algébricité d'un langage^[3].

Description formelle

Un ensemble $R$ de mots de longueur $n$ d'un langage $L$ est un ensemble d’échange pour $L$ s’il existe des entiers $p, q$ tels que pour tous mots

u_{1} v_{1} w_{1}, u_{2} v_{2} w_{2} \in R

avec $| u_{1} | = | u_{2} | = p, | v_{1} | = | v_{2} | = q$ , on a

u_{1} v_{2} w_{1}, u_{2} v_{1} w_{2} \in L

.

L’entier $q$ est la largeur de $R$ . L’énoncé est le suivant^[2] :

Modèle:Théorème

Pour que l’ensemble d’échange ne soit pas vide, $Q$ doit avoir plus de $C n^{2}$ éléments ; en pratique, cela signifie que le nombre de mots de $L$ doit croitre au moins comme $n^{2}$ .

Une variante de ce lemme est appelée Modèle:Citation étrangère par Dömösi et Ito^[4]. Elle apporte une amélioration sur la constante $C n^{2}$ . En revanche, la contrainte sur la largeur n'y figure plus. Avec les notations ci-dessus, elle s'énonce comme suit :

Modèle:Théorème

Exemple d'application

L'exemple d'application qui suit est historiquement le premier ; c'est lui qui a motivé les auteurs, et c'est lui aussi qui a longtemps résisté aux tentatives d'appliquer des résultats plus classiques : Modèle:Théorème Autant il est évident que l’ensemble des mots sans carrés n'est pas algébrique, puisque l'itération d'un facteur produit des puissances arbitrairement grandes, autant ceci n'apporte pas d'information concernant le même énoncé sur le complémentaire du langage.

La démonstration ci-dessous^[2]Modèle:,^[5] est en deux parties : la première explique comment se contenter d'un alphabet à 6 lettres, et la deuxième, plus longue, utilise le lemme d'échange.

Modèle:Démonstration/début On sait qu'il existe une infinité de mots sans carré sur un alphabet à 3 lettres. Pour démontrer que l'ensemble $L_{3}$ des mots sur 3 lettres contenant un carré n'est pas algébrique, on montre, dans la deuxième partie ci-dessous, que l'ensemble des mots $L_{6}$ sur 6 lettres contenant un carré n'est pas algébrique. Pour conclure, on utilise un morphisme sans carré (c'est-à-dire un morphisme qui préserve les mots sans carré) d'un alphabet à 3 lettres sur un alphabet à 6 lettres. Un tel morphisme envoie l'ensemble $L_{3}$ sur l'ensemble $L_{6}$ . Si l'ensemble $L_{3}$ était algébrique, il en serait de même de $L_{6}$ puisqu'un morphisme préserve le caractère algébrique des langages. Modèle:Démonstration/fin

Modèle:Démonstration/début On démontre que l’ensemble des mots

L = L_{6} = {x w w y ∣ x, w, y \in A^{*}}

contenant un carré sur un alphabet à 6 lettres $A = {#, 0, 1, a, b, c}$ n’est pas algébrique. Pour cela, on choisit un entier $N$ assez grand et on considère un mot sans carré fixe de longueur $N$ , soit

v = c_{1} c_{2} \dots c_{N}

sur l’alphabet $B = {a, b, c}$ , avec $c_{i} \in B$ . On considère l’ensemble

Q = {# t # t ∣ t = d_{0} c_{1} d_{1} c_{2} \dots c_{N} d_{N}, d_{i} \in {0, 1}}

.

Chaque mot de $Q$ est un carré, et ne contient aucun autre carré. On pose $M = N + 1$ . Un mot de $Q$ est de longueur $4 M$ , et il y a $2^{M}$ mots dans $Q$ .

On applique le lemme d’échange pour les paramètres $n = 4 M$ et $m = n / 2 = 2 M$ . Il existe un ensemble d’échange $R \subset Q$ de taille

| R | \geq \frac{| Q |}{C n^{2}} = \frac{2^{M}}{16 C M^{2}}

où $C$ est une constante. De plus, la largeur $q$ de $R$ vérifie $M < q \leq 2 M$ .

On considère des mots

u_{1} v_{1} w_{1}, u_{2} v_{2} w_{2} \in R

avec $| u_{1} | = | u_{2} |, | v_{1} | = | v_{2} | = q$ , et on a donc $u_{1} v_{2} w_{1} \in L$ . Les facteurs centraux $v_{1}$ et $v_{2}$ ont les mêmes lettres dans $B$ aux mêmes positions. Mais comme le mot $v$ est sans carré, les deux mots $u_{1} v_{1} w_{1}$ et $u_{1} v_{2} w_{1}$ contiennent tous deux un carré seulement si $v_{1} = v_{2}$ . Ceci montre que si $u_{1} v_{1} w_{1}$ et $u_{2} v_{2} w_{2}$ s’échangent, alors $v_{1} = v_{2}$ . Il en résulte que le nombre d’éléments de $R$ est majoré par

| R | \leq 2^{M - (1 + q / 2)} \leq 2^{M / 2}

puisque $| v_{1} | = q \geq M$ . Mais alors l’encadrement de $| R]$ devient

\frac{2^{M}}{16 C M^{2}} \leq | R | \leq 2^{M / 2}

ce qui est une inégalité impossible si $M = N + 1$ est assez grand. Modèle:Démonstration/fin

D'autres exemples d'application, très proches, sont donnés en exercices dans le livre de Shallit : Les langages suivants ne sont pas algébriques : (a) le langage des mots contenant un chevauchement ; (b) le langage des mots contenant un cube ; (c) le langage des mots contenant un carré abélien (un carré abélien est un mot de la forme xy, où y est une anagramme de x).

D'autres exemples sont donnés par Joaquim Gabarró^[6], et par Michael Main^[7]. Une étude comparative est faite par Boonyavatana et Slutzki^[8]

Notes

Modèle:Références

Références

Modèle:Article
Modèle:Chapitre
Modèle:Ouvrage — Section 4.5: The interchange lamma
Modèle:Ouvrage

Articles liés

Modèle:Portail

↑ Modèle:Harvsp.
↑ ^2,0 ^2,1 et ^2,2 Modèle:Harvsp.
↑ Par exemple Modèle:Article donne un certain nombre d'exemples.
↑ Modèle:Harvsp.
↑ Modèle:Harvsp.
↑ Modèle:Article.
↑ Modèle:Article.
↑ Modèle:Article.

[OgdenRoss1985-1] Modèle:Harvsp.

[BB-2] 2,0 ^2,1 et ^2,2 Modèle:Harvsp.

[3] Par exemple Modèle:Article donne un certain nombre d'exemples.

[4] Modèle:Harvsp.

[5] Modèle:Harvsp.

[6] Modèle:Article.

[7] Modèle:Article.

[8] Modèle:Article.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Lemme d'échange

Sommaire

Description formelle

Exemple d'application

Notes

Références

Articles liés

Menu de navigation

Lemme d'échange

Description formelle

Exemple d'application

Notes

Références

Articles liés

Menu de navigation

Rechercher