On the superimposition of Christoffel words

Paquin, Geneviève et Reutenauer, Christophe (2011). « On the superimposition of Christoffel words ». Theoretical Computer Science, 412(4-5), pp. 402-418.

Fichier(s) associé(s) à ce document :
Télécharger (472kB)


Initially stated in terms of Beatty sequences, the Fraenkel conjecture can be reformulated as follows: for a k-letter alphabet A, with a fixed k ≥ 3, there exists a unique balanced infinite word, up to letter permutations and shifts, that has mutually distinct letter frequencies. Motivated by the Fraenkel conjecture, we study in this paper whether two Christoffel words can be superimposed. Following from previous work on this conjecture using Beatty sequences, we give a necessary and sufficient condition for the superimposition of two Christoffel words having same length, and more generally, of two arbitrary Christoffel words. Moreover, for any two superimposable Christoffel words, we give the number of different possible superimpositions and we prove that there exists a superimposition that works for any two superimposable Christoffel words. Finally, some new properties of Christoffel words are obtained as well as a geometric proof of a classic result concerning the money problem, using Christoffel words.

Type: Article de revue scientifique
Mots-clés ou Sujets: Fraenkel conjecture; Beatty sequence; Christoffel word; superimposition.
Unité d'appartenance: Faculté des sciences > Département de mathématiques
Déposé par: Christophe Reutenauer
Date de dépôt: 19 avr. 2016 19:08
Dernière modification: 27 avr. 2016 18:32
Adresse URL : http://archipel.uqam.ca/id/eprint/8197


Voir les statistiques sur cinq ans...