Modal Logics of Topological Relations
Modal Logics of Topological Relations
复制标题
拓扑关系的模态逻辑
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
F. Wolter
中科院分区：
文献类型：
--
作者：
C. Lutz;F. Wolter
空间区域间的八种拓扑RCC8（或Egenhofer-Franzosa）关系在空间推理、空间和约束数据库以及地理信息系统中发挥着重要作用。与Halpern和Shoham基于Allen关系的时间间隔模态逻辑类似，我们引入了一组由rcc8关系解释的八个模态算子的模态逻辑。语义是基于由标准拓扑空间，特别是实平面导出的区域空间。我们研究了用这种方法得到的逻辑的表达能力和计算复杂性。结果表明，与Halpern和Shoham的逻辑类似，拓扑模态逻辑的表达能力是相当自然的，但计算行为是有问题的：拓扑模态逻辑通常是不可确定的，甚至往往不是递归可枚举的。如果我们将自己限制在有限区域空间的类别或由拓扑空间引起的区域空间的子结构中，这一点甚至成立。我们还分析了基于rcc5关系集的模态逻辑，得到了类似的结果。
The eight topological RCC8(or Egenhofer-Franzosa)- relations between spatial regions play a fundamental role in spatial reasoning, spatial and constraint databases, and geographical information systems. In analogy with Halpern and Shoham’s modal logic of time intervals based on the Allen relations, we introduce a family of modal logics equipped with eight modal operators that are interpreted by the RCC8-relations. The semantics is based on region spaces induced by standard topological spaces, in particular the real plane. We investigate the expressive power and computational complexity of the logics obtained in this way. It turns our that, similar to Halpern and Shoham’s logic, the expressive power is rather natural, but the computational behavior is problematic: topological modal logics are usually undecidable and often not even recursively enumerable. This even holds if we restrict ourselves to classes of finite region spaces or to substructures of region spaces induced by topological spaces. We also analyze modal logics based on the set of RCC5relations, with similar results.