TY - GEN
T1 - On the complexity of qualitative spatial reasoning
T2 - 15th International Joint Conference on Artificial Intelligence
AU - Renz, J
AU - Nebel, B
PY - 1997
Y1 - 1997
N2 - 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.
AB - 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.
UR - https://www.webofscience.com/api/gateway?GWVersion=2&SrcApp=anu_research_portal_plus2&SrcAuth=WosAPI&KeyUT=WOS:000072707200077&DestLinkType=FullRecord&DestApp=WOS_CPL
M3 - Conference contribution
SN - 1-55860-480-4
T3 - International Joint Conference On Artificial Intelligence
SP - 522
EP - 527
BT - Ijcai-97 - Proceedings Of The Fifteenth International Joint Conference On Artificial Intelligence, Vols 1 And 2
A2 - Pollack, ME
PB - Morgan Kaufmann Pub Inc
Y2 - 23 August 1997 through 29 August 1997
ER -