On Well-Founded and Recursive Coalgebras

Adámek J, Milius S, Moss LS (2020)

Publication Type: Conference contribution

Publication year: 2020

Journal

Lecture Notes in Computer Science Springer Verlag

Publisher: Springer

Book Volume: 12077 LNCS

Pages Range: 17-36

Conference Proceedings Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Event location: Dublin IE

ISBN: 9783030452308

DOI: 10.1007/978-3-030-45231-5_2

Abstract

This paper studies fundamental questions concerning category-theoretic models of induction and recursion. We are concerned with the relationship between well-founded and recursive coalgebras for an endofunctor. For monomorphism preserving endofunctors on complete and well-powered categories every coalgebra has a well-founded part, and we provide a new, shorter proof that this is the coreflection in the category of all well-founded coalgebras. We present a new more general proof of Taylor’s General Recursion Theorem that every well-founded coalgebra is recursive, and we study conditions which imply the converse. In addition, we present a new equivalent characterization of well-foundedness: a coalgebra is well-founded iff it admits a coalgebra-to-algebra morphism to the initial algebra.

Authors with CRIS profile

Stefan Milius Lehrstuhl für Informatik 8 (Theoretische Informatik)

Involved external institutions

Czech Technical University in Prague / České vysoké učení technické v Praze CZ Czech Republic (CZ) Indiana University US United States (USA) (US)

How to cite

APA:

Adámek, J., Milius, S., & Moss, L.S. (2020). On Well-Founded and Recursive Coalgebras. In Jean Goubault-Larrecq, Barbara König (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 17-36). Dublin, IE: Springer.

MLA:

Adámek, Jiří, Stefan Milius, and Lawrence S. Moss. "On Well-Founded and Recursive Coalgebras." Proceedings of the 23rd International Conference on Foundations of Software Science and Computational Structures, FOSSACS 2020, held as part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2020, Dublin Ed. Jean Goubault-Larrecq, Barbara König, Springer, 2020. 17-36.

BibTeX: Download