AAAI Publications, Twenty-Second International Joint Conference on Artificial Intelligence

Font Size: 
RCC8 Is Polynomial on Networks of Bounded Treewidth
Manuel Bodirsky, Stefan Wölfl

Last modified: 2011-06-28


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.

Full Text: PDF