Some combinatorial properties of Sturmian words. (English) Zbl 0874.68245

Summary: We give a characterization of finite Sturmian words, by palindrome words, which generalizes a property of the Fibonacci words. We prove that the set \(St\) of finite Sturmian words coincides with the set of the factors of all the words \(w\) such that \(w=AB=Cxy\) with \(A\), \(B\), \(C\) palindromes, \(x\), \(y\in {a, b}\) and \(x\neq y\). Moreover, using this result we prove that \(St\) is equal to the set of the factors of all words w having two periods \(p\) and \(q\) which are coprimes and such that \(|w|\geq p+q-2\). Several other combinatorial properties concerning special and bispecial elements of \(St\) are shown. As a consequence we give a new, and purely combinatorial, proof of the enumeration formula of \(St\).


68R15 Combinatorics on words
05A15 Exact enumeration problems, generating functions
Full Text: DOI


[1] Berstel, J.; Pocchiola, M., A geometric proof of the enumeration formula for Sturmian words, Internat. J. Algebra Comput., 3, 349-355 (1993) · Zbl 0802.68099
[2] de Luca, A., A combinatorial property of the Fibonacci word, Inform. Process. Lett., 12, 193-195 (1981)
[3] Dulucq, S.; Gouyou-Beauchamps, D., Sur les facteurs des suites de Sturm, Theoret. Comput. Sci., 71, 381-400 (1990) · Zbl 0694.68048
[4] Fine, N. J.; Wilf, H. S., Uniqueness theorems for periodic functions, Proc. Amer. Math. Soc., 16, 109-114 (1965) · Zbl 0131.30203
[5] Hedlund, G. A., Sturmian minimal sets, Amer. J. Math., 66, 605-620 (1944) · Zbl 0063.01982
[6] Knuth, D. E.; Morris, J. H.; Pratt, V. R., Fast Pattern matching in strings, SIAM J. Comput., 6, 323-350 (1977) · Zbl 0372.68005
[7] Lothaire, M., Combinatorics on Words (1983), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0514.20045
[8] Mignosi, F., Infinite words with linear subword complexity, Theoret. Comput. Sci., 65, 221-242 (1989) · Zbl 0682.68083
[9] Mignosi, F., On the number of factors of Sturmian words, Theoret. Comput. Sci., 82, 71-84 (1991) · Zbl 0728.68093
[10] Pedersen, A., Solution of Problem E 3156, Amer. Math. Monthly, 95, 954-955 (1988)
[11] Rauzy, G., Mots infinis en arithmétique, (Nivat, M.; Perrin, D., Automata on Infinite Words, 192 (1984), Springer: Springer Berlin), 165-171, Lecture Notes in Computer Science · Zbl 0613.10044
[12] Robinson, R. M., Problem E 3156, Amer. Math. Monthly, 93, 482 (1986)
[13] Venkov, B. A., Elementary Number Theory (1970), Wolters-Noordhoff: Wolters-Noordhoff Groningen · 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.