Logical resources and arboreal adjunctions

I will give an overview of some recent work on applying categorical methods in finite model theory and descriptive complexity.

A key idea of a research program started by Abramsky, Dawar et al. in 2017 is that various forms of model comparison game, central to finite model theory, can be encoded as `game comonads', i.e. resource-indexed comonads on the category of relational structures. For example, the following ingredients can be captured in a syntax-free way: Ehrenfeucht-Fraïssé games, fragments of first-order logic with bounded quantifier rank, and the combinatorial parameter of tree-depth. This approach covers also finite variable fragments, modal and guarded fragments, and more.

The pattern of game comonads has been axiomatised at a general level in terms of `arboreal adjunctions', i.e. adjunctions between an extensional category (typically, in the examples, a category of relational structures) and a resource-indexed family of `arboreal categories'. If time allows, I will illustrate an application of this axiomatic framework to the study of `equi-resource' homomorphism preservation theorems in model theory (exemplified by Rossman's equirank homomorphism preservation theorem) and discuss recent work on identifying the expressive power of arboreal adjunctions.