Initial algebras and terminal coalgebras in many-sorted sets

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F11%3A10104336" target="_blank" >RIV/00216208:11320/11:10104336 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1017/S0960129510000502" target="_blank" >http://dx.doi.org/10.1017/S0960129510000502</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1017/S0960129510000502" target="_blank" >10.1017/S0960129510000502</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Initial algebras and terminal coalgebras in many-sorted sets

Popis výsledku v původním jazyce

We prove that the iterative construction of initial algebras converges for endofunctors F of many-sorted sets whenever F has an initial algebra. In the case of one-sorted sets, the convergence takes n steps where n is either an infinite regular cardinalor is at most 3. Dually, the existence of a many-sorted terminal coalgebra implies that the iterative construction of a terminal coalgebra converges. Moreover, every endofunctor with a fixed-point pair larger than the number of sorts is proved to have aterminal coalgebra. As demonstrated by James Worell, the number of steps here need not be a cardinal even in the case of a single sort: it is omega + omega for the finite power-set functor. The above results do not hold for related categories, such as graphs: we present non-constructive initial algebras and terminal coalgebras.

Název v anglickém jazyce

Initial algebras and terminal coalgebras in many-sorted sets

Popis výsledku anglicky

We prove that the iterative construction of initial algebras converges for endofunctors F of many-sorted sets whenever F has an initial algebra. In the case of one-sorted sets, the convergence takes n steps where n is either an infinite regular cardinalor is at most 3. Dually, the existence of a many-sorted terminal coalgebra implies that the iterative construction of a terminal coalgebra converges. Moreover, every endofunctor with a fixed-point pair larger than the number of sorts is proved to have aterminal coalgebra. As demonstrated by James Worell, the number of steps here need not be a cardinal even in the case of a single sort: it is omega + omega for the finite power-set functor. The above results do not hold for related categories, such as graphs: we present non-constructive initial algebras and terminal coalgebras.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2011

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Mathematical Structures in Computer Science

ISSN

0960-1295

e-ISSN

—

Svazek periodika

21

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

29

Strana od-do

481-509

Kód UT WoS článku

000289006300009

EID výsledku v databázi Scopus

—