Recursive coalgebras of finitary functors
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 41 (2007) no. 4, p. 447-462

For finitary set functors preserving inverse images, recursive coalgebras $A$ of Paul Taylor are proved to be precisely those for which the system described by $A$ always halts in finitely many steps.

DOI : https://doi.org/10.1051/ita:2007028
Classification:  18A25,  08C05,  68R65
Keywords: recursive coalgebra, coalgebra, definition by recursivity
@article{ITA_2007__41_4_447_0,
author = {Ad\'amek, Ji\v r\'\i\ and L\"ucke, Dominik and Milius, Stefan},
title = {Recursive coalgebras of finitary functors},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
publisher = {EDP-Sciences},
volume = {41},
number = {4},
year = {2007},
pages = {447-462},
doi = {10.1051/ita:2007028},
zbl = {pre05301991},
mrnumber = {2377973},
language = {en},
url = {http://www.numdam.org/item/ITA_2007__41_4_447_0}
}

Adámek, Jiří; Lücke, Dominik; Milius, Stefan. Recursive coalgebras of finitary functors. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 41 (2007) no. 4, pp. 447-462. doi : 10.1051/ita:2007028. http://www.numdam.org/item/ITA_2007__41_4_447_0/

[1] P. Aczel and N. Mendler, A Final Coalgebra Theorem, Proceedings Category Theory and Computer Science, edited by D.H. Pitt et al. Lect. Notes Comput. Sci. (1989) 357-365.

[2] J. Adámek and S. Milius, Terminal coalgebras and free iterative theories. Inform. Comput. 204 (2006) 1139-1172. | Zbl 1104.68068

[3] J. Adámek and V. Trnková, Automata and Algebras in Categories. Kluwer Academic Publishers (1990). | MR 1071169 | Zbl 0698.18001

[4] J. Adámek, D. Lücke and S. Milius, Recursive coalgebras of finitary functors, in CALCO-jnr 2005 CALCO Young Researchers Workshop Selected Papers, edited by P. Mosses, J. Power and M. Seisenberger, Report Series, University of Swansea, 1-14.

[5] M. Barr, Terminal coalgebras in well-founded set theory. Theoret. Comput. Sci. 114 (1993) 299-315. | Zbl 0779.18004

[6] V. Capretta, T. Uustalu and V. Vene, Recursive coalgebras from comonads. Inform. Comput. 204 (2006) 437-468. | Zbl 1110.68068

[7] V. Koubek, Set functors. Comment. Math. Univ. Carolin. 12 (1971) 175-195. | Zbl 0217.06803

[8] J. Lambek, A fixpoint theorem for complete categories. Math. Z. 103 (1968) 151-161. | Zbl 0149.26105

[9] S. Milius, Completely iterative algebras and completely iterative monads. Inform. Comput. 196 (2005) 1-41. | Zbl 1062.68075

[10] R. Montague, Well-founded relations; generalizations of principles of induction and recursion (abstract). Bull. Amer. Math. Soc. 61 (1955) 442.

[11] G. Osius, Categorical set theory: a characterization of the category of sets. J. Pure Appl. Algebra 4 (1974) 79-119. | Zbl 0282.02027

[12] J. Rutten, Universal coalgebra, a theory of systems. Theoret. Comput. Sci. 249 (2000) 3-80. | Zbl 0951.68038

[13] P. Taylor, Practical Foundations of Mathematics. Cambridge University Press (1999). | MR 1694820 | Zbl 1141.18001 | Zbl 0939.18001

[14] V. Trnková, On a descriptive classification of set-functors I. Comment. Math. Univ. Carolin. 12 (1971) 143-174. | Zbl 0232.18004