Title: The pebbling comonad in finite model theory (an exposition)
Abstract: In this talk, I will exposit some of the main ideas and results of the seminal 2017 paper “The pebbling comonad in finite model theory” by Samson Abramsky, Anuj Dawar, and Pengming Wang. In this paper, the authors demonstrate that pebble games, which are a powerful combinatorial tool in the study of finite model theory, constraint satisfaction, and database theory, admit a natural formulation in terms of comonads, which leads to comonadic characterizations of many central concepts in finite model theory. Specifically, given a relational signature S and S-structures A and B, the authors establish that winning strategies for the Duplicator in existential pebble games from A to B are equivalently given by morphisms from A to B in the coKleisli categories of certain comonads on the category of S-structures. The paper thereby provides a connection between two broad topics in logic and computer science that have previously been largely disjoint: the interaction of logic with computational complexity, and the study of the semantics of programs and processes. Time permitting, I will also discuss some extensions of their results that I have recently proved.
