

















Abstract:In this paper, we explore the issue of inconsistency handling over prioritized knowledge bases (KBs), which consist of an ontology, a set of facts, and a priority relation between conflicting facts. In the database setting, a closely related scenario has been studied and led to the definition of three different notions of optimal repairs (global, Pareto, and completion) of a prioritized inconsistent database. After transferring the notions of globally-, Pareto- and completion-optimal repairs to our setting, we study the data complexity of the core reasoning tasks: query entailment under inconsistency-tolerant semantics based upon optimal repairs, existence of a unique optimal repair, and enumeration of all optimal repairs. Our results provide a nearly complete picture of the data complexity of these tasks for ontologies formulated in common DL-Lite dialects. The second contribution of our work is to clarify the relationship between optimal repairs and different notions of extensions for (set-based) argumentation frameworks. Among our results, we show that Pareto-optimal repairs correspond precisely to stable extensions (and often also to preferred extensions), and we propose a novel semantics for prioritized KBs which is inspired by grounded extensions and enjoys favourable computational properties. Our study also yields some results of independent interest concerning preference-based argumentation frameworks.
| Comments: | This is an extended version of a paper appearing at the 17th International Conference on Principles of Knowledge Representation and Reasoning (KR 2020). This version corrects the statement of Theorem 43 (missing hypothesis). 27 pages |
| Subjects: | Logic in Computer Science (cs.LO); Artificial Intelligence (cs.AI); Databases (cs.DB) |
| Cite as: | arXiv:2003.05746 [cs.LO] |
| (or arXiv:2003.05746v4 [cs.LO] for this version) | |
| https://doi.org/10.48550/arXiv.2003.05746 arXiv-issued DOI via DataCite |
From: Camille Bourgaux [view email]
[v1]
Thu, 12 Mar 2020 12:38:37 UTC (65 KB)
[v2]
Mon, 29 Jun 2020 16:15:30 UTC (67 KB)
[v3]
Fri, 7 Jun 2024 06:42:55 UTC (67 KB)
[v4]
Tue, 26 May 2026 07:18:33 UTC (67 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。