[Back]

St. Ellmauthaler:
"Abstract Dialectical Frameworks: Properties, Complexity, and Implementation";
Supervisor: S. Woltran, J. P. Wallner; Institut für Informationssysteme, 2012; final examination: 09-13-2012.

Over the last two decades the interest for Abstract Argumentation steadily raised in the field of Artificial Intelligence.
The concept of Dung's Argumentation Frameworks (AFs), where arguments and their relations are represented in a directed graph-structure, is a well-known, simple, and powerful concept. This framework is used to find acceptable sets of arguments, which have specific properties (e.g. being conflict free), defined by several semantics.
Recently Abstract Dialectical Frameworks (ADFs) were introduced, a generalization of Dung's approach, to overcome the limitation of attack-relations being the only type of native relations. To reach this goal, in addition to the relations, total functions are used to decide the acceptance of an argument. These functions are so called acceptance conditions. Due to the high expressiveness of this newly proposed theory, some semantics were only generalized for the restricted bipolar ADFs yet.
This work will give an exhaustive overview on ADFs. The restriction to bipolar ADFs for some of the semantics is not desired, so we try to develop a solution to gain the generalized stable model semantics. This semantics is particularly important because the other semantics which are restricted to bipolar ADFs, depend on stable models. To gain such a generalization, we will try to connect the foundations of ADFs to other fields of computer science. So we may relate subclasses of these fields to the bipolar ADF to overcome this obstacle. This connection also makes ADFs more accessible to other fields of computer science.
We will concentrate mainly on the introduction of the alternative representation of propositional-formula ADFs (pForm-ADFs), but we will also show that ADFs can be represented as hyper-graphs. Based on the new representation a transformation from ADFs to pForm-ADFs, together with a generalization of the stable model semantics will be presented. In addition some properties between semantics will be investigated and an overview of complexity results, enriched with new ones is given.
Currently there is no software system available to compute semantics for ADFs. So in addition to the formal results we also present an Answer Set Programming (ASP) based implementation to solve these highly complex computations. We will also present preliminary empirical experiments.

Abstract Argumentation konnte im Laufe der letzten zwei Dekaden stetig immer mehr Interesse im Forschungsbereich der Künstlichen Intelligenz gewinnen. Eines der wichtigsten Konzepte ist dabei Dung's Argumentation Framework. Hierbei handelt es sich um einen einfachen, jedoch mächtigen und gut entwickelten Ansatz zum Darstellen von Argumenten und deren Beziehungen. Diese Informationen sind hierbei in Form eines gerichteten Graphen kodiert, wo jede Kante einen Angriff auf ein anderes Argument symbolisiert. Mittels dieses Frameworks ist es ebenfalls möglich, durch Semantiken Mengen von Argumenten auszuwählen und zu prüfen ob sie gewisse Eigenschaften besitzen (z.B. ob die Menge konfliktfrei ist).
Vor kurzem wurde in Form von Abstract Dialectical Frameworks (ADFs) eine Verallgemeinerung dieses Konzepts vorgestellt. Dabei werden die Beziehungen mittels einer vollständigen Funktion definiert, wodurch sie nicht mehr nur auf Angriffe beschränkt sind. Durch diese Funktion, welche Akzeptanzbedingung genannt wird, ist es nun möglich sehr komplexe Beziehungen zu beschreiben. Aufgrund dieser Ausdrucksstärke gibt es nun jedoch Probleme gewisse Semantiken für ADFs zu definieren. Daher ist die Unterklasse der bipolaren ADFs eingeführt worden.
Im Rahmen dieser Arbeit wird das Konzept der ADFs nochmals genau vorgestellt. Da die Einschränkung auf bipolare ADFs nur eine vorübergehende Lösung darstellt, wird versucht eine allgemeine Form der stabilen Modell-Semantik zu finden. Da dies die grundlegende Semantik für alle anderen ist, welche auf bipolare ADFs beschränkt sind, wird hierfür ein generalisierter Ansatz am meisten benötigt. Um dies zu erreichen werden Konzepte von anderen Bereichen der theoretischen Informatik genutzt um deren Ergebnisse für die Probleme mit bipolaren ADFs zu nutzen. Dadurch können ADFs ebenfalls leichter in jenen Gebieten eingesetzt werden.
Hauptsächlich werden die aussagenlogischen ADFs behandelt werden, da es mit deren Hilfe möglich ist ADFs relativ natürlich in bipolare umzuwandeln. Darauf aufbauend wird dann die Entwicklung einer allgemeinen stabilen Modell-Semantik gezeigt. Zusätzlich werden noch einige Eigenschaften zwischen einzelnen Semantiken diskutiert. Eine Zusammenfassung bereits vorhandener komplexitätsanalytischer Resultate wird ebenfalls präsentiert um danach neue Ergebnisse zeigen zu können.
Da es derzeit kein adäquates Software-System zum Berechnen von Modellen für Semantiken auf ADFs gibt, wird zusätzlich zu den formalen Ergebnissen noch eine neue ASP (Answer Set Programming) basierte Implementierung präsentiert. Um ein Gefühl für die Effizienz des Systems zu bekommen werden außerdem noch empirische Experimente zur Laufzeit diskutiert.