A Complete Classification of Tractability in RCC-5

JAIR 1997 pp. 211-221

doi:10.1613/JAIR.379 /jair/1997/jonsson1997jair-complete/

Abstract

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.

PDF JAIR Semantic Scholar

Cite

Text

Jonsson and Drakengren. "A Complete Classification of Tractability in RCC-5." Journal of Artificial Intelligence Research, 1997. doi:10.1613/JAIR.379

Markdown

[Jonsson and Drakengren. "A Complete Classification of Tractability in RCC-5." Journal of Artificial Intelligence Research, 1997.](https://mlanthology.org/jair/1997/jonsson1997jair-complete/) doi:10.1613/JAIR.379

BibTeX

@article{jonsson1997jair-complete,
  title     = {{A Complete Classification of Tractability in RCC-5}},
  author    = {Jonsson, Peter and Drakengren, Thomas},
  journal   = {Journal of Artificial Intelligence Research},
  year      = {1997},
  pages     = {211-221},
  doi       = {10.1613/JAIR.379},
  volume    = {6},
  url       = {https://mlanthology.org/jair/1997/jonsson1997jair-complete/}
}