Hall word (original) (raw)
In mathematics, in the areas of group theory and combinatorics, Hall words provide a unique monoid factorisation of the free monoid. They are also totally ordered, and thus provide a total order on the monoid. This is analogous to the better-known case of Lyndon words; in fact, the Lyndon words are a special case, and almost all properties possessed by Lyndon words carry over to Hall words. Hall words are in one-to-one correspondence with Hall trees. These are binary trees; taken together, they form the Hall set. This set is a particular totally ordered subset of a free non-associative algebra, that is, a free magma. In this form, the Hall trees provide a basis for free Lie algebras, and can be used to perform the commutations required by the Poincaré–Birkhoff–Witt theorem used in the cons
| Property | Value |
|---|---|
| dbo:abstract | In mathematics, in the areas of group theory and combinatorics, Hall words provide a unique monoid factorisation of the free monoid. They are also totally ordered, and thus provide a total order on the monoid. This is analogous to the better-known case of Lyndon words; in fact, the Lyndon words are a special case, and almost all properties possessed by Lyndon words carry over to Hall words. Hall words are in one-to-one correspondence with Hall trees. These are binary trees; taken together, they form the Hall set. This set is a particular totally ordered subset of a free non-associative algebra, that is, a free magma. In this form, the Hall trees provide a basis for free Lie algebras, and can be used to perform the commutations required by the Poincaré–Birkhoff–Witt theorem used in the construction of a universal enveloping algebra. As such, this generalizes the same process when done with the Lyndon words. Hall trees can also be used to give a total order to the elements of a group, via the commutator collecting process, which is a special case of the general construction given below. It can be shown that Lazard sets coincide with Hall sets. The historical development runs in reverse order from the above description. The commutator collecting process was described first, in 1934, by Philip Hall and explored in 1937 by Wilhelm Magnus. Hall sets were introduced by Marshall Hall based on work of Philip Hall on groups. Subsequently, Wilhelm Magnus showed that they arise as the graded Lie algebra associated with the filtration on a free group given by the lower central series. This correspondence was motivated by commutator identities in group theory due to Philip Hall and Ernst Witt. (en) |
| dbo:wikiPageID | 31782613 (xsd:integer) |
| dbo:wikiPageLength | 15722 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1048560707 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Monoid_factorisation dbr:Binary_tree dbc:Combinatorics_on_words dbr:Commutator dbr:Mathematics dbr:Markov_odometer dbr:Möbius_function dbr:Confluence_(abstract_rewriting) dbr:Lexicographic_order dbr:Lower_central_series dbr:Combinatorics dbr:Commutator_collecting_process dbr:Chen–Fox–Lyndon_theorem dbr:Hall–Petresco_identity dbr:Totally_ordered dbr:Ernst_Witt dbr:Dirichlet_convolution dbr:Graded_Lie_algebra dbr:Free_magma dbr:Universal_enveloping_algebra dbc:Formal_languages dbr:Marshall_Hall_(mathematician) dbr:Philip_Hall dbr:Poincaré–Birkhoff–Witt_theorem dbr:Circular_shift dbr:Filtration_(mathematics) dbr:Free_Lie_algebra dbr:Free_group dbr:Free_monoid dbr:Group_theory dbr:Term_rewriting_system dbr:Sequence dbr:Kleene_star dbr:Wilhelm_Magnus dbr:Necklace_polynomial dbr:Lyndon_word |
| dbp:wikiPageUsesTemplate | dbt:Short_description |
| dcterms:subject | dbc:Combinatorics_on_words dbc:Formal_languages |
| rdfs:comment | In mathematics, in the areas of group theory and combinatorics, Hall words provide a unique monoid factorisation of the free monoid. They are also totally ordered, and thus provide a total order on the monoid. This is analogous to the better-known case of Lyndon words; in fact, the Lyndon words are a special case, and almost all properties possessed by Lyndon words carry over to Hall words. Hall words are in one-to-one correspondence with Hall trees. These are binary trees; taken together, they form the Hall set. This set is a particular totally ordered subset of a free non-associative algebra, that is, a free magma. In this form, the Hall trees provide a basis for free Lie algebras, and can be used to perform the commutations required by the Poincaré–Birkhoff–Witt theorem used in the cons (en) |
| rdfs:label | Hall word (en) |
| owl:sameAs | wikidata:Hall word https://global.dbpedia.org/id/FQwEk |
| prov:wasDerivedFrom | wikipedia-en:Hall_word?oldid=1048560707&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Hall_word |
| is dbo:wikiPageRedirects of | dbr:Hall_set |
| is dbo:wikiPageWikiLink of | dbr:Morphic_word dbr:Monoid_factorisation dbr:Commutator_collecting_process dbr:Universal_enveloping_algebra dbr:Philip_Hall dbr:Free_Lie_algebra dbr:Free_monoid dbr:Wilhelm_Magnus dbr:Lyndon_word dbr:Hall_set |
| is foaf:primaryTopic of | wikipedia-en:Hall_word |