| dbo:abstract
|
- In mathematics, Higman's lemma states that the set of finite sequences over a finite alphabet, as partially ordered by the subsequence relation, is well-quasi-ordered. That is, if is an infinite sequence of words over some fixed finite alphabet, then there exist indices such that can be obtained from by deleting some (possibly none) symbols. More generally this remains true when the alphabet is not necessarily finite, but is itself well-quasi-ordered, and the subsequence relation allows the replacement of symbols by earlier symbols in the well-quasi-ordering of labels. This is a special case of the later Kruskal's tree theorem. It is named after Graham Higman, who published it in 1952. (en)
- En mathématiques, le lemme de Higman est un résultat de la théorie des ordres qui affirme que, pour un ensemble muni d'un bel ordre, l'ensemble des mots finis sur muni de l'ordre sous-mot est également un bel ordre. C'est un cas particulier du théorème de Kruskal sur les arbres, qui se généralise à son tour en le théorème de Robertson-Seymour sur les graphes. Ce lemme est dû à Graham Higman, qui l'a publié en 1952. (fr)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 1718 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- In mathematics, Higman's lemma states that the set of finite sequences over a finite alphabet, as partially ordered by the subsequence relation, is well-quasi-ordered. That is, if is an infinite sequence of words over some fixed finite alphabet, then there exist indices such that can be obtained from by deleting some (possibly none) symbols. More generally this remains true when the alphabet is not necessarily finite, but is itself well-quasi-ordered, and the subsequence relation allows the replacement of symbols by earlier symbols in the well-quasi-ordering of labels. This is a special case of the later Kruskal's tree theorem. It is named after Graham Higman, who published it in 1952. (en)
- En mathématiques, le lemme de Higman est un résultat de la théorie des ordres qui affirme que, pour un ensemble muni d'un bel ordre, l'ensemble des mots finis sur muni de l'ordre sous-mot est également un bel ordre. C'est un cas particulier du théorème de Kruskal sur les arbres, qui se généralise à son tour en le théorème de Robertson-Seymour sur les graphes. Ce lemme est dû à Graham Higman, qui l'a publié en 1952. (fr)
|
| rdfs:label
|
- Higman's lemma (en)
- Lemme de Higman (fr)
|
| owl:differentFrom
| |
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
