Generalized balances in Sturmian words Original Research Article

One of the numerous characterizations of Sturmian words is based on the notion of balance. An infinite word x on the {0,1} alphabet is balanced if, given two factors of x, w and w′, having the same length, the difference between the number of 0ʹs in w (denoted by |w|0) and the number of 0ʹs in w′ is at most 1, i.e. ||w|0−|w′|0|⩽1. It is well known that an aperiodic word is Sturmian if and only if it is balanced. In this paper, the balance notion is generalized by considering the number of occurrences of a word u in w (denoted by |w|u) and w′. The following is obtained. Theorem. Let x be a Sturmian word. Let u, w and w′ be three factors of x. Then,|w|=|w′|⇒||w|u−|w′|u|⩽|u|. Another balance property, called equilibrium, is also given. This notion permits us to give a new characterization of Sturmian words. The main techniques used in the proofs are word graphs and return