| Property |
Value |
| dbo:abstract
|
- 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. (fr)
- 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. (fr)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 10889 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:année
|
- 1985 (xsd:integer)
- 1990 (xsd:integer)
- 2009 (xsd:integer)
- 2014 (xsd:integer)
|
| prop-fr:auteur
|
- Jeffrey Shallit (fr)
- Jean Berstel (fr)
- Masami Ito (fr)
- Luc Boasson (fr)
- Pál Dömösi (fr)
- Jeffrey Shallit (fr)
- Jean Berstel (fr)
- Masami Ito (fr)
- Luc Boasson (fr)
- Pál Dömösi (fr)
|
| prop-fr:auteursOuvrage
|
- G. Rozenberg, A. Salomaa (fr)
- G. Rozenberg, A. Salomaa (fr)
|
| prop-fr:doi
| |
| prop-fr:isbn
|
- 0 (xsd:integer)
- 978 (xsd:integer)
|
| prop-fr:issn
| |
| prop-fr:journal
|
- SIAM Journal on Computing (fr)
- SIAM Journal on Computing (fr)
|
| prop-fr:langue
| |
| prop-fr:nom
|
- Ross (fr)
- Ogden (fr)
- Lemme d'échange (fr)
- Lemme d'échange fort (fr)
- Winklmann (fr)
- Ross (fr)
- Ogden (fr)
- Lemme d'échange (fr)
- Lemme d'échange fort (fr)
- Winklmann (fr)
|
| prop-fr:numéro
| |
| prop-fr:pages
| |
| prop-fr:pagesTotales
|
- 240 (xsd:integer)
- 520 (xsd:integer)
|
| prop-fr:passage
| |
| prop-fr:prénom
|
- William F. (fr)
- Karl (fr)
- Rockford J. (fr)
- William F. (fr)
- Karl (fr)
- Rockford J. (fr)
|
| prop-fr:présentationEnLigne
| |
| prop-fr:titre
|
- A Second Course in Formal Languages and Automata Theory (fr)
- An “Interchange Lemma” for Context-Free Languages (fr)
- Context-free languages and primitive words (fr)
- A Second Course in Formal Languages and Automata Theory (fr)
- An “Interchange Lemma” for Context-Free Languages (fr)
- Context-free languages and primitive words (fr)
|
| prop-fr:titreChapitre
|
- Context-Free Languages (fr)
- Context-Free Languages (fr)
|
| prop-fr:titreOuvrage
|
- Handbook of Theoretical Computer Science (fr)
- Handbook of Theoretical Computer Science (fr)
|
| prop-fr:titreVolume
|
- Formal Models and Sematics (fr)
- Formal Models and Sematics (fr)
|
| prop-fr:volume
| |
| prop-fr:wikiPageUsesTemplate
| |
| prop-fr:éditeur
| |
| prop-fr:énoncé
|
- 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 . (fr)
- 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 . (fr)
- 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 . (fr)
- 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 . (fr)
|
| dct:subject
| |
| rdfs:comment
|
- 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, comme les autres lemmes, formule une condition nécessaire, mais pas suffisante, pour l'algébricité d'un langage. (fr)
- 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, comme les autres lemmes, formule une condition nécessaire, mais pas suffisante, pour l'algébricité d'un langage. (fr)
|
| rdfs:label
|
- Lemme d'échange (fr)
- Lemme d'échange (fr)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
