Publications in Scientific Journals:
R. Pichler, St. Rümmele, St. Szeider, S. Woltran:
"Tractable answer-set programming with weight constraints: bounded treewidth is not enough";
Theory and Practice of Logic Programming,
We study the computational complexity of problems that arise in ab- stract argumentation in the context of dynamic argumentation, minimal change, and aggregation. In particular, we consider the following problems where always an argumentation framework F and a small positive integer k are given.
- The REPAIR problem asks whether a given set of arguments can be modified into an extension by at most k elementary changes (i.e., the extension is of distance k from the given set).
- The ADJUST problem asks whether a given extension can be modified by at most k elementary changes into an extension that contains a specified argument.
- The CENTER problem asks whether, given two extensions of distance k, whether there is a "center" extension that is of distance at most k − 1 from both given extensions.
We study these problems in the framework of parameterized complexity, and take the distance k as the parameter. Our results cover several different semantics, including admissible, complete, preferred, semi-stable and stable semantics.
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
Project Head Stefan Szeider:
The Parameterized Complexity of Reasoning Problems
Created from the Publication Database of the Vienna University of Technology.