Luca Reggio (UCL)
| Dates: | 26 April 2023 |
|---|
| Times: | 15:15 - 16:15 |
|---|
| What is it: | Seminar |
|---|
| Organiser: | Department of Mathematics |
|---|
| Who is it for: | University staff, External researchers, Adults, Alumni, Current University students |
|---|
|
Title: Logical resources and arboreal adjunctions
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 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.
Travel and Contact Information
Find event
Frank Adams 1 (and zoom, link in email)
Alan Turing Building
Manchester
