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である.

• 参考; http://swatmac.info/wp-content/uploads/2013/05/mpaper.pdf

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

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

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

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

というわけで、

これで、計算ができる.

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

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

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

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

予想

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

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