Coalgebras, Monads and Semantics

Stefan Milius

PhD thesis, Technische Universität Braunschweig, October 2005.


We study mathematical structures arising in the theory of coalgebras which are useful for providing semantics of recursive specifications. We begin by investigating (completely) iterative algebras and (complete) Elgot algebras, and we establish the connection of these algebras to coalgebra---final coalgebras are precisely the same as free completely iterative algebras, or free complete Elgot algebras, respectively. Similarly, for the non-complete case we show that free iterative algebras, and free Elgot algebras, respectively, exist and can be constructed from finite coalgebras. Furthermore, we show that the monads arising from free (completely) iterative algebras are characterized by a universal property; they are free (completely) iterative monads. This generalizes and extends classical work of Calvin Elgot and Evelyn Nelson. The second main topic of this thesis is to provide a category theoretic semantics of so-called recursive program schemes. By exploiting the structure of free completely iterative monads and of complete Elgot algebras we are able to provide an uninterpreted as well as an interpreted semantics of recursive program schemes. We show that both are connected as expected from the classical work. Finally, we present applications of our abstract theory. We demonstrate how to recover the usual denotational semantics using ordered or metrized structures, and we present new applications defining for example operations satisfying certain equations, fractals, or hypersets recursively.

Available for Download

This is a cumulative PhD thesis. It consists of a summary and 7 scientific articles. References from the summary to those articles are consistent with the versions on this page. Most recent versions of those articles which were preprints at the time of the final submission of the thesis can be found here.

Complete File
containing summary and all the papers below (361 pp.; Acrobat Reader 7.0 required)

comprehensive summary of all the papers below with references to proofs in those papers (xi+74 pp.)

Free iterative theories: a coalgebraic view,
joint paper with J. Adámek and J. Velebil, Math. Structures Comput. Sci. 13 (2003), no. 2, 259-320.

From Iterative Algebras to Iterative Theories,
joint paper with J. Adámek and J. Velebil, preprint, October 2005.

Elgot Algebras,
joint paper with J. Adámek and J. Velebil, preprint, October 2005.

Infinite Trees and Completely Iterative Monads: A Coalgebraic View,
joint paper with P. Aczel, J. Adámek and J. Velebil, Theoret. Comput. Sci. 300 (2003), 1-45.

Completely Iterative Algebras and Completely Iterative Monads,
Inform. and Comput. 196 (2005), 1-41.

On Iteratable Endofunctors,
Electron. Notes. Theor. Comput. Sci. 69 (2002), 18pp.

The Category Theoretic Solution of Recursive Program Schemes,
joint paper with L. S. Moss, preprint, December 2005.