Dyck Words, Pattern Avoidance, and Automatic Sequences
| Autor: | Mol, Lucas, Rampersad, Narad, Shallit, Jeffrey |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Zdroj: | Communications in Mathematics, Volume 33 (2025), Issue 2 (Special issue: Numeration, Liège 2023, dedicated to the 75th birthday of professor Christiane Frougny) (August 2, 2024) cm:12695 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.46298/cm.12695 |
| Popis: | 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$. Comment: Full version of a paper appearing in the conference proceedings of WORDS 2023 |
| Databáze: | arXiv |
| Externí odkaz: |
|