Structure and Power: an emerging landscape

In this paper, we give an overview of some recent work on applying tools fromcategory theory in finite model theory, descriptive complexity, constraintsatisfaction, and combinatorics. The motivations for this work come fromComputer Science, but there may also be something of interest for modeltheorists and other logicians. The basic setting involves studying the category of relational structures viaa resource-indexed family of adjunctions with some process category - whichunfolds relational structures into treelike forms, allowing natural resourceparameters to be assigned to these unfoldings. One basic instance of thisscheme allows us to recover, in a purely structural, syntax-free way: theEhrenfeucht-Fraisse~game; the quantifier rank fragments of first-order logic;the equivalences on structures induced by (i) the quantifier rank fragments,(ii) the restriction of this fragment to the existential positive part, and(iii) the extension with counting quantifiers; and the combinatorial parameterof tree-depth (Nesetril and Ossona de Mendez). Another instance recovers thek-pebble game, the finite-variable fragments, the corresponding equivalences,and the combinatorial parameter of treewidth. Other instances cover modal,guarded and hybrid fragments, generalized quantifiers, and a wide range ofcombinatorial parameters. This whole scheme has been axiomatized in a verygeneral setting, of arboreal categories and arboreal covers. Beyond this basic level, a landscape is beginning to emerge, in whichstructural features of the resource categories, adjunctions and comonads arereflected in degrees of logical and computational tractability of thecorresponding languages. Examples include semantic characterisation andpreservation theorems, and Lovasz-type results on counting homomorphisms.Comment: To appear in special issue for Trakhtenbrot centenary of Fundamenta Informaticae vol. 186 no 1-