论文标题
离散密度共同和图参数
Discrete density comonads and graph parameters
论文作者
论文摘要
Game ComonAds带来了一种新的方法来显然研究有限模型理论。通过以语义代表模型比较游戏，它们允许重要的逻辑和组合属性以其Eilenberg-Moore Colgebras的形式降低。结果，有限模型理论的许多结果，例如保存定理和计算定理的同构理论，已被comoNADS形式化和参数化，仅通过改变ComOnad而产生了新的结果。 在本文中，无论是否涉及任何模型比较游戏，我们都研究了该理论的组合和同态计数方面的共生方法的局限性。我们表明，任何标准图参数都有相应的comonad，对同一类进行分类。该ComOnad是通过简单的KAN扩展公式构建的，使其成为解决此问题的初始解决方案，此外，自动承认对定理的同态性。
Game comonads have brought forth a new approach to studying finite model theory categorically. By representing model comparison games semantically as comonads, they allow important logical and combinatorial properties to be exressed in terms of their Eilenberg-Moore coalgebras. As a result, a number of results from finite model theory, such as preservation theorems and homomorphism counting theorems, have been formalised and parameterised by comonads, giving rise to new results simply by varying the comonad. In this paper we study the limits of the comonadic approach in the combinatorial and homomorphism-counting aspect of the theory, regardless of whether any model comparison games are involved. We show that any standard graph parameter has a corresponding comonad, classifying the same class. This comonad is constructed via a simple Kan extension formula, making it the initial solution to this problem and, furthermore, automatically admitting a homomorphism-counting theorem.
