Knowledge-Base Degrees of Inconsistency: Complexity and Counting
Authors: Johannes K. Fichte, Markus Hecher, Arne Meier6349-6357
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we provide a complexity analysis of fixed-domain nonentailment (NE) on Datalog programs for well-established families of knowledge-bases (KBs). We exhibit a detailed complexity map for the decision cases, counting and projected counting, which may serve as a quantitative measure for inconsistency of a KB with respect to a query. Our results show that NE is natural for the second, third, and fourth level of the polynomial (counting) hierarchy depending on the type of the studied query (stratified, tight, normal, disjunctive) and one level higher for the projected versions. Further, we show fixed-parameter tractability by bounding the treewidth, provide a constructive algorithm, and show its theoretical limitation in terms of conditional lower bounds. |
| Researcher Affiliation | Academia | Johannes K. Fichte1 Markus Hecher2 Arne Meier3 1 TU Dresden 2 TU Wien 3 Leibniz Universität Hannover johannes.fichte@tu-dresden.de, markus.hecher@tuwien.ac.at, meier@thi.uni-hannover.de |
| Pseudocode | Yes | Figure 2: Bag algorithm #NETight(t, τ1, . . . , τℓ ). |
| Open Source Code | No | The paper discusses related work and mentions that 'competitive implementations are available' in external citations (e.g., 'Fichte et al. 2018b, 2020; Hecher, Thier, and Woltran 2020; Dudek, Phan, and Vardi 2020'), but it does not provide any statement or link for the source code specifically developed for the methodology presented in this paper. |
| Open Datasets | No | This paper is theoretical and does not conduct experiments on datasets. The examples provided (e.g., Example 2 with domain = {donald, emanuel, silvio}) are illustrative for theoretical concepts rather than empirical evaluations, and thus no publicly available dataset is used for training. |
| Dataset Splits | No | As a theoretical paper that does not involve empirical experiments with data, there are no training, validation, or test dataset splits mentioned. |
| Hardware Specification | No | This paper is theoretical and does not involve empirical experiments requiring specific hardware. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | This paper is theoretical, focusing on complexity analysis and algorithm design, and does not describe an implementation that would require specific software dependencies with version numbers. While it references other implementations, it does not list any for its own work. |
| Experiment Setup | No | This paper is theoretical and does not involve empirical experiments. Therefore, no experimental setup details, such as hyperparameters or training configurations, are provided. |