@inproceedings{d8b51537be8d4e2cbfe98a173fc026b7,
title = "On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the region connection calculus",
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 ii maximal tractable subset of the relations in RCC-8 that contains all base relations. Further, we shaw that for this subset path-consistency is sufficient for deciding consistency.",
author = "J Renz and B Nebel",
year = "1997",
language = "English",
isbn = "1-55860-480-4",
series = "International Joint Conference On Artificial Intelligence",
publisher = "Morgan Kaufmann Pub Inc",
pages = "522--527",
editor = "ME Pollack",
booktitle = "Ijcai-97 - Proceedings Of The Fifteenth International Joint Conference On Artificial Intelligence, Vols 1 And 2",
note = "15th International Joint Conference on Artificial Intelligence ; Conference date: 23-08-1997 Through 29-08-1997",
}