Coalgebra (MGS 2022)

State transition systems are widespread in computer science. Coalgebra is a more abstract approach to these transition systems.

First we shall see what a coalgebra is, and a number of examples involving input, output, nondeterminism, divergence and (discrete) probability. In particular, we look at final coalgebras, which are used to represent data types such as lazy lists and lazy trees.

We look at various kinds of simulation and bisimulation, and see how they can be brought together using the notion of a relator.

Finally we see that simulation and bisimulation can be characterized using a final coalgebra, and conversely that we can construct a final coalgebra by taking a strongly extensional quotient.

Here are the evolving course notes.

Last modified: Mon Apr 11 11:01:51 BST 2022