Coalgebra (NWI-IMC036), fall 2016

Lecturers: Jurriaan Rot, Aleks Kissinger, Julian Salamanca

General information on this course can be found in the studiegids.

Contents of this course webpage


Dates, Time and Location

Course Material

We will follow Bart Jacobs' draft book, available here. We also use additional material, such as slides, hand-outs, and research papers on coalgebra. All material will be made available electronically via this webpage, or distributed during class. Pointers to the relevant literature are in the Lectures Overview section below.

We also recommend the tutorial on coalgebras and coinduction by Bart Jacobs and Jan Rutten. See here.


Lectures Overview

Details for each lecture and suggested exercises will be posted here during the course.
  1. Lecture 1, Monday 29 Aug, 15:45-17:30, in HG00.086
  2. No exercise class on Friday 2 Sep
  3. Lecture 2, Monday 5 Sept, 15:45-17:30, in HG00.086
  4. Exercise class, Friday 9 Sept, 10:45-12:30, in HG01.058
  5. Lecture 3, Monday 12 Sept, 15:45-17:30, in HG00.086
  6. Exercise class, Friday 16 Sept, 10:45-12:30, in HG01.058
  7. Lecture 4, Monday 19 Sept, 15:45-17:30, in HG00.086
  8. Exercise class, Friday 23 Sept, 10:45-12:30, in HG01.058
  9. Lecture 5, Monday 26 Sept, 15:45-17:30, in HG00.086
  10. Exercise class, Friday 30 Sept, 10:45-12:30, in HG01.058
  11. Lecture 6, Monday 3 Oct, 15:45-17:30, in HG00.086
  12. Exercise class, Friday 7 Oct, 10:45-12:30, in HG01.058
  13. Lecture 7, Monday 10 Oct, 15:45-17:30, in HG00.086
  14. Exercise class, Friday 14 Oct, 10:45-12:30, in HG01.058
  15. Lecture 8, Monday 17 Oct, 15:45-17:30, in HG00.086
  16. Exercise class, Friday 21 Oct, 10:45-12:30, in HG01.058
  17. Lecture 9, Monday 7 Nov, 15:45-17:30, in HFML0220
  18. Exercise class, Friday 11 Nov, 10:45-12:30, in E2.12
  19. Lecture 10, Monday 14 Nov, 15:45-17:30, in HFML0220
  20. Exercise class, Friday 18 Nov, 10:45-12:30, in HG00.086
  21. Lecture 11, Monday 21 Nov, 15:45-17:30, in HFML0220
  22. Exercise class, Friday 25 Nov, 10:45-12:30, in HG00.086
  23. Lecture 12, Monday 28 Nov, 15:45-17:30, in HFML0220
  24. Exercise class, Friday 2 Dec, 10:45-12:30, in HG00.086
  25. Lecture 13, Monday 5 Dec, 15:45-17:30, in HFML0220
  26. Exercise class, Friday 9 Dec, 10:45-12:30, in HG00.086
  27. Lecture 14, Monday 12 Dec, 15:45-17:30, in HFML0220
  28. Exercise class, Friday 16 Dec, 10:45-12:30, in HG00.086
  29. Lecture 15, Monday 19 Dec, 15:45-17:30, in HFML0220
  30. No exercise class on Friday 25 Dec.

Course Description and Prerequisites

Course description:

State-based systems are used widely in computer science to model concrete systems such as digital hardware, software programs, and distributed systems. Coalgebra is a unifying framework for studying the behaviour of state-based systems. In coalgebra, a system is viewed as a black box where knowledge of the system's state can only be obtained by observing the external behaviour. In particular, two states s and t are considered equivalent if whenever we run the system starting in state s, the observed behaviour is the same as when we run the system in starting in state t. The type of observations and transitions in the external behaviour is specified by the system type. The theory of universal coalgebra provides general definitions of observable behaviour and bisimilarity that can be instantiated for concrete system types, as well as a powerful and fascinating reasoning principle called coinduction (a notion that is dual to the well known induction principle).

This course is an introduction to coalgebra. The course starts by studying how various types of systems can be modelled as coalgebras, and how coinduction can be applied to them. These systems include basic datatypes, such as infinite streams and trees, and many types of automata (deterministic, nondeterministic, probabilistic, ...). Next, a number of fundamental notions such as language equivalence of automata, bisimilarity of processes and determinisation of nondeterministic automata, will be treated coalgebraically. The students will learn how to combine coinduction and induction to derive effective specification and reasoning techniques for automata. The coalgebraic framework will then be used to obtain generalisations of these constructions to other types of systems.

Coalgebra is a rather recent field of research, existing for a mere two decades, and it is attracting an enthusiastic, ever-growing community. Being relatively young, it still has many elementary and exciting research questions to offer.

Prerequisites: We only assume basic knowledge of automata, formal languages and propositional logic, for example, as covered in the courses Talen en Automaten, Discrete Wiskunde, Beweren en Bewijzen, en Semantiek en Correctheid. With respect to category theory, the course will be self-contained: only basic definitions will be needed, and these will be introduced as part of the course.


There will a final exam, and two extended homework assignments, the first due by the end of October, and the second in January. The final grade will be the maximum of (H+E)/2 and E, where H is the grade given for the homework assignments and E is the grade given for the final exam.