Metraipolis › archive › dc_2ca344fe0d78
Lemme d'échange — Wikipedia (fr)
- Source
- Wikipedia (fr)
- Original
- https://fr.wikipedia.org/wiki/Lemme_d%27%C3%A9change
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-11-10T03:37:34.825Z
- SHA-256 of the archived text
3e53cb4edab1ab67d7a324f4356298fdee2e7e61d8f7fdc3ee6aa74592223211- Stable URL of this page
https://metraipolis.com/documento/dc_2ca344fe0d78
How to cite
Lemme d'échange — Wikipedia (fr) — Wikipedia (fr), https://fr.wikipedia.org/wiki/Lemme_d%27%C3%A9change (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_2ca344fe0d78 (Metraipolis archive dc_2ca344fe0d78, sha256 3e53cb4edab1ab67d7a324f4356298fdee2e7e61d8f7fdc3ee6aa74592223211)
BibTeX
@misc{dc2ca344fe0d78,
title = {Lemme d'échange — Wikipedia (fr)},
howpublished = {Wikipedia (fr)},
url = {https://fr.wikipedia.org/wiki/Lemme_d%27%C3%A9change},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_2ca344fe0d78; sha256 3e53cb4edab1ab67d7a324f4356298fdee2e7e61d8f7fdc3ee6aa74592223211},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (fr), https://fr.wikipedia.org/wiki/Lemme_d%27%C3%A9change. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in francese, in ordine alfabetico). Fonte: Wikipedia in francese, voce «Lemme d'échange» — https://fr.wikipedia.org/wiki/Lemme_d%27%C3%A9change Wikidata Q30753970 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q30753970 Autori: i contributori di Wikipedia (cronologia: https://fr.wikipedia.org/wiki/Lemme_d%27%C3%A9change?action=history). Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza. Estratto dell'introduzione non modificato nel contenuto; revisione 225797527, consultata il 2026-11-10T03:34:27.670Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 64fba8762ab7b987c63471787fd1ef8684c3f70d9dda33f487075f32bebf3699