Manuel Bodirsky
Classification Transfer for Qualitative Reasoning Problems
Bodirsky, Manuel; Jonsson, Peter; Martin, Barnaby; Mottet, Antoine
Authors
Peter Jonsson
Dr Barnaby Martin barnaby.d.martin@durham.ac.uk
Summer School Academic (Casual)
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
Presentation Conference Type | Conference Paper (Published) |
---|---|
Conference Name | IJCAI-ECAI 2018, the 27th International Joint Conference on Artificial Intelligence and the 23rd European Conference on Artificial Intelligence. |
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
Depth lower bounds in Stabbing Planes for combinatorial principles
(2024)
Journal Article
Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs
(2023)
Presentation / Conference Contribution
The Complexity of L(p, q)-Edge-Labelling
(2023)
Journal Article
Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs
(2023)
Journal Article
Few induced disjoint paths for H-free graphs
(2022)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search