Avoidable patterns on two letters (Q1114419): Difference between revisions

We examine avoidable patterns, unavoidable in the sense of \textit{D. R. Bean}, \textit{A. Ehrenfeucht} and \textit{G. F. McNulty} [Pac. J. Math. 85, 261-294 (1979; Zbl 0428.05001)]. We prove that each pattern on two letters of length at least 13 is avoidable on an alphabet with two letters. The proof is based essentially on two facts: First, each pattern containing an overlapping factor is avoidable by the infinite word of Thue-Morse; secondly, each pattern without overlapping factor is avoidable by the infinite word of Fibonacci. We further discuss the minimal alphabet on which very short patterns on a 2-letter and a 3- letter alphabet are avoidable.