ECAI-2000 Conference Paper

[full paper]

Spatial Reasoning in RCC-8 with Boolean Region Terms

Frank Wolter, Michael Zakharyaschev

This work belongs to the field of qualitative spatial representation and reasoning. We extend the expressive power of the region connection calculus RCC-8 by allowing applications of the 8 binary relations of RCC-8 not only to atomic regions but also to Boolean combinations of them. It is shown that the satisfiability problem for the extended language in arbitrary topological spaces is still NP; however, it becomes PSPACE-complete if only Eucledean spaces are regarded as possible interpretations. In particular, in contrast to pure RCC-8, the language is capable to distinguishing between connected an non-connected topological spaces.

Keywords: Spatial Reasoning, Qualitative Reasoning

Citation: Frank Wolter, Michael Zakharyaschev: Spatial Reasoning in RCC-8 with Boolean Region Terms. In W.Horn (ed.): ECAI2000, Proceedings of the 14th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2000, pp.244-248.