Expressive completeness through logically tractable models
Expressive completeness through logically tractable models
复制标题
通过逻辑上易于处理的模型表达完整性
DOI：
10.1016/j.apal.2013.06.017
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
M. Otto
中科院分区：
文献类型：
--
作者：
M. Otto
我们如何证明给定逻辑的某个片段有能力精确地定义满足某些特征语义保持条件的所有结构属性？这个问题是一个基本的经典模型理论和应用程序在非经典设置一样。虽然方法有很大的不同，而经典的方法通常不能匹配，例如在有限模型理论的设置，本说明调查一些有趣的共性围绕使用和可用性的听话的代表在相关的模型类。模型的构建，其中简单的不变量，如部分类型的基础上一些弱片段控制所有相关的结构属性，可以看到在这些问题的核心。我们强调了一些建设涉及程度的非循环和饱和度，可以实现在有限的模型建设，并讨论其使用表达完整性w.r.t.超图和关系结构中基于互模拟的等价。重点是在这种更具建设性的方法，在非经典的设置，特别是在有限模型理论的组合的挑战。一个新的结果涉及表达的完整性w.r.t.保护否定互模拟，涉及局部同态的来回等价。
How can we prove that some fragment of a given logic has the power to define precisely all structural properties that satisfy some characteristic semantic preservation condition? This issue is a fundamental one for classical model theory and applications in non-classical settings alike. While methods differ greatly, and while the classical methods can usually not be matched for instance in the setting of finite model theory, this note surveys some interesting commonality revolving around the use and availability of tractable representatives in the relevant model classes. The construction of models in which simple invariants like partial types based on some weak fragment control all the relevant structural properties, may be seen at the heart of such questions. We highlight some constructions involving degrees of acyclicity and saturation that can be achieved in finite model constructions, and discuss their uses towards expressive completeness w.r.t. bisimulation based equivalences in hypergraphs and relational structures. The emphasis is on the combinatorial challenges in such more constructive approaches that work in non-classical settings and especially in finite model theory. One new result concerns expressive completeness w.r.t. guarded negation bisimulation, a back-and-forth equivalence involving local homomorphisms.
登录
查看更多内容
DOI：
10.1145/1379759.1379763
发表时间：
2008
期刊：
J. ACM
影响因子：
--
作者：
Benjamin Rossman
通讯作者：
Benjamin Rossman
互模拟不变性和有限模型
DOI：
--
发表时间：
2006
期刊：
影响因子：
--
作者：
M. Otto
通讯作者：
M. Otto
有限共形超图覆盖和有限结构中的盖夫曼团
影响因子：
0.6
作者：
I. Hodkinson;M. Otto
通讯作者：
M. Otto
DOI：
10.1007/3-540-61604-7_60
发表时间：
1996-08
期刊：
--
影响因子：
--
作者：
David Janin;I. Walukiewicz
通讯作者：
David Janin;I. Walukiewicz
有限结构上的模态逻辑
DOI：
--
发表时间：
1997
期刊：
Journal of Logic, Language and Information
影响因子：
--
作者：
Eric Rosen
通讯作者：
Eric Rosen