Extremal Infinite Overlap-Free Binary Words

Abstract

Let t be the infinite fixed point, starting with 1, of the morphism μ:0→01, 1→10. An infinite word over {0,1} is said to be overlap-free if it contains no factor of the form axaxa, where a∈{0,1} and x∈{0,1}∗. We prove that the lexicographically least infinite overlap-free binary word beginning with any specified prefix, if it exists, has a suffix which is a suffix of t In particular, the lexicographically least infinite overlap-free binary word is 001001t.