Statements (24)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
gptkb:mathematical_concept
combinatorics |
| gptkbp:application |
used in the construction of bases for free Lie algebras
used in combinatorial enumeration used in de Bruijn sequences used in string algorithms |
| gptkbp:defines |
A Lyndon word is a nonempty string that is strictly lexicographically smaller than all of its nontrivial rotations.
|
| gptkbp:enumerationFormula |
The number of Lyndon words of length n over an alphabet of k symbols is (1/n) times the sum over all divisors d of n of μ(d)k^{n/d}, where μ is the Möbius function.
|
| gptkbp:field |
theoretical computer science
combinatorics |
| https://www.w3.org/2000/01/rdf-schema#label |
Lyndon words
|
| gptkbp:introducedIn |
1954
|
| gptkbp:namedAfter |
gptkb:Roger_Lyndon
|
| gptkbp:property |
Lyndon words are aperiodic.
Lyndon words are primitive words. Every string can be uniquely factorized into a non-increasing sequence of Lyndon words (Chen–Fox–Lyndon theorem). |
| gptkbp:relatedTo |
gptkb:de_Bruijn_sequences
free Lie algebra necklaces (combinatorics) |
| gptkbp:studiedBy |
gptkb:Roger_Lyndon
|
| gptkbp:supportsAlgorithm |
Duval's algorithm
|
| gptkbp:bfsParent |
gptkb:de_Bruijn_sequence
gptkb:Combinatorics_of_Words |
| gptkbp:bfsLayer |
8
|