@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",

}