| Property |
Value |
| dbo:abstract
|
- En informatique théorique, le lemme d'Ogden est un résultat de théorie des langages analogue au lemme de l'étoile. On l'utilise principalement pour démontrer que certains langages ne sont pas algébriques. Il est nommé ainsi d'après William F. Ogden, un informaticien théoricien américain qui l’a publié en 1968. Le lemme d'Ogden est une version plus élaborée du lemme d'itération pour les langages algébriques, aussi connu sous le nom de lemme de Bar-Hillel, Perles et Shamir. Il existe des langages qui satisfont le lemme d'Ogden mais qui ne sont pas algébriques. Ce lemme donne une condition nécessaire pour les langages algébriques, mais pas une condition suffisante. Il est très utile, dans sa version grammaticale, pour prouver que certains langages sont inhéremment ambigus. (fr)
- En informatique théorique, le lemme d'Ogden est un résultat de théorie des langages analogue au lemme de l'étoile. On l'utilise principalement pour démontrer que certains langages ne sont pas algébriques. Il est nommé ainsi d'après William F. Ogden, un informaticien théoricien américain qui l’a publié en 1968. Le lemme d'Ogden est une version plus élaborée du lemme d'itération pour les langages algébriques, aussi connu sous le nom de lemme de Bar-Hillel, Perles et Shamir. Il existe des langages qui satisfont le lemme d'Ogden mais qui ne sont pas algébriques. Ce lemme donne une condition nécessaire pour les langages algébriques, mais pas une condition suffisante. Il est très utile, dans sa version grammaticale, pour prouver que certains langages sont inhéremment ambigus. (fr)
|
| dbo:thumbnail
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 13202 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:année
|
- 1968 (xsd:integer)
- 2004 (xsd:integer)
|
| prop-fr:contenu
|
- Si , il n'y a pas de nœud spécial ; il n'y a qu'une seule feuille distinguée, car s'il y en avait deux, leur ancêtre commun serait spécial.
Supposons donc , et soit un nœud spécial dont aucun descendant n’est spécial ; chacun des sous-arbres de contient au plus une feuille distinguée, et comme a au plus enfants, l'arbre de racine contient au plus feuilles distinguées. On remplace maintenant chaque sous-arbre de cette nature une simple feuille distinguée. Le nombre de nœuds spéciaux diminue de 1 sur chaque branche. L'arbre obtenu a, par récurrence, au plus feuilles distinguées. Comme chacune des nouvelles feuilles a remplacé un sous-arbre avec au plus feuilles, ceci prouve le résultat. (fr)
- Si , il n'y a pas de nœud spécial ; il n'y a qu'une seule feuille distinguée, car s'il y en avait deux, leur ancêtre commun serait spécial.
Supposons donc , et soit un nœud spécial dont aucun descendant n’est spécial ; chacun des sous-arbres de contient au plus une feuille distinguée, et comme a au plus enfants, l'arbre de racine contient au plus feuilles distinguées. On remplace maintenant chaque sous-arbre de cette nature une simple feuille distinguée. Le nombre de nœuds spéciaux diminue de 1 sur chaque branche. L'arbre obtenu a, par récurrence, au plus feuilles distinguées. Comme chacune des nouvelles feuilles a remplacé un sous-arbre avec au plus feuilles, ceci prouve le résultat. (fr)
|
| prop-fr:doi
| |
| prop-fr:déroulante
| |
| prop-fr:langue
|
- english (fr)
- english (fr)
|
| prop-fr:nom
|
- Ogden (fr)
- Lemme (fr)
- Kracht (fr)
- Ogden (fr)
- Lemme (fr)
- Kracht (fr)
|
| prop-fr:numéro
| |
| prop-fr:pages
| |
| prop-fr:prénom
|
- Marcus (fr)
- William F. (fr)
- Marcus (fr)
- William F. (fr)
|
| prop-fr:périodique
|
- Mathematical Systems Theory (fr)
- University of Pennsylvania Working Papers in Linguistics (fr)
- Mathematical Systems Theory (fr)
- University of Pennsylvania Working Papers in Linguistics (fr)
|
| prop-fr:titre
|
- A Helpful Result for Proving Inherent Ambiguity (fr)
- Too Many Languages Satisfy Ogden’s Lemma (fr)
- A Helpful Result for Proving Inherent Ambiguity (fr)
- Too Many Languages Satisfy Ogden’s Lemma (fr)
|
| prop-fr:volume
|
- 2 (xsd:integer)
- 10 (xsd:integer)
|
| prop-fr:wikiPageUsesTemplate
| |
| prop-fr:énoncé
|
- Soit un arbre de degré avec feuilles distinguées. Si chaque branche contient au plus nœuds spéciaux, alors . (fr)
- Soit un arbre de degré avec feuilles distinguées. Si chaque branche contient au plus nœuds spéciaux, alors . (fr)
|
| dct:subject
| |
| rdfs:comment
|
- En informatique théorique, le lemme d'Ogden est un résultat de théorie des langages analogue au lemme de l'étoile. On l'utilise principalement pour démontrer que certains langages ne sont pas algébriques. Il est nommé ainsi d'après William F. Ogden, un informaticien théoricien américain qui l’a publié en 1968. Le lemme d'Ogden est une version plus élaborée du lemme d'itération pour les langages algébriques, aussi connu sous le nom de lemme de Bar-Hillel, Perles et Shamir. (fr)
- En informatique théorique, le lemme d'Ogden est un résultat de théorie des langages analogue au lemme de l'étoile. On l'utilise principalement pour démontrer que certains langages ne sont pas algébriques. Il est nommé ainsi d'après William F. Ogden, un informaticien théoricien américain qui l’a publié en 1968. Le lemme d'Ogden est une version plus élaborée du lemme d'itération pour les langages algébriques, aussi connu sous le nom de lemme de Bar-Hillel, Perles et Shamir. (fr)
|
| rdfs:label
|
- Lema de Ogden (pt)
- Lemat Ogdena (pl)
- Lemma di Ogden (it)
- Lemme d'Ogden (fr)
- Ogdens Lemma (de)
- Лемма Огдена (ru)
- オグデンの補題 (ja)
- Lema de Ogden (pt)
- Lemat Ogdena (pl)
- Lemma di Ogden (it)
- Lemme d'Ogden (fr)
- Ogdens Lemma (de)
- Лемма Огдена (ru)
- オグデンの補題 (ja)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
