F余代数のソースを表示

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

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

== 定義 ==
{{mvar|F}}を圏<math>\mathcal{C}</math>上の[[関手|自己関手]]
: <math>F \colon \mathcal{C}\longrightarrow \mathcal{C}</math> 
とするとき、'''{{mvar|F}}-余代数'''とは<math>\mathcal{C}</math>の対象 <math>A</math> と[[射]]
: <math>\alpha \colon A \longrightarrow FA</math>
の組 <math>(A, \alpha)</math> である。

{{mvar|F}}-余代数 <math>(A, \alpha)</math> から別の{{mvar|F}}-余代数 <math>(B, \beta)</math> への({{mvar|F}}-余代数としての)[[準同型]]とは、<math>\mathcal{C}</math>の射
: <math>f \colon A\longrightarrow B</math> 
であって
: <math> Ff\circ \alpha = \beta \circ f</math>
を満たすものである。

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

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

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

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

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

== 関連項目 ==
* [[余代数]] (代数学における)

== 参考文献 ==
* [http://www.cs.ru.nl/B.Jacobs/PAPERS/JR.pdf B. Jacobs and J. Rutten,  A Tutorial on (Co)Algebras and (Co)Induction.  EATCS Bulletin 62, 1997, p.222-259]. 
* [http://www.cwi.nl/~janr/papers/files-of-papers/universal_coalgebra.pdf Jan J. M. M. Rutten: Universal coalgebra: a theory of systems. Theor. Comput. Sci. 249(1): 3-80 (2000)].
* [http://www.tac.mta.ca/tac/volumes/14/8/14-08abs.html J. Adámek, Introduction to coalgebra. Theory and Applications of Categories 14 (2005), 157-199]
* [http://www.cs.ru.nl/B.Jacobs/CLG/JacobsCoalgebraIntro.pdf B. Jacobs, Introduction to Coalgebra. Towards Mathematics of States and Observations] (book draft)
* [https://staff.science.uva.nl/y.venema/papers/2006/vene-auto06.pdf Yde Venema: Automata and Fixed Point Logics: a Coalgebraic Perspective. Information and Computation, 204 (2006) 637-678].

== 外部リンク ==
* [http://calco09.dimi.uniud.it/ CALCO 2009: Conference on Algebra and Coalgebra in Computer Science]
* [http://calco2011.ecs.soton.ac.uk/ CALCO 2011]

{{DEFAULTSORT:Fえふよたいすう}}
[[Category:圏論]]
[[Category:余代数]]
[[Category:数学に関する記事]]