Fixed Points of Set Functors: How Many Iterations are Needed?

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F16%3A10329041" target="_blank" >RIV/00216208:11320/16:10329041 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/68407700:21230/16:00302998

Výsledek na webu

<a href="http://dx.doi.org/10.1007/s10485-016-9451-1" target="_blank" >http://dx.doi.org/10.1007/s10485-016-9451-1</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s10485-016-9451-1" target="_blank" >10.1007/s10485-016-9451-1</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Fixed Points of Set Functors: How Many Iterations are Needed?

Popis výsledku v původním jazyce

The initial algebra for a set functor can be constructed iteratively via a well-known transfinite chain, which converges after a regular infinite cardinal number of steps or at most three steps. We extend this result to the analogous construction of relatively initial algebras. For the dual construction of the terminal coalgebra Worrell proved that if a set functor is alpha-accessible, then convergence takes at most alpha + alpha steps. But until now an example demonstrating that fewer steps may be insufficient was missing. We prove that the functor of all alpha-small filters is such an example. We further prove that for beta aecurrency sign alpha the functor of all alpha-small beta-generated filters requires precisely alpha + beta steps and that a certain modified power-set functor requires precisely alpha steps. We also present an example showing that whether a terminal coalgebra exists at all does not depend solely on the object mapping of the given set functor. (This contrasts with the fact that existence of an initial algebra is equivalent to existence of a mere fixed point.).

Název v anglickém jazyce

Fixed Points of Set Functors: How Many Iterations are Needed?

Popis výsledku anglicky

The initial algebra for a set functor can be constructed iteratively via a well-known transfinite chain, which converges after a regular infinite cardinal number of steps or at most three steps. We extend this result to the analogous construction of relatively initial algebras. For the dual construction of the terminal coalgebra Worrell proved that if a set functor is alpha-accessible, then convergence takes at most alpha + alpha steps. But until now an example demonstrating that fewer steps may be insufficient was missing. We prove that the functor of all alpha-small filters is such an example. We further prove that for beta aecurrency sign alpha the functor of all alpha-small beta-generated filters requires precisely alpha + beta steps and that a certain modified power-set functor requires precisely alpha steps. We also present an example showing that whether a terminal coalgebra exists at all does not depend solely on the object mapping of the given set functor. (This contrasts with the fact that existence of an initial algebra is equivalent to existence of a mere fixed point.).

Druh

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

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2016

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

Applied Categorical Structures

ISSN

0927-2852

e-ISSN

—

Svazek periodika

24

Číslo periodika v rámci svazku

5

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

13

Strana od-do

649-661

Kód UT WoS článku

000383603000015

EID výsledku v databázi Scopus

2-s2.0-84983542777