ふうううううう、なんとかなりそう、ダイクストラ法

ふううううううーーーーーーーーー、ふうううううううううーーーーーーーーーーーー。

正規言語の包含性判定にダイクストラ法を使うアイディアはなんとか救えそうだ、、、実に紆余曲折だったが。

実行用のオートマトンと判定用のオートマトンはまったく違ったアィディアで作らないとダメだった。

• 実行用では、無音遷移も決定性があったほうがいい。無音遷移パスはチェーンとなる。
• 判定用は、無音遷移が長いのが問題、長さ1の無音遷移に限定すべき。決定性は犠牲にする。

判定用のオートマトンの条件：

1. スタートノードとルーピング始境界は区別される。
2. ゴールノードとルーピング終境界は区別される。
3. スタートと始境界は入る辺を持たない。
4. ゴールと終境界は出る辺を持たない。
5. 長さが2以上の無音遷移パスを持たない。

無音遷移で決定性を壊しているので、アルゴリズムは非決定性でも通用しそうだ。が、無音遷移以外は決定性であるオートマトンを対象とする。

グラフ上でステップ1以下の近傍を考える。このなかでコスト0（入力なし）で行ける範囲が無音近傍（と定義する）。自分自身（近傍の中心）は明らかの無音近傍に入るので、無音近傍は空ではない。

状態点s（in S）と状態点t（in T）が、既に模倣対応で結ばれているとき、sの無音近傍とtの無音近傍も模倣で結ぶ。このとき、完全二部グラフを作る。無音近傍に含まれる状態点の個数を n, m （それぞれS内、T内）とすると、模倣関係グラフは n×m 本の辺を含む。1本は既に存在するので、新たに加える関係辺は n×m - 1 。

ステップ1以下の近傍で、無音でない点の全体を有音近傍と呼ぶ。有音近傍は決定性。有音近傍の点の個数をkとすると、新しい模倣関係辺はk本。無音と有音を足すと、n×m - 1 + k 本の関係辺を加えることになる。ダイクストラ波動のホイヘンス原理による進行は、n + k個の新しい波頭集合（既に通ったところを再度通るかも知れない）を作る。

今言ったような手順を、ダイクストラ波動の波頭集合のそれぞれの点、それぞれの関係辺ごとに行う。波頭集合の点の個数より関係辺は多くなるのが普通。無音辺があると、そこで完全二部グラフを作るので、関係辺は増える。この部分が手間になっているので、できるだけ無音辺を減らすようにすべきだ。

波頭集合は、無音遷移で来た点と有音遷移で来た点では扱いが異なる。無音遷移のみで到着した状態点では模倣の構築が失敗しても許される。失敗した点は、単に波頭集合から取り除かれるだけ。有音遷移で到着した点では失敗すればただちにアルゴリズム全体が失敗して終了する。ここでの失敗は模倣構築の失敗で、正常処理なのは言うまでもない。

波頭集合内で、失敗を許される点と許されない点を識別する必要がある。相手方を走るダイクストラ波動は、相手方の終境界を超えて走る可能性があるので、ルーピング（ワープ）して追跡する。

全体的な失敗成功の判定だが：

1. スタートノードからのゴールまたは終境界まで到達できたか？ 到達前に模倣構築が行き詰まれば失敗。
2. 終境界の各点を始境界の対応点と同一視する。始境界の点を選んで、同じ手順を繰り返す。
3. L0とL1をルーピング境界として、I:L0→L1⊆S を同一視対応。構築した模倣関係をRとして、RのL0への制限が、I;R で与えられるなら模倣は整合的。

まだまだ細部の場合分けがあるんだけど、方針はこんな感じかな。

[追記]背景はこんなだろう。

1. 都合のいいオートマトンのクラスを決める。
2. ルーピング境界付きのオートマトンつうもんを定義する。
3. ルーピング境界付きのオートマトンに対して閉包演算を考える。
4. ルーピング境界付きのオートマトンMがあり、別なオートマトンNがMを模倣し、かつ模倣関係がルーピング整合的なとき、Lang(cl(M))⊆lang(N)
5. ルーピング整合的な模倣関係と閉包オートマトンの模倣関係は1：1に対応する。特に、最大のルーピング整合的な模倣関係と、閉包オートマトンの最大模倣関係は対応する。
6. 適当な条件下で、「Lang(cl(M))⊆lang(N) ならば、NはMをルーピング整合的に模倣できる」。
7. 適当な条件下で、「ダイクストラ法は、最大のルーピング整合的な模倣を求めることができる」。

[/追記]