Lemme d'échange

En informatique théorique, le lemme d'échange, en anglais « interchange lemma » 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.

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.

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.

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 :

Lemme d'échange — Soit $L$ un langage algébrique. Il existe un nombre $C$ tel que, pour tous entiers $n\geq m\geq 2$ et pour tout ensemble $Q\subseteq L$ de mots de longueur $n$ de $L$, il existe un ensemble d’échange $R\subset Q$ pour $L$ de taille $|R|\geq |Q|/{Cn^{2}}$ et de largeur $q$ comprise entre $m/2$ et $m$.

Pour que l’ensemble d’échange ne soit pas vide, $Q$ doit avoir plus de $Cn^{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 « strong interchange lemma » par Dömösi et Ito. Elle apporte une amélioration sur la constante $Cn^{2}$. En revanche, la contrainte sur la largeur n'y figure plus. Avec les notations ci-dessus, elle s'énonce comme suit :

Lemme d'échange fort — Soit $L$ un langage algébrique. Il existe un nombre $C$ tel que, pour tout entier $n\geq 2$ et pour tout ensemble $Q\subseteq L$ de mots de longueur $n$ de $L$, il existe un ensemble d’échange $R\subset Q$ pour $L$ de taille $|R|\geq |Q|/{Cn}$.

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 :

Propriété — Le langage des mots sur 3 lettres ou plus qui contiennent un carré en facteur n'est pas algébrique.

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 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.

Démonstration (première partie)

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.

Démonstration (deuxième partie)

On démontre que l’ensemble des mots

$L=L_{6}=\{xwwy\mid 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}\cdots c_{N}$

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

$Q=\{\#t\#t\mid t=d_{0}c_{1}d_{1}c_{2}\cdots 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 $4M$, et il y a $2^{M}$ mots dans $Q$.

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

$|R|\geq {\frac {|Q|}{Cn^{2}}}={\frac {2^{M}}{16CM^{2}}}$

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

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}}{16CM^{2}}}\leq |R|\leq 2^{M/2}$

ce qui est une inégalité impossible si $M=N+1$ est assez grand.

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ó, et par Michael Main. Une étude comparative est faite par Boonyavatana et Slutzki

Références

• (en) William F. Ogden, Rockford J. Ross et Karl Winklmann, « An “Interchange Lemma” for Context-Free Languages », SIAM Journal on Computing, vol. 14, n^o 2,‎ 1985, p. 410–415 (ISSN 0097-5397, DOI 10.1137/0214031)
• Jean Berstel et Luc Boasson, « Context-Free Languages », dans G. Rozenberg, A. Salomaa (éditeurs), Handbook of Theoretical Computer Science, vol. B : Formal Models and Sematics, Elsevier et MIT Press, 1990 (ISBN 0-444-88074-7), p. 59-102
• (en) Jeffrey Shallit, A Second Course in Formal Languages and Automata Theory, Cambridge University Press, 2009, 240 p. (ISBN 978-0-521-86572-2) — Section 4.5: The interchange lamma
• Pál Dömösi et Masami Ito, Context-free languages and primitive words, World Scientific Publishing, 2014, 520 p. (ISBN 978-981-4271-66-0, présentation en ligne)

Articles liés

• Lemme d'itération
• Langage algébrique
• Mot sans carré