Avoiding squares and overlaps over the natural numbers

Abstract: We consider avoiding squares and overlaps over the natural numbers, using a greedy algorithm that chooses the least possible integer at each step; the word generated is lexicographically least among all such infinite words. In the case of avoiding squares, the word is , the familiar ruler function, and is generated by iterating a uniform morphism. The case of overlaps is more challenging. We give an explicitly-defined morphism that generates the lexicographically least infinite overlap-free word by iteration. Furthermore, we show that for all with , the word is the lexicographically least overlap-free word starting with the letter and ending with the letter , and give some of its symmetry properties. [Copyright &y& Elsevier]