Coalgebras, Monads and Semantics
Stefan Milius
PhD thesis, Technische Universität Braunschweig, October 2005.
Abstract
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)
Summary
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.