@inproceedings{8dabadbf7f014661a2725c18da194e58,
title = "Universal Lyndon words",
abstract = "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.",
keywords = "Lex-code, Lyndon word, Universal cycle, Universal Lyndon word",
author = "Arturo Carpi and Gabriele Fici and {\v S}t{\v e}p{\'a}n Holub and Jakub Opr{\v s}al and Marinella Sciortino",
year = "2014",
doi = "10.1007/978-3-662-44522-8_12",
language = "English",
isbn = "9783662445211",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
number = "PART 1",
pages = "135--146",
booktitle = "Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Proceedings",
edition = "PART 1",
note = "39th International Symposium on Mathematical Foundations of Computer Science, MFCS 2014 ; Conference date: 25-08-2014 Through 29-08-2014",
}