Modal characterisation theorems over special classes of frames
Modal characterisation theorems over special classes of frames
复制标题
特殊类别框架的模态表征定理
DOI：
10.1016/j.apal.2009.04.002
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
M. Otto
中科院分区：
文献类型：
--
作者：
A. Dawar;M. Otto
我们研究了模态逻辑在互模拟不变性方面的表达能力的模型论特征。这种类型的典型结果是货车Bentham定理，它说一个一阶公式在互模拟下是不变的，当且仅当它等价于基本模态逻辑的公式。目前的调查主要涉及特定类别的结构的后果。我们研究特别是模型类定义的基础框架上的条件，重点放在框架类中发挥了重要作用，模态对应理论，往往对应于典型的应用领域的模态逻辑。经典模型论的论点不适用于许多最有趣的类，例如，根框架，有限根框架，有限传递框架，良基传递框架，有限等价框架，因为这些都不是基本的。相反，我们开发和扩展基于游戏的分析（一阶Escherichfeucht-Fraïssé与互模拟游戏）在这些类，并提供互模拟保持这些类内的模型构造。在大多数的类考虑，我们得到有限的模型理论类似物的经典预期的特征，新的证明也为经典的设置。传递框架类是一个显著的例外，经典的互模拟不变的一阶性质和有限模型理论之间存在显著的差异。特别是在所有有限传递框架的类中，我们发现一元二阶逻辑在互模拟不变性质方面并不比一阶逻辑更有表现力--尽管两者在这里都比基本模态逻辑更有表现力。我们得到的德容-Sambin定理的分支和一个新的和具体的模拟的Janin-Walukiewicz表征互模拟不变的一元二阶有限传递框架。
We investigate model theoretic characterisations of the expressive power of modal logics in terms of bisimulation invariance. The paradigmatic result of this kind is van Benthem’s theorem, which says that a first-order formula is invariant under bisimulation if, and only if, it is equivalent to a formula of basic modal logic. The present investigation primarily concerns ramifications for specific classes of structures. We study in particular model classes defined through conditions on the underlying frames, with a focus on frame classes that play a major role in modal correspondence theory and often correspond to typical application domains of modal logics. Classical model theoretic arguments do not apply to many of the most interesting classes–for instance, rooted frames, finite rooted frames, finite transitive frames, well-founded transitive frames, finite equivalence frames–as these are not elementary. Instead we develop and extend the game-based analysis (first-order Ehrenfeucht–Fraïssé versus bisimulation games) over such classes and provide bisimulation preserving model constructions within these classes. Over most of the classes considered, we obtain finite model theory analogues of the classically expected characterisations, with new proofs also for the classical setting. The class of transitive frames is a notable exception, with a marked difference between the classical and the finite model theory of bisimulation invariant first-order properties. Over the class of all finite transitive frames in particular, we find that monadic second-order logic is no more expressive than first-order as far as bisimulation invariant properties are concerned — though both are more expressive here than basic modal logic. We obtain ramifications of the de Jongh–Sambin theorem and a new and specific analogue of the Janin–Walukiewicz characterisation of bisimulation invariant monadic second-order for finite transitive frames.
登录
查看更多内容
DOI：
10.1016/s0049-237x(08)72008-1
发表时间：
1978
期刊：
Studies in logic and the foundations of mathematics
影响因子：
--
作者：
C. Smorynski
通讯作者：
C. Smorynski
DOI：
10.1016/s1570-2464(07)80008-5
发表时间：
2007
期刊：
--
影响因子：
--
作者：
V. Goranko;M. Otto
通讯作者：
V. Goranko;M. Otto
论CTL的表达能力
DOI：
--
发表时间：
1999
期刊：
Proceedings. 14th Symposium on Logic in Computer Science (Cat. No. PR00158)
影响因子：
--
作者：
F. Moller;A. Rabinovich
通讯作者：
A. Rabinovich
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