Some characterizations of Sturmian words in terms of the lexicographic order (Q2893296)

The authors present some characterizations of infinite Sturmian words \(w\), over an ordered alphabet \(\{0, 1, \ldots, k\}\) where \(0 < 1 < \cdots < k\), in terms of the lexicographic order of their factors. They prove that \(w\) is Sturmian over \(\{0,1\}\) if and only if \(w\) satisfies the so-called ``Nice Factors Ordering property''. The authors give some equivalent formulations of this property, one of them being the following: for \(k=1\) and every lexicographically consecutive factors \(v\) and \(v'\) of \(w\) of equal length, there exist words \(\lambda\) and \(\mu\) over \(\{0,1\}\) such that \(v=\lambda 01 \mu\) and \(v' = \lambda 10 \mu\) or \(v = \lambda 0\) and \(v' = \lambda 1\). Under the additional hypotheses of recurrence and aperiodicity of \(w\), they prove that \(w\) is Sturmian if and only if for all factors \(v\) and \(v'\) of \(w\) of equal length, if \(v\) is lexicographically smaller than \(v'\) then the number of occurrences of \(1\) in \(v\) is no more than that number in \(v'\). Under these additional hypotheses, they also prove that \(w\) is Sturmian if and only if all lexicographically consecutive factors \(v\) and \(v'\) of \(w\) of equal length differ in at most two positions.