2023/03/25 by James D. Currie, Currie, James D.
Computer Science · #68R15 #Coding theory and cryptography #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2303.14539
openalex publication_date 2023/03/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Good words are binary words avoiding factors 11 and 1001, and patterns 0000 and 00010100. We show that good words bear the same relationship to the period-doubling sequence that overlap-free words bear to the Thue-Morse sequence. We prove an analogue of Fife's Theorem for good words, exhibit the lexicographically least and greatest infinite good words, and determine the patterns avoided by the period doubling word.