Luca Reggio (Università di Milano) will give a talk on
Resource-bounded logics: a categorical and modal view
Abstract:
Logics 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. I will describe a categorical approach to the study of these logic fragments based on so-called game comonads. The main properties of the categories of coalgebras for these comonads lead to the axiomatic notion of arboreal categories, which in turn suggest a modal treatment of many resource-bounded logics.