2009/01/12 by Mathieu Guay-Paquet, Jeffrey Shallit, Guay-Paquet, Mathieu +1
Computer Science · Mathematics · #68R15 #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Logic, programming, and type systems #cs.FL #math.CO #msc:68R15 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.0901.1397
16 pages, 2 tables
arxiv created 2009/01/12 · openalex publication_date 2009/01/12 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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..., 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 phi : N* -> N* that generates the lexicographically least infinite overlap-free word by iteration. Furthermore, we show that for all h,k in N with h <= k, the word phik-h(h) is the lexicographically least overlap-free word starting with the letter h and ending with the letter k, and give some of its symmetry properties.