pith. sign in

arxiv: 2301.06145 · v3 · pith:S2SA7JVInew · submitted 2023-01-15 · 💻 cs.DM · cs.FL· math.CO

Dyck Words, Pattern Avoidance, and Automatic Sequences

Lucas Mol , Narad Rampersad , Jeffrey Shallit This is my paper

Pith reviewed 2026-05-24 10:13 UTC · model grok-4.3

classification 💻 cs.DM cs.FLmath.CO
keywords Dyck wordsThue-Morse wordpower-free wordsnesting levelpattern avoidanceautomatic sequencesbinary factorsrepetition threshold
0
0 comments X

The pith

Binary words avoiding 7/3-powers have bounded nesting levels as Dyck words, with an explicit characterization and tight bounds on the count for Thue-Morse factors.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that any binary word free of 7/3-powers, interpreted as parentheses with 0 as left and 1 as right, reaches only a limited maximum nesting depth. The bound disappears once the forbidden repetition exponent increases. For the Thue-Morse word the authors supply an exact description of which finite factors form valid Dyck words and prove matching upper and lower bounds on the number f(n) of such factors of length 2n.

Core claim

Binary words that are 7/3-power-free have bounded nesting level. This no longer holds for larger repetition exponents. The factors of the Thue-Morse word that are Dyck admit an explicit characterization, and the number f(n) of Dyck factors of length 2n satisfies tight upper and lower bounds.

What carries the argument

Nesting level of a Dyck word (maximum depth in the parenthesis matching) together with the standard morphism generating the Thue-Morse word and the classical definition of k-power-freeness.

If this is right

  • Every 7/3-power-free binary word has finite nesting level when read as parentheses.
  • For any repetition exponent strictly larger than 7/3 there exist power-free words with arbitrarily large nesting levels.
  • The Dyck factors of the Thue-Morse word are completely described by a finite collection of allowed patterns.
  • The counting function f(n) is pinned between two explicit functions whose ratio tends to 1.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Repetition thresholds in combinatorics on words translate directly into structural restrictions on balanced parenthesis sequences.
  • The low subword complexity of automatic sequences such as Thue-Morse sharply limits the possible Dyck factors they can contain.
  • The same nesting bound may apply to other overlap-free or power-free morphic words generated by uniform morphisms.

Load-bearing premise

That the standard morphism for the Thue-Morse word and the usual definition of k-power-freeness suffice to control nesting depth and to list all Dyck factors without further unstated restrictions.

What would settle it

A single 7/3-power-free binary word whose parenthesis interpretation reaches a nesting depth exceeding the stated bound, or a Dyck factor of the Thue-Morse word that falls outside the given characterization.

Figures

Figures reproduced from arXiv: 2301.06145 by Jeffrey Shallit, Lucas Mol, Narad Rampersad.

Figure 1
Figure 1. Figure 1: DFA accepting base-2 representations of i such that the Thue-Morse word has arbitrarily long Dyck factors starting at index i. Now we turn to enumerating Dyck factors by length. Let us recall that a sequence (s(n))n≥0 is k-regular if there is a finite set of sequences (si(n))n≥0, i = 1, . . . , t, with s = s1, such that every subsequence of the form (s(k en+a))n≥0 with e ≥ 0 and 0 ≤ a < ke can be expressed… view at source ↗
Figure 2
Figure 2. Figure 2: DFAO computing q(n). States are in the form q/a, where q is the name of the state and a is the output. Proof. Notice that 1 ≤ q(n) ≤ 2 for n ≥ 1. These relations can be proved using linear representations computable by Walnut. We only prove the most complicated one, namely Eq. (3). Substituting n = m+ 3, we see that Eq. (3) is equivalent to the claim that d(8m + 25) = 2d(2m + 7) + d(4m + 13) − q(m + 3) for… view at source ↗
Figure 3
Figure 3. Figure 3: DFA accepting base-4 representations of n such that the Rudin–Shapiro sequence contains a Dyck factor of length n. The Walnut code given below computes an automaton ( [PITH_FULL_IMAGE:figures/full_fig_p019_3.png] view at source ↗
read the original 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$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper studies Dyck words in binary sequences (0 as open parenthesis, 1 as close). It proves that 7/3-power-free binary words have bounded nesting level (but this fails for larger exponents), gives an explicit characterization of the Dyck factors of the Thue-Morse word, and establishes tight upper and lower bounds on f(n), the number of length-2n Dyck factors of the Thue-Morse word.

Significance. If the proofs hold, the result links classical notions of power-freeness and overlap-freeness in automatic sequences to the nesting depth of Dyck words, yielding both a sharp threshold (7/3) and a concrete enumeration for the Thue-Morse word. The explicit characterization and tight bounds on f(n) constitute a concrete, falsifiable contribution to combinatorics on words.

minor comments (3)
  1. The abstract and introduction should explicitly state the definition of nesting level used for binary Dyck words and confirm that it matches the classical height function.
  2. Section on the characterization of Dyck factors of Thue-Morse should include a short table or example listing the first few such factors to illustrate the claimed explicit form.
  3. The proof of the 7/3 threshold would benefit from a brief remark on why the constant is sharp, perhaps by exhibiting a single 7/3-power-free word whose nesting level exceeds any given bound.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, significance assessment, and recommendation of minor revision. No specific major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper's central results rely on standard external definitions: the Thue-Morse word via its fixed morphism, classical k-power-freeness, and the nesting level for binary Dyck words (0 open, 1 close). The 7/3-power-free bounded-nesting claim and the explicit Dyck-factor characterization of Thue-Morse factors are derived via combinatorial arguments and pattern-avoidance properties that do not reduce to self-citations, fitted parameters, or redefinitions of the inputs. No load-bearing step equates a prediction to a fit by construction or imports uniqueness solely from the authors' prior work. The bounds on f(n) follow directly from the characterization without circular reduction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on standard definitions and known properties of the Thue-Morse word and power-free languages; no free parameters, invented entities, or ad-hoc axioms are visible in the abstract.

axioms (2)
  • domain assumption Standard morphism definition and overlap-free properties of the Thue-Morse word.
    Used to identify its Dyck factors.
  • standard math Classical definitions of k-power-free words and Dyck words over a binary alphabet.
    Foundational for the nesting-level claim.

pith-pipeline@v0.9.0 · 5623 in / 1392 out tokens · 96432 ms · 2026-05-24T10:13:14.108827+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

  1. [1]

    Allouche and J

    J.-P. Allouche and J. Shallit. The ring of k-regular sequences. Theoret. Comput. Sci. , 98(2):163–197, 1992

    work page 1992

  2. [2]

    Balkov´ a, E

    L. Balkov´ a, E. Pelantov´ a, and W. Steiner. Return words in the Thue-Morse and other sequences, 2006. Preprint available at https://hal.science/hal-00089863v2

    work page 2006

  3. [3]

    Berstel and C

    J. Berstel and C. Reutenauer. Noncommutative rational series with applications, volume 137 of Encyclopedia of Mathematics and its Applications . Cambridge University Press, Cam- bridge, 2011

    work page 2011

  4. [4]

    Brillhart and P

    J. Brillhart and P. Morton. ¨Uber Summen von Rudin-Shapiroschen Koeffizienten. Illinois J. Math., 22(1):126–148, 1978

    work page 1978

  5. [5]

    Choffrut, A

    C. Choffrut, A. Malcher, C. Mereghetti, and B. Palano. First-order logics: some character- izations and closure properties. Acta Inform., 49(4):225–248, 2012

    work page 2012

  6. [6]

    Chomsky and M

    N. Chomsky and M. P. Sch¨ utzenberger. The algebraic theory of context-free languages. In Computer programming and formal systems , pages 118–161. North-Holland, Amsterdam, 1963

    work page 1963

  7. [7]

    Ker¨ anen

    V. Ker¨ anen. Onk-repetition freeness of length uniform morphisms over a binary alphabet. Discrete Appl. Math. , 9(3):297–300, 1984

    work page 1984

  8. [8]

    Lothaire

    M. Lothaire. Combinatorics on words . Cambridge Mathematical Library. Cambridge Uni- versity Press, Cambridge, 1997

    work page 1997

  9. [9]

    L. Mol, N. Rampersad, and J. Shallit. Extremal overlap-free and extremal β-free binary words. Electron. J. Combin., 27(4):Paper No. 4.42, 2020

    work page 2020

  10. [10]

    L. Mol, N. Rampersad, and J. Shallit. Dyck words, pattern avoidance, and automatic sequences. In Combinatorics on words , volume 13899 of Lecture Notes in Comput. Sci. , pages 220–232. Springer, 2023. 20 Dyck words, pattern avoidance, and automatic sequences

    work page 2023

  11. [11]

    H. Mousavi. Automatic theorem proving in Walnut, 2016. Preprint available at http: //arxiv.org/abs/1603.06017

    work page arXiv 2016

  12. [12]

    P. Ochem. A generator of morphisms for infinite words. Theor. Inform. Appl., 40(3):427–441, 2006

    work page 2006

  13. [13]

    Rampersad and J

    N. Rampersad and J. Shallit. Rudin-Shapiro sums via automata theory and logic. In Combinatorics on words , volume 13899 of Lecture Notes in Comput. Sci. , pages 233–246. Springer, 2023

    work page 2023

  14. [14]

    J. Shallit. Synchronized sequences. In Combinatorics on words , volume 12847 of Lecture Notes in Comput. Sci. , pages 1–19. Springer, 2021

    work page 2021

  15. [15]

    J. Shallit. The logical approach to automatic sequences—exploring combinatorics on words with Walnut, volume 482 of London Mathematical Society Lecture Note Series . Cambridge University Press, Cambridge, 2023

    work page 2023

  16. [16]

    Shallit and A

    J. Shallit and A. Zavyalov. Transduction of automatic sequences and applications. In Implementation and application of automata , volume 14151 of Lecture Notes in Comput. Sci., pages 266–277. Springer, 2023

    work page 2023

  17. [17]

    N. J. A. Sloane. The On-Line Encyclopedia of Integer Sequences, 2022. Available online at https://oeis.org

    work page 2022

  18. [18]

    A. Thue. ¨Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Norske vid. Selsk. Skr. Mat. Nat. Kl. , 1:1–67, 1912. Reprinted in Selected Mathematical Papers of Axel Thue , T. Nagell, editor, Universitetsforlaget, Oslo, 1977, pp. 413–478. Received: December 15, 2023 Accepted for publication: May 27, 2024 Communicated by: Rigo Michel, Emilie ...

    work page 1912