Skip to main content

Research Repository

Advanced Search

Classification Transfer for Qualitative Reasoning Problems

Bodirsky, Manuel; Jonsson, Peter; Martin, Barnaby; Mottet, Antoine

Authors

Manuel Bodirsky

Peter Jonsson

Antoine Mottet



Contributors

Jérôme Lang
Editor

Abstract

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.

Citation

Bodirsky, M., Jonsson, P., Martin, B., & Mottet, A. (2018). Classification Transfer for Qualitative Reasoning Problems. In J. Lang (Ed.), Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18) (1256-1262). https://doi.org/10.24963/ijcai.2018/175

Conference Name IJCAI-ECAI 2018, the 27th International Joint Conference on Artificial Intelligence and the 23rd European Conference on Artificial Intelligence.
Conference Location Stockholm, Sweden
Start Date Jul 13, 2018
End Date Jul 19, 2018
Acceptance Date Jun 7, 2018
Publication Date Jul 19, 2018
Deposit Date Jun 22, 2018
Pages 1256-1262
Book Title Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18).
DOI https://doi.org/10.24963/ijcai.2018/175
Public URL https://durham-repository.worktribe.com/output/1144428
Publisher URL https://www.ijcai-18.org/


You might also like



Downloadable Citations