F -коалгебра

В математике , особенно в теории категорий , $F$ -коалгебра – это структура , определяемая функтором $F$ , с конкретными свойствами, как определено ниже. И для алгебр и для коалгебр , ^{[ нужны разъяснения ]} Функтор — это удобный и общий способ организации подписи . Это имеет применение в информатике : примеры коалгебр включают ленивые вычисления , бесконечные структуры данных , такие как потоки , а также системы переходов .

$F$ -коалгебры двойственны $F$ -алгебры . Точно так же, как класс всех алгебр для данной сигнатуры и эквациональной теории образует многообразие , так же и класс всех $F$ -коалгебры, удовлетворяющие данной эквациональной теории, образуют комногообразие, сигнатура которого имеет вид $F$ .

Определение

Позволять

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

быть эндофунктором категории ${\mathcal {C}}$ . Ан $F$ -коалгебра – это объект $A$ из ${\mathcal {C}}$ вместе с морфизмом

\alpha :A\longrightarrow FA

из ${\mathcal {C}}$ , обычно пишется как $(A,\alpha )$ .

Ан $F$ -коалгебрный гомоморфизм из $(A,\alpha )$ другому $F$ -коалгебра $(B,\beta )$ является морфизмом

f:A\longrightarrow B

в ${\mathcal {C}}$ такой, что

Ff\circ \alpha =\beta \circ f

.

Таким образом, $F$ -коалгебры для данного функтора F составляют категорию.

Примеры

Рассмотрим эндофунктор $X\mapsto X\sqcup \{*\}:\mathbf {Set} \to \mathbf {Set}$ который отправляет набор в его непересекающееся объединение с одноэлементным набором $\{\ast \}$ . Коалгебра этого эндофунктора имеет вид $({\overline {\mathbb {N} }},\alpha )$ , где ${\overline {\mathbb {N} }}=\{0,1,2,\ldots \}\sqcup \{\infty \}$ – это так называемые натуральные числа, состоящие из целых неотрицательных чисел, а также бесконечности, и функция $\alpha$ дается $\alpha (0)=\ast$ , $\alpha (n)=n-1$ для $n=1,2,\ldots$ и $\alpha (\infty )=\infty$ . Фактически, $({\overline {\mathbb {N} }},\alpha )$ является терминальной коалгеброй этого эндофунктора.

В общем, исправьте некоторый набор $A$ и рассмотрим функтор $F:\mathbf {Set} \longrightarrow \mathbf {Set}$ который отправляет $X$ к $(X\times A)\cup \{1\}$ . Затем $F$ -коалгебра $\alpha :X\longrightarrow (X\times A)\cup \{1\}=FX$ это конечный или бесконечный поток по алфавиту $A$ , где $X$ представляет собой совокупность состояний и $\alpha$ — функция перехода состояний. Применение функции перехода состояний к состоянию может дать два возможных результата: либо элемент $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$ -алгебры в суммы «конструкторов».

Пусть P — конструкция степенного множества в категории множеств, рассматриваемая как ковариантный функтор. P -коалгебры находятся в биективном соответствии с множествами с бинарным отношением. Теперь исправим другой набор A . Тогда коалгебры для эндофунктора P ( A ×(-)) находятся в биективном соответствии с помеченными переходными системами , а гомоморфизмы между коалгебрами соответствуют функциональным бисимуляциям между помеченными переходными системами.

Приложения

В информатике коалгебра возникла как удобный и достаточно общий способ определения поведения систем и структур данных, которые потенциально бесконечны, например классов в объектно-ориентированном программировании , потоков и систем переходов . В то время как алгебраическая спецификация имеет дело с функциональным поведением, обычно используя индуктивные типы данных, генерируемые конструкторами, коалгебраическая спецификация связана с поведением, моделируемым коиндуктивными типами процессов, которые могут наблюдаться селекторами, во многом в духе теории автоматов . Важную роль здесь играют финальные коалгебры , которые представляют собой полные наборы возможно бесконечных поведений, таких как потоки. Естественной логикой для выражения свойств таких систем является коалгебраическая модальная логика . ^{[ нужна ссылка ]}

См. также

Ссылки

Внешние ссылки