Dyck words, pattern avoidance, and automatic sequences
Communications in Mathematics, 2024•cm.episciences.org
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.
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.
Abstract
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.
cm.episciences.org
Showing the best result for this search. See all results