Details
| Original language | English |
|---|---|
| Title of host publication | 35th AAAI Conference on Artificial Intelligence, AAAI 2021 |
| Pages | 6349-6357 |
| Number of pages | 9 |
| ISBN (electronic) | 9781713835974 |
| Publication status | Published - 18 May 2021 |
| Event | Thirty-Fifth AAAI Conference on Artificial Intelligence - online Duration: 2 Feb 2021 → 9 Feb 2021 |
Publication series
| Name | AAAI-21 Technical Tracks |
|---|---|
| Number | 7 |
| Volume | 35 |
| ISSN (Print) | 2159-5399 |
| ISSN (electronic) | 2374-3468 |
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 often have a certain inconsistency (with respect to a given query) or we are required to estimate a degree of inconsistency when 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, 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.
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
35th AAAI Conference on Artificial Intelligence, AAAI 2021. 2021. p. 6349-6357 (AAAI-21 Technical Tracks; Vol. 35, No. 7).
Research output: Chapter in book/report/conference proceeding › Conference contribution › Research › peer review
}
TY - GEN
T1 - Knowledge-Base Degrees of Inconsistency - Complexity and Counting
AU - Fichte, Johannes Klaus
AU - Hecher, Markus
AU - Meier, Arne
N1 - Funding Information: The work has been supported by FWF, Grants Y698, and P32830, WWTF Grant ICT19-065, and the German Research Foundation (DFG) under the project number ME 4279/1-2. Markus Hecher is also affiliated with the University of Potsdam, Germany. The authors would like to thank the anonymous reviewers for the valuable feedback they have provided.
PY - 2021/5/18
Y1 - 2021/5/18
N2 - 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 often have a certain inconsistency (with respect to a given query) or we are required to estimate a degree of inconsistency when 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, 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.
AB - 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 often have a certain inconsistency (with respect to a given query) or we are required to estimate a degree of inconsistency when 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, 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.
UR - http://www.scopus.com/inward/record.url?scp=85113472336&partnerID=8YFLogxK
U2 - 10.1609/aaai.v35i7.16788
DO - 10.1609/aaai.v35i7.16788
M3 - Conference contribution
T3 - AAAI-21 Technical Tracks
SP - 6349
EP - 6357
BT - 35th AAAI Conference on Artificial Intelligence, AAAI 2021
T2 - Thirty-Fifth AAAI Conference on Artificial Intelligence
Y2 - 2 February 2021 through 9 February 2021
ER -