You are here

Priority Queue Implementations for Abstract Argumentation Solvers

Computational Models of Argumentation [1] are approaches to knowledge representation and reasoning that focus on the interplay between arguments and counterarguments in order to reach decisions. One of the most popular formalisms in this area are abstract argumentation frameworks [2] which model argumentation scenarios as directed graphs, with vertices representing arguments and a directed edge representing an attack of one argument on another. Semantics are given to such frameworks by means of so-called extensions, i.e. sets of arguments that are mutually acceptable. The development of algorithms to compute extensions is a core requirement to make such models of argumentation practically relevant and has recently gathered major interest [3].

This bachelor thesis is about the development of an algorithm and an implemented system that solves problems wrt. the "grounded semantics" of abstract argumentation frameworks, one of the most important semantics that defines "acceptability" and the only one where all reasoning tasks can be solved in polynomial time. A core component for the algorithm will be a priority queue that orders the arguments of a framework wrt. to their remaining attacks. The current reference implementation Harper [4] uses a binary heap for this priority queue. The task of the bachelor thesis is to implement further priority queues such as [5] in C and compare their performance in order to find the best priority queue implementation for reasoning with abstract argumentation frameworks.

[1] Katie Atkinson, Pietro Baroni, Massimiliano Giacomin, Anthony Hunter, Henry Prakken, Chris Reed, Guillermo R. Simari, Matthias Thimm, Serena Villata. Towards Artificial Argumentation. In AI Magazine, 38(3):25-36. October 2017.
[2] Phan Minh Dung. On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning, Logic Programming and n-Person Games. In Artificial Intelligence, 77(2):321-358, 1995
[3] Federico Cerutti, Sarah A. Gaggl, Matthias Thimm, Johannes P. Wallner. Foundations of Implementations for Formal Argumentation. In Pietro Baroni, Dov Gabbay, Massimiliano Giacomin, Leendert van der Torre (Eds.), Handbook of Formal Argumentation, also appears in IfCoLog Journal of Logics and their Applications 4(8):2623--2706, College Publications. February 2018.
[5] Mikkel Thorup. Integer priority queues with decrease key in constant time and the single source shortest paths problem. In Journal of Computer and System Sciences 69, 330–353, 2004.