Complexity of Linear Subsequences of $k$-Automatic Sequences

该论文通过构建识别基本关系的$k$-自动机并分析其状态复杂度，建立了$k$-自动序列内部序列的子词复杂度与线性子序列状态复杂度之间的联系，解决了 Zantema 和 Bosma 关于最高位优先格式下线性子序列的未决问题，并探讨了利用 Büchi 算术构造相关自动机及执行序列操作时的状态与时间复杂度。

要点

这是一篇关于**“自动机（Automata）”和“序列（Sequences）”的学术论文。为了让你轻松理解，我们可以把这篇论文想象成是在研究“如何用最简单的机器（自动机）来预测或生成复杂的数字规律”**。

想象一下，你有一个**“魔法预言机”**（这就是论文里的自动机）。

• 你给它输入一个数字（比如用二进制或十进制表示）。
• 它根据内部的规则，吐出一个结果（0 或 1，或者别的符号）。
• 如果这个机器能用有限个状态（就像只有有限个开关）就能预测无限长的数字序列，那这个序列就叫**"k-自动序列”**。

这篇论文主要做了三件大事，我们可以用生活中的比喻来解释：

1. 给机器“瘦身”：研究状态复杂度

核心问题： 这个预言机需要多少个“开关”（状态）才能工作？

• 比喻： 想象你要设计一个自动售货机。如果它只能卖一种饮料，它只需要很少的按钮（状态）。但如果它要处理复杂的逻辑，比如“如果你买了可乐，下次买雪碧就打折”，它就需要更多的内部记忆（状态）。
• 论文发现： 作者们研究了当输入数字的格式改变（比如从“最高位在前”变成“最低位在前”）时，或者当我们要对序列进行**“线性变换”**（比如只取第 1、3、5、7...项，或者第 2、4、6...项）时，这个机器需要增加多少“开关”。
• 关键突破： 他们发现，如果你把序列里的数字每隔 $n$ 个取一个（线性子序列），新机器需要的开关数量，竟然和原序列中**“不同的小片段（子串）”的数量**有直接关系。这就像说：如果你想知道每隔 5 步走一次会看到什么风景，你只需要知道原路上一共出现过多少种不同的“5 步风景组合”就够了。

2. 解决了一个“老难题”

背景： 之前有两位学者（Zantema 和 Bosma）提出了一个问题：如果我们把序列里的数字每隔 $n$ 个取一个，而且输入格式是“最高位在前”（就像我们平时读数字，先读亿位，再读万位），这个新机器到底需要多大？

• 比喻： 就像大家一直争论：如果我要从一条长龙里每隔 10 个人挑一个出来排队，我到底需要准备多大的候场区？
• 论文贡献： 作者们给出了精确的答案，并建立了一个新的公式，把“候场区的大小”（状态复杂度）和“龙里不同的小队形数量”（子串复杂度）联系了起来。他们还特别研究了著名的Thue-Morse 序列（一种在数学和自然界中都很神奇的 0 和 1 的排列），算出了它经过各种变换后，机器到底需要多大。

3. 算算“造机器”要花多少时间

背景： 光知道机器需要多大还不够，我们还得知道造出这个机器需要多久。

• 比喻： 就像你不仅要知道盖一栋大楼需要多少块砖，还要知道用现在的建筑技术，盖完这栋楼需要多少天。
• 论文贡献： 作者们模拟了使用一种叫**"Büchi 算术”**（一种处理数字逻辑的数学工具，类似于给机器写代码）的方法，来计算构建这些机器需要的时间。
  • 他们发现，对于某些简单的操作（比如加法），造机器很快。
  • 但对于复杂的操作（比如乘法或取子序列），随着数字变大，造机器的时间会呈指数级增长，或者至少是多项式增长。
  • 这就像告诉软件开发者：如果你用某种特定的逻辑语言去写一个自动识别数字规律的程序，当数字很大时，编译这个程序可能会非常慢，你需要提前规划好时间。

总结：这篇论文有什么用？

1. 理论价值： 它揭示了数字规律（自动序列）的内在结构。它告诉我们，序列的“复杂性”（有多少种不同的片段）直接决定了处理它的“机器”需要多复杂。
2. 实际应用： 在计算机科学中，处理无限序列（比如加密算法、数据压缩、甚至某些生物基因序列分析）时，我们需要高效的自动机。这篇论文告诉工程师们：
   • 如果你要处理“每隔几个取一个”的数据，你的程序内存（状态）大概需要多大。
   • 如果你用特定的逻辑工具（如 Walnut 软件）去生成这些规则，程序运行需要多久，会不会卡死。

一句话概括：
这篇论文就像是一份**“自动机建筑指南”**，它告诉我们在处理各种数字规律时，如何用最少的“开关”（状态）来构建机器，以及建造这些机器需要花费多少“工时”（时间），特别是当我们想要从长序列中“挑挑拣拣”（取子序列）的时候。

技术摘要

这篇论文题为《k-自动序列线性子序列的复杂度》（Complexity of Linear Subsequences of k-Automatic Sequences），由 Delaram Moradi、Narad Rampersad 和 Jeffrey Shallit 撰写。文章主要研究了在 $k$ 进制输入下，自动序列（Automatic Sequences）的线性子序列（Linear Subsequences）的状态复杂度（State Complexity），以及利用 Büchi 算术构建识别这些序列和关系的自动机的计算复杂度。

以下是对该论文的详细技术总结：

1. 研究背景与问题定义

• k-自动序列：由 Cobham 引入，指可以通过确定性有限自动机输出（DFAO）生成的序列，输入为整数 $i$ 的 $k$ 进制表示。
• 核心问题：
  1. 状态复杂度：给定一个 $m$ 状态的 $k$-自动序列 $h(i)$，其线性子序列 $h(ni+c)$（其中 $n, c$ 为常数）生成所需的最小 DFAO 的状态数是多少？
  2. 输入格式差异：区分最高位优先（msd-first）和最低位优先（lsd-first）输入格式下的复杂度差异。
  3. 构建复杂度：在使用 Büchi 算术（如 Walnut 软件系统）将逻辑表达式转换为自动机时，中间自动机的大小和运行时间是多少？
• 现有缺口：Zantema 和 Bosma 之前的研究解决了 lsd-first 输入下的部分问题，但 msd-first 输入下的线性子序列状态复杂度上界是一个开放问题。

2. 方法论

论文采用了以下主要方法：

• 自动机构造：针对加法、乘法等算术关系，以及序列的移位和线性子序列变换，构造具体的 DFAO。
• 子词复杂度（Subword Complexity）关联：建立自动序列的状态复杂度与其内部序列（Interior Sequence）的子词复杂度之间的数学联系。
• Büchi 算术解释：分析通过逻辑公式（如 $\exists y, \forall u$ 等）构建自动机的过程，评估乘积构造（Product Construction）、投影（Projection）和子集构造（Subset Construction）带来的状态爆炸和时间开销。
• Myhill-Nerode 定理的变体：用于证明特定序列（如 Thue-Morse 序列）状态复杂度的下界。

3. 主要贡献与结果

3.1 算术关系识别的复杂度

• 加法关系：证明了识别 $[x]_k + [y]_k = [z]_k$ 的自动机仅需 2 个状态（对 msd-first 和 lsd-first 均成立）。
• 常数加法/减法：对于 $[x]_k + c = [y]_k$，证明了状态数为 $O(\log_k c)$。
• 精确状态数：针对 msd-first 输入，给出了识别 $[x]_k + c = [y]_k$ 的最小 DFA 状态数的精确公式（定理 6），该公式依赖于 $c$ 的 $k$ 进制表示长度、$k$ 进位制估值 $\nu_k(c)$ 以及前导位特征。

3.2 线性子序列的状态复杂度（核心贡献）

这是论文最重要的部分，解决了 Zantema 和 Bosma 提出的开放问题。

• msd-first 输入下的新上界：
  • 定理 10 建立了线性子序列 $h(ni+c)$ 的状态复杂度与原始序列内部序列 $h'$ 的子词复杂度 $\rho_{h'}$ 之间的直接联系。
  • 若 $c < n$，状态数上界为 $\rho_{h'}(n)$。
  • 若 $c \ge n$，状态数上界为 $\rho_{h'}(c+1)$。
  • 结合子词复杂度的已知上界（$\rho_{h'}(n) \le k^n m^2$），得到了具体的多项式上界（推论 11）。
• lsd-first 输入的下界：
  • 证明了对于 lsd-first 输入，移位序列 $h(i+1)$ 的状态复杂度下界可达 $2m-1$（定理 8），修正了之前认为$2m$ 是紧确界的猜测。
• Thue-Morse 序列的应用：
  • 将上述理论应用于著名的 Thue-Morse 序列。
  • 定理 15 给出了生成 $(t(ni))_{i \ge 0}$ 的最小自动机状态数的精确公式：$\rho_t(n/\nu_2(n))$。
  • 定理 21 证明了对于移位序列 $(t(i+c))_{i \ge 0}$，其状态复杂度下界至少为 $c^{0.694}$（基于斐波那契数列增长），表明其增长速度快于对数级。

3.3 基于 Büchi 算术的构建复杂度分析

论文分析了在 Walnut 等系统中，通过逻辑表达式构建自动机的实际运行时间：

• 常数识别：识别 $[x]_k = c$ 的自动机构建时间为 $O((\log^2 c)(\log \log c))$。
• 线性变换：构建识别 $n[x]_k + c = [z]_k$ 的自动机，时间复杂度为 $O(\log^2 c \log \log c + n \log^2 n + n \log c \log(n \log c))$。
• 序列变换：给定 $m$ 状态 DFAO 生成 $h(i)$，构建生成 $h(ni+c)$ 的 DFAO 的时间复杂度为：
  $$O(\log^2 c \log \log c + n \log^2 n + n \log c \log(n \log c) + m^2(n+c) \log(m^2(n+c)))$$
  这表明虽然中间状态可能较多，但在特定条件下（如 $n, c$ 较大时），构建过程是可行的，且主要开销在于子集构造和最小化步骤。

4. 关键发现与意义

1. msd-first 与 lsd-first 的本质差异：
   论文明确指出，虽然算术运算在两种格式下都有有限自动机，但子序列的复杂度行为截然不同。在 lsd-first 中，有限状态转换器可以处理加法和常数乘法，但在 msd-first 中则不行，导致 msd-first 下子序列的状态复杂度分析更为复杂，且与子词复杂度紧密相关。

2. 状态复杂度与子词复杂度的桥梁：
   定理 10 是理论上的重大突破，它将“线性子序列的状态数”这一自动机理论问题，转化为“内部序列的子词数”这一组合数学问题。这不仅提供了上界，还揭示了自动序列结构的深层性质。

3. 解决开放问题：
   论文成功回答了 Zantema 和 Bosma 关于 msd-first 输入下线性子序列状态复杂度的问题，并给出了具体的构造方法和上界。

4. 对工具开发的指导意义：
   通过分析 Büchi 算术实现中的中间状态大小和运行时间，论文为 Walnut 等自动序列验证工具的用户提供了性能预期，解释了为什么某些复杂表达式会导致构建时间过长或内存溢出，并指出了优化方向。

5. 结论与未来工作

论文总结了对 $k$-自动序列线性子序列状态复杂度的全面分析，并给出了精确的构造算法和复杂度界限。作者指出，对于某些特定序列（如 Thue-Morse），状态复杂度的下界可能远高于简单的对数级。

遗留问题（Open Problems）：

• 寻找一类自动序列，其线性子序列的状态复杂度达到 $Cnm^2$ 级别（即推论 11 的上界是否紧确）。
• 寻找生成 $(t(i+c))$ 的最小自动机状态数的精确公式。
• 研究识别“子串相等”关系（即 $h([x]..[x]+z-1) = h([y]..[y]+z-1)$）的自动机状态复杂度和构建时间。

总体而言，这篇论文在形式语言与自动机理论领域做出了重要贡献，特别是在连接自动序列的结构性质（子词复杂度）与计算性质（状态复杂度）方面，并为相关软件工具的性能分析提供了坚实的理论基础。