モノイドの有限族と部分作用

モノイドの有限族〈finite family of monoids〉とは、圏論を使って定義すれば:

  • Mは圏である。
  • |M|は有限集合である。
  • a, b∈|M|, a ≠ b ならば M(a, b) = ∅

このMモノイドの有限族

モノイドの有限族は圏なので、準同型射=関手で、終対象/始対象/直和/直積なども圏として考える。(Mi|i∈I) のような書き方も使う。

Mがモノイドの有限族だとして、集合S上へのMの右作用 a:S×M→S を考えることができる。ただし、全域作用を要求するのは辛いので、部分作用でいいとする。

状態空間にボトム⊥を入れて、S+⊥ = S∪{⊥S} に対する全域作用が部分作用だと言ってもいい。よって、状態空間のほうは付点集合〈pointed set〉として、付点=ボトムへの作用は自明(⊥は不動点)だとする。

SにMが部分作用している とは、S+⊥にMが⊥を固定して全域作用していることだとする。部分作用しか考えないので、単に「作用」で「部分作用」を意味する。

A→S←B をコスパンだとして、SにMが作用しているとする。これを一種の状態遷移系とする。A, Bを固定して、そのような状態遷移系の全体を TS[M](A, B) とする。TS[M](A, B) は圏になる。

TS[M](A, B)とTS[N](B, C) のあいだに“横結合”を定義できれば、モノイドの有限族をパラメータに含む弱2-圏(双圏)ができるだろう。たぶんこれは、インデックス付き2-圏だと思う。グロタンディーク平坦化できるだろう。

上記のインデックス付き2-圏(反変共変はどうでもいい)は、ラベル付き遷移系とオートマトンの拡張になっていて、作用域(モノイドの有限族)の始対象と直和がちゃんとある。空な作用域を認めているから、空な状態空間もOKで、構成の幅がグッと広がる。直和のフォールド M+MM が使える。

適当な係数半環Rを用意すると、M上の畳込み多元環を作れる。この畳込み多元環は、オートマトンにおける言語、プログラム意味論における観測可能振る舞いの概念を拡張するものになる。受理言語関手、振る舞い観測関手に相当する関手も定義できるだろう。

決定性オートマトンの圏のモデル構造が載りそうなのだが、このインデックス付き2-圏(の平坦化)にモデル構造が載ると、すごくいいなー。