技術要約：アリスとボブから見た正則性

1. 問題提起

本論文は、出力ドメインがブール値以外の関数における「正則性（regularity）」の統一的かつ原理的な特徴付けが欠如しているという問題に対処している。正則言語（関数 $f: \Sigma^* \to \{true, false\}$）は、有限オートマトン、正規表現、マイヒル・ネローデの定理といった等価なモデルを通じて十分に理解されているが、他のドメインについては状況が断片化している。

• 文字列から文字列への関数: 非等価な複数のクラス（有理的、正則、ポリレギュラーなど）が存在し、どれが「真の」正則関数であるかについての合意がない。
• 文字列から数値への関数: 重み付きオートマトン（線形更新）や多項式オートマトン（多項式更新）といった異なるモデルが存在し、どれが正しい正則性の概念を捉えているのかについて不明確である。
• 無限アルファベット: 無限アルファベット（文字は等価性においてのみ比較可能）上の言語において、有限オートマトンモデルを拡張すると、17個の互いに非等価なモデルが生じ、統一的な原理を欠いている。

核心となる問題は、これらの多様な出力ドメインおよび入力設定にわたって、正則性を特徴付ける単一の、マシンに依存しないフレームワークを見出すことである。

2. 手法：プロトコルモデル

著者らは、通信複雑性の研究（特に Hauser [Hau89] の研究）を適応させた、通信量に基づく統一的なモデルを提案している。このモデルでは、任意の出力ドメイン $D$ を持つ関数 $f: \Sigma^* \to D$ を計算する、協力関係にある二者、アリスとボブが登場する。

主要なメカニズム:

• 入力の分割: 入力文字列 $w$ は、任意に $w = w_1w_2$ と分割される。アリスは $w_1$ を保持し、ボブは $w_2$ を保持する。
• 定数通信: 当事者は、入力の長さに依存しない一定数のメッセージを交換する。
• メッセージの型: メッセージは以下の要素で構成される：
  1. シグナル: 有限集合（ビットまたは有限の記号）の要素。
  2. ドメイン要素: 出力ドメイン $D$ の要素。
• ブラックボックス制限: 決定的な制約として、ドメイン $D$ の要素を含むメッセージは、直接「読み取られたり」検査されたりすることはできない。それらは、ドメインの定義された演算（例：体における加算と乗算、文字列における連結）を用いて操作することのみが可能である。これにより、単一のドメイン要素の中に、入力文字列全体をエンコードすることを防いでいる。
• 分割不変性（Split Invariance）: プロトコルは、同じ入力文字列 $w$ に対して、あらゆる分割 $w = w_1w_2$ について同一の出力を生成しなければならない。
• 非一様性（Non-Uniformity）: アリスとボブは無制限の計算能力を持つ。制限は、通信帯域幅とブラックボックスの規律にのみ存在する。

論文では、これをプロトコルとして定式化し、異なるドメイン $D$ に対するその表現能力を調査している。

3. 主要な貢献と結果

3.1 ブール出力 ($D = \{true, false\}$)

本論文は、ベースラインとして機能させるために、既知の結果（元は Hauser [Hau89] によるもの）を再確立している。

• 定理 1.1: ある言語がプロトコルによって計算されるのは、それが正則である場合、かつその場合に限る。
• 意義: これは、モデルが標準的な正則性を捉えていることを確認し、一般化のための基礎を提供する。証明は、マルチラウンド・プロトコルをワンラウンド・プロトコルに還元し、マイヒル・ネローデの定理を適用することに基づいている。

3.2 体出力 ($D$ は体である)

これは本論文の主要な貢献である。

• 定理 1.2: 関数 $f: \Sigma^* \to D$（$D$ が体の場合）がプロトコルによって計算されるのは、それが $D$ 上の重み付きオートマトンによって計算される場合、かつその場合に限る。
• 手法: 証明では、一般的なプロトコルをスカラー積プロトコル（アリスとボブがベクトル $\sigma_A(w_1)$ と $\sigma_B(w_2)$ を計算し、出力はその内積となるもの）に還元している。その後、ハンケル行列の有限ランクによって重み付きオートマトンを特徴付ける Fliess の定理 [Fli74] を援用している。
• 洞察: 分割不変性の制約は線形性を強制する。たとえプロトコルが（合成を通じて）多項式演算を許容していたとしても、分割不変性の要求により、表現能力は線形写像に制限され、一般的な多項式オートマトンは除外される。
• 限界: この等価性は体において成立する。一般的な半環（例：自由冪等半環）の場合、プロトコルは重み付きオートマトンよりも厳密に強力になる可能性がある（例：プロトコルは、その半環において有理的関係ではない文字列反転を計算できる）。

3.3 文字列出力 ($D = \Gamma^*$)

本論文は、ドメインの演算が連結である文字列から文字列への関数を調査している。

• 予想 1.3: 文字列から文字列への関数がプロトコルによって計算されるのは、それが出力付き決定性二方向オートマトン（従来の正則関数の定義）によって計算される場合、かつその場合に限る。
• 提示された根拠:
  • 含意 ($\Leftarrow$): 証明済み。決定性二方向オートマトンは、クロッシングシーケンスを用いてプロトコルによってシミュレートできる。
  • 含意 ($\Rightarrow$): 完全には証明されていないが、強力な証拠によって支持されている：
    • プロトコルは線形サイズの出力を生成し、線形時間で計算可能である。
    • プロトコルは逆像の下で正則性を保存する（ブール連続性）。
    • 体連続性: プロトコルは、体上の重み付きオートマトンによる前合成に対して閉じている。
    • 単項ケース: 予想は、有理関数が正則関数と一致する単項出力アルファベットにおいて証明されている。
• 意義: もしこれが真であれば、これは有理的な関数よりも弱く、ポリレギュラーな関数よりも強い、正則な文字列から文字列への関数の、マシンに依存しない特徴付けを提供する。

3.4 無限アルファベット

本論文は、文字が等価性においてのみ比較可能な（atoms）無限アルファベットへと、**名目集合（nominal sets）および軌道有限集合（orbit-finite sets）**のフレームワークを用いてモデルを拡張している。

• 予想 6.5: 無限アルファベット上の言語が軌道有限プロトコルによって計算されるのは、それが非決定的なレジスタオートマトンによって認識される場合、かつその場合に限る。
• 文脈: 決定的なレジスタオートマトンはあまりに弱すぎ（特定の反転を扱えない）、非決定的なものは強すぎる（プロトコルが検出できない繰り返しを検出できる）。プロトコルにとっての「ゴールドロックス（適度な）」モデルとして、アンビギュアス（曖昧さのない）オートマトンが提案されている。
• 結果:
  • 含み ($\Leftarrow$): 証明済み。著者らは、軌道（orbits）とサンフラワー補題の変種を用いて、可能な中間状態の集合を反復的に絞り込むことにより、アンビギュアス・オートマトンをシミュレートするマルチラウンド・プロトコルを構築している。
  • 含み ($\Rightarrow$): 証拠が提供されている。著者らは、重み付き軌道有限オートマトンを用いて、プロトコルが軌道有限に生成される左微分を持つ関数を計算することを示す、軌道有限 Fliess 定理（定理 6.19）を証明している。これは、プロトコルが決定可能であり、重み付きモデルと非決定モデルの交わりの中に位置することを示唆している。
• 新規性: 有限アルファベットの場合とは異なり、無限アルファベットに対するプロトコルは、ワンラウンドに還元することはできない。インタラクティブな性質が不可欠である。

4. 意義と主張

本論文は、特定のオートマトン定義を超越する、正則性のための統一的モデルを提供することを主張している。その意義は以下の点にある：

1. マシン独立性: 特定の状態遷移構造ではなく、通信制約（定数メッセージ、ブラックボックス演算）を通じて正則性を特徴付けている。
2. 統一: 多様なモデル（重み付きオートマトン、決定性二方向トランスデューサ、アンビギュアス・レジスタ・オートマトン）がすべて、同じ基礎的な原理（制限されたドメイン演算を伴う定数情報フロー）のインスタンスであることを示唆している。
3. 新しい特徴付け: 重み付きオートマトンに対するマシンに依存しない特徴付け（定理 1.2）を提供し、正則な文字列から文字列への関数（予想 1.3）およびアンビギュアス・レジスタ・オートマトン（予想 6.5）に対する特徴付けを提案している。
4. 計算特性: モデルは、他のトランスデューサモデル（例：ポリレギュラー関数）では必ずしも保証されない、線形出力サイズや計算可能性といった望ましい特性を自然に強制している。

著者らは、文字列から文字列へのケースおよび無限アルファベットのケースについては謙虚な姿勢を保っており、それらを完全に解決された定理ではなく、実質的な証拠（一方の方向の証明、単項ケース、および構造的特性）に支えられた「予想」として提示している。また、「ブラックボックス」制限が良好な関数をもたらさないような、一般的な半環や任意の出力ドメインに関する結果を主張することを明示的に避けている。