モナドの作用乗法って？

• モナドの作用乗法（action multiplication） - 檜山正幸のキマイラ飼育記 メモ編

ここらのことが、今読むとどうも分からないなー。

Lは集合圏の上で定義された言語自己関手を意図しているんだろう； L(S) = Pow(S^*)。Mは適当な指標Σによる項生成関手かな、M(S) = Term_Σ(S) とか。ρは、なにか標準的な項の評価；たぶん正規表現の標準的な意味とかだろう。ρ:Term_Σ(S) → L(S) は、アルファベットS上の正規表現を同じS上の言語に対応させる。

τは、言語から生成した正規表現を言語として解釈することか。

標数1の代数の圏、掛け算から足し算

コンヌとか黒川さんが、「標数1」とか言っている。標数が1の体を生真面目・杓子定規に考えれば自明。「いったい何を言ってんだろう？？」と不思議でしょうがなかった。あんまり不思議なんで興味が湧かなかったよ。

生真面目・杓子定規に考えてはダメで、半体（semi-field）とか半環（semi-ring）の圏で考えるのだ。Field ⊆ SemiField ⊆ SemiRing だから、標数pの体に関しては、Field_p ⊆ SemiField_p ⊆ SemiRing_p 。SemiRing₁ とかなら自明にならない。

体の単元（0以外）の群の代わりに、半環の乗法モノイドとかを考える。 0 = 1 だと0を除くと1もなくなるので、モノイドにもならなくなるが、別にそれならそれでかまわん、と。引き算もできないが、それもかまわん、と。

そもそも、モノを集合と要素で考えている限りダメそうだ。モノに要素が全然ないとか1個しかないというのは、集合圏で点の集合をみてるだけだから、それでモノが空だとか単元だとか断言はできない。外延的点の双対側で、基礎体Kと座標環Rで考えると、R→K が点で、Kを変えれば点のあるなしも変わる。体Kと環Rを半体／半環にまで一般化すると、今まで点をもたないと思っていた対象物にも点が見つかるかもしれない。

それはそうと、コンヌが掛け算から足し算を作る方法をすごく丁寧（馬鹿丁寧と言えるほど）に書いていて、基点つき集合Xに群Gが作用しているとき、s:X→X がサクセッサらしきものである条件は：

• sは全単射
• s(x^-1・y・x) = x^-1・s(y)・x
• s(0) ≠ 0 （0は前もって特定されている基点）

だいたい、x + y := x・s(x^-1・y) のように定義する。

あーそうそう（と脈絡がメチャクチャだが）、次のものは標数1だ。

1. 0以上の実数の、max-plus代数
2. 0以化の実数の、min-plus代数
3. 1以上の実数の、max-times代数
4. 1以下の正実数の、min-times代数

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

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

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

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

• 実行用では、無音遷移も決定性があったほうがいい。無音遷移パスはチェーンとなる。
• 判定用は、無音遷移が長いのが問題、長さ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. 適当な条件下で、「ダイクストラ法は、最大のルーピング整合的な模倣を求めることができる」。

[/追記]