Coinductive Methods in Computer Science (and beyond) – F. Bonchi

We are happy to host Filippo Bonchi, Chargé de Recherche at the Ecole Normale Supérieure Lyon, who will give a PhD course about

Coinductive Methods in Computer Science (and beyond).

The lectures will take place at the Department of Mathematics, Computer Science and Physics, as follows:

  1. May 9, 10.30–12.30, Sala Riunioni – slides
  2. May 10, 10.30–12.30, Aula Multimediale – slides
  3. May 11, 14.30–16.30, Sala Riunioni
  4. May 12, 11.00–13.00, Sala Riunioni
  5. May 13, 10.00–12.00, Sala Riunioni

The induction principle is ubiquitous in computer science. For instance it is used to prove properties of programs involving finite data structures, such as natural numbers, lists and trees. For reasoning about concurrent programs or infinite data structures, like streams and infinite trees, one needs a dual principle — coinduction — which is the main topic of this course.
The relevance of coinductive reasoning has been usually associated with bisimilarity, a notion of equivalence that emerged at the end of the seventies in three different fields: non-well founded set theory, modal logics and concurrency theory. In the last years, coinductive methods has been studied in more and more areas of computer science, such as automata and type theory. Perhaps unexpectedly, applications to game theory and economy have been proposed recently.
We will introduce the coinductive definition and proof principles, several techniques to enhance coinductive proofs, and some algorithms to automatize such proofs. During the course, we will encounter examples stemming from different areas, with particular focus to automata and concurrency theory. If time allows, we will also give an overview to the theory of coalgebras, which is the abstract framework encompassing all these different examples.