両オートマトン

未整理にゴチャゴチャと書く：

双オートマトン（biautomaton）という言葉は既に使われているし、その定義はまっとうなものだ。モノイドが両側から作用しているいる集合のこと。双加群＝両側加群と同じ意味での「双」。双オートマトンは、集合圏の双加群として考えたことがあるが、あまりパッとしなかった。

IO付きの遷移系は、この意味での双オートマトンとは違うので、両オートマトン（di-automatonまたはdiautomaton）にしようかな。

両オートマトン、または両側（2-sided）オートマトンはアルファベットを2つ持ち、入力アルファベットと出力アルファベットと呼ぶ。X, Yが入力／出力アルファベットのとき、Σ = in(X) + out(Y) + io(X×Y) + {τ} + {ι} としてアルファベットを組み立てて、Σをアルファベットとするオートマトンに制約を入れたもの。

F:X >> Y、G:Y >> Z が両オートマトンのとき、その並列同期IO結合 F*G が定義できる。それとは別に直列化同期IO結合 F□G を定義したい。

• F□G ではFとGの同時実行はない。どちらか一方の動作しか起きない。
• 言語のインターリーブ演算（シャフル演算）と関係があるはずだ。
• IO命令の内部化だけは同期なので、同時実行が起きる。
• Fが容量1のバッファのとき、F*FとF□Fは差が出るはずだ。

両オートマトンは2セルとなる。3セルは弱模倣（weak sumulation）で、非決定性コンパイルとも呼ぶ。

両オートマトンの台である幾何的有向グラフからパスの圏を生成して、パスに簡約列ペアで再ラベリグする。ブランク縮約列化により、a|→ "a"、_|→ "" という列（ストリング）が出来る。よって、遷移ステップに対するラベリングは事実上変化がない（変わるのはブランク記号←→空列）。

通常のオートマトンが列言語を受理または生成するのに対して、両オートマトンは列ペア（ペアの列ではない！）の言語を生成する。アルファベットΣ、入力アルファベットXと出力アルファベットYに対して、Σ-言語、X-Y-両言語と呼ぶ。

• LがΣ言語 ⇔ L∈Pow(Σ^*)
• LがX-Y両言語 ⇔ L∈Pow(X^*×Y^*)

X-両言語はX言語と同型、-Y両言語はY言語と同型、となる。

オートマトン	両オートマトン
状態空間S	状態空間S
状態s	状態空間s
記号a	入力記号x、出力記号y
アルファベットΣ	両アルファベット (X, Y)
言語 L⊆Σ*	両言語 L⊆X*×Y*
始状態i、終状態B	始状態i、終状態B
遷移ステップ(s,a,s')	遷移ステップ(s,(x, y),s')
遷移写像f	遷移写像f
遷移関係F	遷移関係F

ブランク記号（無音記号、タイムフィラー）とnopの導入がある。