Formal argumentation has evolved into an important field in Artificial Intelligence. Abstract argumentation frameworks (AFs for short), as introduced by Dung [1995], are central in formal argumentation, providing a simple yet powerful formalism to reason about conflicts between arguments. The power of the formalism, however, comes at a price. In particular, many important reasoning problems for AFs are located on the second level of the polynomial hierarchy, including skeptical reasoning in the preferred semantics [Dunne and Bench-Capon, 2002], and both skeptical and credulous reasoning in the semi-stable and the stage semantics [Dvorak and Woltran, 2010]. This naturally raises the question about the origin of this high complexity and, in particular, calls for research on lower complexity fragments of the reasoning tasks. The focus of this article is both on the identification of such lower-complexity fragments of second-level reasoning problems arising from abstract argumentation, and on exploiting this knowledge in developing efficient complexity-sensitive decision procedures for the generic second-level problems.
展开▼
