Coalgebra: an introduction and an application
by
Jan Rutten
CWI and VUA, Amsterdam

Coalgebras are the formal dual of algebras and have over the last decade or so become popular in both mathematics and computer science as unified models of various state-based dynamical systems. Examples are automata, transition systems, (infinite) data types, discrete event systems, and many more. In this lecture, we shall briefly review the basic notions of the discipline of coalgebra, which are bisimulation, finality, and coinduction. Next we shall discuss, more concretely, a recent application of coalgebra to the symbolic synthesis of sequential digital circuits for binary arithmetic. As we shall see, the analysis of the final coalgebra of so-called causal functions on bitstreams will lead to the construction of circuits with minimal memory.

Date received: May 18, 2004