Sturmian words: structure, combinatorics, and their arithmetics

• Published in: Theoretical computer science 1997-08, Vol.183 (1), p.45-82
• Main Author: de Luca, Aldo
• Format: Article
• Language: English
• Subjects: Palindromes; Standard words; Sturmian words
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/S0304-3975(96)00310-6

We prove some new results concerning the structure, the combinatorics and the arithmetics of the set PER of all the words w having two periods p and q, p⩽ q, which are coprimes and such that ¦w¦= p + q− 2. A basic theorem relating PER with the set of finite standard Sturmian words was proved in de Luca and Mignosi (1994). The main result of this paper is the following simple inductive definition of PER: the empty word belongs to PER, If w is an already constructed word of PER, then also ( aw) (−) and ( bw) (−) belong to PER, where (−) denotes the operator of palindrome left-closure, i.e. it associates to each word u the smallest palindrome word u (−) having u as a suffix. We show that, by this result, one can construct in a simple way all finite and infinite standard Sturmian words. We prove also that, up to the automorphism which interchanges the letter a with the letter b, any element of PER can be codified by the irreducible fraction p q . This allows us to construct for any n⩾0 a natural bijection, that we call Farey correspondence, of the set of the Farey series of order n + 1 and the set of special elements of length n of the set St of all finite Sturmian words. Finally, we introduce the concepts of Farey tree and Farey monoid. This latter is obtained by defining a suitable product operation on the developments in continued fractions of the set of all irreducible fractions p q .