F-余代数

数学、特に圏論において、-余代数は、関数に従って定義される構造であり、以下に定義される特定の特性を持つ。代数と余代数の両方において、^{[説明が必要]関数は、}署名を編成する便利で一般的な方法です。これは、コンピュータサイエンスに応用されています。余代数の例としては、遅延評価、ストリームなどの無限データ構造、遷移システムなどがあります。 ${\displaystyle F}$ ${\displaystyle F}$

${\displaystyle F}$-余代数は-代数と双対です。与えられた署名と等式理論のすべての代数のクラスが多様体を形成するのと同様に、与えられた等式理論を満たすすべての -余代数のクラスは共多様体を形成します。ここで、署名は によって与えられます。 ${\displaystyle F}$${\displaystyle F}$${\displaystyle F}$

させて

${\displaystyle F:{\mathcal {C}}\longrightarrow {\mathcal {C}}}$

はカテゴリ上の自己関数子である。-coalgebraは射を伴うの対象である。${\displaystyle {\mathcal {C}}}$${\displaystyle F}$${\displaystyle A}$${\displaystyle {\mathcal {C}}}$

${\displaystyle \alpha :A\longrightarrow FA}$

の、通常は と表記されます。 ${\displaystyle {\mathcal {C}}}$${\displaystyle (A,\alpha )}$

-余代数から別の-余代数 への準同型写像は射である ${\displaystyle F}$${\displaystyle (A,\alpha )}$${\displaystyle F}$${\displaystyle (B,\beta )}$

${\displaystyle f:A\longrightarrow B}$

そのような ${\displaystyle {\mathcal {C}}}$

${\displaystyle Ff\circ \alpha =\beta \circ f}$。

したがって、与えられた関数Fの -余代数はカテゴリを構成します。 ${\displaystyle F}$

集合 をその単独集合 との分離和集合に送る自己関数子を考えてみましょう。この自己関数子の余代数は で与えられます。ここで は、非負の整数 と無限大からなる、いわゆるコナチュラル数です。関数 は、およびに対してで与えられます。実際、はこの自己関数子の終端余代数です。 ${\displaystyle X\mapsto X\sqcup \{*\}:\mathbf {Set} \to \mathbf {Set} }$${\displaystyle \{\ast \}}$${\displaystyle ({\overline {\mathbb {N} }},\alpha )}$${\displaystyle {\overline {\mathbb {N} }}=\{0,1,2,\ldots \}\sqcup \{\infty \}}$${\displaystyle \alpha}$${\displaystyle \alpha (0)=\ast }$${\displaystyle \alpha (n)=n-1}$${\displaystyle n=1,2,\ldots }$${\displaystyle \alpha (\infty )=\infty }$${\displaystyle ({\overline {\mathbb {N} }},\alpha )}$

より一般的には、何らかの集合 を固定し、を に送信する関数を考えます。すると、-coalgebraはアルファベット上の有限または無限のストリームになります。ここで、 は状態の集合で、 は状態遷移関数です。状態遷移関数を状態に適用すると、2 つの結果が生成される可能性があります。1 つは、 の要素とストリームの次の状態の組み合わせ、もう 1 つは、ストリームに値が存在しないことを示す別の「最終状態」としての シングルトン セットの要素です。${\displaystyle A}$${\displaystyle F:\mathbf {集合} \longrightarrow \mathbf {集合} }$${\displaystyle X}$${\displaystyle (X\times A)\cup \{1\}}$${\displaystyle F}$${\displaystyle \alpha :X\longrightarrow (X\times A)\cup \{1\}=FX}$ ${\displaystyle A}$${\displaystyle X}$${\displaystyle \alpha}$${\displaystyle A}$${\displaystyle \{1\}}$

多くの実際のアプリケーションでは、このような余数的オブジェクトの状態遷移関数は の形式になる可能性があり、これは「セレクタ」、「オブザーバー」、「メソッド」のコレクションに簡単に因数分解されます。 実際の関心のある特殊なケースには、属性値を生成するオブザーバーや、追加のパラメータを受け取り状態を生成する の形式のミューテーター メソッドが含まれます。 この分解は、初期-代数を「コンストラクタ」の合計に 分解することと双対です。${\displaystyle X\rightarrow f_{1}\times f_{2}\times \ldots \times f_{n}}$${\displaystyle X\rightarrow f_{1},\,X\rightarrow f_{2}\,\ldots \,X\rightarrow f_{n}}$${\displaystyle X\rightarrow X^{A_{1}\times \ldots \times A_{n}}}$${\displaystyle F}$

P を、共変関数として考えられる集合のカテゴリ上のべき集合構成とします。P余代数は、2項関係を持つ集合と全単射に対応します。ここで別の集合A を固定します。すると、自己関数P ( A ×(-)) の余代数は、ラベル付き遷移システムと全単射に対応し、余代数間の準同型性は、ラベル付き遷移システム間の機能的双模倣に対応します。

コンピュータサイエンスにおいて、コジェネバは、潜在的に無限であるシステムやデータ構造、例えばオブジェクト指向プログラミングのクラス、ストリーム、遷移システムの動作を指定するための便利で適切な汎用方法として登場した。代数仕様は、通常コンストラクタによって生成される帰納的データ型を使用して機能的な動作を扱うのに対し、コジェネバ仕様は、オートマトン理論の精神に非常に近い、セレクタによって観察可能な共帰納的プロセス型によってモデル化された動作を扱う。ここで重要な役割を果たすのは、ストリームなどの潜在的に無限の動作の完全なセットである最終コジェネバである。このようなシステムのプロパティを表現する自然な論理は、コジェネバ的様相論理である。^[要出典]

• 初期代数
• 共誘導
• 余代数

• B. Jacobs と J. Rutten、「(Co)Algebras と (Co)Induction に関するチュートリアル」、EATCS Bulletin 62、1997 年、p.222-259。
• Jan JMM Rutten: ユニバーサルコアルゲーブラ: システム理論。Theor. Comput. Sci. 249(1): 3-80 (2000).
• J. アダメック、コアルジーブラ入門。カテゴリーの理論と応用 14 (2005)、157-199
• B. ジェイコブス、コ代数入門。状態と観測の数学に向けて（本の草稿）
• Yde Venema: オートマトンと固定小数点論理: 余代数の観点。情報と計算、204 (2006) 637-678。

• CALCO 2009: コンピュータサイエンスにおける代数と余代数に関する会議
• カルコ2011