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 ORCID; Jeffrey Shallit ORCID

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

https://doi.org/10.46298/cm.12695
Source: arXiv.org:2301.06145
Volume: Volume 33 (2025), Issue 2 (Special issue: Numeration, Liège 2023, dedicated to the 75th birthday of professor Christiane Frougny)
Published on: August 2, 2024
Accepted on: May 27, 2024
Submitted on: December 15, 2023
Keywords: Computer Science - Discrete Mathematics, Computer Science - Formal Languages and Automata Theory, Mathematics - Combinatorics
Licence: Attribution-ShareAlike 4.0 International (CC BY-SA 4.0)
Funding:
    Source : OpenAIRE Graph
  • Funder: Natural Sciences and Engineering Research Council of Canada

Classifications

Mathematics Subject Classification 20201
Sources:
  • [1] zbMATH Open.

Publications

Has review
  • 1 zbMATH Open

Share and export

Consultation statistics

This page has been seen 671 times.
This article's PDF has been downloaded 1310 times.