A Tale of Trees, Resource-Bounded Logics, and Comonads
Luca Reggio, University of Milan
Logics that are obtained by constraining the available syntactic resources, such as first-order logic with a finite number of variables or with bounded quantifier rank, are central to finite model theory and descriptive complexity. In this talk, I will describe a categorical approach, which is model-theoretic in spirit, to study these logics using so-called game comonads. I will explain how these comonads capture various logic fragments (positive, existential, etc.) and combinatorial parameters of structures in a syntax-free manner. Furthermore, I will argue that this categorical perspective suggests a modal approach to various resource-bounded logics.