On the limits of expressiveness in abstract argumentation semantics : realizability and signatures

Abstract

In den letzten Jahren hat sich das Forschungsfeld der Formalen Argumentation als eine Hauptströmung im Bereich der Künstlichen Intelligenz etabliert. Allen voran löste Dungs Ansatz der Abstract Argumentation großes Forschungsinteresse aus. Ein sogenanntes Abstract Argumentation Framework (AF) ist ein gerichteter Graph, dessen Knoten Argumente und dessen gerichtete Kanten Konflikte zwischen diesen Argumenten repräsentieren. Wird ein Argument als Gegenargument zu einem anderen Argument angesehen, so wird dies durch eine gerichtete Kante vom ersten zum zweiten Argument dargestellt. Die Frage, welche Argumente eines AFs gemeinsam akzeptiert werden können, wird durch Semantiken beantwortet, wobei das Ergebnis der Anwendung einer Semantik auf ein AF als eine Menge von Extensionen bezeichnet wird.<br />Überraschenderweise wurde bisher ein systematischer Vergleich der Ausdruckskraft verschiedener Semantiken, und folglich deren Fähigkeit, verschiedene Standpunkte eines einzelnen AFs darzustellen, vernachlässigt. Das Wissen über die Tatsache, welche Extensionen gemeinsam das Ergebnis der Anwendung einer Semantik auf ein AF darstellen können, gibt nicht nur Aufschlüsse über die Ausdrucksstärke einer Semantik. Vielmehr ist es auch von großem Vorteil für eine Fülle von Anwendungen.<br />Das Ziel dieser Diplomarbeit ist die Untersuchung der Ausdrucksstärke der naive, stage, stable, preferred, semi-stable und complete Semantik.<br />Dies wird durch die Charakterisierung der Signaturen dieser Semantiken bewerkstelligt. Die Signatur einer Semantik ist durch die Menge aller möglicher Mengen an Extensionen, die durch die Anwendung der Semantik auf ein beliebiges AF erlangt werden können, definiert.<br />Die Arbeit definiert für jede Semantik notwendige Bedingungen für eine Menge an Extensionen, um Teil der Signatur zu sein, also Eigenschaften, die von jedem Ergebnis der Semantik erfüllt sind, sowie (entsprechende) hinreichende Bedingungen einer Menge an Extensionen, um Teil der Signatur zu sein, also Eigenschaften, welche die Realisierbarkeit der Menge an Extensionen durch die Semantik bezeugen. Weiters beinhaltet die Diplomarbeit Konstruktionen von AFs, welche die gegebene Menge an Extensionen durch die jeweilige Semantik realisieren.<br />Die Charakterisierung der Signaturen der Semantiken ermöglicht einen systematischen Vergleich derer Ausdruckskraft. Die Ergebnisse dieser Arbeit zeigen, dass, mit einer einzigen Ausnahme, alle behandelten Semantiken verschiedene Grade an Ausdrucksstärke aufweisen.<br />Schließlich untersucht die Arbeit Strikte Realisierbarkeit, d.h.<br />Realisierbarkeit von Extensionsmengen durch AFs, welche keine zusätzlichen Argumente verwenden. Dazu enthält die Arbeit ähnliche Bedingungen wie oben bereits beschrieben, sowie Resultate, welche die Unmöglichkeit der strikten Realisierbarkeit bestimmter Extensionsmengen bezeugen.<br />

In recent years the research field of argumentation has become a major topic in the study of Artificial Intelligence. In particular the formal approach of abstract argumentation introduced by Dung has aroused much interest of research. A so-called abstract argumentation framework is a directed graph where nodes represent arguments and arrows represent conflicts between arguments, i.e. counter-arguments "attack" arguments by arrows. The question of which arguments can be accepted out of an argumentation framework is answered by argumentation semantics, where the outcome of applying a semantics to an argumentation framework is a set of extensions.<br />Surprisingly, a systematic comparison of their capability in terms of multiple extensions, and thus their expressive power in modellin multiple viewpoints with a single argumentation framework has been neglected so far. Understanding which extensions can, in principle, go together when a framework is evaluated with respect to a semantics of interest not only clarifies the "strength" of that semantics but also is a crucial issue in several applications.<br />The aim of the master's thesis is to study the expressiveness of the naive, stage, stable, preferred, semi-stable, and complete semantics, by characterizing their signatures. The signature of a semantics is defined as the set of all possible sets of extensions one can obtain from the semantics, given an arbitrary argumentation framework.<br />For each semantics we give necessary conditions for an extension-set to be in the signature, i.e. properties which are fulfilled by the outcomes of the semantics for each framework, as well as (corresponding) sufficient conditions for an extension-set to be in the signature, which make the extension-set realizable under the semantics. The thesis provides constructions of argumentation frameworks realizing extension-sets under the various semantics.<br />The characterizations of the signatures of the semantics give rise to a systematic comparison of their expressiveness. We show that, with one exception, all semantics we deal with possess different levels of expressiveness.<br />Finally the thesis investigates strict realizability, i.e. realizing an extension-set by a framework by not using additional arguments. Here we provide properties as stated above as well as impossibility results, showing that extension-sets cannot be strictly realized under certain conditions.