Reasoning about Betweenness and RCC8 Constraints in Qualitative Conceptual Spaces
Authors: Steven Schockaert, Sanjiang Li
IJCAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | we study the problem of spatial reasoning about qualitative abstractions of such representations. In particular, we consider the problem of deciding whether an RCC8 network extended with constraints about betweenness can be realized using bounded and convex regions in a highdimensional Euclidean space. After showing that this decision problem is PSPACE-hard in general, we introduce an important fragment for which deciding realizability is NP-complete. To this end, we study the problem of deciding whether a set of RCC8 constraints with betweenness information can be realized using convex regions. First, we show that this decision problem is PSPACE-hard in general. We then introduce an important fragment, and show that deciding realizability for this fragment is NP-complete. The paper contains proofs (e.g., Theorem 1, Theorem 2, Proposition 1, Proposition 2) and complexity analysis, which are hallmarks of theoretical research. It does not describe any empirical studies, data analysis, or performance metrics from experiments. |
| Researcher Affiliation | Academia | Steven Schockaert School of Computer Science and Informatics Cardiff University, UK schockaerts1@cardiff.ac.uk Sanjiang Li Centre for Quantum Software and Information University of Technology Sydney, Australia sanjiang.li@uts.edu.au |
| Pseudocode | No | The paper does not contain any pseudocode or clearly labeled algorithm blocks. |
| Open Source Code | No | The paper provides a link to an 'online appendix' for proofs, but not to open-source code for any described methodology. 'The proofs of all results from this paper are available in an online appendix at: http://users.cs.cf.ac.uk/S.Schockaert/reports/betweennessRCC8supplement.pdf' |
| Open Datasets | No | The paper is theoretical and does not use datasets for training or empirical evaluation. |
| Dataset Splits | No | The paper is theoretical and does not involve dataset splits for validation. |
| Hardware Specification | No | The paper is theoretical and does not describe any experimental setup or the hardware used. |
| Software Dependencies | No | The paper is theoretical and does not specify any software dependencies with version numbers for implementation or experiments. |
| Experiment Setup | No | The paper is theoretical and does not include details about an experimental setup, hyperparameters, or training settings. |