On Computational Problems for Infinite Argumentation Frameworks: Classifying Complexity via Computability

This paper investigates infinite argumentation frameworks. We introduce computability theoretic machinery as a robust method of evaluating, in the infinite setting, the complexity of the main computational issues arising from admissible, complete, and stable semantics: in particular, for each of these semantics, we measure the complexity of credulous and skeptical acceptance of arguments, and that of determining existence and uniqueness of extensions. We also propose a way of using Turing degrees to classify, for a given infinite argumentation framework, the exact difficulty of computing an extension in a given semantics and show that these problems give rise to a rich class of complexities.