Dyck Words, Pattern Avoidance, and Automatic Sequences
This is an incremental theoretical contribution for researchers in combinatorics on words and automatic sequences.
The paper studies Dyck words in binary sequences, showing that 7/3-power-free words have bounded nesting depth, while larger exponents do not. It characterizes Dyck factors in the Thue-Morse word and provides tight bounds on their count.
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$.