[Back]

G. Charwat:
"Tree-Decomposition based Algorithms for Abstract Argumentation Frameworks";
Supervisor: S. Woltran, W. Dvorak; Institut für Informationssysteme, 2012; final examination: 2012-02-22.

In recent years abstract argumentation frameworks (AFs) have emerged as an important research field in artificial intelligence. AFs are defined as directed graphs consisting of arguments (nodes in the graph) and attack relations (edges in the graph).
We are interested in the selection of 'appropriate' arguments in an AF.
The sets of appropriate arguments are then called the extensions of the AF. In abstract argumentation this 'appropriateness' can be defined by a wide variety of different semantics. For most semantics the computation of extensions for an AF is in general computationally hard. But by binding a certain problem parameter to a fixed constant many of those intractable problems become tractable. One important parameter for graph problems is the tree-width of a graph which represents the tree-likeliness of the AF. The tree-width is defined on tree decompositions of an AF. A tree decomposition is a mapping of a graph to a tree where the latter can be used to evaluate a certain problem efficiently.
In this thesis we introduce novel algorithms for stable and complete semantics that are defined on so-called normalized tree decompositions.
Furthermore we present a novel algorithm for admissible semantics based on semi-normalized tree decompositions that generalizes an existing algorithm on normalized tree decompositions. The advantage of semi-normalized (compared to normalized) tree decompositions is that they consist of less nodes and thus the overall depth of a semi-normalized tree decomposition is lower.
Besides the algorithms and the correctness proofs thereof we provide an implementation on basis of a purpose-built framework for algorithms on tree decompositions. This allows us to compare our novel algorithm for admissible semantics on semi-normalized tree decompositions to the existing algorithm on normalized tree decompositions. Our experimental results show that our novel implementation outperforms the existing one.

In den letzten Jahren gewannen Abstract Argumentation Frameworks (AFs) im Forschungsbereich der künstlichen Intelligenz immer mehr an Bedeutung. AFs sind als gerichtete Graphen definiert, welche aus Argumenten (Knoten im Graphen) und Angriffsbeziehungen (Kanten im Graphen) bestehen.
Wir beschäftigen uns nun mit der Auswahl von "passenden" Argumenten aus dem AF. Diese werden auch als Extensions des AFs bezeichnet. Es existiert eine Vielzahl von Semantiken, die definieren, welche Argumente als "passend" angesehen werden. Allerdings ist die Selektion der Argumente auf Basis einer Semantik in den meisten Fällen rechnerisch extrem aufwendig. Eine Idee aus dem Bereich der Komplexitätstheorie besteht nun darin, einen Problemparameter zu fixieren, wodurch das Problem im Allgemeinen leichter lösbar wird. Für Probleme auf Graphen ist der Parameter der Tree-Width relevant, welcher, informell gesagt, angibt, wie sehr der Graph einem Baum ähnelt. Die Tree-Width ist auf sogenannten Tree Decompositions definiert welche dazu verwendet werden können, ein Problem effizient zu lösen.
In dieser Diplomarbeit werden neue Algorithmen für die Berechnung von Extensions für die Semantiken Stable und Complete auf Basis von normalisierten Tree Decompositions präsentiert. Weiters wird ein neuer Algorithmus für die Semantik Admissible auf semi-normalisierten Tree Decompositions entwickelt. Der Unterschied zwischen normalisierten und semi-normalisierten Tree Decompositions besteht darin, dass letztere weniger Knoten enthalten und damit die gesamte Baumtiefe geringer ist.
Zusätzlich zu den Korrektheitsbeweisen der Algorithmen werden diese mithilfe eines bereits existierenden Frameworks implementiert, welches speziell dafür entwickelt wurde, auf Tree Decompositions basierende Algorithmen zu entwerfen. Der Algorithmus für die Semantik Admissible auf semi-normalisierten Tree Decompositions wird mit dem Algorithmus auf normalisierten Tree Decompositions verglichen. Die experimentellen Resultate zeigen, dass die semi-normalisierte Implementierung durchwegs schneller als die bereits existierende ist.