Complexity of Semi-Stable Semantics in Abstract Dialectical Frameworks

Abstract dialectical frameworks (ADFs) have been introduced as a formalism for modeling and evaluating argumentation, allowing for general logical acceptance conditions of arguments. Different criteria used to settle the acceptance of arguments are called semantics. Two-valued semantics of ADFs reflect the ‘black-and-white’ character of classical logic in non-monotonic frameworks. Stable semantics of ADFs were introduced to exclude cycles of self-justification of arguments among two-valued models. The stable semantics faces the challenge of potential non-existence of stable models. However, one might still want to draw conclusions even in case that an ADF has no two-valued models or stable models. Recently, the notions of semi-two-valued semantics and semi-stable semantics were introduced for ADFs. In the current work, we study the computational complexity of these two novel semantics. We show that the complexity of the semi-stable semantics is in general one level up in the polynomial hierarchy, compared to the stable semantics. We study the prominent reasoning tasks of credulous and skeptical reasoning, as well as the verification problem.