Abschlussarbeit

Beschreibung:

Das Teilgebiet der Abstrakten Argumentation im Fachbereich der Wissensrepräsentation nutzt gerichtete Graphen als Modelle für Konflikte zwischen Argumenten aus. Dabei werden die Angriffe zwischen den einzelnen Argumenten (Knoten) in Form von Attacken (gerichteten Kanten) innerhalb eines gerichteten Graphen, Argumentation Framework (AF) genannt, betrachtet. Für die Auswertung eines Argumentation Frameworks können z.B. Rang-Semantiken verwendet werden, diese definieren ein Ranking auf den Argumenten eines AFs nach bestimmten Kriterien, z.B. Anzahl oder Rang der Angreifer eines Argumentes, [Bonzon et al., 2016]. Die Komplexität der Frage, ob ein gegebenes Ranking auf einem AF das korrekte Ranking bezüglich einer bestimmten Rangsemantik ist, ist für die meisten Rangsemantiken ungeklärt. Eine entscheidende Größe stellt hierbei die Anzahl der gerichteten Wege bestimmter Länge zu den fraglichen Argumenten da.

Ziel der Arbeit soll es sein, systematisch gerichte Graphen mit 3 − 10 Knoten daraufhin zu untersuchen, bei welchem die Anzahl der Wege der Länge n für zwei Knoten a, b spätestens zum ersten Mal voneinander abweicht. Dafür soll ein Programm geschrieben werden, dass die Anzahl der Wege der Länge k = 1, 2, 3, ..., die in einem bestimmten Knoten enden, berechnet, und für eine gesetzte Obergrenzen nach gerichteten Graphen sucht, bei denen diese Werte sich das erste Mal für ein k > n unterscheiden. Die gefundenen Gegenbeispiele sowie Fälle, bei denen kein Unterschied auftritt, sollen anschließend auf ihre Eigenschaften hin untersucht werden [Gera et al., 2018]. Haben z.B. Größen wie der Maximum Degree, Cycle Rank oder Tree-Width einen Einfluss darauf, wann zum ersten Mal ein Unterschied sichtbar wird? Eine Auswahl möglicherweise relevanter Maße ist zu treffen und auf einen Einfluss auf die Obergrenze hin zu untersuchen.

References

[Bonzon et al., 2016] Bonzon, E., Delobelle, J., Konieczny, S., and Maudet, N. (2016). A comparative study of ranking-based semantics for abstract argumentation. In Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI’16).

[Gera et al., 2018] Gera, R., Haynes, T. W., Hedetniemi, S. T., and Henning, M. A. (2018). An Annotated Glossary of Graph Theory Parameters, with Conjectures, pages 177–281. Springer International Publishing, Cham.