Dyck words, pattern avoidance, and automatic sequences

DOI10.46298/CM.12695MaRDI QIDQ6615627zbMATH OpenFDO

Authors L. A. S. Mól, Narad Rampersad, Jeffrey Shallit

Publication date 8 October 2024

Published in Communications in Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-ShareAlike 4.0 International

Full work available at URL https://doi.org/10.46298/CM.12695

zbMATH Keywords

automatic sequencesbinary wordscombinatorics on wordsDyck wordsFibonacci sequencepattern avoidanceperiod-doubling sequenceRudin-Shapiro sequenceThue-Morse sequenceWalnut theorem prover

Mathematics Subject Classification ID

Automata sequences (11B85) Combinatorics on words (68R15)

Review text

In this paper the authors study properties of factors of infinite binary words that are Dyck words. In this respect, \(0\) is treated as a left parenthesis and \(1\) as a right parenthesis, and a binary word is \textit{Dyck} if it represents a string of balanced parentheses. Some of the work is carried out using the \texttt{Walnut} theorem prover.\N\NAfter a brief introduction the authors study in Section 2 words avoiding some pattern and having the Dyck property. Furthermore, they introduce and study some properties of \textit{ternary Dyck words}. In Section 3 they characterize those factors of the Thue-Morse sequence that are Dyck. Section 4 is concerned with Dyck factors of particular automatic sequences. Examples of their results are given in terms of the Thue-Morse sequence. In Section 5 they give tight upper and lower bounds for the number of Dyck factors of the Thue-Morse sequence. In Section 6 they look at Dyck factors of other famous infinite sequence such as the Fibonacci, the period-doubling, and the Rudin-Shapiro sequences. They end the section with a conjecture on the paperfolding sequence.

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

• A generator of morphisms for infinite words
• Dyck Words, Pattern Avoidance, and Automatic Sequences
• Extremal overlap-free and extremal -free binary words
• First-order logics: some characterizations and closure properties
• scientific article; zbMATH DE number 1024080 (Why is no real title available?)
• scientific article; zbMATH DE number 3238653 (Why is no real title available?)
• Noncommutative rational series with applications
• On k-repetition freeness of length uniform morphisms over a binary alphabet
• Rudin-Shapiro Sums via Automata Theory and Logic
• Synchronized sequences
• The Logical Approach to Automatic Sequences
• The ring of k-regular sequences
• Transduction of automatic sequences and applications
• Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen.
• Über Summen von Rudin-Shapiroschen Koeffizienten

Cited in

(1)

• Dyck Words, Pattern Avoidance, and Automatic Sequences

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 Q6615627)