Lemme d'échange

Un article de Wikipédia, l'encyclopédie libre.

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[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[modifier | modifier le code]

Un ensemble de mots de longueur d'un langage est un ensemble d’échange pour s’il existe des entiers tels que pour tous mots

avec , on a

.

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

Lemme d'échange — Soit un langage algébrique. Il existe un nombre tel que, pour tous entiers et pour tout ensemble de mots de longueur de , il existe un ensemble d’échange pour de taille et de largeur comprise entre et .

Pour que l’ensemble d’échange ne soit pas vide, doit avoir plus de éléments ; en pratique, cela signifie que le nombre de mots de doit croitre au moins comme .

Une variante de ce lemme est appelée « strong interchange lemma » par Dömösi et Ito[4]. Elle apporte une amélioration sur la constante . 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 un langage algébrique. Il existe un nombre tel que, pour tout entier et pour tout ensemble de mots de longueur de , il existe un ensemble d’échange pour de taille .

Exemple d'application[modifier | modifier le code]

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[1].

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],[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.

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[modifier | modifier le code]

  1. a et b Ogden, Ross et Winklmann 19685.
  2. a b et c Berstel et Boasson 1990.
  3. Par exemple Victor Mitrana, « On languages satisfying "interchange lemma" », Informatique théorique et applications, t. 27, no 1,‎ , p. 71-79 (lire en ligne) donne un certain nombre d'exemples.
  4. Dömösi et Ito 2014.
  5. Shallit 2009.
  6. Joaquim Gabarró, « Some applications of the interchange lemma », Bull. Eur. Assoc. Theor. Comput. Sci., no 25,‎ , p. 19–21.
  7. Michael G. Main, « Permutations are not context-free: An application of the interchange lemma », Inf. Process. Lett., vol. 15,‎ , p. 68–71.
  8. R. Boonyavatana et Giora Slutzki, « The interchange or pump (di)lemmas for context-free languages », Theo. Comput. Sci., vol. 56,‎ , p. 321–338.

Références[modifier | modifier le code]

  • (en) William F. Ogden, Rockford J. Ross et Karl Winklmann, « An “Interchange Lemma” for Context-Free Languages », SIAM Journal on Computing, vol. 14, no 2,‎ , 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, (ISBN 0-444-88074-7), p. 59-102
  • (en) Jeffrey Shallit, A Second Course in Formal Languages and Automata Theory, Cambridge University Press, , 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, , 520 p. (ISBN 978-981-4271-66-0, présentation en ligne)

Articles liés[modifier | modifier le code]