On rejected arguments and implicit conflicts: The hidden power of argumentation semantics

摘要

Abstract argumentation frameworks (afs) are one of the most studied formalisms in AI and are formally simple tools to model arguments and their conflicts. The evaluation of an af yields extensions (with respect to a semantics) representing alternative acceptable sets of arguments. For many of the available semantics two effects can be observed: there exist arguments in the given af that do not appear in any extension (rejected arguments); there exist pairs of arguments that do not occur jointly in any extension, albeit there is no explicit conflict between them in the given af (implicit conflicts). In this paper, we investigate the question whether these situations are only a side-effect of particular afs, or whether rejected arguments and implicit conflicts contribute to the expressiveness of the actual semantics. We do so by introducing two subclasses of afs, namely compact and analytic frameworks. The former class contains afs that do not contain rejected arguments with respect to a semantics at hand; afs from the latter class are free of implicit conflicts for a given semantics. Frameworks that are contained in both classes would be natural candidates towards normal forms for afs since they minimize the number of arguments on the one hand, and on the other hand maximize the information on conflicts, a fact that might help argumentation systems to evaluate afs more efficiently. Our main results show that under stable, preferred, semi-stable, and stage semantics neither of the classes is able to capture the full expressive power of these semantics; we thus also refute a recent conjecture by Baumann et al. on implicit conflicts. Moreover, we give a detailed complexity analysis for the problem of deciding whether an af is compact, resp. analytic. Finally, we also study the signature of these subclasses for the mentioned semantics and shed light on the question under which circumstances an arbitrary framework can be transformed into an equivalent compact, resp. analytic, af.