В математике , в частности в теории категорий , -коалгебра — это структура, определяемая в соответствии с функтором , со специфическими свойствами, как определено ниже. Как для алгебр , так и для коалгебр , [ необходимо разъяснение ] функтор — это удобный и общий способ организации сигнатуры . Это имеет приложения в информатике : примеры коалгебр включают ленивые вычисления , бесконечные структуры данных , такие как потоки , а также системы переходов .
-коалгебры двойственны -алгебрам . Так же, как класс всех алгебр для данной сигнатуры и эквациональной теории образуют многообразие , так и класс всех -коалгебр, удовлетворяющих данной эквациональной теории , образует комногообразие, где сигнатура задается как .
Позволять
быть эндофунктором в категории . -Коалгебра является объектом вместе с морфизмом
из , обычно пишется как .
Гомоморфизм -коалгебры в другую -коалгебру является морфизмом
в таком виде, что
Таким образом, -коалгебры для данного функтора F образуют категорию.
Рассмотрим эндофунктор , который переводит множество в его несвязное объединение с одноэлементным множеством . Коалгебра этого эндофунктора задается как , где — так называемые конатуральные числа, состоящие из неотрицательных целых чисел и бесконечности, а функция задается как , для и . Фактически, — конечная коалгебра этого эндофунктора.
В более общем случае зафиксируем некоторое множество и рассмотрим функтор , который отправляет в . Тогда -коалгебра — это конечный или бесконечный поток над алфавитом , где — множество состояний, а — функция перехода состояний. Применение функции перехода состояний к состоянию может дать два возможных результата: либо элемент из вместе со следующим состоянием потока, либо элемент синглтонного множества как отдельное «конечное состояние», указывающее на то, что в потоке больше нет значений.
Во многих практических приложениях функция перехода состояний такого коалгебраического объекта может иметь вид , который легко факторизуется в набор «селекторов», «наблюдателей», «методов» . Особые случаи практического интереса включают наблюдателей, дающих значения атрибутов, и методы-мутаторы вида, принимающие дополнительные параметры и дающие состояния. Это разложение является двойственным разложению исходных -алгебр в суммы «конструкторов».
Пусть P — конструкция множества степеней на категории множеств, рассматриваемая как ковариантный функтор. P -коалгебры находятся в биективном соответствии с множествами с бинарным отношением. Теперь зафиксируем другое множество, A . Тогда коалгебры для эндофунктора P ( A ×(-)) находятся в биективном соответствии с помеченными системами переходов , а гомоморфизмы между коалгебрами соответствуют функциональным бисимуляциям между помеченными системами переходов.
В информатике коалгебра возникла как удобный и достаточно общий способ задания поведения систем и структур данных, которые потенциально бесконечны, например, классов в объектно-ориентированном программировании , потоков и систем переходов . В то время как алгебраическая спецификация имеет дело с функциональным поведением, обычно используя индуктивные типы данных, генерируемые конструкторами, коалгебраическая спецификация касается поведения, моделируемого коиндуктивными типами процессов, которые наблюдаются селекторами, во многом в духе теории автоматов . Важную роль здесь играют конечные коалгебры , которые являются полными наборами возможно бесконечных поведений, таких как потоки. Естественной логикой для выражения свойств таких систем является коалгебраическая модальная логика . [ требуется цитата ]
