Sturmian Words, Lyndon Words and Trees

J. Berstel, A. De Luca

IBP-Litp 1995/24: Rapport de Recherche Litp / Litp research reports
32 pages - Juin/June 1995 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Sturmian Words, Lyndon Words and Trees

Résumé : Nous prouvons de nouvelles propriétés combinatoires de l'ensemble PER des mots w qui ont deux périodes p et q premières entre elles et tels que la longueur de w est p+q-2. C'est ensemble est essentiellement l'ensemble des mots de Christoffel, et aussi l'ensemble des mots de Sturm finis qui sont des mots de Lyndon. Nous montrons que la fraction continue du nombre p/q est l'image miroir de la fraction continue de la pente du mot. Ces résultats sont interprétés en associant aux mots (plutôt aux couples de mots) trois arbres : l'arbre standard, l'arbre de Christoffel et l'arbre de Farey. On montre que le nombre de Stern-Brocot est égale à la pente d'un mot, alors que le nombre de Raney est le quotient des périodes minimales de deux mots.

Abstract : We prove some new combinatorial properties of the set PER of words w that have two periods p and q which are coprime and such that the length of w is p+q-2. This is basically the set of Christoffel words, and also the set of finite Sturmian words which are Lyndon words. We show that the continued fraction of the number p/q is the reversal of the continued fraction of the slope of the word. These results are viewed by associating to words (more precisely to pairs of words) three trees : the standard tree, the Christoffel tree and the Farey tree. We show that the Stern-Brocot number is equal to the slope of some word, while the Raney number is the ration of the minimal periods of two words.

Publications internes Litp 1995 / Litp research reports 1995