Ranked MSO-enumeration over compressed words

技術要約：圧縮された単語に対するランク付きMSO列挙

問題設定
本論文は、圧縮された形式で提供される文字列に対する、固定された単一的二次（Monadic Second-Order; MSO）クエリの回答を列挙する問題に取り組んでいる。入力文字列 $w$ は、正確に一つの文字列を生成する文脈自由文法である直線プログラム（Straight-Line Program; SLP）によって与えられる。目標は、 $w$ において $\Phi(x_1, \dots, x_k)$ を満たす位置のタプル $(a_1, \dots, a_k)$ をすべて計算することである。

本研究における重要な制約は、ランク付き列挙（ranked enumeration）である。出力順序が不透明な標準的な列挙アルゴリズムとは異なり、ランク付き列挙では、それ自体がMSOで定義可能な（例：位置タプルの辞書式順序）特定のユーザー定義順序に従って出力される必要がある。このようなアルゴリズムの効率性の指標は、線形前処理時間（SLPのサイズ $|G|$ に対して線形）と、それに続く定数遅延（constant delay）（連続するタプルを出力する間の時間の一定の上限）である。

この研究以前には、非圧縮された文字列や木構造に対してはMSOクエリのランク付き列挙が知られていたが、圧縮されたデータに関する結果は存在しなかった。さらに、圧縮された文字列に関する既存の列挙結果（例：[29]）は、出力線形遅延（output-linear delay）しか達成できず、ランク付き列挙をサポートしていなかった。

手法
解決策は、主に以下の3つの技術的コンポーネントを組み合わせたものである：

1. 分解木（Factorization Trees）とSimon SLP:
   核となる構造的ツールは、有限モノイドへの射（morphism）に関する単語の解析木である分解木である。ここで、3つ以上の子を持つノードは同じ冪等元（idempotent element）へと評価される。Simonの定理は、このような木がモノイドのサイズに依存する定数の高さを持つことを保証している。
   本論文では、Simon SLP (SSLP) という概念を導入している。これは、生成される単語の分解木と構造的に互換性のあるSLPである。著者らは、任意のSLPは線形時間で等価なSSLPに変換可能であることを証明している（定理3.1）。この変換は、分解木を生成する非決定性トランスデューサを構築し、その後、木の階層構造を反映するように文法を再構成するプロセスを含む。これにより、SLPの「冪等縮約深さ（idempotent-contracted depth）」が定数（$3|M|$）に抑えられることが保証される。

2. 圧縮された文字列内での定数時間走査:
   圧縮された文字列を効率的にナビゲートするために、本論文では[26]の二方向定数時間走査の技術を利用・拡張している。著者らは、圧縮パス（SLPのDAGにおける左/右への移動を表すトリプルのシーケンス）を定義し、一定数の「アクティブな」パスを保持する動的データ構造（二分木 $B$）を維持する。
   決定的なのは、圧縮表現におけるパスが与えられたとき、その辞書式の後続者または先行者を定数時間で計算する right および left 手続きを定義していることである。これには、走査木の枝の分割や、特定のパート（$e$-parts）内での「冪等縮約された」部分パスの管理が含まれる。

3. MSO解釈と後続者計算:
   列挙アルゴリズムは、ポリレギュラー関数（またはより一般的には、MSO文字列対文字列の解釈）の像を計算するものとしてフレーム化されている。アルゴリズムは、分解木（または同等のSSLP）のノードに対するモノイド要素を事前計算することで、現在の位置のタプルの「後続者（successor）」をMSO定義された線形順序に従って反復的に計算する。
   証明には、MSO論理式を非決定性有限オートマトン（NFA）に変換し、有限モノイド $M$ を導出するプロセスが含まれる。アルゴリズムは、現在の位置間のセグメントのモノイド要素を分析し、分解木の構造を利用して、文字列を解凍することなく次の有効な位置へとナビゲートすることで、列挙シーケンスにおける次の位置を定数時間で決定できる。

主な貢献と結果

• 主要定理 (Theorem 5.1): 固定された $k$ 個の自由一階変数を持つMSO論理式と、$k$ タプルに対するMSO定義可能な線形順序に対し、SLP圧縮された文字列上のクエリ回答は、線形前処理時間（$O(|G|)$）および定数遅延で列挙可能である。これは、圧縮データに対するランク付き列挙において、この種の結果としては初である。
• ポリレギュラー関数のための系 (Corollary 5.3): この結果は、ポリレギュラー文字列対文字列関数へと一般化される。固定されたポリレギュラー関数 $f$ と、 $w$ を生成するSLP $G$ に対し、$f(w)$ の記号を線形前処理と定数遅延をもって左から右へと列挙できる。これは、Bojanczyk [8] による（非圧縮入力を仮定した）既存の結果を、ポリレギュラー関数が一般に圧縮サイズを保存しないにもかかわらず、圧縮設定へと拡張するものである。
• Successor-MSOのための系 (Corollary 5.5): 結果は、ポリレギュラー関数よりも厳密に大きいクラスである、Successor-MSO文字列対文字列の解釈にも適用される。
• 技術的貢献 (Simon SLPs): 本論文は、すべてのSLPが線形時間でSimon SLPに変換可能であることを確立している。これにより、分解木が文法圧縮の設定においても利用可能となる。これは独立した関心事としても注目される貢献である。

意義と主張
本論文は、圧縮データに対するランク付き列挙への方向における「第一歩」を踏み出したと主張している。従来の圧縮列挙アルゴリズム（例：[29]）は出力順序を制御できず、従来のランク付き列挙アルゴリズム（例：[2, 12, 19]）は圧縮入力を扱うことができなかったという、特定のギャップに対処している。

著者らは、彼らのアプローチが分解木の特定の構造と、SLP上での定数時間ナビゲーションの能力に依存していることを強調している。また、以下の制限についても明示している：

• 現在の結果は、自由一階変数を持つクエリにのみ適用される。自由な集合変数（これらを扱うには定数遅延ではなく出力線形遅延が必要となる）を扱うことは、分解木の構成法が現在のところ集合変数に拡張できないため、未解決の問題である。
• 本研究は現在文字列に限定されている。森林直線のプログラム（forest straight-line programs）を用いた森林への拡張は、森林の分解定理と森林SLP走査技術の結合を待つ、将来の課題として特定されている。
• ランキングはMSO定義可能な線形順序に限定されている。このモデルと、コストトランスデューサを用いた重みベースのランキングとの関係は依然として不明である。

要約すると、本論文は、出力順序がMSOで定義可能である場合に限り、高度に圧縮されたデータに対する効率的な順序付きクエリ処理のための理論的基礎を提供し、SLP上のMSOクエリに対して「ゴールドスタンダード」である線形前処理と定数遅延が達成可能であることを示している。