模倣と行列計算

一応次のことはわかった。

Kは足し算がべき等な半環、Kはブール代数を半環とみなしたものを含むと考える。AとBはKを係数とする正方行列で、行列のインデックスの集合はグラフの頂点とみなす。A:n→n, B:m→m、A、Bは隣接行列か、それのベキだの和を取ったりした、ともかくも経路を表現する行列だとする。行列の順序は、成分ごとの比較で考える（バカ順序）。

S:m→n はブール値行列で、普通の行列掛け算の記法で AS ≦ SB が成立するとき、「BはSによりAを模倣する」という。なんで、これが模倣なのか、ということを以下に説明する。ちなみに、図式順で書けば S;A ≦ B;S 。

i,j を[n] = {1, 2, .., n}を走る変数、同じくα, βなどは[m]を走る変数だとする。このような記号を使ったのは、[n]と[m]を完全に区別したいから。AとBを[n]上と[m]上のラベル付き遷移系だとみなす。Sは、[n]と[m]との関係。向きはどっちもいいが、i 〜 α などで、iとαがSで関係付けられていることを示す。

Sが模倣関係だと言う定義は：

• i〜α, i -(a)->j ならば、「j〜β かつ α-(a)->β」となるβが存在する。

これを行列計算と論理式で書けば：

    S[i←α] = 1 ∧ A[j←i] = a

  -------------------------------

  ∃β.( S[j←β] ∧ B[β←α] = a

aはゼロでなくてSがブールであることから、

    A[j←i]S[i←α] = a

  -------------------------------

  ∃β.( S[j←β]B[β←α] = a )

下側の∃βは、a ≦ Σ(β: S[j←β]B[β←α]) という不等号で書ける。a = A[j←i]S[i←α] を使えば：

• A[j←i]S[i←α] ≦ Σ(β: S[j←β]B[β←α])

ここで、iを動かして足し算する、ベキ等性から右辺はいくら足しても変わらないから：

• Σ(i: A[j←i]S[i←α]) ≦ Σ(β: S[j←β]B[β←α])

これは行列の掛け算になっていて、

• (AS)[j←α] ≦ (SB)[j←α]

jとαは任意だったから

• (AS) ≦ (SB)

(AS) ≦ (SB) を仮定すれば、そのまま逆にたどって A[j←i]S[i←α] ≦ Σ(β: S[j←β]B[β←α]) が出る。a ≦ Σ(β: S[j←β]B[β←α]) から ∃β.( S[j←β] ∧ B[β←α] = a は行列計算だけでは出ない。a が素元（超素元）が必要そう。が、むしろ a ≦ Σ(β: S[j←β]B[β←α]) のまま使ったほうがいいような気もする。aが任意の元でこれが成立する。

A[j←i]S[i←α] ≦ Σ(β: S[j←β]B[β←α]) は、Aによる遷移の可能性は、SによりBへ対応付けて考えればすべて尽くされることを示している。

• AS ≦ SB ならば A* ≦ SB*

は、順番にやっていけば出そう、この形でいいのかは自信ないが。欲しいのは、

• A(1(+)S) ≦ (S(+)1)B ならば Tr(A) ≦ Tr(B)

いや、ほんとに欲しいのは：

• Tr(A) ≦ Tr(B) ならば A(1(+)S) ≦ (S(+)1)B となるSが存在する
• ダイクストラ法は、A(1(+)S) ≦ (S(+)1)B となる最大のSを求めることができる。

とりあえず、(a + b)* = (a*b)*b* とか (ab)* = 1 + a(ba)*b とかが機械的に示せないと。