F余代数

数学の特に圏論における F-余代数 (エフよだいすう、英: F-coalgebra) は、(自己)関手 F によって定義される構造の一つである。代数や余代数を扱う文脈ではよく、シグネチャに由来する関手を考える。F-余代数の概念は計算機科学で使われることが多い。例えば、遅延評価、ストリームのような無限データ構造、状態遷移系などはF-余代数の言葉で説明される。

F-余代数はF-代数の双対である。あるシグネチャと等式理論に対する代数を全て集めたクラスがバラエティをなすのと同様、所与の等式理論を満たすF-余代数 (Fはそのシグネチャから由来するとする) 全体は余バラエティーをなす。

定義

Fを圏${\mathcal {C}}$上の自己関手

$F\colon {\mathcal {C}}\longrightarrow {\mathcal {C}}$

とするとき、F-余代数とは${\mathcal {C}}$の対象 $A$ と射

$\alpha \colon A\longrightarrow FA$

の組 $(A,\alpha )$ である。

F-余代数 $(A,\alpha )$ から別のF-余代数 $(B,\beta )$ への(F-余代数としての)準同型とは、${\mathcal {C}}$の射

$f\colon A\longrightarrow B$

であって

$Ff\circ \alpha =\beta \circ f$

を満たすものである。

これにより、ある自己関手Fについて、F-余代数全体は圏をなす。

例

関手 $F\colon \mathbf {Set} \longrightarrow \mathbf {Set}$ として、 $X$ を $(X\times A)\cup \{1\}$ に送るものを考える。すると F-余代数 $\alpha \colon X\longrightarrow (X\times A)\cup \{1\}=FX$ はアルファベット$A$上の有限または無限のストリームをあらわすことになる。このとき $X$ は状態集合、 $\alpha$ は状態遷移関数である。状態遷移関数を状態に適用した場合、2通りの結果が考えられる。ひとつは $A$ の元とストリームの次の状態が返される場合、もうひとつは単元集合 $\{1\}$ の元が返される場合である。後者は特別な「終状態」、つまりストリームが打ち止めであることを表す値である。

多くの実用的な例では、このような余代数の状態遷移関数は $X\rightarrow f_{1}\times f_{2}\times \ldots \times f_{n}$ という形になっていて、「セレクタ」「オブザーバ」「メソッド」のように機能別に $X\rightarrow f_{1},\,X\rightarrow f_{2}\,\ldots \,X\rightarrow f_{n}$ と分割して考えることができるようになっている。多くの場合、オブザーバーは何らかの属性値を出力するようになっていて、状態を書き換えるメソッドは $X\rightarrow X^{A_{1}\times \ldots \times A_{n}}$ のように追加のパラメーターを受け取って次の状態を返す形になっている。このような分解は、F-始代数をいくつかの「コンストラクタ」の直和に分解できる現象の双対になっている。

${\mathcal {P}}(X)$を$X$の冪集合とし、これを集合の圏の共変関手とみなす。このとき、${\mathcal {P}}$-余代数は二項関係の入った集合と一対一に対応する。さらにここで集合$A$を固定する。すると自己関手${\mathcal {P}}(A\times (-))$の余代数はラベルつき遷移系と一対一に対応し、余代数の間の準同型は関数双模倣に対応する。

応用

余代数は状態をもつシステム (状態遷移系や、オブジェクト指向プログラミングにおけるクラスなど) や、無限の内容を持ちうるデータ構造 (ストリームなど) などの挙動を、十分に一般的かつ利用しやすい形で記述できることから、計算機科学で広く用いられるようになった。代数的仕様がシステムの動作を関数として (特に、コンストラクタによって生成される帰納的なデータ型を用いて) 記述するのに対し、余代数的仕様はシステムの動作を余帰納的なプロセス、つまりセレクタの出力によって観測される内容として (オートマトン理論のような考え方で) 記述する。このときありえる全ての無限動作を漏れなく重複なく集めてきた集合が終余代数となるため、終余代数も重要な役割を果たす。余代数によって記述されるシステムの性質を記述するのには、余代数的様相論理が適している。

関連項目

• 余代数 (代数学における)

参考文献

• B. Jacobs and J. Rutten, A Tutorial on (Co)Algebras and (Co)Induction. EATCS Bulletin 62, 1997, p.222-259.
• Jan J. M. M. Rutten: Universal coalgebra: a theory of systems. Theor. Comput. Sci. 249(1): 3-80 (2000).
• J. Adámek, Introduction to coalgebra. Theory and Applications of Categories 14 (2005), 157-199
• B. Jacobs, Introduction to Coalgebra. Towards Mathematics of States and Observations (book draft)
• Yde Venema: Automata and Fixed Point Logics: a Coalgebraic Perspective. Information and Computation, 204 (2006) 637-678.

外部リンク

• CALCO 2009: Conference on Algebra and Coalgebra in Computer Science
• CALCO 2011