T. Drakengren and P. Jonsson (1997) "A Complete Classification of Tractability in RCC-5", Volume 6, pages 211-221

PDF | PostScript | doi:10.1613/jair.379
Appendix - Source code

We investigate the computational properties of the spatial algebra RCC-5 which is a restricted version of the RCC framework for spatial reasoning. 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.

Click here to return to Volume 6 contents list