Another characterization of Sturmian words (one more)
Gwénaël Richomme, Jules Verne · 1999
Sturmian words (balanced, non ultimately periodic, innite words) have been widely studied since the works of Morse and Hedlund [5]. Many equivalent denitions have been established. Here, we give another one related to the notion of n-chains of Morse and Hedlund. We consider here the alphabet = fa; bg. Given a word w, i.e. an element of the free monoid , and given a letter x in , we denote jwj x the number of occurrences of x in w. For a subset X of , we denote by Card(X) the number of elements in X and by X ! the set of (right) innite words obtained by concatenation of words of X. Given an innite word w, we denote by F (w) the set of (nite) factors of w, and by F n (w) the set of factors of w of length n. An innite word is ultimately periodic if there exist two nite words u and v such that w = uv ! . A word w over is balanced, if for any factors u and v of w, juj = jvj implies jjuj a jvj a j 1. Observe that if w is balanced, than there exists an integer...