论文标题
Courcelle和Feferman-Mostowski定理的游戏说明
A game comonadic account of Courcelle and Feferman-Vaught-Mostowski theorems
论文作者
论文摘要
由Abramsky，Dawar和Wang推出，由Abramsky和Shah开发的Game Comonads提供了一个分类语义，用于模型比较游戏。我们提供了Feferman-Dubthing-Mostowski（FVM）组成定理的公理帐户，该构图由模型比较游戏进行了参数化。我们以统一的方式为所讨论的逻辑产生组成性结果及其积极的存在和计数量词变体。 其次，我们将游戏comonads扩展到第二阶设置，特别是在Monadic二阶（MSO）逻辑的情况下。然后，我们将FVM定理概括为第二阶情况。最后，我们以库尔塞尔算法元元理论的抽象表述，利用了我们早期的发展。该实例化是为了恢复图形上MSO的众所周知的界限和有界的COURCELLE定理。
Game comonads, introduced by Abramsky, Dawar and Wang, and developed by Abramsky and Shah, give a categorical semantics for model comparison games. We present an axiomatic account of Feferman-Vaught-Mostowski (FVM) composition theorems within the game comonad framework, parameterized by the model comparison game. In a uniform way, we produce compositionality results for the logic in question, and its positive existential and counting quantifier variants. Secondly, we extend game comonads to the second order setting, specifically in the case of Monadic Second Order (MSO) logic. We then generalize our FVM theorems to the second order case. We conclude with an abstract formulation of Courcelle's algorithmic meta-theorem, exploiting our earlier developments. This is instantiated to recover well-known bounded tree-width and bounded clique-width Courcelle theorems for MSO on graphs.
