Computational aspects of abstract argumentation

Abstract

Diese Arbeit beschäftigt sich mit Formaler Argumentation, einem Teilgebiet der Künstlichen Intelligenz. Einer der erfolgreichsten Formalismen in der Formalen Argumentation sind sogenannte Abstract Argumentation Frameworks, die 1995 von Dung eingeführt wurden. Das Konzept der Abstract Argumentation Frameworks abstrahiert von dem konkreten Inhalt der Argumente zu abstrakten Entitäten und einer Konfliktrelation zwischen diesen Entitäten. Diese Frameworks kann man sich also als gerichtete Graphen vorstellen, wobei die Knoten des Graphen die Argumente repräsentieren während gerichtete Kanten Konflikte zwischen Argumenten darstellen. Auf dieser abstrakten Ebene kann man nun die Konflikte zwischen Argumenten studieren und kohärente Mengen von Argumenten identifizieren. Die Literatur kennt eine Vielzahl an unterschiedlichen Kriterien, sogenannte Semantiken, um solche kohärenten Mengen zu definieren.<br />Eine wichtige Aufgabe in computerunterstützten Argumentations-Systemen ist die Bestimmung von kohärenten Mengen von Argumenten oder allgemeiner die Auswertung des zugehörigen Abstract Argumenation Frameworks mit der entsprechenden Semantik. Der Focus dieser Arbeit liegt in der computationalen Analyse dieser Aufgaben für Abstract Argumenation Frameworks und die unterschiedlichen Semantiken aus der Literatur.<br />Der erste Teil dieser Arbeit ist eine Komplexitätsanalyse dieser Probleme für beliebige Abstract Argumentation Frameworks mit Methoden der klassischen Komplexitätstheorie. Wie sich herausstellt ist ein Großteil der betrachteten Probleme schwierig im Sinne der Komplexitätstheorie, d.h. die Probleme sind NP-schwer und teilweise noch schwerer.<br />Daher werden in einem zweiten Teil sogennante tractable fragments untersucht. Das heißt wir betrachten Abstract Argumentation Frameworks mit einer bestimmte Struktur und untersuchen ob diese mit weniger computionalen Aufwand ausgewertet werden können. Zu diesem Zweck betrachten wir die Graph-Klassen von azyklischen Graphen, Graphen ohne Zyklen gerader Länge, symmetrischen Graphen und bipartiten Graphen.<br />Desweiteren untersuchen wir mehrere Graph-Parameter, welche strukturelle Eigenschaften von Abstract Argumentation Frameworks messen. Mit diesen Parametern wenden wir Methoden der Parametrsierten Komplexitätstheorie an, und zeigen, dass Abstract Argumentation Frameworks effizient ausgewertet werden können wenn nur der dazugehörige Graph-Parameter nicht zu groß ist.<br />Der dritte Teil dieser Arbeit beschäftigt sich mit Übersetzbarkeit von verschiedenen Semantiken für Abstract Argumentation Frameworks. Unter einer Übersetzung von einer Semantik A in eine Semantik B versteht man in diesem Zusammenhang eine Funktion die jedem beliebigen Abstract Argumentation Framework F ein Abstract Argumentation Framework G zuordnet sodass die kohärenten Mengen von F bezüglich Semantik A den kohärenten Mengen von G bezüglich Semantik B entsprechen.<br />

This work is in the context of formal argumentation, a sub-field of Artificial Intelligence. Probably the most popular formalism in argumentation is abstract argumentation as introduced by Dung.So called abstract argumentation frameworks abstract from the actual content of arguments and represent them as abstract entities and further abstract from the reasons of conflicts between arguments and represent them as a binary relation. Hence abstract argumentation frameworks can be simply interpreted as directed graphs. On this abstract level one can study the conflicts between arguments and identify coherent sets of arguments.<br />There is a plethora of approaches when a set of arguments should be considered to be coherent, each of these approaches is called a semantics for abstract argumentation.<br />In every argumentation system, towards conclusions, at some point we have to identify coherent sets of arguments. Hence we identify this as an important computational issue which indeed can be studied on the abstract level. In this work we are doing a computational analysis of evaluating abstract argumentation frameworks with semantics proposed in the literature.<br />The first part of this work is devoted to a classicalcomplexity analysis of the associated reasoning problems, using methods from classical complexity theory.We complement existing results and it turns out that most problems are computationally intractable, i.e. NP-hard and in some cases even harder.<br />In a second part we explore the range of tractable subclasses. We study tractable fragments, i.e. graph classes that allow for an efficient evaluation of the argumentation framework. We extend and complement existing results for acyclic, even-cycle free, symmetric and bipartite Argumentation Frameworks. Moreover we consider the graph parameters tree-width and clique-width to obtain Fixed-Parameter Tractability results. We call a problem fixed parameter tractable if it can be solved by an algorithm, with a run-time that may highly increase with the value of the parameter for a concrete instance but is polynomial in the size of the instance.<br />Finally we consider the intertranslatability of different argumentation semantics. We consider a semantic A to be translatable to a semantics B if there is a (translation) function modifying frameworks such that semantics A on the original framework is in certain correspondence to B on the modified framework.