Dyck words, pattern avoidance, and automatic sequences (Q6615627)

In this paper the authors study properties of factors of infinite binary words that are Dyck words. In this respect, \(0\) is treated as a left parenthesis and \(1\) as a right parenthesis, and a binary word is \textit{Dyck} if it represents a string of balanced parentheses. Some of the work is carried out using the \texttt{Walnut} theorem prover.\N\NAfter a brief introduction the authors study in Section 2 words avoiding some pattern and having the Dyck property. Furthermore, they introduce and study some properties of \textit{ternary Dyck words}. In Section 3 they characterize those factors of the Thue-Morse sequence that are Dyck. Section 4 is concerned with Dyck factors of particular automatic sequences. Examples of their results are given in terms of the Thue-Morse sequence. In Section 5 they give tight upper and lower bounds for the number of Dyck factors of the Thue-Morse sequence. In Section 6 they look at Dyck factors of other famous infinite sequence such as the Fibonacci, the period-doubling, and the Rudin-Shapiro sequences. They end the section with a conjecture on the paperfolding sequence.