[Back]

M. König:
"Graph-classes of argumentation frameworks with collective attacks - properties and complexity results";
Supervisor: W. Dvorak, S. Woltran; Institut für Logic and Computation, 2020; final examination: 2020-08-24.

Abstract Argumentation Frameworks (AFs) constitute a simple formalism to represent and reason over knowledge. The simple way of modelling information just as a directed graph lead to a rapid rise of its popularity. However, the simplicity came with the cost of strict syntactic restrictions, and as it is often inconvenient to formalize certain natural structures in the original notion of frameworks, many extensions have been proposed.We deal with one such extension, namely Argumentation Frameworks with Collective Attacks (SETAFs), which allow attacks to origin from sets of arguments. In particular,this means that instead of a directed graph, the underlying structure of the framework is a directed hypergraph. Many applications motivated the search for efficient reasoning tools for the frame-works, and as most reasoning problems are intractable in general, a more fine-grained complexity analysis was needed. In this thesis we try to identify tractable fragments for reasoning tasks on SETAFs. In particular, we investigate how certain restrictions on the hypergraph-structure such as acyclicity, symmetry, and bipartiteness can be formulated and whether they allow us to reason more efficiently. We show that the low complexity of acyclicity carries over from AFs to SETAFs, and give the even more general result that this fragment extends to frameworks that have cycles of length 1. Moreover we establish tractable fragments in even-cycle-freeness, self-attack-free -symmetry, andβ-bipartiteness, the respective defining properties are introduced in the course of this thesis.

Abstract Argumentation Frameworks (AFs) bieten die Möglichkeit, Wissen auf einfache Art zu repräsentieren und Schlüsse daraus zu ziehen. Diese Einfachheit führte dazu, dass sie seit ihrer Einführung durch Phan Minh Dung im Jahr 1995 immer beliebter wurden, und in zahlreichen wissenschaftlichen Publikationen zur Anwendung in verschiedenen Bereichen verwendet wurden. Die simple Struktur der Frameworks - das Wissen wird in Form von Argumenten und Attacken als gerichteter Graph dargestellt - lässt allerdingsbestimmte syntaktische Konstruktionen nicht zu, weshalb in der Folge einige Erweiterungen für den Formalismus eingeführt wurden. Diese Arbeit beschäftigt sich mit so einer Erweiterung: Argumentation Frameworks mit gemeinsamen Attacken (SETAFs). Hier können Attacken - anstatt nur von einem Argument - im Allgemeinen von beliebig vielen Argumenten ausgehen. Die zugrundeliegende Struktur ist damit kein gerichteter Graph mehr, sie ist ein gerichteter Hypergraph.Die Vielzahl an Anwendungsmöglichkeiten bedingt die Suche nach effizienten Argumentationssystemen. Die Komplexität der meisten gängigen Probleme auf Argumentation Frameworks ist auf den ersten beiden Stufen der polynomiellen Hierarchie einzuordnen, weshalb eine detaillierte Komplexitätsanalyse erforderlich ist. In dieser Arbeit wird nach Fragmenten mit geringerer Komplexität gesucht. Dazu werden Strukturen in den Hypergraphen, welche den SETAFs zugrunde liegen, betrachtet. Der Fokus liegt herbei auf Azyklizität, Symmetrie, und 2-Färbbarkeit bzw. Bipartitness - es werden verschiedene Varianten dieser Eigenschaften für Hypergraphen definiert und geprüft, ob die entsprechenden Klassen von SETAFs eine Reduktion der Komplexität bei den gängigen Argumentationsproblemen aufweisen. Es werden die folgenden einfachen Fragmente etabliert: SETAFs, welche keine Zyklen beinhalten, die aus mehr als einem Argument bestehen, SETAFs ohne Zyklen gerader Länge, epsilon-symmetrische SETAFs ohne Selbst-Attacken, und beta-bipartite SETAFs. Die entsprechenden Eigenschaften werden in dieser Arbeit eingeführt.

http://dx.doi.org/10.34726/hss.2020.77665

https://repositum.tuwien.at/handle/20.500.12708/15572