Monthly Archives: February 2021

Talk by Adam Ó Conghaile

Today Adam Ó Conghaile will give a talk on “Games & Comonads in Finite Model Theory” as a part of our Theory Seminar Series.

Abstract. Model-comparison games (such as Ehrenfeucht-Fraïssé games, pebble games and modal bisimulation) capture various approximations to isomorphism and homomorphism between structures. These approximations are important and well-studied in computer science for their connections with logic and algorithms but their descriptions are often ad hoc and unified approach to these games is lacking in classical finite model theory. Game comonads, introduced by Abramsky, Dawar & Wang [1], provide a categorical semantics for these games which reveals connections between these games and relates them in a surprising and elegant way to structural parameters such as treewidth.

In my talk, I will survey the landscape of model-comparison games and developments in this new comonadic perspective to them, including contributions from my recent work with Anuj Dawar on game comonads for logics with generalised quantifiers. [2]

[1] – S. Abramsky, A. Dawar, P. Wang The pebbling comonad in finite model theory, LiCS 2017
[2] – A. Ó Conghaile, A. Dawar Game comonads & generalised quantifiers, CSL 2021