Universal Lyndon Words

Preprint English OPEN
Carpi, Arturo ; Fici, Gabriele ; Holub, Stepan ; Oprsal, Jakub ; Sciortino, Marinella (2014)
  • Subject: 68R15 | Mathematics - Combinatorics | Computer Science - Discrete Mathematics | Computer Science - Formal Languages and Automata Theory
    arxiv: Mathematics::Representation Theory | Computer Science::Discrete Mathematics | Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) | Mathematics::Group Theory | Computer Science::Formal Languages and Automata Theory

A word $w$ over an alphabet $\Sigma$ is a Lyndon word if there exists an order defined on $\Sigma$ for which $w$ is lexicographically smaller than all of its conjugates (other than itself). We introduce and study \emph{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.
  • References (6)

    1. A. Carpi and A. de Luca. Words and special factors. Theoret. Comput. Sci., 259(1- 2):145-182, 2001.

    2. F. Chung, P. Diaconis, and R. Graham. Universal cycles for combinatorial structures. Discrete Math., 110:43-59, 1992.

    3. A. E. Holroyd, F. Ruskey, and A. Williams. Shorthand universal cycles for permutations. Algorithmica, 64(2):215-245, 2012.

    4. B. Jackson. Universal cycles of k-subsets and k-permutations. Discrete Math., 117(1-3):141-150, 1993.

    5. M. Lothaire. Combinatorics on words. Cambridge University Press, Cambridge, 1997.

    6. F. Ruskey and A. Williams. An explicit universal cycle for the (n − 1)-permutations of an n-set. ACM Trans. Algorithms, 6(3), article 45, 2010.

  • Metrics
    No metrics available
Share - Bookmark