Advances in abstract argumentation : expressiveness and dynamics

Abstract

In recent years the research field of argumentation has become a major topic in the study of artificial intelligence (AI). This is not only due to recent applications such as legal reasoning and medicine, but also because of fundamental connections to other areas of AI research such as nonmonotonic reasoning. AI and automated reasoning can be helpful to various tasks within the argumentation process, but the focus of this work is on the evaluation of the acceptability of conflicting arguments. The most prominent approach to this problem is the formal model of abstract argumentation frameworks (AFs) introduced by Dung. An AF is a directed graph where nodes represent arguments and directed edges represent conflicts between arguments. Conditions for the acceptability of arguments are given by argumentation semantics. Several semantics have been defined over the years. The central question, given an AF, is which sets of arguments (so-called extensions) can be jointly accepted under a certain semantics. While Dung¿s argumentation frameworks enjoyed and still enjoy great popularity, their conceptual simplicity also imposes certain limitations, which has led to a considerable number of generalizations of Dung's AFs. In particular, abstract dialectical frameworks (ADFs) constitute a very powerful generalization of AFs by additionally assigning to each argument an acceptance condition in the form of a propositional formula. In this work we contribute to the advancement of the study of abstract argumentation by addressing aspects of expressiveness and dynamics of argumentation semantics in AFs as well as in ADFs. In terms of expressiveness we first complement recent work on realizability in AFs. Moreover, we investigate the role of arguments that do not appear in any extension, so-called rejected arguments, and study the induced class of compact argumentation frameworks. We give full pictures of the relations between the compact AF classes and between the expressiveness of the various semantics when restricted to compact AFs. Then, we lift the study of expressiveness to the concept of input-output AFs and give, for the major semantics, exact characterizations of functions which are realizable in this setting. Finally, we present a unifying algorithmic approach to realizability capturing AFs and ADFs as well as intermediate formalisms in a modular way, which is also implemented in answer set programming. These results not only contribute to the systematic comparison of semantics, but can also provide the theoretical basis for the advancement of solving techniques for problems in argumentation. Taking into account the dynamic nature of argumentation, we study two central issues therein: revision and splitting. For revision we apply the seminal AGM theory of belief change to argumentation. We are the first to present a representation theorem for revision operators which guarantee to result in a single framework. For AFs we give a generic solution which applies to many prominent semantics. For ADFs we study revision under preferred and admissible semantics as well as a novel hybrid approach. We also present concrete belief change operators and analyze their computational complexity. Finally, we study splitting of ADFs, aiming for optimization of computation by incremental computation of semantics. We provide suitable techniques for directional splitting under all standard semantics of ADFs as well as for general splitting under selected semantics.