The memory of $\omega$-regular and BC($\Sigma_2^0$) objectives

技术摘要：$\omega$-正则与 $BC(\Sigma^0_2)$ 目标的记忆（Memory）

问题陈述
在（可能为无限图的）两人零和无限持续博弈的背景下，目标 $W$ 的记忆（memory）定义为最小整数 $k$，使得在任何 Eve 拥有必胜策略的游戏中，她都拥有一种由最多具有 $k$ 个记忆状态的有限自动机实现的必胜策略。虽然 $\omega$-正则目标的位势性（positionality，即记忆 $k=1$）的判定性最近已被建立，但计算 $\omega$-正则目标记忆的通用问题仍然是一个开放问题。具体而言，目前尚不清楚计算记忆是否是可判定的，也不清楚在有限游戏图上的所需记忆是否与在任意无限图上的所需记忆一致。此外，关于目标并集下的记忆行为（广义 Kopczyński 猜想）也是一个关于需要记忆的目标的开放问题。

方法论
作者引入了一种基于 $k$-wise $\varepsilon$-completable 自动机的对具有记忆 $\le k$ 的目标的全新刻画。这种方法将用于位势性的通用图（universal graphs）和 $\varepsilon$-completable 自动机的概念扩展到了有限记忆的设定中。

1. $k$-wise $\varepsilon$-completable 自动机： 如果一个自动机的状态（被划分为 $k$ 个记忆链）可以通过增加 $\varepsilon$-转移来构成如下结构：对于每个偶数优先级 $x$ 和记忆状态 $m$，具有记忆 $m$ 的状态是全序的。具体而言，对于任何状态对 $(q, m)$ 和 $(q', m)$，要么存在从 $q$ 到 $q'$ 且优先级为 $x$ 的 $\varepsilon$-转移，要么存在从 $q'$ 到 $q$ 且优先级为 $x+1$ 的转移。
2. 提取引理（Extraction Lemmas）： 核心技术创新在于从无限或大型有限图中提取同质子结构。
   • 对于无穷情形（第 3.1 节），作者使用组合引理（引理 12）从通用图 $S_\kappa^d$（其中 $\kappa = 2^{\aleph_0}$）中提取“处处共尾”（everywhere cofinal）树，从而确保状态间的支配关系在各层级间是均匀的。
   • 对于有限情形（第 3.2 节），他们将这些提取技术应用于有限自动机，利用“正则词”（regular words）和同步子词（引理 24）来处理有限分支，并确保存在一个满足 $\varepsilon$-completeness 条件的 $k$-blowup。
3. 级联乘积（Cascade Products）： 证明过程高度依赖于将确定性自动机与通用图（或签名树）进行级联乘积，以编码所有可能的接受行为，随后构造一个保留语言且满足 $\varepsilon$-completeness 条件的 $k$-blowup。

核心贡献与结果

1. 刻画定理（定理 7）： 本文建立了一个关于 $BC(\Sigma^0_2)$ 目标（由潜在无限确定性奇偶自动机识别）具有记忆 $\le k$ 的充要条件。以下各项等价：

   • 该目标在规模 $\le 2^{2^{\aleph_0}}$ 的博弈上具有记忆 $\le k$。
   • 识别该目标的每个自动机都允许一个具有 $k$-blowup 且是 $k$-wise $\varepsilon$-complete 的自动机。
   • 存在一个是 $k$-wise $\varepsilon$-completable 且识别该目标的确定性 $k$-自动机。
   • 对于每个基数 $\kappa$，存在一个良基且 $k$-wise $\varepsilon$-complete 的 $(\kappa, W)$-通用图。
   • 该目标在任意博弈上具有记忆 $\le k$。

2. NP 可判定性（推论 9）： 对于 $\omega$-正则目标（有限自动机），记忆（以及染色记忆/chromatic memory）可以在 NP 内计算。算法通过猜测候选记忆大小 $k$、一个规模 $\le kn$ 的确定性自动机以及一个 $\varepsilon$-completion，然后在多项式时间内验证语言包含关系。在此工作之前，开放型 $\omega$-正则目标的记忆判定性是未知的。

3. 有限到无限的提升（推论 8）： 本文证明了对于 $\omega$-正则目标，在有限游戏图上所需的记忆与在任意（无限）游戏图上所需的记忆是相同的。这解决了 Vandenhove 关于 $\omega$-正则情况的猜想。

4. 对并集的封闭性（定理 10）： 作者证明了针对 $BC(\Sigma^0_2)$ 目标的强形式广义 Kopczyński 猜想。如果 $W_1$ 和 $W_2$ 分别是具有记忆 $k_1$ 和 $k_2$ 的目标，且 $W_2$ 是前缀递增的，那么 $W_1 \cup W_2$ 的记忆至多为 $k_1 \cdot k_2$。该界限被证明是紧致的。

5. 染色记忆（Chromatic Memory）： 所有结果同样适用于染色记忆，即策略只能根据所见边的颜色而非边本身来更新其记忆状态。

意义与主张
本文声称提供了第一个已知的关于 $\omega$-正则目标的（染色）记忆刻画，超越了先前受限的类别（如 Muller 或闭目标）。通过确立记忆计算属于 NP 类，本文将该问题从一个开放的判定性问题转变为一个可处理的复杂度类。作者强调，其证明技术涉及从无限图中提取结构以及操作序数，这与以往处理位势性的技术（依赖于连续的自动机变换）截然不同，且显著更短。

这些结果将记忆分析的范围扩展到了更广泛的 $BC(\Sigma^0_2)$ 语言类，其中包括非 $\omega$-正则目标（如能量博弈和平均收益博弈）以及由确定性 $\omega$-图灵机识别的语言。论文明确指出，虽然本文恢复了 $\omega$-正则目标的有限-到-无限提升，但并未恢复记忆 $k > 1$ 时的“1-对-2-玩家提升”（不对称提升），因为存在反例。

局限性与开放问题
作者承认，虽然他们确立了 NP 内的可判定性，但确切的复杂度（特别是是否在 P 内）仍然是一个开放问题。他们还指出，由于提取引理难以推广，其方法目前无法扩展到 $\Delta^0_3$ 类。关于 $\omega$-正则目标的染色记忆是否存在不对称提升的问题仍然是一个开放问题。