Dyck Words, Pattern Avoidance, and Automatic Sequences

DOI10.1007/978-3-031-33180-0_17MaRDI QIDQ6134876zbMATH OpenOpenAlexFDO

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)

Full work available at URL https://arxiv.org/abs/2301.06145

zbMATH Keywords

pattern avoidanceautomatic sequenceDyck word

Mathematics Subject Classification ID

Combinatorics on words (68R15)

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$.

Recommendations

• Dyck words, pattern avoidance, and automatic sequences
• Dyck words, lattice paths, and abelian borders
• Dyck Words, Lattice Paths, and Abelian Borders
• On complexity functions of infinite words associated with generalized Dyck languages
• Binary words avoided by the Thue-Morse sequence

Cites work

• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 3238653 (Why is no real title available?)
• Dyck Words, Pattern Avoidance, and Automatic Sequences
• First-order logics: some characterizations and closure properties
• Noncommutative rational series with applications
• On k-repetition freeness of length uniform morphisms over a binary alphabet
• Sequences with constant number of return words
• Subword complexity and \(k\)-synchronization
• Synchronized sequences
• The Logical Approach to Automatic Sequences
• The ring of \(k\)-regular sequences

Cited in

(6)

• Dyck Words, Pattern Avoidance, and Automatic Sequences
• Dyck words, pattern avoidance, and automatic sequences
• scientific article; zbMATH DE number 5562328 (Why is no real title available?)
• The phagocyte lattice of Dyck words
• Transduction of automatic sequences and applications
• scientific article; zbMATH DE number 5557896 (Why is no real title available?)

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)