On an involution of Christoffel words and Sturmian morphisms

Abstract : There is a natural involution on Christoffel words, originally studied by the second author in [A. de Luca, Combinatorics of standard Sturmian words, Lecture Notes in Computer Science 1261 (1997) 249-267]. We show that it has several equivalent definitions: one of them uses the slope of the word, and changes the numerator and the denominator respectively in their inverses modulo the length; another one uses the cyclic graph allowing the construction of the word, by interpreting it in two ways (one as a permutation and its ascents and descents, coded by the two letters of the word, the other in the setting of the Fine and Wilf periodicity theorem); a third one uses central words and generation through iterated palindromic closure, by reversing the directive word. We show further that this involution extends to Sturmian morphisms, in the sense that it preserves conjugacy classes of these morphisms, which are in bijection with Christoffel words. The involution on morphisms is the restriction of some conjugation of the automorphisms of the free group. Finally, we show that, through the geometrical interpretation of substitutions of Arnoux and Ito, our involution is the same thing as duality of endomorphisms (modulo some conjugation).
Type de document :
Article dans une revue
European Journal of Combinatorics, Elsevier, 2008, 29 (2), pp.535-553. 〈10.1016/j.ejc.2007.03.001〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00260803
Contributeur : Valerie Berthe <>
Soumis le : mercredi 5 mars 2008 - 11:35:25
Dernière modification le : jeudi 24 mai 2018 - 15:59:21

Lien texte intégral

Identifiants

Collections

Citation

Valerie Berthe, Aldo De Luca, Christophe Reutenauer. On an involution of Christoffel words and Sturmian morphisms. European Journal of Combinatorics, Elsevier, 2008, 29 (2), pp.535-553. 〈10.1016/j.ejc.2007.03.001〉. 〈lirmm-00260803〉

Partager

Métriques

Consultations de la notice

108