2020/01/31 by Lucas Mol, Narad Rampersad, Mol, Lucas +1
Computer Science · #68R15 #Advanced Algebra and Logic #Coding theory and cryptography #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2001.11763
openalex publication_date 2020/01/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A square-free word w over a fixed alphabet Σ is extremal if every word obtained from w by inserting a single letter from Σ (at any position) contains a square. Grytczuk et al. recently introduced the concept of extremal square-free word, and demonstrated that there are arbitrarily long extremal square-free ternary words. We find all lengths which admit an extremal square-free ternary word. In particular, we show that there is an extremal square-free ternary word of every sufficiently large length. We also solve the analogous problem for circular words.