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

de Luca, Aldo; Mignosi, Filippo

Theor. Comput. Sci. 136, No. 2, 361-385 (1994).

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\).

MSC:

68R15	Combinatorics on words
05A15	Exact enumeration problems, generating functions

References:

[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