2003/06/04 by Narad Rampersad, Jeffrey Shallit, Rampersad, Narad +4 · 1 citation
Computer Science · Mathematics · #68R15 #Algorithms and Data Compression #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO #msc:68R15 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.math/0306081
arxiv created 2003/06/04 · openalex publication_date 2003/06/04 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider three aspects of avoiding large squares in infinite binary words. First, we construct an infinite binary word avoiding both cubes xxx and squares yy with |y| >= 4; our construction is somewhat simpler than the original construction of Dekking. Second, we construct an infinite binary word avoiding all squares except 00, 11, and 0101; our construction is somewhat simpler than the original construction of Fraenkel and Simpson. In both cases, we also show how to modify our construction to obtain exponentially many words of length n with the given avoidance properties. Finally, we answer an open question of Prodinger and Urbanek from 1979 by demonstrating the existence of two infinite binary words, each avoiding arbitrarily large squares, such that their perfect shuffle has arbitrarily large squares.