6533b858fe1ef96bd12b634d
RESEARCH PRODUCT
Universal Lyndon Words
ŠTěpán HolubJakub OpršalArturo CarpiMarinella SciortinoGabriele Ficisubject
Discrete mathematicsExistential quantificationLyndon word Universal cycle Universal Lyndon wordComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Lyndon word Universal cycle Universal Lyndon word Lex-codeLexicographical orderLyndon wordUniversal Lyndon wordLyndon wordsPrefixCombinatoricsMathematics::Group TheoryCombinatorics on wordsComputer Science::Discrete MathematicsUniversal cycleBijectionAlphabetMathematics::Representation TheoryComputer Science::Formal Languages and Automata TheoryMathematicsdescription
A word w over an alphabet Σ is a Lyndon word if there exists an order defined on Σ for which w is lexicographically smaller than all of its conjugates (other than itself). We introduce and study universal Lyndon words, which are words over an n-letter alphabet that have length n! and such that all the conjugates are Lyndon words. We show that universal Lyndon words exist for every n and exhibit combinatorial and structural properties of these words. We then define particular prefix codes, which we call Hamiltonian lex-codes, and show that every Hamiltonian lex-code is in bijection with the set of the shortest unrepeated prefixes of the conjugates of a universal Lyndon word. This allows us to give an algorithm for constructing all the universal Lyndon words.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2014-01-01 |