有向グラフのあるノードからあるノードへの全てのパスを表現する

いつまでたってもまとまらないので落書き程度で適当に書く。

有向グラフから圏Cを作る
作り方は http://d.hatena.ne.jp/m-hiyama/20090525/1243210967
ここで、

• length([a, f1, f2..., fn, b]) = n + 2

とする。

Cの射の集合を射とする圏C'を作る
a, b, cをC'の対象、F, GをC'の射として、

• 対象 : |C'| = Cの対象
• 射 : Cのホムセットの部分集合
• 域 : dom(F) = Fの要素の域
• 余域 : cod(F) = Fの要素の余域
• 結合 : cod(F) = dom(G)のとき、F;G = {f;g | f∈F, g∈G}
• 恒等射 : id_a = {[a, a]}

で、さらに以下を定義する。

• F:a→a のとき、F* = ∪{φ, F, F;F, F;F;F,...} （クリーネ閉包みたいなもの）
• prim(a, b) = {f | f∈Hom_C(a, b) ∧ length(f)=3} （Hom_C(a, b)をCのHom(a, b)とする）
• S⊂|C'| のとき、Path(S, a, b) = prim(a, b)∪{f | f∈prim(a, k);Path(T, k, k)*;Path(T, k, b), T=S-{a, b}, k∈T}

これがなんだというと、これでnの倍数を受理するオートマトンから正規表現を生成するのに使える。

追記：色々書き直した