Query Answering with Transitive and Linear-Ordered Data
Authors: Antoine Amarilli, Michael Benedikt, Pierre Bourhis, Michael Vanden Boom
JAIR 2018 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We consider entailment problems involving powerful constraint languages... We give some natural variants of guardedness that allow inference to be decidable in each case, and isolate the complexity of the corresponding decision problems. Finally we show that slight changes in these conditions lead to undecidability. ... We provide new results on QA with transitivity and transitive closure assertions. We show that query answering is decidable... 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. ... We also show that loosening our conditions leads to undecidability. We provide both upper and lower bounds on the QA problem... |
| Researcher Affiliation | Academia | Antoine Amarilli EMAIL LTCI, T el ecom Paris Tech, Universit e Paris-Saclay; Michael Benedikt EMAIL University of Oxford; Pierre Bourhis EMAIL CNRS CRISt AL, Universit e Lille 1, INRIA Lille; Michael Vanden Boom EMAIL University of Oxford |
| Pseudocode | No | No specific section titled 'Pseudocode' or 'Algorithm' was found. The paper primarily uses mathematical notation and logical formulations to describe its methods and proofs, rather than structured algorithmic steps. |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code, nor does it provide links to code repositories or mention code in supplementary materials. |
| Open Datasets | No | The paper uses abstract examples and logical structures to illustrate its theoretical concepts (e.g., Example 2.1 showing F0 = {car(c), motor(m), sparkplug(p), part-of(p, m), part-of(m, c), broken(p)}). It does not mention the use of any publicly available or open datasets for empirical studies. |
| Dataset Splits | No | The paper is theoretical and focuses on decidability and complexity results for query answering. It does not describe any experimental evaluation using datasets, and therefore no dataset split information (training/test/validation) is provided. |
| Hardware Specification | No | The paper is a theoretical work on logical query answering and complexity. It does not include any details or specifications about hardware used for experiments or computations. |
| Software Dependencies | No | The paper presents theoretical results and does not describe any practical implementation or experimental setup. Therefore, it does not specify any software dependencies or their version numbers. |
| Experiment Setup | No | The paper focuses on theoretical contributions regarding the decidability and complexity of query answering. It does not describe any empirical experiments, and consequently, no experimental setup details, hyperparameters, or system-level training settings are provided. |