Classification transfer for qualitative reasoning problems

Publikationstyp
Conference Paper
Date Issued
2018-07
Sprache
English
Author(s)
Bodirsky, Manuel  
Jonsson, Peter  
Martin, Barnaby  
Mottet, Antoine  
TORE-URI
http://hdl.handle.net/11420/12094
Volume
2018-July
Start Page
1256
End Page
1262
Citation
27th International Joint Conference on Artificial Intelligence (IJCAI 2018)
Contribution to Conference
27th International Joint Conference on Artificial Intelligence, IJCAI 2018  
Publisher DOI
10.24963/ijcai.2018/175
Scopus ID
2-s2.0-85055721352
We study formalisms for temporal and spatial reasoning in the modern, algebraic and model-theoretic, context of infinite-domain 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.