Complexity and Expressive Power of Disjunction and Negation in Limit Datalog
Authors: Mark Kaminski, Bernardo Cuenca Grau, Egor V. Kostylev, Ian Horrocks2862-2869
AAAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we study the complexity and expressive power of limit Datalog programs extended with disjunction in the heads of rules and non-monotonic negation under the stable model semantics. We show that allowing for unrestricted use of negation leads to undecidability of reasoning. Decidability can be restored by stratifying the use of negation over predicates carrying numeric values. We show that the resulting language is ΠEXP 2 -complete in combined complexity and that it captures ΠP 2 over ordered structures in the sense of descriptive complexity. |
| Researcher Affiliation | Academia | Mark Kaminski, Bernardo Cuenca Grau, Egor V. Kostylev, Ian Horrocks Department of Computer Science, University of Oxford, UK {mark.kaminski, bernardo.cuenca.grau, egor.kostylev, ian.horrocks}@cs.ox.ac.uk |
| Pseudocode | Yes | ALGORITHM 1: Fact Non-Entailment |
| Open Source Code | No | The paper does not provide any links or explicit statements about the availability of open-source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not involve empirical experiments with datasets, thus no training dataset is mentioned. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with datasets, thus no validation dataset is mentioned. |
| Hardware Specification | No | The paper is theoretical and does not describe any experimental setup that would require hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not describe any experimental setup that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on complexity and expressive power of a language, not on experimental setup details like hyperparameters or training settings. |