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
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