Query Answering with Transitive and Linear-Ordered Data
Authors: Antoine Amarilli, Michael Benedikt, Pierre Bourhis, Michael Vanden Boom
IJCAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We consider entailment problems involving powerful constraint languages such as guarded existential rules, in which additional semantic restrictions are put on a set of distinguished relations. We give some natural generalizations of guardedness that allow inference to be decidable in each case, and isolate the complexity of the corresponding decision problems. Our results are shown by arguing that it is enough to consider entailment over tree-like sets of facts. By representing the set of witness representations as a tree automaton, we derive upper bounds for the combined complexity of the problem. The sufficiency of tree-like examples also enable a refined analysis of data complexity (when the query and constraints are fixed). Further, we use a set of coding techniques to show matching lower bounds within our fragment. We also show that loosening our conditions leads to undecidability. |
| Researcher Affiliation | Academia | Antoine Amarilli LTCI, CNRS, T el ecom Paris Tech Universit e Paris-Saclay Michael Benedikt University of Oxford Pierre Bourhis CNRS CRISt AL, Universit e Lille 1 INRIA Lille Michael Vanden Boom University of Oxford |
| Pseudocode | No | The paper does not contain any pseudocode or clearly labeled algorithm blocks. |
| Open Source Code | No | The paper does not provide any specific links or explicit statements about the availability of open-source code for the methodology described. |
| Open Datasets | No | This is a theoretical paper that does not involve training or using empirical datasets. Therefore, it does not discuss public dataset availability. |
| Dataset Splits | No | This is a theoretical paper and does not discuss empirical dataset splits for validation. |
| Hardware Specification | No | This is a theoretical paper and does not describe hardware specifications used for experiments. |
| Software Dependencies | No | This is a theoretical paper that focuses on logical formalisms and complexity results, and therefore does not list specific software dependencies with version numbers for experimental reproducibility. |
| Experiment Setup | No | This is a theoretical paper and does not describe an empirical experimental setup with details such as hyperparameters or training configurations. |