エライ見落とし！！

明瞭オートマトンの包含性決定問題だが、ダイクストラ波動を、サイクルを持つような空間で走らせると永久に走っている。これは困る。アルゴリズムが止まらない。それは分かっていたんだが、サイクルはすぐに消せると、サイクルの扱いを甘く見ていたなーー。ダメだよ＞自分

それでまず、正規形を考えた。サイクルを持つ空間を、サイクルを持たない部分とサイクル群（帯状の並行サイクルの集まり）に分ける。で、n重サイクル標準型（正規形）はできる。n（0以上の整数）が小さいほど扱い易いので、できる限りnを小さくする努力をする。で、任意の空間つうか力学系だが、それは、サイクルを持たない境界付き力学系のn重サイクル標準形に書ける。

で、そこでダイクストラ波動を走らせる。これは、(n + 1)回やらなくてはならない。ここが痛い勘違い。nが大きいとそれなりの負荷だ。失敗するときは早めにわかるけど。成功の判定には作業を全部やる必要がある。

もうひとつの勘違いは、ダイクストラ波動がはめ込みを定義するところ。局所的に単射なのは間違いないが、「局所的」には時間も含まれる。つまり長時間の蓄積を取ると、同じ場所に戻るを何度も通ることがあるので、空間の点の対応としては写像にさえならない。これを管理するには、2つのオートマトンのサイズをかけ算したサイズの2次元テーブルが必要になる。ここでまたメモリーがいるし、手順も複雑化する。

まーともかく、サイクルなし空間内のダイクストラ波動は境界まで達してそこで消えてくれる。波頭集合はいずれは境界に吸収されてなくなる。その結果として、空間の点（ノード）のあいだの対応を作る。この対応が模倣になっていりゃいいってことだろう。

模倣／双模倣／一様性は気にしていたのだが、ちゃんと勉強してないからなー。最後の判定条件に模倣／双模倣／一様性を使う気がする。

どうもハナシがうまく行き過ぎると思った。簡単な問題なら誰かが解いているよな。今の状況では、これはかなり難しい。解けたらエライ、と言える。ダイクストラ波動を(n +1)回走らせるのはいいんだが、その結果の解釈が難しい。どうなったら成功なんだろう？

参考： http://d.hatena.ne.jp/m-hiyama-memo/20061110/1163147851 長谷川の一様性原理：

 f:A+X→B+X, g:A+Y→B+Y, ψ;X→Y,  f;(B+ψ) = (A+ψ);g

 -----------------------------------------------------[HU]

 Tr(f)  = Tr(g) : A→B