Argumentation frameworks with claims and collective attacks - : complexity results and answer-set programming encodings

Abstract

Abstract argumentation frameworks, as proposed by Dung in 1995, constitute one of the most widely used formalisms to model argumentation processes in the field of artificial intelligence. An abstract argumentation framework models an argumentation process as a directed graph, representing arguments as vertices and attacks between those arguments as directed arcs between the respective vertices. Furthermore, the coherent sets of arguments that are jointly acceptable under a given semantics, satisfying certain properties, are commonly called extensions. We consider two generalizations of such abstract argumentation frameworks. The first generalization that we consider, abstract argumentation frameworks with collective attacks, allows for attacks to be between sets of arguments and arguments, enabling a natural way of modeling that a set of arguments might defeat another argument if considered together which, in general, is not the case if viewed individually. Furthermore, the second considered generalization, claim augmented abstract argumentation frameworks, introduces the augmentation of arguments using claims. Such augmented frameworks allow for an intuitive way of expressing the extensions in terms of claims, that might be shared across multiple arguments, relaxing the abstraction to some extent. We provide complexity results for these two generalizations. To this end, we consider five common decision problems as well as various semantics for both types of argumentation frameworks and locate their position on the polynomial hierarchy. Furthermore, we make use of the well-established formalism of answer-set programming and give encodings for the various semantics, considering multiple approaches where applicable, to efficiently compute the extensions of such argumentation frameworks. Finally, we conduct experiments to compare the performance of our encodings. We present the results and the acquired data and discuss our findings and the drawn conclusions.