A characterization of infinite smooth Lyndon words
Geneviève Paquin
Abstract
In a recent paper, Brlek, Jamet and Paquin showed that some extremal
infinite smooth words are also infinite Lyndon words. This result
raises a natural question: are they the only ones? If no, what do the
infinite smooth words that are also Lyndon words look like? In this
paper, we give the answer, proving that the only infinite smooth
Lyndon words are m{a<b}, with
a,b even, m{1<b}
and
Δ-11(m{1<b}),
with b odd, where mA is the
minimal infinite smooth word with respect to the lexicographic order
over a numerical alphabet A and Δ is
the run-length encoding function.
Full Text: PDF PostScript