技术摘要：具有简洁且机器无关轨迹的语言识别

1. 问题陈述

本文探讨了极限下的语言识别问题，这是由 Gold (1967) 最初提出的一个框架。在这种设定下，算法试图通过观察目标语言 $K$ 的字符串枚举，从一个可数候选语言集合 $\mathcal{L} = \{L_1, L_2, \dots\}$ 中识别出目标语言。Gold 的原始定理指出，对于大多数非平凡的语言族，如果不引入额外信息，极限下的识别是不可能的。

近期的研究试图通过引入计算轨迹或注释（例如 Papazov 和 Flammarion, 2025; Bhattamishra 等人, 2026; Peng 等人, 2026）来克服这些负面结果。这些工作认为，如果训练数据通过底层机器模型（例如有限自动机的状态或图灵机的配置）生成的轨迹进行增强，识别将变得可能。然而，这些现有方法存在两个局限性：

1. 机器依赖性： 它们需要知道生成该语言的具体机器模型。
2. 字母表大小： 轨迹通常需要庞大的字母表（例如，机器状态的全集或词汇表的幂集），这对于大规模模型而言是不切实际的。

作者提出了疑问：我们能否使用满足以下条件的轨迹来实现语言识别的正向结果：(a) 独立于任何底层机器模型，且 (b) 定义在小规模、简洁的字母表之上？

2. 方法论与定义

轨迹模型

作者定义了一个基于有限颜色集（即“调色板”）$P$ 的轨迹着色函数 $c$。对于字符串 $x = x_1 x_2 \dots x_n$，其颜色轨迹定义为应用于该字符串每个前缀的颜色序列：
$$\text{trace}_c(x) := (c(\epsilon), c(x_{\le 1}), c(x_{\le 2}), \dots, c(x_{\le n}))$$
其中 $x_{\le i}$ 是长度为 $i$ 的前缀。与基于机器的轨迹不同，此定义适用于任何语言，而不假设存在生成自动机。

识别条件

本文确立了对于集合 $\mathcal{C}$，使用颜色轨迹进行极限下识别的充分必要条件（定理 1）。该条件推广了 Angluing 的“特征集”（tell-tale sets）：对于每一个语言 $L \in \mathcal{C}$，必须存在一个有限子集 $T_L \subseteq L$，使得对于任何真子集 $L' \subset L$，要么 $L'$ 不包含 $T_L$，要么存在一个字符串 $x \in L'$，使得 $x$ 在 $L'$ 下的轨迹与在 $L$ 下的轨迹不同。

为了简化构造，作者专注于一个更强的**“可区分着色条件”**：对于任何满足 $L, L' \in \mathcal{C}$ 且 $L \subsetneq L'$ 的情况，存在一个 $x \in L$，使得 $\text{trace}_{c_L}(x) \neq \text{trace}_{c_{L'}}(x)$。如果该条件成立，则不需要特征集，且识别是保证实现的。

3. 核心贡献与结果

A. 通用语言集合 (定理 3)

主要结果表明，对于任何基于大小为 $k$ 的有限字母 $\Sigma$ 的可数语言集合，都存在使用大小为 $k+1$ 的调色板的轨迹着色函数，并满足可区分着色条件。

• 构造： 着色函数 $c_L(x)$ 根据字符串 $x$ 相对于语言 $L$ 的两个属性进行定义：
  1. $IsAccept_L(x)$：是否 $x \in L$。
  2. $NextLive_L(x)$：字符 $a \in \Sigma$ 的计数，使得 $xa$可以被扩展为$L$ 中的字符串。
     颜色分配为 $IsAccept_L(x) + NextLive_L(x)$（对于无法扩展到 $L$ 的字符串，默认值为 1）。
• 意义： 这种构造是机器无关的（它仅依赖于语言集合本身），并且使用的字母表大小与输入字母表大小呈线性关系，独立于任何底层模型的复杂度。

B. 调色板大小的紧致性

• 下界： 作者证明了对于二进制字母表（$k=2$），2 种颜色不足以满足所有语言集合的可区分着色条件（命题 8）。一个特定的包含 5 个语言的有限集合需要 3 种颜色。因此，在二进制字母表的通用情况下，$k+1$ 是最优的。
• 自动机的状态着色： 对于有限自动机集合，作者定义了状态着色函数（将状态映射到颜色）。他们证明了在这一设定下，$k+1$ 种颜色对于可区分条件也是必要且充分的（引理 4）。

C. 正则语言 (定理 5)

针对正则语言这一特殊情况，本文提出了一个重要的改进。

• 结果： 如果集合 $\mathcal{C}$ 由无限正则语言组成，则可以使用仅 2 种颜色实现极限下的识别。
• 机制： 作者构造了用于这些语言的 DFA 序列，并归纳地分配状态颜色。对于每个语言 $L_i$，他们选择特定的“活跃”状态，以将 $L_i$ 与出现在枚举中较早出现的任何超集 $L_j$ ($j < i$) 区分开来。语言的无限性确保了存在足够的足够状态来进行这种区分。
• 最优性： 2 种颜色是最优的，因为 1 种颜色不提供任何信息（等同于没有轨迹），且 Gold 的结果表明，如果没有轨迹，某些无限正则语言集合是无法识别的。

D. 对损坏的鲁棒性

本文将这些结果扩展到了轨迹可能被损坏的场景（第 3.1 节）。

• 鲁棒着色引理： 对于损坏预算 $\ell$（汉明距离），作者表明，大小为 $O(k \cdot 2^\ell)$ 的调色板足以确保极限下的识别。
• 状态着色： 对于带有损坏轨迹的正则语言，大小为 $O(k \cdot 2^\ell)$ 的调色板是充分的，而 $k \cdot 2^{\ell-1}$ 是必要的。

4. 意义与主张

本文声称解决了先前关于计算轨迹研究留下的两个基本开放问题：

1. 机器无关性： 它证明了正向识别结果并不需要访问底层的生成机器模型；轨迹可以直接从语言结构中定义。
2. 简洁性： 它证明了可以通过非常小的标记字母表（相对于输入字母表为线性关系，甚至对于正则语言是常数级）来实现识别，这与之前需要指数级或依赖于状态的字母表的著作形成了对比。

作者强调，他们的方法是信息论层面的。虽然他们指明了着色函数和识别算法的存在，但并未声称在通用情况下具有计算效率（指出对于任意语言，成员判定是不可判定的）。其重点在于利用最小的注释开销实现识别在理论上的可能性。

文章最后指出，最近的一项独立发展（Charikar 等人, 2026）显示，对于无限语言集合，即使使用“终止”着色（一次性对整个字符串着色），通过涉及超限递归的非构造性方法，2 种着色也是可能的，这凸显了本文所提出的构造性 $k+1$ 界限仍然是自然的、机器无关的标准。