IDA Dept. of Computer and Information science, Linköping University

IDA Technical Reports: abstract

Generated: Fri, 21 Jul 2017 16:39:42

Jonsson, P. and Drakengren, T. (1996). RCC-5 and its Tractable Subclasses. Technical Report LiTH-IDA-R-96-25, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),

Abstract: We investigate the computational properties of the spatial algebra RCC-5 which is a restricted version of the RCC framework. The satisfiability problem for RCC-5 is known to be NP-complete but not much is known about its approximately four billion subclasses. We provide a complete classification of satisfiability for all these subclasses into polynomial and NP-complete respectively. In the process, we identify all maximal tractable subalgebras which are four in total.

Goto (at Linköping University): CS Dept TR Overview