Sat Jun 27 20:31:12 JST 2015

ここまで考えたことのまとめ

kMMGのアルゴリズムに、 \(L^{\leq \ell}(p)\) をヒューリスティック関数として導入する. あるいは 最終的に得られる \(P\) に対して \(L^{\leq \ell}(P)\) を最小化するための貪欲法も考えられる.

\(L^{\leq \ell}(P)\) を直接求めるより先に \(L^{\leq \ell}(p)\) を求めることを考えた. さらに \(L^{= \ell}(p)\) を計算することまでに還元する.

パターン \(p\) に対して、 自明に、 言語 \(L(p)\) を受理する非決定性有限オートマトン (NFA) は構成できる. このNFAの状態数は、パターン長 \(|p|\) の二倍で抑えられる. 厳密に言えば、\(p\) 中の \(\diamond\) が2つの状態に変換されて、 その他の要素はちょうど1つの状態に変換される. (誤り. 厳密に、状態数は \(1 + |p|\) だ. 一つの状態からなるNFAについて、各要素はちょうど一つの状態を追加することしかしない.) 教科書的に、NFAから決定性有限オートマトン (DFA) もまた、構成できる. しかしながら、一般的には、このDFAの状態数は、NFAの状態数の指数を最大で持ちうる.

無曖昧有限オートマトン (UFA) とは、次の2つを満たす有限オートマトンである.

  1. 任意の状態、状態、語 \((p, q, w)\) について、UFAの上で、\(p \rightarrow^w q\) というパスは高々一つだけ存在する.
  2. UFAが受理する語 \(w\) について、\(p \rightarrow^w q\) というパスを作る初期状態 \(p\) と終了状態 \(q\) の組は一意であること.

明らかに、一般にNFAはUFAとは限らなく、また、一般にDFAはUFAである.

さて、UFAの上では、それが受理する言語 \(L\) に対して \(\# L^{= \ell}\) は次のようにして計算できる.

UFAの隣接行列を次のように定義する.

\((M)_{pq} =\) \(p \rightarrow^a q\) という遷移をなすアルファベット \(a\) の数

この行列を \(k\)乗して得られる行列 \(M^k\)\(pq\) 成分は、\(p \rightarrow q\) というパスで長さが \(k\) の語の数に相当する.

UFAの状態数を \(m\) とすると、\(M\)\(m \times m\) 行列であって、 その \(k\) 乗は行列乗算については素朴に計算することで \(O(m^3 \log k)\) かかる.

というわけで、

「パターン \(p\)」 → 「\(L(p)\) を受理するNFA」 → 「同等なDFA」 → 「隣接行列」

これで、計算ができる.

最終的に欲しいのは、\(\#L^{\leq \ell}\) であって、 これを \(\#L^{= 1} + \#L^{= 2} + \cdots \#L^{= \ell}\) と計算する予定なので、 全体として \(O(m^3 \ell)\) ということになる.

追記 (Tue Jun 30 20:31:34 JST 2015)

直接 \(M^k\) を求めるんじゃなくて、 初期ベクトル: \(V = [1, 0 .. 0]\) (初期状態だけ立ってるbit列) を用いて
\(M^k V\) が、初期状態付きの、最終状態なわけ. これは、\(k\) 回、行列とベクトルの掛け算をすればいいんだけど、 これって、一回の掛け算が \(O(m^2)\) でできる. というわけで、全体としては、 \(O(m^2 \ell)\) となってオーダーが落ちる

ちゃんと授業を聞いててよかった

\(\ell\) はせいぜい30程度の大きさのつもりである. \(|p|\) も、それと同程度である. ではさて、\(m\) (UFAにおける状態数) は、\(2|p|\) の指数ありそう.

予想

パターン言語を受理するDFAの状態数は、 (別にそれが上手な構築方法でなくても) \(|p|\) の定数倍程度.

これは完全に、いくつかを、手で実際に作ってみて得られた経験である. といっても、本当に複雑すぎるパターンについてそんなやったわけではない. 実際にDFAを構築してみせるプログラムをさっさと書いて、 その状態数がどう増えるかを見てみようと思う.