事情があって、モノイドと有向グラフから圏を構成する方法を考えたので書いておきます。
自由圏（道の圏、パスの圏）
Gが有向グラフのとき、Gから作られる自由圏（free category）はよく知られています。復習しておきます。記号法は圏論のものを用います； |G|, dom, cod はそれぞれ、グラフの頂点集合、辺の始点、辺の終点です。
A0, A1, ... , An が頂点の列、f1, ... , fn が辺の列で、次の条件を満たすとします。
- dom(fi) = Ai-1
- cod(fi) = Ai
このとき、[A0, f1, A1, ... , An-1, fn, An] を、G上の長さnの道と呼びます。n = 0, 1 のときは次のような形です。
- [A, A] （Aは頂点）
- [A, f, B] （dom(f) = A, cod(f) = B）
道に対しても dom, cod を定義します。
- dom([A0, f1, A1, ... , An-1, fn, An] ) = A0
- codo([A0, f1, A1, ... , An-1, fn, An] ) = An
道の結合は連接として定義します。
こう定義すると頂点と道の全体は圏になります。出来た圏は、Gから作った自由圏、またはGの道の圏、パスの圏と呼びます。
モノイドで辺ラベル付けされた有向グラフ
M = (M, ・, e) をモノイド、Xは単なる集合とします。Hは、Xの要素のペアにMの部分集合を対応付ける写像だとします。つまり、H:X×X→Pow(M)。Pow(M)はMのベキ集合です。
a, b∈X と m∈H(a, b) の3つ組 (a, m, b) を辺だと考えると、Xを頂点集合とする有向グラフができます。辺 (a, m, b) は、モノイドの要素mでラベル付けされていると考えることもできます。写像としてのHも、Mで辺ラベル付けされたグラフとしてのHも同じ記号で表すことにします。
写像 T:X×X→Pow(M) を、a, b がなんでも T(a, b) = M として定義します。この写像から作られる有向グラフも同じ記号Tで表します。
自由圏からの評価
Hを、先に述べたように H:X×X→Pow(M) という写像から定義されたグラフとします。Hはグラフなので、その自由圏Free(H)を作れます。Free(H)の射は次の形をしています。
- [a0, (a0, m1, a1), a1, ..., an-1, (an-1, mn, an), an]
冗長なので、次のように略記することにします。
- [a0, m1, a1, ..., an-1, mn, an]
Free(H)からグラフTへの写像Evを次のように定義します。
- 頂点に対しては恒等写像
- Ev([a, a]) = e
- Ev([a0, m1, a1, ..., an-1, mn, an]) = (a0, m1・...・mn, an)
- 特に、Ev([a, m, b]) = (a, m, b)
Evはグラフの準同型となっています。道に対してモノイド演算を実行する（評価する）ので評価写像と呼んでおきます。評価写像Evによる像は、Tの部分グラフになりますが、(a, m, b) と (b, m', c) の結合を (a, m・m', b) と定義すれば圏になります。Evの像に圏の構造を入れたものを Cat(H) としましょう。
解釈
H |→ Cat(H) は、モノイドMでラベル付けされたグラフから圏を作る構成法を与えます。Mの要素をなんらかのオペレーションと考えると、Hはそれらのオペレーションを含む状態遷移図とみませます。個々の頂点は状態点というよりは、オペレーションが作用する状態空間を表すと見たほうがよいでしょう。
構文的に解釈すれば、Hは正規表現または構文図（syntax diagram）だと言えます。Free(H)は、正規表現が定義する正規言語に対応します。Evは、圏Cat(H)に値を取る意味写像となります。
ただし、ほんとの意味はCat(H)のさらに先にあって、例えば関係の圏Relなどの値を取るべきでしょう。Free(H)からRelへの関手がCat(H)を中継するような状況が実際的に使うモデルとなります。
