Logical resources and arboreal adjunctions


Luca Reggio, Oxford. 2 mars 2023 10:15 limd
Abstract:

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 ofarboreal 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. I will illustrate an application of this axiomatic framework to the study ofequi-resource' homomorphism preservation theorems in (finite) model theory, exemplified by Rossman's equirank homomorphism preservation theorem. If time allows, I will also discuss recent work on identifying the expressive power of arboreal adjunctions.