论文标题
守护片段的共生语义
Comonadic semantics for guarded fragments
论文作者
论文摘要
In previous work, Abramsky, Dawar and Wang (LiCS 2017) and Abramsky and Shah (CSL 2018) have shown how a range of model comparison games which play a central role in finite model theory, including Ehrenfeucht-Fraisse, pebbling, and bisimulation games, can be captured in terms of resource-indexed comonads on the category of relational structures.此外，这些共同的山地捕获了重要的组合参数，例如树宽度和树深度。 本文将此分析扩展到了一阶逻辑的量化片段。我们提供一个系统的帐户，涵盖原子，松散和集团的后卫。在每种情况下，我们都表明，Cokleisli的形态捕获了在存在的受保护的分配游戏中为重复者的获胜策略，而来回分配，因此在完全保护的碎片中相等，被开放式形态学的跨度捕获。我们研究了这些共同的山地，并表明它们对应于保护树的分解。我们将这些结构与无语法设置联系起来，并在HyperGraphs类别上使用ComOnad。
In previous work, Abramsky, Dawar and Wang (LiCS 2017) and Abramsky and Shah (CSL 2018) have shown how a range of model comparison games which play a central role in finite model theory, including Ehrenfeucht-Fraisse, pebbling, and bisimulation games, can be captured in terms of resource-indexed comonads on the category of relational structures. Moreover, the coalgebras for these comonads capture important combinatorial parameters such as tree-width and tree-depth. The present paper extends this analysis to quantifier-guarded fragments of first-order logic. We give a systematic account, covering atomic, loose and clique guards. In each case, we show that coKleisli morphisms capture winning strategies for Duplicator in the existential guarded bisimulation game, while back-and-forth bisimulation, and hence equivalence in the full guarded fragment, is captured by spans of open morphisms. We study the coalgebras for these comonads, and show that they correspond to guarded tree decompositions. We relate these constructions to a syntax-free setting, with a comonad on the category of hypergraphs.
