Universal Lyndon words

DOI10.1007/978-3-662-44522-8_12MaRDI QIDQ2922009zbMATH OpenOpenAlexFDO

Authors Gabriele Fici, Jakub Opršal, M. Sciortino, Arturo Carpi, Štěpán Holub

Publication date 14 October 2014

Published in Mathematical Foundations of Computer Science 2014 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1406.5895

zbMATH Keywords

lex-codeLyndon worduniversal cycleuniversal lyndon word

Mathematics Subject Classification ID

Combinatorics on words (68R15) Prefix, length-variable, comma-free codes (94A45)

Abstract: 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.

Recommendations

• Génération d'une section des classes de conjugaison et arbre des mots de Lyndon de longueur bornée. (Generation of a section of conjugation classes and trees of Lyndon words of bounded length)
• Nyldon words
• scientific article; zbMATH DE number 4123678
• Language of Lyndon partial words
• On generalized Lyndon words

Cited in

(4)

• 2D Lyndon words and applications
• Periods of strongly connected multivariate digraphs
• New results on Nyldon words and Nyldon-like sets
• Lyndon words formalized in Isabelle/HOL

This page was built for publication: Universal Lyndon words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2922009)