オートマトン、余オートマトン、文法

オートマトンを形式言語（列言語）の代数の上の左加群とみなす。言語の代数をAとして、a∈Aによる左作用 a・s を次のように解釈する。

• s'∈(a・s) ⇔ input a may-cause transiton s-->s'

通常のオートマトンを受動的オートマトンと呼ぶ。つまり、オートマトンは受理器という解釈。

Aの右加群に対して、a∈Aによる右作用 s・a を次のように解釈する。

• s'∈(s・a) ⇔ transiton s-->s' may-emit output a

右加群を余オートマトン、または能動的オートマトンと呼ぶ。余オートマトンは生成器という解釈。余オートマトンはまた、文法と解釈してもよい。文法は生成器を与えるから。

受理機と文法の同等性は、左加群と右加群の同等性により解釈できる。さらに、トランスデューサーは双加群と解釈し、入出力の同期結合は右加群と左加群のテンソル積と解釈できる。

代数（多元環）Aを固定して、左加群射＝オートマトン射、右加群射＝余オートマトン射、双加群射＝トランスデューサー射などを考えると、これはラベル付き遷移系の双模倣と同じ定義になるはずだ。

多元環の定義で、「生成系＋関係」による定義があるが、生成系＝指標、関係＝制約、となる。指標＋制約＝仕様＝セオリーだから、仕様（セオリー）の圏は多元環の圏であり、それに対するモデルの圏は、多元環上の加群の圏となっていると思ってよい。インスティチューションがインデックス付き圏の形をしているのは、多元環上の加群の圏とも解釈できるからだろう。