On cube-free ω-words generated by binary morphisms

AbstractLet h be a morphism satisfying h(a) = ax for a letter a and a nonempty word x. Then h defines an infinite word (an ω-word) when applied iteratively starting from a. Such ω-words are considered in a binary case. It is shown that only biprefixes can generate cube-free ω-words, i.e. words which do not contain a word υ3, with υ ≠ λ, as a subword. The same does not hold true for fourth power-free ω-words, the counterexample being the ω-word defined by the Fibonaccimorphism: h(a) = ba, h(b) = a.As the main result it is proved that it is decidable whether a given morphism of the above form generates a cube-free ω-word. Moreover, it is shown that no more than 10 steps of iterations are needed to solve the problem