ML Anthology

RCC8 Is Polynomial on Networks of Bounded Treewidth

Manuel Bodirsky, Stefan Wölfl
IJCAI 2011 pp. 756-761
doi:10.5591/978-1-57735-516-8/IJCAI11-133 /ijcai/2011/bodirsky2011ijcai-rcc/

Abstract

We construct an homogeneous (and omega-categorical) representation of the relation algebra RCC8, which is one of the fundamental formalisms for spatial reasoning. As a consequence we obtain that the network consistency problem for RCC8 can be solved in polynomial time for networks of bounded treewidth.

PDF IJCAI Semantic Scholar

Cite

Text

Bodirsky and Wölfl. "RCC8 Is Polynomial on Networks of Bounded Treewidth." International Joint Conference on Artificial Intelligence, 2011. doi:10.5591/978-1-57735-516-8/IJCAI11-133

Markdown

[Bodirsky and Wölfl. "RCC8 Is Polynomial on Networks of Bounded Treewidth." International Joint Conference on Artificial Intelligence, 2011.](https://mlanthology.org/ijcai/2011/bodirsky2011ijcai-rcc/) doi:10.5591/978-1-57735-516-8/IJCAI11-133

BibTeX

@inproceedings{bodirsky2011ijcai-rcc,
  title     = {{RCC8 Is Polynomial on Networks of Bounded Treewidth}},
  author    = {Bodirsky, Manuel and Wölfl, Stefan},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2011},
  pages     = {756-761},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-133},
  url       = {https://mlanthology.org/ijcai/2011/bodirsky2011ijcai-rcc/}
}