Discrete Mathematics & Theoretical Computer Science, Vol 9, No 2 (2007)

Font Size:  Small  Medium  Large

Properties of the extremal infinite smooth words

Srecko Brlek, Guy Melançon, Geneviève Paquin

Abstract


Smooth words are connected to the Kolakoski sequence. We construct the maximal and the minimal infinite smooth words, with respect to the lexicographical order. The naive algorithm generating them is improved by using a reduction of the De Bruijn graph of their factors. We also study their Lyndon factorizations. Finally, we show that the minimal smooth word over the alphabet {1,3} belongs to the orbit of the Fibonacci word.

Full Text: PDF PostScript