Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6874854 | Journal of Logical and Algebraic Methods in Programming | 2018 | 41 Pages |
Abstract
This is a survey on fixed points of endofunctors, including initial algebras and terminal coalgebras. We also consider the rational fixed point, a canonical domain of behavior for finitely presentable systems. In addition to the basic existence theorems for fixed points, several new results are presented. For example, the Smyth-Plotkin theorem that locally continuous endofunctors of DCPO have terminal coalgebras is derived from a new result stating that every locally monotone endofunctor with a fixed point has a terminal coalgebra. We introduce bounded endofunctors on abstract categories and prove that they have terminal coalgebras. We study well-founded coalgebras and prove that for set functors, the largest well-founded coalgebra of every fixed point is the initial algebra. Another new result concerns mixed fixed points: initial algebras and terminal coalgebras of a parametrized accessible functor always form accessible functors.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
JiÅÃ Adámek, Stefan Milius, Lawrence S. Moss,