Dyck Words, Pattern Avoidance, and Automatic Sequences
From MaRDI portal
Publication:6134876
DOI10.1007/978-3-031-33180-0_17arXiv2301.06145OpenAlexW4381304074MaRDI QIDQ6134876FDOQ6134876
Authors: L. A. S. Mól, Narad Rampersad, Jeffrey Shallit 
Publication date: 25 July 2023
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Abstract: We study various aspects of Dyck words appearing in binary sequences, where is treated as a left parenthesis and as a right parenthesis. We show that binary words that are -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 , the number of Dyck factors of Thue-Morse of length .
Full work available at URL: https://arxiv.org/abs/2301.06145
Cites Work
- Title not available (Why is that?)
- The ring of \(k\)-regular sequences
- Noncommutative rational series with applications
- Title not available (Why is that?)
- Sequences with constant number of return words
- First-order logics: some characterizations and closure properties
- Subword complexity and \(k\)-synchronization
- On k-repetition freeness of length uniform morphisms over a binary alphabet
- Dyck Words, Pattern Avoidance, and Automatic Sequences
- Synchronized sequences
- The Logical Approach to Automatic Sequences
Cited In (6)
This page was built for publication: Dyck Words, Pattern Avoidance, and Automatic Sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6134876)
