论文标题
结构和力量：新兴景观
Structure and Power: an emerging landscape
论文作者
论文摘要
在本文中，我们概述了一些在有限模型理论，描述性复杂性，约束满意度和组合学中应用类别理论的工具的最新工作。这项工作的动机来自计算机科学，但对于模型理论家和其他逻辑学家来说，也可能引起人们的兴趣。 基本设置涉及通过具有一些过程类别的资源指标家族来研究关系结构的类别 - 将关系结构展开为Treeliele形式，从而使自然资源参数可以分配给这些展开。该方案的一个基本实例使我们能够以纯粹的结构，无语法的方式恢复：ehrenfeucht-fraisse〜游戏；一阶逻辑的量词等级片段； （i）量词秩片段引起的结构的等价，（ii）限制该片段对存在阳性部分的限制，以及（iii）用计数量词的扩展；以及Tree-Depth（Nesetril和Ossona de Mendez）的组合参数。另一个实例恢复了k-pebble游戏，有限变量的片段，相应的等价和treewidth的组合参数。其他实例涵盖了模态，保护和混合片段，广义量词以及广泛的组合参数。整个方案已在非常一般的树木类别和树木覆盖物中进行了公理。 除了这个基本层面之外，景观开始出现，其中资源类别，附件和comoNADS的结构特征以相应语言的逻辑和计算障碍度反映。例子包括语义表征和保存定理，以及lovasz型的结果，以计数同态。
In this paper, we give an overview of some recent work on applying tools from category theory in finite model theory, descriptive complexity, constraint satisfaction, and combinatorics. The motivations for this work come from Computer Science, but there may also be something of interest for model theorists and other logicians. The basic setting involves studying the category of relational structures via a resource-indexed family of adjunctions with some process category - which unfolds relational structures into treelike forms, allowing natural resource parameters to be assigned to these unfoldings. One basic instance of this scheme allows us to recover, in a purely structural, syntax-free way: the Ehrenfeucht-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 parameter of tree-depth (Nesetril and Ossona de Mendez). Another instance recovers the k-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 of combinatorial parameters. This whole scheme has been axiomatized in a very general setting, of arboreal categories and arboreal covers. Beyond this basic level, a landscape is beginning to emerge, in which structural features of the resource categories, adjunctions and comonads are reflected in degrees of logical and computational tractability of the corresponding languages. Examples include semantic characterisation and preservation theorems, and Lovasz-type results on counting homomorphisms.
