用 Alice 与 Bob 重新理解“正则性”：一篇关于 Nerode 风格刻画的统一尝试

导语

“正则语言”通常让人想到有限自动机、正则表达式，以及 Myhill–Nerode 定理中关于有限等价类的经典刻画。但当我们不只判断一个词是否属于某个语言，而是要计算一个取值更丰富的函数时，类似的正则性该如何定义？arXiv 新论文《Regularity as seen by Alice and Bob》尝试给出一个统一视角：把输入拆成两段，交给通信复杂性中常见的两位角色 Alice 和 Bob，让他们通过有限而受限的消息交换来完成计算。

核心要点

• 研究对象更一般：论文考虑的不是单纯的布尔语言，而是形如 Σ* → D 的函数。其中 Σ 是有限字母表，D 可以是任意输出域。这让问题从“接受或拒绝”扩展到“输出某个结构化结果”。
• 通信模型承担正则性刻画：一个输入词 w 被切分为 w = w1w2，Alice 得到前缀，Bob 得到后缀。两方协作，交换常数数量的消息，并且对每一种允许的切分都必须算出正确函数值。
• 消息形式受到限制：每条消息要么是输出域中的一个元素，要么来自某个有限信号集合。这种设计保留了有限自动机式“有限控制”的味道，同时允许非布尔输出。
• 连接已知计算模型：作者表示，对于若干具体输出域，该模型与已有的计算模型相吻合。这意味着它不是孤立定义，而可能是把多个已有正则性概念放到同一框架下的抽象层。
• 进一步走向无限字母表：论文还把框架扩展到 nominal sets 语境中的无限字母表，并讨论其在“带原子的词语言”上的表达能力。

意义与影响

这项工作的重要性不在于提出一个可直接部署的 AI 系统，而在于为形式语言、自动机理论和计算复杂性之间搭建更统一的语言。Nerode 风格刻画的价值，是把“可由有限机制识别”转化为结构性的等价关系或交互条件；而 Alice-Bob 模型则把这种结构性条件重新表述为“分布式观察下的可通信计算”。

对 AI 研究而言，这类基础理论可能显得遥远，却与模型、程序和语言处理中的可识别结构密切相关。尤其是在自然语言、程序语言、符号系统以及带有名称、变量或绑定结构的数据中，传统有限字母表假设经常不够自然。论文对 nominal sets 和带原子的词的讨论，正触及这类更复杂符号对象的理论基础。

当然，素材显示这篇论文仍以理论建模与对应性证明为主，并包含对其他输出域的进一步猜想。其价值更适合被理解为一个统一框架的提出，而非某个单点算法突破。若后续工作能验证更多输出域上的对应关系，这一视角有望成为理解“广义正则性”的重要工具。

来源：arXiv