Srečko Brlek ; Guy Melançon ; Geneviève Paquin - Properties of the extremal infinite smooth words

dmtcs:412 - Discrete Mathematics & Theoretical Computer Science, January 1, 2007, Vol. 9 no. 2 -
Properties of the extremal infinite smooth words

Authors: Srečko Brlek 1; Guy Melançon ORCID-iD2; Geneviève Paquin 3

  • 1 Laboratoire de combinatoire et d'informatique mathématique [Montréal]
  • 2 Laboratoire Bordelais de Recherche en Informatique
  • 3 Laboratoire de Mathématiques

Smooth words are connected to the Kolakoski sequence. We construct the maximal and the minimal in nite 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 f1; 3g belongs to the orbit of the Fibonacci word.

Volume: Vol. 9 no. 2
Published on: January 1, 2007
Imported on: March 26, 2015
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
    Source : OpenAIRE Graph
  • Funder: Natural Sciences and Engineering Research Council of Canada

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo DOI 10.1016/j.tcs.2007.11.019
  • 10.1016/j.tcs.2007.11.019
Smooth words on 2-letter alphabets having same parity

Consultation statistics

This page has been seen 218 times.
This article's PDF has been downloaded 327 times.