Sturmian words: structure, combinatorics, and their arithmetics. (English) Zbl 0911.68098

Summary: 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 [A. de Luca and F. Mignosi, ibid. 136, No. 2, 361-385 (1994; Zbl 0874.68245)]. The main result of this paper is the following simple inductive definition of PER: (i) The empty word belongs to PER. (ii) 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\geqslant 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 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\).


68R15 Combinatorics on words


Zbl 0874.68245
Full Text: DOI


[1] Berstel, J.; Perrin, D., Theory of Codes (1985), Academic Press: Academic Press New York · Zbl 1022.94506
[2] Berstel, J.; Séébold, P., A remark on Morphic Sturmian words, R.A.I.R.O., I.T., 28, 255-263 (1994) · Zbl 0883.68104
[3] Brown, T. C., Descriptions of the characteristic sequence of an irrational, Canad. Math. Bull., 36, 15-21 (1993) · Zbl 0804.11021
[4] Christoffel, E. B., Observatio Arithmetica, Ann. Mat. Pura Appl., 6, 145-152 (1875) · JFM 06.0136.03
[5] de Luca, A., A combinatorial property of the Fibonacci word, Inform. Process. Lett., 12, 193-195 (1981)
[6] de Luca, A., Sturmian words: new combinatorial results, (Almeida, J.; Gomes, G. M.S.; Silva, P. V., Proc. Conf. on Semigroups Automata and Languages. Proc. Conf. on Semigroups Automata and Languages, Porto, 1994 (1996), World Scientific: World Scientific Singapore), 67-83 · Zbl 0917.20042
[7] de Luca, A.; Mignosi, F., On some Combinatorial properties of Sturmian words, Theoret. Comput. Sci., 136, 361-385 (1994) · Zbl 0874.68245
[8] Dulucq, S.; Gouyou-Beauchamps, D., Sur les facteurs des suites de Sturm, Theoret. Comput. Sci., 71, 381-400 (1990) · Zbl 0694.68048
[9] Fine, N. J.; Wilf, H. S., Uniqueness theorems for periodic functions, (Proc. Amer. Math. Soc., 16 (1965)), 109-114 · Zbl 0131.30203
[10] Hedlund, G. A.; Morse, M., Sturmian sequences, Amer. J. Math., 61, 605-620 (1940)
[11] Lothaire, M., Combinatorics on Words (1983), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0514.20045
[12] Mignosi, F., Infinite words with linear subword complexity, Theoret. Comput. Sci., 65, 221-242 (1989) · Zbl 0682.68083
[13] Mignosi, F., On the number of factors of Sturmian words, Theoret. Comput. Sci., 82, 71-84 (1991) · Zbl 0728.68093
[14] Pedersen, A., Solution of Problem E 3156, Amer. Math. Monthly, 95, 954-955 (1988)
[15] Raney, G. N., On continued fractions and finite automata, Math. Ann., 206, 265-283 (1973) · Zbl 0251.10024
[16] Rauzy, G., Mots infinis en arithmétique, (Nivat, M.; Perrin, D., Automata on Infinite Words. Automata on Infinite Words, Lectures Notes in Computer Science, vol. 192 (1984), Springer: Springer Berlin), 165-171 · Zbl 0613.10044
[17] Robinson, R. M., Problem E3156, Amer. Math. Monthly, 93, 482 (1986)
[18] Venkov, B. A., Elementary Number Theory (1970), Wolters-Noordhoff: Wolters-Noordhoff Pays-Bas · Zbl 0204.37101
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.