Lucas Mol ; Narad Rampersad ; Jeffrey Shallit - Dyck Words, Pattern Avoidance, and Automatic Sequences

cm:12695 - Communications in Mathematics, August 2, 2024, Volume 33 (2025), Issue 2 (Special issue: Numeration, Liège 2023, dedicated to the 75th birthday of professor Christiane Frougny) - https://doi.org/10.46298/cm.12695
Dyck Words, Pattern Avoidance, and Automatic SequencesArticle

Authors: Lucas Mol ; Narad Rampersad ; Jeffrey Shallit

    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$.


    Volume: Volume 33 (2025), Issue 2 (Special issue: Numeration, Liège 2023, dedicated to the 75th birthday of professor Christiane Frougny)
    Published on: August 2, 2024
    Accepted on: May 27, 2024
    Submitted on: December 15, 2023
    Keywords: Computer Science - Discrete Mathematics,Computer Science - Formal Languages and Automata Theory,Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 175 times.
    This article's PDF has been downloaded 69 times.