STR 2020冬

文字列方程式 について
稲永 俊介

文字列方程式
 定数記号集合 Σ と変数記号集合 V について，(L, R) ∈ (Σ ∪ V)*×(Σ ∪ V)* を文字列方程式と呼ぶ（通常 L = R と表記する）．
例） Σ = {a, b}，V = {u, x, y, z} とする．文字列方程式
xauzau = yzbxaabyは次の解 f (morphism) を持つ．
f(u) = bab, f(x) = abb, f(y) = ab, f(z) = ba についてf(xauzau) = f(yzbxaaby) = abbababbaabab※ 一般に文字列方程式の解は複数存在しうる

文字列方程式の計算量の上界
アルゴリズムMakanin 1977

Decidable

Jaffar 1990,
Schulz 1990

4-NEXPTIME

Koscielski &Pacholski 1996

この世で最も複雑なアルゴリズムの１つ

計算量

2非決定性チューリング機械で 223-NEXPTIME

2非決定性チューリング機械で 222𝑝𝑝(𝑛𝑛)𝑝𝑝(𝑛𝑛)

時間時間

Plandowski & Rytter 2-NEXPTIME
𝑝𝑝(𝑛𝑛)
1998
非決定性チューリング機械で 22
時間
Gutierrez 1998

Plandowski 1999

EXPSPACE

決定性チューリング機械で 2𝑝𝑝(𝑛𝑛) 領域

NEXPTIME

非決定性チューリング機械で 2𝑝𝑝(𝑛𝑛) 時間

Plandowski 2004

PSPACE 決定性チューリング機械で p(n) 領域

Jez 2016

PSPACE 決定性チューリング機械で p(n) 領域
n: 文字列多項式の記述長，p(n)： n の任意の多項式文字列方程式の計算量の上界
アルゴリズム

計算量

Makanin 1977

Decidable

Jaffar 1990,
Schulz 1990

4-NEXPTIME

Koscielski &Pacholski 1996

2
非決定性チューリング機械で 223-NEXPTIME

2
非決定性チューリング機械で 222𝑝𝑝(𝑛𝑛)𝑝𝑝(𝑛𝑛)

時間

時間

Plandowski & Rytter 2-NEXPTIME
𝑝𝑝(𝑛𝑛)
1998
非決定性チューリング機械で 22時間
Gutierrez 1998

Plandowski 1999

Makanin

EXPSPACE

決定性チューリング機械で 2𝑝𝑝(𝑛𝑛) 領域

LZ分解
Makanin

NEXPTIME

Plandowski 2004

非決定性チューリング機械で 2𝑝𝑝(𝑛𝑛) 時間

PSPACE 決定性チューリング機械で p(n) 領域

LZ分解

Jez 2016

PSPACE 決定性チューリング機械で p(n) 領域

Recompression

n: 文字列多項式の記述長，p(n)： n の任意の多項式文字列方程式の極小解の長さ
論文

極小解の長さ の上界

Makanin 1977
Plandowski 1999

222𝑝𝑝(𝑛𝑛)2𝑝𝑝(𝑛𝑛)2n: 文字列多項式の記述長知られている下界は 2𝑝𝑝(𝑛𝑛)未解決問題 (予想) とその帰結
予想１
記述長 n の文字列方程式の極小解の長さの上界は 2𝑝𝑝(𝑛𝑛) である．
予想２

文字列方程式の判定問題は NP に属する．
※文字列方程式は NP 困難 [Angluin, 1980]

定理１ [Plandowski & Rytter, 1998]
予想１ 予想２系１
予想２  文字列方程式は NP 完全

定理１の概要
定理１ [Plandowski & Rytter, 1998]
文字列方程式の極小解の長さ M の上界が 2𝑝𝑝(𝑛𝑛)ならば，文字列方程式の判定問題は NP に属する．
補題１ [Plandowski & Rytter, 1998]
文字列方程式の極小解の LZ 分解のサイズはO(n2log2M (log n + loglog M)) で抑えられる．
n: 文字列多項式の記述長，M：極小解の長さ

定理１の概要
定理１ [Plandowski & Rytter, 1998]
文字列方程式の極小解の長さ M の上界が 2𝑝𝑝(𝑛𝑛)ならば，文字列方程式の判定問題は NP に属する．
1. 極小解の候補の LZ 分解が与えられたとする．
2. 1. の LZ 分解を文法に変換する．
3. 2. で求めた文法を方程式の左右に代入した式を２つの文法とみなして，等価性を判定する．
 補題1より，LZ分解のサイズは O(poly(n)polylog(M))
2. 3 は LZ分解のサイズの多項式時間．

補題１(再掲)
補題１ [Plandowski & Rytter, 1998]
文字列方程式の極小解の LZ 分解のサイズはO(n2log2M (log n + loglog M)) で抑えられる．
n: 文字列多項式の記述長，M：極小解の長さ

次に示す補題２を用いて，補題１を証明している．
直感的には，極小解は繰り返し構造を多く含むことを補題２で示している．

補題２
補題２ [Plandowski & Rytter, 1998]
文字列方程式 E の任意の極小解の任意の部分文字列はE の少なくとも１つのカットを含む，または触れている．

文字列方程式
xyzx = yzyxs のカット

文字列方程式と圧縮
 文字列方程式の極小解は繰り返しを多く含む
 LZ分解を用いると，指数的に縮む．
 また Jez は，Recompression と呼ばれるLZ とは大きく異なる圧縮方法を用いて，文字列方程式を解くアルゴリズムを提案している．
 また，文字列方程式をデータ圧縮に応用する研究も一部で始まっている (詳細不明)．
Generalized Word Equations:
A New Approach to Data Compression
M. Kutwin, W. Plandowski, A. Zaroda, DCC 2019: 585

１変数の文字列方程式
 変数の種類数を１つに限定し，両辺における変数の出現回数は任意とする．
例） xxbaababa = ababaxab x
この文字列方程式は解 x = ababaabab a を持つ．

１変数の文字列方程式
 変数の種類数を１つに限定すると，極小解の長さは方程式の長さ未満であることが知られている．
論文

１変数文字列方程式の極小解の長さの上界

Khmelevskii 1971

cnObono et al. 1994

4n (証明なし)

Baba et al. 2003

n–1n: 文字列多項式の記述長１変数の文字列方程式の解の長さ Y ∈ (Σ ∪{x})* 中の変数 x の出現回数を #x(Y) と書く．
 L = R を任意の１変数 文字列方程式とする．
#x(L) ≠ #x(R) のとき，解は一意に決まり，その長さは n 未満である [Obono et al. 1994]．
 よって，以降は #x(L) = #x(R) の場合を考える．

１変数の文字列方程式の解の長さ
観察 [Baba et al. 2003]
A を１変数文字列方程式 L = R の解とする．
L と R それぞれの k 番目の x の出現位置の差 dk が|A| 以下であるとき，A は dk を周期に持つ．
xLRxAxAAAxA

１変数の文字列方程式の解の長さ
補題３ [Baba et al. 2003]
p を 文字列方程式 L = R の解 A の周期の１つとする．
このとき |A| ≥ max1≤𝑘𝑘≤𝑚𝑚 dk + p – 1 ならば，A の接頭辞 A[1..|A| – p] もまた L = R の解である．
ただし m = #x(L) = #x(R) 前述の観察と，周期性補題を用いて証明できる．

１変数の文字列方程式の解の長さ
補題４ [Baba et al. 2003]#x(L) = #x(R) を満たす文字列方程式 L = R の極小解の長さは高々max1≤𝑘𝑘≤𝑚𝑚 dk + min1≤𝑘𝑘≤𝑚𝑚,𝑑𝑑𝑘𝑘≠0 dk – 2

 |A| ≥ max1≤𝑘𝑘≤𝑚𝑚 dk + min1≤𝑘𝑘≤𝑚𝑚,𝑑𝑑𝑘𝑘≠0 dk – 1を満たす極小解 A が存在すると仮定する．
観察より，A は周期 p ≤ min1≤𝑘𝑘≤𝑚𝑚,𝑑𝑑𝑘𝑘≠0 dk を持つ．
補題３より，A[1..|A| – p] もこの文字列方程式の解となるが，これは A の極小性に反する．

１変数の文字列方程式を解くアルゴリズム
アルゴリズム

計算時間

Charatonik & Pacholski 1991

O(n6)Obono et al. 1994

O(n log n)

Dabrowski & Plandowski 2011

O(n + #x log n)

Jez 2016

O(n)n: 文字列多項式の記述長，#x : 変数 x の出現回数

各アルゴリズムの概要１
１変数文字列方程式 E: A0 x A1x ... xAr = xB1x ... xBr
 Obono et al. 1994: O(n log n)
 解の周期性を利用．
 u, v を原始的 (primitive) な文字列とし，|uv| ≤ |A0B1| を満たすとする．

 (uv)k u が文字列方程式 E の解であるようなすべての k を O(n) 時間で求められる．
 u と v の組の候補は O(log n) 個．

各アルゴリズムの概要２
１変数文字列方程式 E: A0 x A1x ... xAr = xB1x ... xBr
 Dabrowski & Plandowski 2011: O(n + #x log n)
 Obono et al. のアルゴリズムの改良版．
 文字列方程式の定数部分の文字列集合
S = {A0 , A1, ..., Ar, B1, ..., Br} を前処理して，解の検証を高速化する．
 S に対する Aho-Corasik オートマトンを使って，S の Prefix Table を O(n) 時間で構築．
 解１つあたり，O(#x) 時間で検証可能．

各アルゴリズムの概要３
１変数文字列方程式 E: A0 x A1x ... xAr = xB1x ... xBr
 Jez 2016: O(n)
 前述の２つのアルゴリズムとは異なり，解の組合せ的性質は使わない．
 Recompression のアルゴリズムによって，方程式と解の候補の中の２グラムを新しい文字に置き換えていく．
 O(n + #x log n) 時間の手法を得たのち，色々工夫して O(n) 時間にする．

 論文は50ページ...

２変数の文字列方程式
論文
Ilie & Plandowski 2000

アルゴリズム２変数文字列方程式の解の長さ|x| ≤ 2n|y| ≤ 2n2

計算時間

Charatonik & Pacholski 1991

O(n100)Ilie & Plandowski 2000

O(n6)Dabrowski & Plandowski 2004

O(n5)n: 文字列多項式の記述長これから何をやるべきか？やれそうか？
 Recompression を使わずに１変数文字列方程式を O(n) 時間で解くアルゴリズム？
 ２変数文字列方程式を o(n5) 時間で解くアルゴリズム？
 ３変数の文字列方程式の解の長さは O(n3)？
 究極的には，予想１：「文字列方程式の極小解の長さの上界は 2𝑝𝑝(𝑛𝑛) 」が示せると素晴らしい．