Dyck Words, Pattern Avoidance, and Automatic Sequences

Each language version is independently generated for its own context, not a direct translation.

这篇论文就像是在探索**“数学世界里的乐高积木”和“无限长的密码锁”**之间的有趣关系。

为了让你轻松理解，我们把论文里的核心概念翻译成生活中的故事：

1. 什么是"Dyck 词”？（平衡的括号）

想象你在玩一个括号游戏。

0 代表左括号 (
1 代表右括号 )

一个 Dyck 词（也就是论文里的“合法括号串”），必须满足两个条件：

总数平衡：左括号和右括号的数量一样多。
随时不欠债：从前往后读，任何时候右括号的数量都不能超过左括号。

例子：

01 是合法的：()。
0011 是合法的：(())。
0110 是非法的：() ) (，因为中间那个右括号出现时，前面没有足够的左括号来“接住”它。

嵌套层级（Nesting Level）：
这就好比套娃。

01 是 1 层套娃。
0011 是 2 层套娃（外面包了一层）。
000111 是 3 层套娃。
论文就在研究：在那些无限长的、由 0 和 1 组成的“密码”里，能找出多深的“套娃”？

2. 核心发现一：重复的魔力（7/3 次方规则）

论文首先研究了一个关于**“重复”**的问题。
想象你在写一串数字，如果你写得太像复读机（比如 000 是 3 次重复，010101 是 3 次重复），这种词就被称为“高次幂”。

发现：如果你限制这串数字里不能出现太长的重复（具体来说，不能出现超过 $7/3$ 次，也就是 2.33 次以上的重复），那么这串数字里能找到的“括号套娃”深度是有限的。
比喻：就像如果你规定“积木不能叠得太整齐”，那么你能搭出的“高塔”高度就被锁死在 3 层以内。
结论：只要限制重复程度在 $7/3 $以下，嵌套深度最大只能是 3。但如果允许稍微多一点点重复（比如$ 7/3$ 以上），你就可以搭出无限高的塔。

3. 核心发现二：特洛伊木马（Thue-Morse 序列）

论文重点研究了一个著名的无限序列，叫 Thue-Morse 序列。

它是怎么生成的？ 就像玩“镜像游戏”：
- 开始：0
- 下一步：把 0 变成 01，1 变成 10。得到 01。
- 再下一步：把 0 变 01，1 变 10。得到 0110。
- 再下一步：01101001...
  这个序列看起来杂乱无章，但实际上非常有规律（它是“自动序列”）。
论文做了什么？
作者们像侦探一样，在这个无限长的序列里寻找所有的“合法括号串”（Dyck 词）。
- 结果：他们发现，这个序列里的所有合法括号串，都可以通过一种特殊的“翻译规则”（把 0, 1, 2 映射成特定的括号组合）从另一个简单的序列里推导出来。
- 深度限制：在这个著名的 Thue-Morse 序列里，无论你怎么找，括号套娃的深度永远不会超过 2 层。这就像是一个永远只有两层楼高的迷宫，虽然路很长，但永远爬不到三楼。

4. 核心发现三：数数游戏（有多少个？）

既然知道了 Thue-Morse 序列里有这些括号串，作者们开始数数。

问题：长度为 $2n$ 的合法括号串，在这个序列里出现了多少次？
方法：他们利用了一种叫 Walnut 的“数学计算器”（一种能自动证明定理的计算机程序）。
结论：
- 这个数量是有规律的（可以用数学公式算出来）。
- 上限：数量不会超过 $n$ 。
- 下限：数量至少是 $n/2$ 。
- 这就好比，虽然迷宫很大，但如果你走 $n$ 步，你遇到的“宝藏”（合法括号串）数量大概在 $n/2$ 到 $n$ 之间。

5. 核心发现四：其他序列的“奇葩”表现

论文最后还看了其他几个著名的无限序列：

斐波那契数列（Fibonacci word）：这里的合法括号串非常少，只有 01 和 0101 两种。就像是一个只有两个房间的迷宫。
Rudin-Shapiro 序列：这个序列很神奇，它里面竟然藏着无限深的括号套娃！无论你想找多深的嵌套，都能在这个序列里找到。这就像是一个无限向下的地心引力井。

总结：这篇论文讲了什么？

想象你在玩一个无限长的字符串拼图游戏：

规则：0 是左括号，1 是右括号。
限制：如果你禁止字符串里出现太整齐的重复（比如不能连续重复 3 次），那么你能拼出的“套娃”高度就被限制住了（最高 3 层）。
特例：在一个叫 Thue-Morse 的著名序列里，虽然它很长，但它的“套娃”永远只有 2 层高，而且作者们精确算出了里面有多少个这样的套娃。
惊喜：在另一个叫 Rudin-Shapiro 的序列里，套娃可以无限深。

一句话概括：
这篇论文通过数学和计算机，揭示了**“重复的规律”如何限制“结构的深度”**，并像清点宝藏一样，精确计算了这些结构在著名数学序列中的分布情况。

Each language version is independently generated for its own context, not a direct translation.

这是一份关于论文《Dyck words, pattern avoidance, and automatic sequences》（Dyck 词、模式避免与自动序列）的详细技术总结。

1. 研究背景与问题定义

核心概念：

Dyck 词 (Dyck words)： 在二元序列中，将 0 视为左括号 (，1 视为右括号 )。如果一个词在括号匹配意义下是平衡的（即前缀中 0 的数量始终不少于 1 的数量，且总数相等），则称为 Dyck 词。
嵌套层级 (Nesting level)： 衡量括号嵌套深度的指标，记为 $N(x)$ 。
模式避免 (Pattern avoidance)： 研究不包含特定幂次（如 $k$ -power）或重叠（overlap）的序列。例如， $\alpha$ -power-free 表示不包含指数大于等于 $\alpha$ 的幂次。
自动序列 (Automatic sequences)： 如 Thue-Morse 序列、Rudin-Shapiro 序列等，其第 $n$ 项可由有限自动机根据 $n$ 的 $k$ 进制表示生成。

研究问题：
本文主要探讨无限二元序列中作为因子的 Dyck 词的性质，具体包括：

幂次避免与嵌套层级的关系： 如果一个序列避免了高次幂（如 $7/3$-power-free），其 Dyck 因子的嵌套层级是否受限？
Thue-Morse 序列中的 Dyck 因子： 如何刻画 Thue-Morse 序列中的 Dyck 因子？如何计算长度为 $2n $的 Dyck 因子数量$ d(n)$？
其他自动序列： 在 Fibonacci 词、周期加倍序列、Rudin-Shapiro 序列等中，Dyck 因子的存在性与性质。

2. 方法论

本文采用了组合数学、形式语言理论与自动机理论的结合，并大量依赖 Walnut 定理证明器（基于自动机逻辑的验证工具）。

构造性证明与同态 (Morphisms)： 通过定义特定的同态映射（如 $f$ 和 $g$ ），从简单的种子词构造出具有特定嵌套层级且避免特定幂次的 Dyck 词。
自动机与逻辑公式： 利用 Walnut 系统，将序列性质转化为第一阶逻辑公式（First-order logic），构建确定性有限自动机（DFA）或带输出的有限自动机（DFAO）来验证性质或计算数量。
线性表示 (Linear Representations)： 对于计数序列 $d(n)$ ，利用 $k$ -regular 序列的性质，构建线性表示（矩阵、向量）来推导递推关系和渐近界。
同步序列 (Synchronized Sequences)： 引入“运行和同步”（running-sum synchronized）的概念，使得自动机能够同时处理索引 $n$ 和序列前缀和（即括号平衡度），从而判定 Dyck 性质。

3. 主要贡献与结果

3.1 幂次避免与嵌套层级的界限

定理 2.1： 如果一个二元词是 **$7/3 $-power-free**（无指数$ $- p o w er - f r ee * * （无指数$ \ge 7/3 $的幂）且是 Dyck 词，则其嵌套层级$ $的幂）且是 D y c k 词，则其嵌套层级$ N(x) \le 3$。
- 意义： 证明了 $7/3$ 是一个临界值。
定理 2.2 & 推论 2.3： 给出了无重叠（overlap-free）Dyck 词的显式刻画，并证明了存在任意长的无重叠 Dyck 词，其嵌套层级分别为 2 和 3。
定理 2.9： 对于任意嵌套层级 $L$ $L$ ，都存在 **$7/3^+ $-power-free**（无指数$ $- p o w er - f r ee * * （无指数$ > 7/3$ 的幂）的 Dyck 词。
- 构造方法： 利用两个特定的同态 $g$ （6-均匀）和 $f$ （38-均匀），通过迭代 $f(g^t(2))$ 构造出嵌套层级为 $2t+2$ 的 Dyck 词。
- 验证： 使用 Walnut 进行了大规模计算（消耗 130GB 内存），验证了构造出的无限词 $f(g^\omega(0))$ 是 $7/3^+$-power-free。

3.2 Thue-Morse 序列中的 Dyck 因子

定理 3.1 (显式刻画)： Thue-Morse 序列 $t$ 的 Dyck 因子恰好是形如 $h(x)$ 的词，其中 $x$ 是 Thue-Morse 序列相关的一个三元序列 $s$ 的因子， $h$ 是一个特定的同态映射。
定理 4.1 & 4.5： 证明了对于任何“运行和同步”的 $k$ $k$ -自动序列，其 Dyck 因子的数量序列 $d(n)$ $d (n)$ 是 $k$ -regular 的。
- 这意味着 $d(n)$ 满足线性递推关系，可以通过有限状态自动机计算。
定理 5.2 (上界)： 对于 Thue-Morse 序列，长度为 $2n $的 Dyck 因子数量$ $的 D y c k 因子数量$ d(n) $满足$ $满足$ d(n) \le n$。
- 紧确性：当 $n = 3 \cdot 2^i$ 时， $d(n) = n$ 。
定理 5.3 (下界)： $d(n) \ge n/2$ $d (n) \geq n /2$ 。对于奇数 $n$ $n$ ， $d(n) \ge (n+3)/2$ $d (n) \geq (n + 3) /2$ 。
- 紧确性：当 $n = 2^i$ ( $i \ge 2$ ) 时， $d(n) = n/2$ 。
定理 5.4 (平均值)： $d(n)$ 的平均值渐近于 $\frac{19}{24}n$ 。
序列数据： 计算了 $d(n)$ 的前几项（OEIS A345199），并给出了秩为 7 的线性表示矩阵，极大地提高了计算效率。

3.3 其他序列中的 Dyck 词

Fibonacci 词 (Prop 6.1)： 仅包含两个非空 Dyck 因子：01 和 0101。
周期加倍序列 (Prop 6.2)： 仅包含 01, 0101, 010101。
Rudin-Shapiro 序列 (Theorem 6.3)： 存在任意大嵌套层级的 Dyck 因子。
- 通过归纳法证明了特定子段 $x_n$ 是嵌套层级为 $2^{n+1}-1$ 的 Dyck 词。
Rudin-Shapiro 的 Dyck 长度集合 (Theorem 6.4)： 存在长度为 $n$ $n$ 的 Dyck 因子的 $n$ $n$ 的集合是 4-自动（也是 2-自动）的。
- 由于 Rudin-Shapiro 序列在基 2 下不是运行和同步的，作者利用其在基 4 下的同步性质，构建了接受长度为 $n$ 的 Dyck 因子的自动机（见图 3）。
折纸序列 (Conjecture 6.5)： 提出了关于折纸序列中 Dyck 因子长度的猜想：存在长度为 $n$ 的 Dyck 因子当且仅当 $n = 2^k - 2^i$ ($0 \le i < k$)。

4. 技术细节与工具应用

Walnut 的使用： 论文大量使用了 Walnut 进行定理证明。例如，验证 $7/3^+ $-power-free 性质、构建接受 Dyck 因子的自动机、计算$ d(n)$ 的线性表示等。
线性表示的最小化： 利用 Schützenberger 算法将秩为 29 的初始线性表示最小化为秩为 7，使得 $d(n)$ 的计算非常高效。
同态构造： 通过精心设计的同态（如 $g$ 和 $f$ ），在保持 Dyck 性质的同时，精确控制嵌套层级的增长和幂次避免性质。

5. 研究意义

理论界限的确定： 明确了 $7/3$ 作为 Dyck 词嵌套层级受限的临界指数。低于此值，层级有界；高于此值，层级可任意大。这加深了对模式避免与括号结构之间关系的理解。
自动序列性质的扩展： 将自动序列的研究从传统的模式避免扩展到了 Dyck 结构（括号平衡）的计数与判定，证明了在特定同步条件下，Dyck 因子的计数序列具有正则性（ $k$ -regular）。
算法与工具的结合： 展示了形式化验证工具（Walnut）在解决复杂组合数学问题（如证明无限序列的性质、计算复杂计数序列）中的强大能力，为后续研究提供了范式。
具体序列的完整刻画： 对 Thue-Morse、Fibonacci、Rudin-Shapiro 等经典序列中的 Dyck 结构给出了精确的数学描述（包括显式刻画、计数公式、自动机描述），填补了相关领域的空白。

总结： 该论文通过结合组合构造、自动机理论和形式化验证，系统地解决了 Dyck 词在各类自动序列中的存在性、结构刻画及计数问题，揭示了幂次避免与括号嵌套深度之间的深刻联系。