WikiDer > F-коалгебра - Википедия

Эта статья может быть слишком техническим для большинства читателей, чтобы понять. Пожалуйста помогите улучшить это к сделать понятным для неспециалистов, не снимая технических деталей. (Июль 2020) (Узнайте, как и когда удалить этот шаблон сообщения)

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

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

Определение

Позволять

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

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

${ displaystyle alpha: A longrightarrow FA}$

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

An ${ displaystyle F}$-коалгебра гомоморфизм из ${ Displaystyle (А, альфа)}$ другому ${ displaystyle F}$-коалгебра${ displaystyle (B, beta)}$ это морфизм

${ displaystyle f: A longrightarrow B}$

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

${ Displaystyle Ff circ alpha = beta circ f}$.

Таким образом ${ displaystyle F}$-коалгебры для данного функтора 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}$-алгебры в суммы «конструкторов».

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

Приложения

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

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

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

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

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

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

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