Talks and Poster Presentations (with Proceedings-Entry):

J. Fichte, M. Hecher, A. Meier:
"Knowledge-Base Degrees of Inconsistency: Complexity and Counting";
Talk: 35th AAAI 2021, virtual event; 2021-02-02 - 2021-02-09; in: "Thirty-Fifth {AAAI} Conference on Artificial Intelligence, {AAAI} 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, {IAAI} 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, {EAAI} 2021, Virtual Event, February 2-9, 2021}", (2021), 6349 - 6357.

English abstract:
Description logics (DLs) are knowledge representation languages that are used in the field of artificial intelligence (AI). A common technique is to query DL knowledge bases, e.g., by Boolean Datalog queries, and ask for entailment. But real world knowledge-bases are often obtained by combining data from various sources. This, inherently, might result in certain inconsistencies (with respect to a given query) and requires to estimate a degree of inconsistency before using a knowledge-base. In this paper, we provide a complexity analysis of fixed-domain non-entailment (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, 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.

Computational Complexity of Reasoning, Description Logics, Logic Programming

Related Projects:
Project Head Stefan Woltran:

Created from the Publication Database of the Vienna University of Technology.