We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Classification transfer for qualitative reasoning problems.

Bodirsky, Manuel and Jonsson, Peter and Martin, Barnaby and Mottet, Antoine (2018) 'Classification transfer for qualitative reasoning problems.', in Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18). , pp. 1256-1262.


We study formalisms for temporal and spatial reasoning in the modern context of Constraint Satisfaction Problems (CSPs). We show how questions on the complexity of their subclasses can be solved using existing results via the powerful use of primitive positive (pp) interpretations and pp-homotopy. We demonstrate the methodology by giving a full complexity classification of all constraint languages that are first-order definable in Allen's Interval Algebra and contain the basic relations (s) and (f). In the case of the Rectangle Algebra we answer in the affirmative the old open question as to whether ORD-Horn is a maximally tractable subset among the (disjunctive, binary) relations. We then generalise our results for the Rectangle Algebra to the r-dimensional Block Algebra.

Item Type:Book chapter
Full text:Publisher-imposed embargo
(AM) Accepted Manuscript
File format - PDF
Publisher Web site:
Date accepted:07 June 2018
Date deposited:25 June 2018
Date of first online publication:2018
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar