Avoiding squares and overlaps over the natural numbers

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 01020103⋯01020103⋯, 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 φ:N∗→N∗φ:N∗→N∗ that generates the lexicographically least infinite overlap-free word by iteration. Furthermore, we show that for all h,k∈Nh,k∈N with h≤kh≤k, the word φk−h(h)φk−h(h) is the lexicographically least overlap-free word starting with the letter hh and ending with the letter kk, and give some of its symmetry properties.