Finite Model Reasoning in Hybrid Classes of Existential Rules
Authors: Georg Gottlob, Marco Manna, Andreas Pieris
IJCAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | The complexity of query answering under this hybrid class of existential rules is by now well-understood. However, the complexity of finite query answering, i.e., query answering under finite models, has remained an open problem. Closing this problem is the main goal of this work. The main outcome of our analysis is that finite query answering under tameness has the same complexity as (unrestricted) query answering. This is obtained by showing that the tamed combination of guardedness and stickiness enjoys finite controllability, i.e., finite and unrestricted query answering coincide. This exploits the fact that both guardedness and stickiness enjoy finite controllability [B ar any et al., 2014; Gogacz and Marcinkowski, 2017]. Our results can be summarized as follows: We first focus on a subclass of tame rules, obtained by posing a stratification condition on guarded and sticky rules, and show that is finitely controllable. We then establish that a tame set of guarded and sticky rules can be rewritten as a stratified one that preserves finite answers, and thus tameness ensures finite controllability. This result immediately implies that finite query answering under tame guarded and sticky rules is 2EXPTIME-complete in combined complexity, and PTIME-complete in data complexity. |
| Researcher Affiliation | Academia | 1Department of Computer Science, University of Oxford 2Department of Mathematics and Computer Science, University of Calabria 3School of Informatics, University of Edinburgh georg.gottlob@cs.ox.ac.uk, manna@mat.unical.it, apieris@inf.ed.ac.uk |
| Pseudocode | No | The paper describes algorithms and procedures textually, such as the enriching step and formalization of embedding, but does not provide structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any explicit statements about releasing source code for the methodology described, nor does it include links to code repositories. |
| Open Datasets | No | This is a theoretical paper focusing on complexity and decidability in logic, not on empirical experiments with datasets. Thus, no datasets, public or otherwise, are mentioned for training. |
| Dataset Splits | No | This is a theoretical paper. It does not involve experimental validation on datasets, and therefore, no training/test/validation splits are discussed. |
| Hardware Specification | No | This is a theoretical paper, and thus it does not mention any hardware specifications used for experiments. |
| Software Dependencies | No | This is a theoretical paper. It does not discuss any software dependencies or versions used for empirical experiments. |
| Experiment Setup | No | This is a theoretical paper. It does not describe an experimental setup, hyperparameters, or training settings, as no empirical experiments are conducted. |