[Back]

W. Dvorak, St. Szeider, S. Woltran:
"Abstract Argumentation via Monadic Second Order Logic";
Talk: International Conference on Scalable Uncertainty Management (SUM), Marburg, Germany; 09-17-2012 - 09-19-2012; in: "Proceedings of Sixth International Conference on Scalable Uncertainty Management (SUM 2012)", E. Hüllermeier, S. Link, T. Fober, B. Seeger (ed.); Lecture Notes in Computer Science / Springer, 7520 (2012), ISBN: 978-3-642-33361-3; 85 - 98.

We propose the formalism of Monadic Second Order Logic (MSO) as a unifying framework for representing and reasoning with various semantics of abstract argumentation. We express a wide range of semantics within the pro- posed framework, including the standard semantics due to Dung, semi-stable, stage, cf2, and resolution-based semantics. We provide building blocks which make it easy and straight-forward to express further semantics and reasoning tasks. Our results show that MSO can serve as a lingua franca for abstract argu- mentation that directly yields to complexity results. In particular, we obtain that for argumentation frameworks with certain structural properties the main compu- tational problems with respect to MSO-expressible semantics can all be solved in linear time. Furthermore, we provide a novel characterization of resolution-based grounded semantics.

http://dx.doi.org/10.1007/978-3-642-33362-0_7

Project Head Stefan Szeider:
The Parameterized Complexity of Reasoning Problems

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