Classification Transfer for Qualitative Reasoning Problems
Authors: Manuel Bodirsky, Peter Jonsson, Barnaby Martin, Antoine Mottet
IJCAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study formalisms for temporal and spatial reasoning in the modern, algebraic and modeltheoretic, 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 pphomotopy. 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. |
| Researcher Affiliation | Academia | Manuel Bodirsky1, Peter Jonsson2 e, Barnaby Martin3, Antoine Mottet1 1 Institut f ur Algebra, TU Dresden, Germany 2 Dept. of Computer and Information Science, Link opings Universitet, Sweden 3 Dept. of Computer Science, Durham University, UK |
| Pseudocode | No | The paper does not contain any pseudocode or clearly labeled algorithm blocks. |
| Open Source Code | No | The paper does not provide any concrete access to source code for the methodology described. |
| Open Datasets | No | The paper discusses mathematical formalisms and structures (e.g., Interval Algebra, Rectangle Algebra, Block Algebra) rather than empirical datasets. Therefore, no information about publicly available datasets for training is provided. |
| Dataset Splits | No | The paper describes theoretical work and does not involve experimental data splits for training, validation, or testing. |
| Hardware Specification | No | The paper describes theoretical work and does not involve empirical experiments requiring specific hardware. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper describes theoretical work and does not mention any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper describes theoretical work and does not detail any experimental setup, hyperparameters, or system-level training settings. |