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

技術要約：$\omega$-正則および $BC(\Sigma^0_2)$ 目的関数のメモリ

問題提起
（潜在的に無限である）グラフ上の2人プレイ・ゼロサム無限持続ゲームの文脈において、目的関数 $W$ のメモリは、イーブ（Eve）が勝利戦略を持つあらゆるゲームにおいて、最大 $k$ 個のメモリ状態を持つ有限オートマトンによって実装可能な勝利戦略を彼女が保持できる最小の整数 $k$ として定義される。$\omega$-正則な目的関数の位置性（positionality, メモリ $k=1$）の決定可能性は最近確立されたが、メモリ $k$ を持つ目的関数のメモリを計算する一般的な問題は未解決のままであった。具体的には、メモリの計算が決定可能か、また、有限のゲームグラフ上で要求されるメモリが任意の無限グラフ上で要求されるメモリと一致するかどうかも不明であった。さらに、メモリを必要とする目的関数の和集合における挙動（一般化されたコプチンスキの予想）も未解決の問いであった。

手法
著者らは、$k$-wise $\varepsilon$-completable オートマトンに基づく、メモリ $\le k$ の目的関数の新しい特徴付けを導入している。このアプローチは、位置性のために以前使用されていたユニバーサルグラフおよび $\varepsilon$-completable オートマトンの概念を、有限メモリの設定へと拡張したものである。

1. $k$-wise $\varepsilon$-completable オートマトン: オートマトンが $k$-wise $\varepsilon$-complete であるとは、その状態（$k$ 個のメモリチェーンに分割されている）を $\varepsilon$ 遷移によって拡張することで、すべての偶数優先度 $x$ とメモリ状態 $m$ に対して、メモリ $m$ を持つ状態が全順序付けられた構造を形成できることを指す。具体的には、任意のペア $(q, m)$ および $(q', m)$ に対して、$x$ を優先度とする $q$ から $q'$ への $\varepsilon$ 遷移が存在するか、あるいは $x+1$ を優先度とする $q'$ から $q$ への遷移が存在する。
2. 抽出補題 (Extraction Lemmas): 本手法の核心的な技術的革新は、無限または大規模な有限グラフから均質な部分構造を抽出することにある。
   • 無限の場合 (Section 3.1): 著者らは、ユニバーサルグラフ $S_\kappa^d$（ここで $\kappa = 2^{\aleph_0}$）から「至る所で余係数的（everywhere cofinal）」な木を抽出するための組合せ論的補題（Lemma 12）を用い、レベル間での状態間の支配関係が均一であることを保証している。
   • 有限の場合 (Section 3.2): 著者らは、これらの抽出技術を有限オートマトンに適応させ、「規則的な語（regular words）」と同期された部分語（Lemma 24）を利用して、有限の分岐を扱い、$\varepsilon$-completable である $k$-blowup の存在を保証している。
3. カスケード積 (Cascade Products): 証明は、決定性オートマトンとユニバーサルグラフ（またはシグネチャ・ツリー）のカスケード積に大きく依存している。これは、あらゆる可能な受理挙動をエンコードするためであり、その後、言語を保持しつつ $\varepsilon$-完全性の条件を満たす $k$-blowup の構築へと続く。

主要な貢献と結果

1. 特徴付け定理 (Theorem 7): 本論文は、$BC(\Sigma^0_2)$ 目的関数（潜在的に無限の決定性パリティ・オートマトンによって認識される）がメモリ $\le k$ を持つための必要十分条件を確立している。以下の条件はすべて同値である：

   • その目的関数は、サイズ $\le 2^{2^{\aleph_0}}$ のゲームにおいてメモリ $\le k$ を持つ。
   • その目的関数を認識するすべてのオートマトンは、$k$-wise $\varepsilon$-complete である $k$-blowup を持つ。
   • 目的関数を認識する、決定的な $k$-オートマトンが存在し、それが $k$-wise $\varepsilon$-completable である。
   • 任意の基数 $\kappa$ に対して、整列可能かつ $k$-wise $\varepsilon$-complete である $(\kappa, W)$-ユニバーサルグラフが存在する。
   • その目的関数は、任意のゲームにおいてメモリ $\le k$ を持つ。

2. NPにおける決定可能性 (Corollary 9): $\omega$-正則な目的関数（有限オートマトン）に対して、メモリ（および彩色メモリ）は NP で計算可能である。アルゴリズムは、候補となるメモリサイズ $k$、サイズ $\le kn$ の決定性オートマトン、および $\varepsilon$-completion を推測し、多項式時間で言語包含を検証する。本研究以前は、開集合 $\omega$-正則目的関数のメモリの決定可能性は不明であった。

3. 有限から無限へのリフト (Corollary 8): 本論文は、$\omega$-正uralな目的関数において、有限のゲームグラフ上で要求されるメモリが、任意の（無限の）ゲームグラフ上で要求されるメモリと同一であることを証明している。これは、$\omega$-正則なケースにおけるヴァンデンホーフェの予想を解決するものである。

4. 和集合による閉包 (Theorem 10): 著者らは、$BC(\Sigma^0_2)$ 目的関数に関する一般化されたコプチンスキの予想の強い形式を証明している。もし $W_1$ と $W_2$ がそれぞれメモリ $k_1$ と $k_2$ を持つ目的関数であり、$W_2$ が接頭辞増加型（prefix-increasing）であるならば、$W_1 \cup W_2$ のメモリは高々 $k_1 \cdot k_2$ である。この境界はタイトであることが示されている。

5. 彩色メモリ (Chromatic Memory): すべての結果は、戦略がエッジそのものではなく、見たエッジの色に基づいてのみメモリ状態を更新できる彩色メモリにも同様に適用される。

意義と主張
本論文は、（Mullerや閉じた目的関数などの）以前の制限されたクラスを超えて、$\omega$-正則な目的関数の（彩色）メモリに関する初の既知の特徴付けを提供したと主張している。メモリ計算がNPに属することを確立することで、この問題を未解決の決定可能性問題から、扱い可能な複雑性クラスへと移行させた。著者らは、無限グラフからの構造の抽出や順序数の操作を含む証明手法が、従来の（逐次的なオートマトン変換に依存していた）位置性の研究とは異なり、著しく簡潔であることを強調している。

これらの結果は、メモリ解析の範囲を、エネルギーゲームや平均支払ゲーム、および決定性 $\omega$-チューリングマシンによって認識される言語を含む、より広範な $BC(\Sigma^0_2)$ 言語へと拡張する。本論文は、$\omega$-正則な目的関数のための「有限から無限へのリフト」は回収しているものの、メモリ $k > 1$ における「1対2プレイヤーのリフト（非対称リフト）」は、反例が存在するため回収していないことを明記している。

限界と未解決問題
著者らは、NPにおける決定可能性を確立した一方で、正確な複雑性（具体的にPに属するかどうか）は依然として未解決であることを認めている。また、抽出補題の一般化が困難であるため、現在の手法は $\Delta^0_3$ クラスには拡張できないことも述べている。$\omega$-正uralな目的関数の彩色メモリにおいて、非対称リフトが存在するかどうかという問いは未解決のままである。