On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus

摘要: The computational properties of qualitative spatial reasoning have been investigated to some degree. However, the question for boundary between polynomial and NP-hard problems has not addressed yet. In this paper we explore in ``Region Connection Calculus'''' RCC-8. We extend Bennett''s encoding RCC-8 modal logic. Based on encoding, prove that is NP-complete general identify a maximal tractable subset relations contains all base relations. Further, show path-consistency sufficient deciding consistency.