2025-11-15T04:52:11.684179

Dyck Words, Pattern Avoidance, and Automatic Sequences

Mol, Rampersad, Shallit

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

academic

Dyck Words, Pattern Avoidance, and Automatic Sequences

基本信息

论文ID: 2301.06145
标题: Dyck Words, Pattern Avoidance, and Automatic Sequences
作者: Lucas Mol (Thompson Rivers University), Narad Rampersad (University of Winnipeg), Jeffrey Shallit (University of Waterloo)
分类: cs.DM (Discrete Mathematics), cs.FL (Formal Languages), math.CO (Combinatorics)
发表期刊: Communications in Mathematics 33 (2025), no. 2, Paper no. 5
论文链接: https://arxiv.org/abs/2301.06145

摘要

本文研究二进制序列中Dyck词的各种性质，其中0被视为左括号，1被视为右括号。研究表明，7/3-无幂二进制词具有有界的嵌套层次，但对于更大的重复指数，这一性质不再成立。论文给出了Thue-Morse词中Dyck因子的显式刻画，并展示了如何计算它们的数量。此外，还证明了长度为2n的Thue-Morse Dyck因子数量f(n)的紧上界和下界。

研究背景与动机

问题定义

本研究探讨的核心问题是理解无限二进制词中Dyck词因子的结构和性质。Dyck词是形式语言理论中的基本概念，代表平衡括号串，在计算机科学和数学中具有重要应用。

研究重要性

理论意义: Dyck语言是上下文无关语言的典型例子，研究其在自动序列中的分布有助于理解形式语言与自动机理论的深层联系
组合数学价值: 模式避免和幂避免是组合词汇学的核心研究方向，本研究将这些概念与Dyck词结合
计算应用: 自动序列在算法和计算复杂性理论中有广泛应用，理解其Dyck因子的性质具有实际意义

现有研究局限性

缺乏对特定自动序列中Dyck因子的系统性刻画
幂避免与嵌套层次关系的定量分析不足
自动序列Dyck因子计数的有效算法缺失

核心贡献

幂避免与嵌套层次的关系: 证明了7/3-无幂Dyck词的嵌套层次至多为3，但存在任意大嵌套层次的7/3+-无幂Dyck词
Thue-Morse词的Dyck因子刻画: 给出了Thue-Morse序列中所有Dyck因子的完整刻画：h(x)形式，其中x是某个三元序列s的因子
自动序列的一般理论: 建立了运行和同步自动序列Dyck因子的可判定性理论框架
精确的计数结果: 证明了Thue-Morse序列中长度2n的Dyck因子数量d(n)的紧上下界：d(n) ≤ n且d(n) ≥ n/2

方法详解

任务定义

给定二进制词w = w1..n，若将0视为左括号、1视为右括号时w表示平衡括号串，则称w为Dyck词。形式化地，w是Dyck词当且仅当：

B(w) = |w|₀ - |w|₁ = 0（平衡条件）
对所有前缀w'，B(w') ≥ 0（非负性条件）

嵌套层次N(w)定义为所有前缀中B(w')的最大值。

核心方法

1. 幂避免分析方法

使用归纳法和构造性证明：

定理2.1: 通过分析7/3-无幂Dyck词的结构，证明其嵌套层次≤3
定理2.9: 构造特殊态射f和g，使得f(gᵗ(2))产生任意大嵌套层次的7/3⁺-无幂Dyck词

2. 自动机理论方法

利用Walnut定理证明器进行计算验证：

morphism f "0->00100110100110010110010011001011001101
           1->00101100110100110110011010010110011011
           2->00101101001101001011001101001011010011"
morphism g "0->022012 1->022112 2->202101"