On the context-freeness of the set of words containing overlaps

2006/10/02 by Narad Rampersad, Rampersad, Narad
Computer Science · #68R15 #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Logic, programming, and type systems #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.math/0610067

openalex publication_date 2006/10/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that the set of binary words containing overlaps is not unambiguously context-free and that the set of ternary words containing overlaps is not context-free. We also show that the set of binary words that are not subwords of the Thue-Morse word is not unambiguously context-free.

Related

• Words avoiding 7/3-powers and the Thue-Morse morphism
• The non-abelian squares are not context-free
• Avoidance of split overlaps
• Binary words containing infinitely many overlaps
• The analogue of overlap-freeness for the period-doubling sequence