If Nothing Is Accepted -- Repairing Argumentation Frameworks

Abstract

Conflicting information in an agent's knowledge base may lead to a semantical defect, that is, a situation where it is impossible to draw any plausible conclusion. Finding out the reasons for the observed inconsistency (so-called diagnoses) and/or restoring consistency in a certain minimal way (so-called repairs) are frequently occurring issues in knowledge representation and reasoning. In this article we provide a series of first results for these problems in the context of abstract argumentation theory regarding the two most important reasoning modes, namely credulous as well as sceptical acceptance. Our analysis includes the following problems regarding minimal repairs/diagnoses: existence, verification, computation of one and enumeration of all solutions. The latter problem is tackled with a version of the so-called hitting set duality first introduced by Raymond Reiter in 1987. It turns out that grounded semantics plays an outstanding role not only in terms of complexity, but also as a useful tool to reduce the search space for diagnoses regarding other semantics.