Universal Lyndon Words

Preprint English OPEN
Carpi, Arturo; Fici, Gabriele; Holub, Stepan; Oprsal, Jakub; Sciortino, Marinella;
  • 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... View more
  • 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
Share - Bookmark