F -коалгебра - F-coalgebra

В математике , особенно в теории категорий , -коалгебра - это структура, определяемая в соответствии с функтором , с конкретными свойствами, как определено ниже. Как для алгебр, так и для коалгебр функтор - это удобный и общий способ организации подписи . Это находит применение в информатике : примеры коалгебр включают ленивые , бесконечные структуры данных , такие как потоки , а также системы переходов . ${\ displaystyle F}$ ${\ displaystyle F}$

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

Определение

Позволять

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

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

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

of , обычно пишется как . ${\ displaystyle {\ mathcal {C}}}$${\ Displaystyle (А, \ альфа)}$

-Коалгеброй гомоморфизм из к другому -коалгебры морфизм ${\ displaystyle F}$${\ Displaystyle (А, \ альфа)}$${\ displaystyle F}$${\ Displaystyle (В, \ бета)}$

${\ 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 \ альфа (0) = \ Ast}$${\ Displaystyle \ альфа (п) = п-1}$${\ Displaystyle п = 1,2, \ ldots}$${\ Displaystyle \ альфа (\ infty) = \ infty}$${\ displaystyle ({\ overline {\ mathbb {N}}}, \ alpha)}$

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

Приложения

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

Смотрите также

• Начальная алгебра
• Коиндукция
• Коалгебра

Рекомендации

• Б. Джейкобс и Дж. Руттен, Учебник по (Ко) алгебрам и (Ко) индукции. Бюллетень EATCS 62, 1997 г., стр . 222-259 .
• Ян Дж. М. М. Руттен: Универсальная коалгебра: теория систем. Теор. Comput. Sci. 249 (1): 3-80 (2000) .
• J. Adámek, Введение в коалгебру. Теория и приложения категорий 14 (2005), 157-199
• Б. Джейкобс, Введение в коалгебру. К математике состояний и наблюдений (черновик книги)
• Иде Венема: Автоматы и логика с фиксированной точкой: коалгебраическая перспектива. Информация и вычисления, 204 (2006) 637-678 .

внешняя ссылка

• CALCO 2009: Конференция по алгебре и коалгебре в компьютерных науках
• CALCO 2011