On the Complexity of Qualitative Spatial Reasoning: A Maximal Tractable Fragment of the Region Connection Calculus
Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence. Diagnosis and Qualitative Reasoning. Pages 522-526.
Abstract
The computational properties of qualitative spatial reasoning have been investigated to some degree. However, the question for the boundary between polynomial and NP-hard reasoning problems has not been addressed yet. In this paper we explore this boundary in the "Region Connection Calculus" RCC-8. We extend Bennett's encoding of RCC-8 in modal logic. Based on this encoding, we prove that reasoning is NP-complete in general and identify a maximal tractable subset of the relations in RCC-8 that contains all base relations. Further, we show that for this subset path-consistency is sufficient for deciding consistency.
@inproceedings{ijcai1997p77,
title = {On the Complexity of Qualitative Spatial Reasoning: A Maximal Tractable Fragment of the Region Connection Calculus},
author = {Renz, Jochen and Nebel, Bernhard},
booktitle = {Proceedings of the Fifteenth International Joint Conference on
Artificial Intelligence, {IJCAI-97}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Martha E. Pollack},
pages = {522--526},
year = {1997},
note = {Diagnosis and Qualitative Reasoning},
url = {https://ijcai.org/proceedings/1997/77},
}
TY - CPAPER TI - On the Complexity of Qualitative Spatial Reasoning: A Maximal Tractable Fragment of the Region Connection Calculus AU - Renz, Jochen AU - Nebel, Bernhard T2 - Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, IJCAI-97 PB - International Joint Conferences on Artificial Intelligence PY - 1997 SP - 522 EP - 526 UR - https://ijcai.org/proceedings/1997/77 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
