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