2022/05/11 by Tomáš Jakl, Jakl, Tomáš, Dan Marsden +3
Computer Science · Economics, Econometrics and Finance · #Category Theory (math.CT) #FOS: Computer and information sciences #FOS: Mathematics #Game Theory and Voting Systems #Logic (math.LO) #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Logic, programming, and type systems
paper · pdf · doi:10.48550/arxiv.2205.05387
openalex publication_date 2022/05/11 · openalex created_date 2022/05/22 · openalex updated_date 2026/07/28
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.