技术摘要：由 Alice 和 Bob 观察到的正则性

1. 问题陈述

本文针对输出域超出布尔情况的函数，旨在解决缺乏统一、原则性“正则性”（regularity）表征的问题。正则语言（函数 $f: \Sigma^* \to \{true, false\}$）已通过等价模型（如有限自动机、正则表达式和 Myhill-Nerode 定理）得到了充分理解，但对于其他定义域的情况，现状却显得碎片化：

• 字符串到字符串的函数： 存在多个互不等价的类别（有理函数、正则函数、多正则函数），且对于哪一种才构成“真正的”正则函数并无共识。
• 字符串到数字的函数： 存在不同的模型，如加权自动机（线性更新）和多项式自动机（多项式更新），且关于哪种模型捕捉了正确的正则性概念，其关系尚不明确。
• 无限字母表： 对于无限字母表上的语言（其中字母仅在相等性方面可比较），将有限自动机模型提升到该领域时，产生了十七个两两不等价的模型，缺乏一个统一的原则。

核心问题在于寻找一个单一的、与机器无关的框架，用以表征跨越这些多样化输出域和输入设置的正则性。

2. 方法论：协议模型

作者提出了一个基于通信复杂度的统一模型，具体改编自 Hauser [Hau89] 的工作。该模型涉及两个协作方：Alice 和 Bob，他们计算一个函数 $f: \Sigma^* \to D$，其中 $D$ 是任意输出域。

关键机制：

• 输入拆分： 输入字符串 $w$ 被任意拆分为 $w = w_1w_2$。Alice 持有 $w_1$，Bob 持有 $w_2$。
• 常数通信： 双方交换常数数量的消息（与输入长度无关）。
• 消息类型： 消息由以下部分组成：
  1. 信号（Signals）： 来自有限集合（比特或有限符号）的元素。
  2. 定义域元素（Domain Elements）： 来自输出域 $D$ 的元素。
• 黑盒限制： 至关重要的一点是，包含 $D$ 中元素的消息不能被直接“读取”或检查。它们只能使用定义域的预定义操作进行操作（例如，对于域（field）而言是加法和乘法，对于字符串而言是拼接）。这防止了将整个输入字符串编码进单个定义域元素中。
• 拆分不变性（Split Invariance）： 协议对于同一输入字符串 $w$ 的任何拆分 $w = w_1w_2$ 必须产生相同的输出。
• 非均匀性（Non-Uniformity）： Alice 和 Bob 拥有无限的计算能力；限制仅在于通信带宽和黑盒约束。

论文将此形式化为一个协议，并研究了其在不同输出域 $D$ 下的表达能力。

3. 主要贡献与结果

3.1 布尔输出 ($D = \{true, false\}$)

论文重新确立了一个已知的结论（最初由 Hauser [Hau89] 提出）作为基准：

• 定理 1.1： 一个语言能被协议计算，当且仅当它是正则的。
• 意义： 这证实了该模型捕捉了标准的正则性，并为泛化提供了基础。其证明依赖于将多轮协议归约为单轮协议，并应用 Myhill-Nerode 定理。

3.2 域输出 ($D$ 为一个域/Field)

这是本文的主要贡献之一。

• 定理 1.2： 函数 $f: \Sigma^* \to D$（其中 $D$ 是一个域）能被协议计算，当且仅当它能被 $D$ 上的加权自动机计算。
• 方法论： 证明过程将一般协议归约为标量积协议（即 Alice 和 Bob 分别计算向量 $\sigma_A(w_1)$ 和 $\sigma_B(w_2)$，输出为它们的点积）。随后调用 Fliess 定理 [Fli74]，该定理通过 Hankel 矩阵的有限秩来表征加权自动机。
• 洞察： 拆分不变性约束强制执行了线性。尽管协议允许多项式操作（通过组合），但拆分不变性的要求将其表达能力限制在了线性映射，排除了通用的多项式自动机。
• 局限性： 该等价性在域（fields）下成立。对于一般的半环（例如自由幂等半环），协议可能比加权自动机更强大（例如，它们可以计算字符串反转，而这在所述半环中不是有理关系）。

3.3 字符串输出 ($D = \Gamma^*$)

论文研究了字符串到字符串的函数，其中定义域操作为拼接。

• 猜想 1.3： 一个字符串到字符串的函数能被协议计算，当且仅当它能被带有输出的双向确定性自动机（传统的正则函数定义）计算。
• 提供的证据：
  • 蕴含关系 ($\Leftarrow$)： 已证明。双向确定性自动机可以通过交叉序列（crossing sequences）由协议模拟。
  • 蕴含关系 ($\Rightarrow$)： 未完全证明，但有强有力的证据支持：
    • 协议产生的输出具有线性大小，且可在线性时间内计算。
    • 协议在逆像下保持正则性（布尔连续性）。
    • 域连续性： 协议对与域上加权自动机的预组合是封闭的。
    • 一元情况： 该猜想在单字母输出字母表的情况下得到证明，此时有理函数与正则函数重合。
• 意义： 如果成立，这将为正则字符串到字符串函数提供一个与机器无关的表征，从而将其与较弱的有理函数和较强的多正则函数区分开来。

3.4 无限输入字母表

论文利用**名集合（nominal sets）和轨道有限集（orbit-finite sets）**的框架，将模型扩展到仅在相等性方面可比较字母的无限字母表（原子）。

• 猜想 6.5： 一个无限字母表上的语言能被轨道有限协议计算，当且仅当它被**无歧义寄存器自动机（unambiguous register automaton）**识别。
• 背景： 确定性寄存器自动机过于微弱（无法处理某些反转），而非确定性寄存器自动机则过于强大（可以检测协议无法检测的重复）。无歧义自动机（最多只有一个接受运行）被提议为“金发姑娘模型”（Goldilocks model，意指恰到好处的模型）。
• 结果：
  • 蕴起来关系 ($\Leftarrow$)： 已证明。作者构造了一个多轮协议，通过使用**轨道（orbits）和向日葵引理（sunflower lemma）**的一个变体，迭代地缩小可能的中间状态集来模拟无歧义自动机。
  • 蕴含关系 ($\Rightarrow$)： 通过加权轨道有限自动机提供证据。作者证明了一个轨道有限 Fliess 定理（定理 6.19），表明协议计算的函数具有轨道有限生成的左导数。这暗示协议是可判定的，并且位于加权模型与非确定性模型的交集内。
• 新颖性： 与有限字母表的情况不同，无限字母表的协议不能归约为单轮协议；交互性质是必不可少的。

4. 意义与主张

本文声称提供了一个超越特定自动机定义的统一正则性模型。其意义在于：

1. 机器无关性： 它通过通信约束（常数消息、黑盒操作）而非特定的状态转移结构来表征正则性。
2. 统一性： 它表明多样化的模型（加权自动机、双向确定性转换器、无歧义寄存器自动机）都是同一种底层原则的不同实例：即受限定义域操作下的常数信息流。
3. 新的表征： 它为加权自动机提供了机器无关的表征（定理 1.2），并为正则字符串到字符串函数（猜想 1.3）以及无歧义寄存器自动机（猜想 6.5）提出了表征。
4. 计算属性： 该模型自然地强制执行了诸如线性输出大小和可计算性等理想属性，而这些属性在其他转换器模型（如多正则函数）中并不总是得到保证。

作者对字符串到字符串及无限字母表的情况保持谦逊，将其作为由实质性证据（单向证明、一元情况和结构属性）支持的猜想而非完全解决的定理进行呈现。他们明确避免对一般半环或任意输出域提出主张，因为在这些情况下，“黑盒”限制可能不会产生行为良好的函数。