Initial Algebras and Terminal Coalgebras
The Theory of Fixed Points of Functors

An in-depth treatment of an active research area of theoretical computer science, presenting and extending its most important results.

Jiří Adámek (Author), Stefan Milius (Author), Lawrence S. Moss (Author)

9781108835466, Cambridge University Press

Hardback, published 6 February 2025

642 pages
23.5 x 15.9 x 3.8 cm, 1.06 kg

'Fixed points are central to computer science. The book is therefore a must for every categorically minded computer scientist.' Ichiro Hasuo, National Institute of Informatics

Providing an in-depth treatment of an exciting research area, this text's central topics are initial algebras and terminal coalgebras, primary objects of study in all areas of theoretical computer science connected to semantics. It contains a thorough presentation of iterative constructions, giving both classical and new results on terminal coalgebras obtained by limits of canonical chains, and initial algebras obtained by colimits. These constructions are also developed in enriched settings, especially those enriched over complete partial orders and complete metric spaces, connecting the book to topics like domain theory. Also included are an extensive treatment of set functors, and the first book-length presentation of the rational fixed point of a functor, and of lifting results which connect fixed points of set functors with fixed points of endofunctors on other categories. Representing more than fifteen years of work, this will be the leading text on the subject for years to come.

1. Introduction
2. Algebras and coalgebras
3. Finitary iteration
4. Finitary set functors
5. Finitary iteration in enriched settings
6. Transfinite iteration
7. Terminal coalgebras as algebras, initial algebras as coalgebras
8. Well-founded coalgebras
9. State minimality and well-pointed coalgebras
10. Fixed points determined by finite behaviour
11. Sufficient conditions for initial algebras and terminal coalgebras
12. Liftings and extensions from Set
13. Interaction between initial algebras and terminal coalgebras
14. Derived functors
15. Special topics
A. Functors with initial algebras or terminal coalgebras
B. A primer on fixed points in ordered and metric structures
C. Set functors
References
Index of categories
Subject index.

Subject Areas: Mathematical theory of computation [UYA]