Qualitative Spatio-Temporal Reasoning with RCC-8 and Allen's Interval Calculus: Computational Complexity
Qualitative Spatio-Temporal Reasoning with RCC-8 and Allen's Interval Calculus: Computational Complexity
复制标题
DOI：
--
复制
发表时间：
2002-07
期刊：
影响因子：
--
通讯作者：
A. Gerevini;Bernhard Nebel
中科院分区：
文献类型：
--
作者：
A. Gerevini;Bernhard Nebel
存在许多定性约束演算，用于表示和推理时间或空间结构。然而，只有很少的方法旨在创建一个时空约束演算。与Bennett等人类似，我们从空间演算RCC-8和Allen的区间演算开始，以构建定性的时空演算。正如我们将展示的，基本演算是np完全的，即使我们只允许基本关系。当添加空间区域的大小随时间持续或变化连续的限制时，演算变得更有用，但可满足性问题似乎要困难得多。然而，我们能够证明NP中仍然存在可满足性。
There exist a number of qualitative constraint calculi that are used to represent and reason about temporal or spatial configurations. However, there are only very few approaches aiming to create a spatio-temporal constraint calculus. Similar to Bennett et al., we start with the spatial calculus RCC-8 and Allen's interval calculus in order to construct a qualitative spatio-temporal calculus. As we will show, the basic calculus is NP-complete, even if we only permit base relations. When adding the restriction that the size of the spatial regions persists over time, or that changes are continuous, the calculus becomes more useful, but the satisfiability problem appears to be much harder. Nevertheless, we are able to show that satisfiability is still in NP.