2023/01/15 by Lucas Mol, Narad Rampersad, Jeffrey Shallit
Computer Science · Mathematics · #Algorithms and Data Compression #Arithmetic #Binary number #Bounded function #Coding theory and cryptography #Combinatorics #Computer science #Counterexample #Discrete mathematics #Geometry #Linguistics #Mathematical analysis #Mathematics #Morse code #Parenthesis #Repetition (rhetorical device) #Upper and lower bounds #Word (group theory) #cs.DM #cs.FL #math.CO #semigroups and automata theory
paper · pdf · doi:10.46298/cm.12695
published as Communications in Mathematics, Volume 33 (2025), Issue 2 (Special issue: Numeration, Liège 2023, dedicated to the 75th birthday of professor Christiane Frougny) (August 2, 2024) cm:12695 · Full version of a paper appearing in the conference proceedings of WORDS 2023
arxiv created 2024/07/31 · openalex publication_date 2024/08/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28 · arxiv updated 2026/08/05
We study various aspects of Dyck words appearing in binary sequences, where 0 is treated as a left parenthesis and 1 as a right parenthesis. We show that binary words that are 7/3-power-free have bounded nesting level, but this no longer holds for larger repetition exponents. We give an explicit characterization of the factors of the Thue-Morse word that are Dyck, and show how to count them. We also prove tight upper and lower bounds on f(n), the number of Dyck factors of Thue-Morse of length 2n.