F -coalgebra - F-coalgebra

W matematyce , a szczególnie w teorii kategorii , -coalgebra jest strukturą zdefiniowaną za pomocą funktora o określonych właściwościach, jak zdefiniowano poniżej. Zarówno dla algebr, jak i koalgebr funktor jest wygodnym i ogólnym sposobem organizacji podpisu . Ma to zastosowanie w informatyce : przykłady węglagebr obejmują leniwe , nieskończone struktury danych , takie jak strumienie , a także systemy przejściowe . ${\ displaystyle F}$ ${\ displaystyle F}$

${\ displaystyle F}$ -coalgebry są podwójne do -algebry . Tak jak klasa wszystkich algebr dla danej sygnatury i teorii równań tworzy różnorodność , tak i klasa wszystkich -coalgebr spełniających daną teorię równań tworzy kowariancję, w której sygnatura jest dana przez . ${\ displaystyle F}$${\ displaystyle F}$${\ displaystyle F}$

Definicja

Pozwolić

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

być endofunktorem w kategorii . -Coalgebra to obiekt z wraz z morfizmu${\ displaystyle {\ mathcal {C}}}$${\ displaystyle F}$${\ displaystyle A}$${\ displaystyle {\ mathcal {C}}}$

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

z , zwykle zapisywane jako . ${\ displaystyle {\ mathcal {C}}}$${\ displaystyle (A, \ alfa)}$

-Coalgebra homomorfizm z innej -coalgebra jest morfizmem ${\ displaystyle F}$${\ displaystyle (A, \ alfa)}$${\ displaystyle F}$${\ displaystyle (B, \ beta)}$

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

w takim, że ${\ displaystyle {\ mathcal {C}}}$

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

Zatem -coalgebry dla danego funktora F stanowią kategorię. ${\ displaystyle F}$

Przykłady

Rozważmy endofunctor, który wysyła zestaw do jego rozłącznego związku z pojedynczym zbiorem . Węgielgebra tego endofunctora jest określona wzorem , gdzie jest tak zwanymi liczbami wrodzonymi, składającymi się z nieujemnych liczb całkowitych, a także nieskończoności, a funkcja jest określona przez , dla i . W rzeczywistości jest to końcowa koalgebra tego endofunctora. ${\ displaystyle X \ mapsto X \ sqcup \ {* \}: \ mathbf {zestaw} \ to \ mathbf {zestaw}}$${\ displaystyle \ {\ ast \}}$${\ displaystyle ({\ overline {\ mathbb {N}}}, \ alpha)}$${\ Displaystyle {\ overline {\ mathbb {N}}} = \ {0,1,2, \ ldots \} \ sqcup \ {\ infty \}}$${\ displaystyle \ alpha}$${\ Displaystyle \ alpha (0) = \ ast}$${\ Displaystyle \ alfa (n) = n-1}$${\ Displaystyle n = 1,2, \ ldots}$${\ Displaystyle \ alpha (\ infty) = \ infty}$${\ displaystyle ({\ overline {\ mathbb {N}}}, \ alpha)}$

Mówiąc bardziej ogólnie, napraw jakiś zestaw i rozważ funktor, który wysyła do . Wtedy -coalgebra jest skończonym lub nieskończonym strumieniem nad alfabetem , gdzie jest zbiorem stanów i jest funkcją przejścia stanów. Zastosowanie funkcji zmiany stanu do stanu może dać dwa możliwe wyniki: albo element razem z następnym stanem strumienia, albo element singletona ustawiony jako oddzielny „stan końcowy” wskazujący, że nie ma więcej wartości w strumień. ${\ displaystyle A}$${\ displaystyle F: \ mathbf {zestaw} \ longrightarrow \ mathbf {zestaw}}$${\ displaystyle X}$${\ Displaystyle (X \ razy A) \ kubek \ {1 \}}$${\ displaystyle F}$${\ Displaystyle \ alpha: X \ longrightarrow (X \ razy A) \ cup \ {1 \} = FX}$ ${\ displaystyle A}$${\ displaystyle X}$${\ displaystyle \ alpha}$${\ displaystyle A}$${\ displaystyle \ {1 \}}$

W wielu praktycznych zastosowaniach funkcja przejścia stanu takiego obiektu typu carbongebraic może mieć postać , która łatwo rozkłada się na czynniki w postaci zbioru „selektorów”, „obserwatorów”, „metod” . Szczególne przypadki o znaczeniu praktycznym obejmują obserwatorów dających wartości atrybutów oraz metody mutatorów postaci przyjmującej dodatkowe parametry i stany uzyskujące. Ten rozkład jest podwójny do rozkładu początkowych -algebr na sumy „konstruktorów”. ${\ Displaystyle X \ rightarrow f_ {1} \ razy f_ {2} \ razy \ ldots \ razy f_ {n}}$${\ Displaystyle X \ rightarrow f_ {1}, \, X \ rightarrow f_ {2} \, \ ldots \, X \ rightarrow f_ {n}}$${\ Displaystyle X \ rightarrow X ^ {A_ {1} \ razy \ ldots \ razy A_ {n}}}$${\ displaystyle F}$

Niech P będzie konstrukcją potęgową na kategorii zbiorów, rozpatrywanych jako kowariantny funktor. Do P -coalgebras są w korespondencji z bijective zestawach z relacji binarnej. Teraz ustalić inny zestaw, A . Wówczas węgielgebry dla endofunctor P ( A × (-)) są w bijektywnej zgodności z oznaczonymi układami przejściowymi , a homomorfizmy między węglagebrami odpowiadają funkcjonalnym bisymulacjom między wyznakowanymi układami przejściowymi.

Aplikacje

W informatyce , coalgebra pojawiła się jako wygodny i odpowiednio ogólny sposób określania zachowania systemów i struktur danych, które są potencjalnie nieskończone, na przykład klas w programowaniu obiektowym , strumieniach i systemach przejść . Podczas gdy specyfikacja algebraiczna zajmuje się zachowaniem funkcjonalnym, zwykle z wykorzystaniem indukcyjnych typów danych generowanych przez konstruktorów, specyfikacja carbongebraiczna dotyczy zachowania modelowanego przez koindukcyjne typy procesów, które są obserwowalne przez selektory, w dużym stopniu w duchu teorii automatów . Ważną rolę odgrywają tu końcowe koegbry , które są kompletnymi zestawami możliwie nieskończonych zachowań, takich jak strumienie. Naturalną logiką służącą do wyrażania właściwości takich układów jest logika modalna typu carbongebraic .

Zobacz też

• Algebra początkowa
• Koindukcja
• Coalgebra

Bibliografia

• B. Jacobs i J. Rutten, Samouczek dotyczący (Co) Algebr i (Co) Indukcji. Biuletyn EATCS 62, 1997, strony 222-259 .
• Jan JMM Rutten: Uniwersalna koalgebra: teoria systemów. Teor. Comput. Sci. 249 (1): 3-80 (2000) .
• J. Adámek, Wprowadzenie do coalgebry. Teoria i zastosowania kategorii 14 (2005), 157-199
• B. Jacobs, Wprowadzenie do Coalgebry. Towards Mathematics of States and Observations (szkic książki)
• Yde Venema: Automata and Fixed Point Logics: a Coalgebraic Perspective. Informacje i obliczenia, 204 (2006) 637-678 .

Zewnętrzne linki

• CALCO 2009: Konferencja na temat algebry i koalgebry w informatyce
• CALCO 2011