[Back]

W. Dvorak, M. Järvisalo, J. P. Wallner, S. Woltran:
"Complexity-Sensitive Decision Procedures for Abstract Argumentation";
Talk: Principles of Knowledge Representation and Reasoning (KR), Rome, Italy; 2012-06-10 - 2012-06-14; in: "Proceedings of 13^th int. conf. of Principles of Knowledge Representation and Reasoning", G. Brewka, T. Eiter, S. McIlraith (ed.); AAAI Press, (2012), ISBN: 978-1-57735-560-1; 54 - 64.

Abstract argumentation frameworks (AFs) provide the basis for various reasoning problems in the areas of Knowledge Representation and Artificial Intelligence. Efficient evaluation of AFs has thus been identified as an important research challenge. So far, implemented systems for evaluating AFs have either followed a straight-forward reduction-based approach or been limited to certain tractable classes of AFs. In this work, we present a generic approach for reasoning over
AFs, based on the novel concept of complexity-sensitivity.
Establishing the theoretical foundations of this approach, we derive several new complexity results for preferred, semistable and stage semantics which complement the current complexity landscape for abstract argumentation, providing further understanding on the sources of intractability of AF reasoning problems. The introduced generic framework exploits decision procedures for problems of lower complexity whenever possible. This allows, in particular, instantiations of the generic framework via harnessing in an iterative way current sophisticated Boolean satisfiability (SAT) solver technology for solving the considered AF reasoning problems.
First experimental results show that the SAT-based instantiation
of our novel approach outperforms existing systems.

Project Head Stefan Woltran:
Neue Methoden für Analyse, Vergleich und Lösung von Argumentationsproblemen