On Computational Problems for Infinite Argumentation Frameworks: The Complexity of Finding Acceptable Extensions⋆ Uri Andrews1,† , Luca San Mauro2,*,† 1 Department of Mathematics, University of Wisconsin, USA 2 Department of Philosophy, University of Bari, Italy Abstract 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. Keywords infinite argumentation frameworks, computability theory, analytic and co-analytic sets, admissible extensions, stable exten- sions, complete extensions, Turing degrees 1. Introduction practical contexts, such as logic programming [3] and the logical analysis of multi-agent or distributed systems Abstract argumentation theory is a fundamental research [4] (the substantial introduction of [1] provides other area in AI, providing a powerful paradigm for reasoning concrete examples of applications of infinite AFs, e.g., to about knowledge representation and multi-agent systems. multiagent negotiations). Historically, the focus has predominantly been on finite Fortunately, recent years have seen a growing interest argumentation frameworks (AFs), leaving the infinite in infinite AFs, with special focus on how the existence case relatively unexplored. As noted in [1], this oversight and interplay of various semantics—well-understood for poses significant theoretical, conceptual, and practical finite AFs—are affected in the infinite realm (see, e.g., limitations. [5, 6, 7, 8, 9]). This increasing recognition underscores Firstly, infinite frameworks align naturally with the importance of infinite AFs for a broad understanding Dung’s seminal approach [2], whose results do not pre- of argumentation theory. suppose finiteness. Secondly, representing argumenta- However, the literature still lacks a comprehensive tion scenarios in an infinite manner captures the inher- framework for systematically exploring all logical as- ently nonmonotonic nature of argumentation, where ar- pects of infinite AFs, particularly regarding their core guments can always be challenged by the emergence of computational issues. A significant research avenue in new information, making any fixed limit on the space finite AFs has been determining the algorithmic complex- of arguments somewhat artificial. Moreover, if one con- ity of tasks associated with finding coherent collections ceives an argumentative scenario with arguments being of arguments (up to suitable collection of semantics), added as time proceeds, e.g., the collection of scientific with numerous complexity theoretic results highlight- studies, then infinite frameworks naturally emerge as ing their inherent computational intractability (see, e.g., the union of the argumentation frameworks that we see [10, 11, 12]). To our knowledge, no analogous study has at each finite time. Thirdly, infinite AFs may arise in been conducted for infinite AFs. This paper addresses this gap by initiating a systematic NMR 2024, 22nd International Workshop on Nonmonotonic Reasoning study of the complexity of computational problems in November 2-4, 2024, Hanoi, Vietnam A condensed version of this article was submitted to SAFA 2024 infinite AFs. For this endeavor, we bring into the subject ⋆ and an expanded version was submitted to FCR 2024. of argumentation theory the machinery of computability * Corresponding author. theory, which may be regarded as an infinitary com- † These authors contributed equally. panion of computational complexity theory and abounds $ andrews@math.wisc.edu (U. Andrews); with concepts and hierarchies for measuring the complex- luca.sanmauro@gmail.com (L. San Mauro) ity of computing and defining countably infinite objects, € https://math.wisc.edu/~andrews (U. Andrews); https://www.lucasanmauro.com/ (L. San Mauro) providing the appropriate machinery for this endeavor. © 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). The application of computability theoretic tools out- CEUR ceur-ws.org Workshop ISSN 1613-0073 Proceedings side of mathematical logic is a well-established idea. Over All AFs investigated in this paper are infinite. the past decades, computability theory has been applied A semantics 𝜎 assigns to every AF ℱ a set of exten- to a wide array of mathematical disciplines, and com- sions 𝜎(ℱ) which are deemed as acceptable. A huge putability theoretic concepts have found applications in number of semantics, fueled by different motivations, other formal subjects, such as theoretical computer sci- have been proposed and analyzed. Here, we focus on ence, economics, and linguistics (see, e.g., [13, 14, 15]). three prominent choices, whose computational aspects The present paper, we argue, provides compelling ev- are well-understood in the finite setting: admissible, com- idence of the benefits of viewing infinite AFs through plete, and stable semantics (abbreviated by ad, stb, co, re- computability theoretic lenses. We assess the complex- spectively). ity of many computational problems—both established Let ℱ = (𝐴ℱ , 𝑅ℱ ) be an AF. Denote by cf(ℱ) the and novel—within our framework, illustrating their un- collection of extensions of ℱ which are conflict-free (i.e., decidability while providing precise measures of their 𝑆 ∈ cf(ℱ) iff 𝑎 ̸↣ 𝑏, for all 𝑎, 𝑏 ∈ 𝑆). Then, for 𝑆 ∈ complexity. cf(ℱ), • 𝑆 ∈ ad(ℱ) iff 𝑆 is self-defending (i.e., 𝑆 ⊆ Organization of the paper 𝑓ℱ (𝑆)); Section 2 briefly reviews the main semantic concepts • 𝑆 ∈ co(ℱ) iff 𝑆 is a fixed point of 𝑓𝐹 (i.e., 𝑆 = from argumentation theory that are relevant to this pa- 𝑓ℱ (𝑆)); per, along with the fundamental computational problems • 𝑆 ∈ stb(ℱ), iff 𝑆 attacks all arguments outside associated with them. In Section 3, we introduce the key of it (i.e., 𝑆 + = 𝐴ℱ ∖ 𝑆). notions of computability theory employed in the work and we define the concept of computable AFs and the In discussing the complete extensions, we will also computational issues that emerges from it. Finally, in briefly mention the grounded extension, which is the Sections 4 through 5, we determine the lower and upper unique smallest fixed point of 𝑓𝐹 ; in any AF, the bounds of the complexity for our computational prob- grounded extension always exists [2, Theorem 3]. lems: a critical technique for achieving hardness results For a given semantics 𝜎, the following are some well- involves suitably encoding trees into AFs. Our main re- known computational problems related to 𝜎: sults are collected in Tables 2 and 3. • Cred𝜎 (for credulous acceptance) is the decision problem whose accepting instances are the pairs 2. Argumentation theoretic (ℱ, 𝑎) so that 𝑎 ∈ 𝑆 for some 𝑆 ∈ 𝜎(ℱ); background • Skept𝜎 (for skeptical acceptance) is the decision problem whose accepting instances are the pairs To keep our paper self-contained, we now briefly review (ℱ, 𝑎) so that 𝑎 ∈ 𝑆 for all 𝑆 ∈ 𝜎(ℱ); some key concepts of Dung-style argumentation theory, • Exist𝜎 is the decision problem whose accepting focusing on the semantics notions considered in this instances are the AFs ℱ so that 𝜎(ℱ) ̸= ∅; paper and the fundamental computational problems asso- • NE𝜎 is the decision problem whose instances are ciated with them (the surveys [16, 17] offer an overview the AFs ℱ so that 𝜎(ℱ) ∖ {∅} ̸= ∅; of these topics). • Uni𝜎 is the decision problem whose accepting An argumentation framework (AF) ℱ is a pair instances are the AFs ℱ so that |𝜎(ℱ)| = 1. (𝐴ℱ , 𝑅ℱ ) consisting of a set 𝐴ℱ of arguments and an attack relation 𝑅ℱ ⊆ 𝐴ℱ × 𝐴ℱ . If some argument 𝑎 In formal argumentation theory, evaluating the compu- attacks some argument 𝑏, we may write 𝑎 ↣ 𝑏 instead tational complexity of the aforementioned problems for of (𝑎, 𝑏) ∈ 𝑅ℱ . Collections of arguments 𝑆 ⊆ 𝐴ℱ are various semantics has been a noteworthy research thread called extensions. For an extension 𝑆, the symbols 𝑆 + and for more than 20 years[17]. Table 1 collects known com- 𝑆 − denote, respectively, the arguments that 𝑆 attacks plexity results for the admissible, stable, and complete and the arguments that attack 𝑆: semantics. This analysis refers only to finite AFs. In the next section, we introduce our computability theoretic 𝑆 + = {𝑥 : (∃𝑦 ∈ 𝑆)(𝑦 ↣ 𝑥)}; perspective that allows us to tackle complexity issues 𝑆 − = {𝑥 : (∃𝑦 ∈ 𝑆)(𝑥 ↣ 𝑦)}. concerning infinite AFs. 𝑆 defends an argument 𝑎, if any argument that attacks 𝑎 is attacked by some argument in 𝑆 (i.e., {𝑎}− ⊆ 𝑆 + ). The characteristic function of ℱ is the following mapping 𝑓ℱ which sends subsets of 𝐴ℱ to subsets of 𝐴ℱ : 𝑓ℱ (𝑆) := {𝑥 : 𝑥 is defended by 𝑆}. 𝜎 Cred𝜎 Skept𝜎 Exist𝜎 NE𝜎 Uni𝜎 ever 𝑖 < 𝑗. A path 𝜋 ∈ 𝜔 𝜔 through a tree 𝒯 ⊆ 𝜔 <𝜔 ad NP-c trivial trivial NP-c coNP-c is an infinite sequence so that 𝜋 ↾𝑛 ∈ 𝒯 , for all num- stb NP-c coNP-c NP-c NP-c DP-c bers 𝑛. The set of paths through a tree 𝒯 is denoted by co NP-c P-c trivial NP-c coNP-c [𝒯 ]. 𝒯 is well-founded if [𝒯 ] = ∅ and otherwise is ill- Table 1 founded. Note that we follow the standard terminology Computational problems for finite AFs. 𝒞 -c denotes complete- in computability theory requiring that paths be infinite. ness for the class 𝒞 . Indeed, if one were to allow paths to be finite, then these notions trivialize, since one could computably find a path through any given computable tree. For example, the set 3. Computational problems for of strings AFs through the lens of 𝒯 := {𝜆} ∪ {𝜎, 𝜎 ⌢ 1 : (∀𝑛 < |𝜎|)(𝜎(𝑛) = 0)} computability theory is an ill-founded tree with [𝒯 ] = {0∞ }. In this section, we introduce computable AFs and we If 𝒯 contains strings of arbitrary length, then 𝒯 has revisit the computational problems of the last section infinite height. Note that there are trees of infinite height through the lens of computability theory. We aim at con- which are well-founded, e.g., 𝒯 = {𝜆} ∪ {𝑛⌢ 𝜎 : |𝜎| ≤ veying the main ideas without delving into too many 𝑛}. technical details. A more formal and comprehensive ex- position of the fundamentals of computability theory can 3.2. Computable argumentation be found, e.g., in the textbooks [18]. We begin by estab- lishing standard notation and terminology for some com- frameworks binatorial notions that appear frequently in our proofs. A basic problem that one encounters when attempting to calibrate the algorithmic complexity of infinite AFs is 3.1. Sequences, strings, and trees that of describing infinite objects in a finitary way. Com- putability theory offers a wide range of tools designed As is common in computability theory, we denote the set for this endeavour. Here, we will concentrate on AFs of natural numbers by 𝜔. Since there is no risk of ambigu- that are computably presentable, in the sense that there ity, we simply refer to the elements of 𝜔 as numbers. The are Turing machines (or, equivalently, modern computer symbol 𝜔 𝜔 denotes the set of all functions from 𝜔 to 𝜔. programs) that, in finitely many steps, decide whether a For our purposes, it is convenient to represent elements given pair of arguments belongs to the attack relation. of 𝜔 𝜔 as infinite sequences of numbers (where the 𝑖+1th bit of 𝜋 ∈ 𝜔 𝜔 will be the output of the function 𝜋 on in- Notation. Let (Φ𝑒 )𝑒∈𝜔 be a uniform enumeration of all put 𝑖). We denote by 0∞ the infinite sequence consisting partial computable functions from 𝜔 to {0, 1}. of only 0’s (or, equivalently, the constant function to 0). The restriction of an infinite sequence 𝜋 ∈ 𝜔 𝜔 to its first Definition 3.1. A number 𝑒 is a computable index for 𝑛 bits is denoted by 𝜋 ↾𝑛 . an AF ℱ = (𝐴ℱ , 𝑅ℱ ) with 𝐴ℱ = {𝑎𝑛 : 𝑛 ∈ 𝜔} so that We use standard notation and terminology about {︃ strings: The set of all finite strings of numbers is denoted 1 if 𝑎𝑛 ↣ 𝑎𝑚 by 𝜔 <𝜔 . The symbol 𝜆 denotes the empty string. The Φ𝑒 (⟨𝑛, 𝑚⟩) = 0 otherwise. concatenation of strings 𝜎, 𝜏 is denoted by 𝜎 ⌢ 𝜏 . The length of a string 𝜎 is denoted by |𝜎|. If there is 𝜌 so that An AF ℱ is computable, if it has a computable index 𝑒 ∈ 𝜔. 𝜎 ⌢ 𝜌 = 𝜏 , we say that 𝜎 is a prefix of 𝜏 and we write 𝜎 ⪯ 𝜏 . Similarly, if 𝜋 ∈ 𝜔 𝜔 and 𝜎 = 𝜋 ↾𝑛 for some 𝑛, We use the notation ℱ𝑒 to refer to the AF with com- we write 𝜎 ≺ 𝜋. putable index 𝑒 (note that every computable AF possesses In order to formulate our problems as subsets of 𝜔, infinitely many computable indices.). it will be convenient to encode pairs of numbers into Remark 3.2. The collection of computable indices for AFs single numbers. The pairing function does this. Fix 𝑝 : just defined is noncomputable (in particular, any index 𝑒 𝜔 × 𝜔 → 𝜔 to be a computable bijection. We adopt the for a non-total computable function Φ𝑒 cannot be a com- common habit of denoting 𝑝(𝑥, 𝑦) by ⟨𝑥, 𝑦⟩. putable index for an argumentation framework). There The encodings discussed in Section 4 heavily rely on are alternative indexings that circumvent this issue; yet, the difficulty of calculating paths through trees. As is adopting another indexing would not alter the complexity common in computability theory, we say that a tree is of the computational problems we analyze, though it would a set 𝒯 ⊆ 𝜔 <𝜔 closed under prefixes. We picture trees make the proofs slightly more cumbersome. Hence, we opt growing upwards, with 𝜎 𝑖 to the left of 𝜎 𝑗, when- ⌢ ⌢ for the simplicity of Definition 3.1. The benefit of dealing with computable AFs is that Proof. We first consider 𝜎 ∈ {ad, stb, co}. To define the complexity of the decision problems associated with Cred∞ 𝜎 , we see from Definition 3.3: Cred𝜎 := {⟨𝑒, 𝑛⟩ ∈ ∞ them do not arise due to complexity of the argumenta- 𝜔 : (∃𝑆 ∈ 𝜎(ℱ𝑒 )(𝑎𝑛 ∈ 𝑆))} uses a single existential tion framework itself, but rather reflects the inherent quantifier over sets 𝑆. This is similarly true for the def- complexity of the decision problem. Further, the compu- initions of Exist∞𝜎 and NE𝜎 in Definition 3.3. Thus, it ∞ tational problems associated with computable AFs can be suffices to see that the condition 𝑆 ∈ 𝜎(ℱ𝑒 ) can be de- naturally represented as subsets of 𝜔, which are suitable fined with only quantification over arguments, which are to be classified by computability theoretic means: in bijection with 𝜔, not needing quantification over sets of arguments. Definition 3.3. For a semantics 𝜎: Note that the definition of 𝑆 + and 𝑆 − use only quanti- 1. Cred∞ fiers over arguments. Thus the definition of 𝑓ℱ (𝑆) given 𝜎 := {⟨𝑒, 𝑛⟩ : (∃𝑆 ∈ 𝜎(ℱ𝑒 ))(𝑎𝑛 ∈ 𝑆)}; by 𝑎 ∈ 𝑓ℱ (𝑆) if and only if {𝑎}− ⊆ 𝑆 + uses only 2. Skept∞ 𝜎 := {⟨𝑒, 𝑛⟩ : (∀𝑆 ∈ 𝜎(ℱ𝑒 ))(𝑎𝑛 ∈ 𝑆)}; quantifiers over arguments. Finally, 𝑆 ∈ ad(ℱ), 𝑆 ∈ stb(ℱ), 𝑆 ∈ co(ℱ) are all defined from 𝑓ℱ (𝑆) and 𝑆 + 3. Exist∞ 𝜎 := {𝑒 : (∃𝑆 ⊆ 𝐴ℱ𝑒 ))(𝑆 ∈ 𝜎(ℱ𝑒 ))}; using only quantifiers over arguments. 4. NE∞ In the case of 𝜎 ∈ {infad, infstb, infco}, we need 𝜎 := {𝑒 : (∃𝑆 ∈ 𝜎(ℱ𝑒 ))(𝑆 ̸= ∅)}; to also observe that 𝑆 being infinite is defined via 5. Uni∞ 𝜎 := {𝑒 : (∃!𝑆 ⊆ 𝐴ℱ𝑒 )(𝑆 ∈ 𝜎(ℱ𝑒 ))}. ∀𝑛∃𝑚(𝑎𝑚 ∈ 𝑆 ∧ 𝑚 > 𝑛), which uses only quanti- fiers over numbers. We also introduce new semantics which make sense only in the infinite setting. This is motivated by the idea Proposition 3.5. Skept∞ 1 𝜎 is Π1 , whenever 𝜎 is in that, given an infinite AF, we might hope for our accepted {ad, stb, co, infad, infstb, infco}. Furthermore, for 𝜎 ∈ sets to give us infinitely much information. {ad, co}, Uni∞ 1 𝜎 is Π1 . 1. 𝑆 ∈ infad(ℱ) if and only if 𝑆 ∈ ad(ℱ) and 𝑆 is Proof. The definition of Skept∞ 𝜎 in Definition 3.3 uses a infinite; single universal set-quantifier followed by only number quantifiers in the definition of 𝜎(ℱ𝑒 ). 2. 𝑆 ∈ infco(ℱ) if and only if 𝑆 ∈ co(ℱ) and 𝑆 is For 𝜎 ∈ {ad, co}, 𝑒 ∈ Uni∞ 𝜎 if and only if there are infinite; not two different 𝜎 extensions (as there is always at least one 𝜎 extension). This is defined by the negation of the 3. 𝑆 ∈ infstb(ℱ) if and only if 𝑆 ∈ stb(ℱ) and 𝑆 is following formula: infinite. (∃𝑆1 ∃𝑆2 )(∃𝑥 ∈ 𝑆1 ∖𝑆2 ∧ 𝑆1 ∈ 𝜎(ℱ𝑒 ) ∧ 𝑆2 ∈ 𝜎(ℱ𝑒 )). As an illustration of why we might want to accept only infinite extensions, we consider that a given infinite Note that ∃𝑆1 ∃𝑆2 can be replaced by a single existen- AF may contain a single argument 𝑏 so that 𝑏 attacks tial quantifier by encoding the pair (𝑆1 , 𝑆2 ) as a single every other argument, and every other argument attacks set {⟨1, 𝑥⟩ : 𝑥 ∈ 𝑆1 } ∪ {⟨2, 𝑦⟩ : 𝑦 ∈ 𝑆2 }. This shows 𝑏. We imagine that 𝑏 is a statement of extreme solipsism that Uni∞𝜎 is the complement of a Σ1 set, thus is Π1 . 1 1 denying the truth of any other statement. While {𝑏} is a stable extension, it represents a negligible fraction of Remark 3.6. The above argument does not suffice to arguments, and we may prefer not to accept it. In an show that Uni∞ stb is also Π1 , since some AFs have no stable 1 infinite AF, any finite set is as negligible as {𝑏}, so we extension. The most obvious definition says there exists may prefer to accept only infinite extensions. one stable extension and there does not exist two, which The complexity classes that most naturally match the gives a definition which is a conjunction of a Σ11 and problems of Definition 3.3 are those of the Σ1 and Π1 sets. a Π1 condition, i.e., a so-called d-Σ1 definition. This is 1 1 1 1 The Σ1 sets are formally defined as those subsets of 𝜔 that 1 analogous to the fact that in the finite case Unistb is DP- are definable in the language of second-order arithmetic complete. Similarly, the argument above does not show using a single second-order existential quantifier ranging that Uni∞ 𝜎 is Π 1 1 for 𝜎 ∈ {infad, infstb, infco}. Yet, it is over subsets of 𝜔 followed by number quantifiers and the true that Uni𝜎 is Π1 for 𝜎 ∈ {stb, infad, infstb, infco} as ∞ 1 first order functions and relations (+, ·, <, 0, 1, ∈); for we show below in Corollaries 5.5,5.10, and 5.14. more details, see [18, §16]. Π11 sets are the complements We note that knowing that a problem is Σ11 does not of Σ11 sets. necessarily mean the problem is complicated. This only Proposition 3.4. Cred∞ ∞ ∞ 1 𝜎 , Exist𝜎 , and NE𝜎 are Σ1 , for gives an upper-bound for its complexity. Sometimes, 𝜎 ∈ {ad, stb, co, infad, infstb, infco}. a simpler definition is achievable. As an example, we consider Credcf := {⟨𝑒, 𝑛⟩ : (∃𝑆 ∈ cf(ℱ𝑒 ))(𝑎𝑛 ∈ 𝑆)}. Though the given definition is Σ11 , to know if an argu- more path than 𝒯 (e.g. 𝒯 ′ = {1⌢ 𝜎 : 𝜎 ∈ 𝒯 } ∪ {𝜎 : ment 𝑎𝑛 belongs to a conflict-free extension of ℱ𝑒 , it (∀𝑛 < |𝜎|)𝜎(𝑛) = 0}). The fact that UB is itself Π11 is suffices to check whether 𝑎𝑛 is non-self-defeating, i.e., the subtle part of this example. 𝑎𝑛 ̸↣ 𝑎𝑛 , which is equivalent to checking the com- putable fact that Φ𝑒 (⟨𝑛, 𝑛⟩) = 0. In contrast, we will Theorem 3.7 along with Definition 3.8 suggest a nat- show that for the computational problems associated to ural approach for gauging the complexity of the com- the admissible, stable, and complete semantics, the use putational problems of Definition 3.3. Namely, given of the quantifier ranging over all sets cannot be avoided. another Σ11 (or Π11 ) set 𝑋, we translate the question ask- We will heavily rely on the following fundamental ing whether 𝑛 ∈ 𝑋 to the question of if the tree 𝒯𝑛𝑋 theorem by Kleene which offers a natural way of repre- is ill-founded (resp., well-founded), and then we need senting Σ11 sets: to computably find an instance of our computational problem which should be accepted if and only if 𝒯𝑛𝑋 is Theorem 3.7 (Kleene [19]). A set 𝑋 ⊆ 𝜔 is Σ11 if and ill-founded (resp., well-founded). This involves coding a only if there is a computable sequence of computable trees tree, or more precisely, the collection of paths through (𝒯𝑛𝑋 )𝑛∈𝜔 so that 𝑛 ∈ 𝑋 iff 𝒯𝑛𝑋 is ill-founded. a tree into the 𝜎 extensions in an argumentation frame- work. We do exactly this in Section 4. We call (𝒯𝑛𝑋 )𝑛∈𝜔 a tree-sequence for 𝑋. As a corollary of Kleene’s theorem, one obtains that the problem of Table 2 collects our results regarding complexities of deciding which computable trees in 𝜔 <𝜔 are ill-founded the computational problems examined for computable (or well-founded) is as hard as any other Σ11 (resp., Π11 ) argumentation frameworks. problem. Remark 3.12. As noted before, the Σ11 sets are natural Theorem 3.7 gives a reason to consider the Σ11 sets as analogs in the infinitary setting of the NP sets, and the the natural infinite analogs of the NP problems. Namely, Π11 sets are the natural analogs of the coNP sets. With given an ill-founded computable tree 𝒯 and a sequence 𝜋 the exception of Skept∞co and Unistb , Table 2 follows this ∞ which is a path through 𝒯 , it is relatively simple to check translation from Table 1 for the first three rows. These that 𝜋 ∈ [𝒯 ] (it requires checking infinitely many simple two results mark surprising differences in the infinite facts: 𝜋 ↾𝑛 ∈ 𝒯 , for each 𝑛), but finding a sequence 𝜋 ∈ setting. [𝑇 ]—or even knowing whether there exists a sequence 𝜋 ∈ [𝑇 ]—is a far harder problem. The trivial entries are due to the fact that ∅ is always Our main goal is to exactly characterize the complexity an admissible extension and the grounded extension is of the computational problems described in Definition always a complete extension. 3.3. To do so, we need to show that they are complete for their respective complexity classes. The following 3.3. Spectra of 𝜎 extensions definition formalizes this notion. We propose a way to more fully understand the complex- Definition 3.8. Let Γ be a complexity class (e.g., Γ ∈ ity of the problem of finding a 𝜎 extension in a given AF {Σ11 , Π11 }). A set 𝑉 ⊆ 𝜔 is Γ-hard, if for every 𝑋 ∈ Γ ℱ. there is a computable function 𝑓 : 𝜔 → 𝜔 so that 𝑥 ∈ 𝑋 if and only if 𝑓 (𝑥) ∈ 𝑉 . If 𝑉 is Γ-hard and belongs to Γ, Definition 3.13. For each 𝑒 ∈ 𝜔 and semantics 𝜎, let then it is Γ-complete. Spec¬∅ 𝜎 (ℱ𝑒 ) be the set of Turing degrees of non-empty sets 𝑋 ⊆ 𝜔 so that {𝑎𝑛 : 𝑛 ∈ 𝑋} is a 𝜎 extension in ℱ𝑒 . Proposition 3.9. It follows from Theorem 3.7 that the set of indices for ill-founded computable trees is a Σ11 - The notion Spec¬∅𝜎 (ℱ𝑒 ) exactly captures the difficulty complete set. Similarly, the set of indices for well-founded of computing a non-empty 𝜎 extension in ℱ𝑒 . We will computable trees is a Π11 -complete set. be relating the problem of computing a 𝜎 extension in ℱ𝑒 to the problem of finding a path through a particular The following example is far less obvious, but will be tree. So, we define the analogous notion of the spectrum useful below to examine Uni∞ 𝜎 . of a tree. Theorem 3.10 ([20, Theorem 18.11]). The set UB of in- Definition 3.14. Given any computable tree 𝒯 , we let dices for computable trees with exactly one path is a Π11 - Spec(𝒯 ) be set of Turing degrees of paths 𝑋 ∈ [𝒯 ]. complete set. Table 3 collects our results on spectra of extensions. Remark 3.11. The hardness in Theorem 3.10 is quite easy. We can reduce the question of whether a tree 𝒯 is well-founded to whether a tree 𝒯 ′ has two paths, where 𝒯 ′ always has at least one path, by simply giving 𝒯 ′ one 𝜎 Cred∞ 𝜎 Skept∞ 𝜎 Exists∞𝜎 NE∞ 𝜎 Uni∞ 𝜎 ad Σ11 -c 4.2,3.4 trivial trivial Σ11 -c 4.2 3.4 Π11 -c 4.3,3.5 stb Σ11 -c 4.2,3.4 Π11 -c 4.4,3.5 Σ11 -c 4.2, 3.4 Σ11 -c 4.2,3.4 Π11 -c 4.3, 5.10 co Σ11 -c 4.2, 3.4 Π11 -c *, 3.5 trivial Σ11 -c 4.2, 3.4 Π11 -c 4.3,3.5 infad Σ11 -c 4.2,3.4 Π11 -c 4.4,3.5 Σ11 -c 4.2, 3.4 Σ11 -c 4.2, 3.4 Π11 -c 4.3,5.5 infstb Σ11 -c 4.2,3.4 Π11 -c 4.4,3.5 Σ11 -c 4.2, 3.4 Σ11 -c 4.2, 3.4 Π11 -c 4.3,5.10 infco Σ11 -c 4.2,3.4 Π11 -c 4.4,3.5 Σ11 -c 4.2, 3.4 Σ11 -c 4.2, 3.4 Π11 -c 4.3, 5.14 Table 2 Computational problems for computable AFs. 𝒞 -c denotes completeness for the class 𝒞 . The entry with an asterisk is not fully proved in this paper. Rather, the Π11 -hardness for Skept∞ co is deferred to future work focusing on the grounded semantics. It is included in the table here (though partially unproved) to give a more complete picture. The numbers in each cell of the table refer to the Theorem number providing the lower bound and upper bounds for the result in that cell. 𝜎 Spec¬∅ 𝜎 Lemma 4.1. A non-empty extension 𝑆 of ℱ 𝒯 is stable ad Exactly Spec(𝒯 ) iff 𝑆 is complete iff 𝑆 is admissible iff 𝑆 is exactly 𝑆𝜋 for stb Exactly Spec(𝒯 ) some 𝜋 ∈ [𝒯 ]. co Any Spec(𝒯 ) infad Exactly Spec(𝒯 ) Proof. Stable always implies complete, which always im- infstb Exactly Spec(𝒯 ) plies admissible. It is straightforward to check that 𝑆𝜋 is infco Any Spec(𝒯 ) stable for any 𝜋 ∈ [𝒯 ], so we need only show that any Table 3 non-empty admissible extension is exactly some 𝑆𝜋 . Sup- For any computable tree 𝒯 , there is a computable argumen- pose that 𝑆 is admissible. Observe that 𝑐 and 𝑏𝜎 cannot tation framework ℱ𝑒 so that Spec(𝒯 ) = Spec¬∅ 𝜎 (ℱ𝑒 ). When be in 𝑆 since these are self-defeating. So some 𝑎𝜎 ∈ 𝑆 𝜎 ∈ {ad, stb, infad, infstb}, the converse also holds. Namely, since 𝑆 is non-empty. Note that since 𝑐 ↣ 𝑎𝜎 , we must for every 𝑒, there is a computable tree so that Spec¬∅ 𝜎 (ℱ𝑒 ) = have 𝑎𝜆 ∈ 𝑆. Next, observe that if 𝑎𝜏 ∈ 𝑆, then there Spec(𝒯 ). We do not know how to attain a corresponding up- must be some 𝑖 so that 𝑎𝜏 ⌢ 𝑖 ∈ 𝑆: this is because some per bound for the complete or infinite complete cases. element of 𝑆 must defend 𝑎𝜏 from 𝑏𝜏 and such an ele- ment must be an 𝑎𝜎 with |𝜎| = |𝜏 | + 1. But it must have 𝜏 ≺ 𝜎 as otherwise 𝑎𝜎 would attack 𝑎𝜏 . It follows that 4. Encoding a tree into an 𝑆 contains 𝑆𝜋 for some 𝜋 ∈ [𝒯 ]. Since 𝑆𝜋 is stable, 𝑆 argumentation framework cannot properly contain 𝑆𝜋 , so 𝑆 = 𝑆𝜋 . We are now in a position to obtain hardness results for Given a tree 𝒯 ⊆ 𝜔 <𝜔 , we will define an argumentation the computational problems described in Definition 3.3. framework ℱ = (𝐴 , 𝑅 ). The set of arguments 𝐴 𝒯 𝒯 𝒯 𝒯 of ℱ 𝒯 is computable and consists of {𝑎𝜎 : 𝜎 ∈ 𝒯 }∪{𝑏𝜎 : Theorem 4.2. The following hold: 𝜎 ∈ 𝒯 } ∪ {𝑐}. The attack relation 𝑅𝒯 of ℱ 𝒯 contains 1. for 𝜎 ∈ {ad, stb, co, infad, infstb, infco}, NE∞ 𝜎 is all and only the following edges: Σ11 -hard; For all 𝜎 ∈ 𝒯 , 2. for 𝜎 ∈ {stb, infad, infstb, infco}, Exist∞ 1 𝜎 is Σ1 - 1. 𝑏𝜎 ↣ 𝑏𝜎 ; hard; 2. 𝑏𝜎 ↣ 𝑎𝜎 ; 3. for 𝜎 ∈ {ad, stb, co, infad, infstb, infco}, Cred∞ 𝜎 is Σ11 -hard. 3. 𝑎𝜎 ↣ 𝑏𝜏 , if |𝜎| = |𝜏 | + 1; Proof. 1. Let 𝑋 ∈ Σ11 and let (𝒯𝑛𝑋 )𝑛∈𝜔 be a tree- 4. 𝑎𝜎 ↣ 𝑎𝜏 , if |𝜎| = |𝜏 | + 1 and 𝜏 ̸⪯ 𝜎; sequence for 𝑋, as given by Theorem 3.7. To show Σ11 - hardness, we need to produce a computable function 5. 𝑐 ↣ 𝑎𝜏 for every 𝜏 ∈ 𝒯 ; 𝑓 so that 𝑛 ∈ 𝑋 if and only if 𝑓 (𝑛) ∈ NE∞ 𝜎 . We let 𝑋 6. 𝑎𝜆 ↣ 𝑐. 𝑓 (𝑛) be a computable index for ℱ 𝒯𝑛 . Then Lemma 4.1 shows that 𝑛 ∈ 𝑋 if and only if 𝒯𝑛𝑋 is ill-founded if Figure 1 gives an example of our encoding for a fi- 𝑋 and only if ℱ 𝒯𝑛 has a non-empty 𝜎 extension for each nite tree. We next consider which extensions in ℱ 𝒯 are 𝜎 ∈ {ad, stb, co, infad, infstb, infco}. admissible, stable, or complete. 2. For each of these 𝜎, the empty set is not a 𝜎 ex- Notation. For 𝜋 ∈ [𝒯 ], let 𝑆𝜋 be the set {𝑎𝜎 : 𝜎 ≺ 𝜋}. tension, so Exist∞𝜎 = NE𝜎 , which we showed above is ∞ Σ1 -hard. 1 𝑐 10 11 𝑎10 𝑏10 𝑎11 𝑏11 0 1 𝑎0 𝑏0 𝑎1 𝑏1 𝜆 𝑎𝜆 𝑏𝜆 Figure 1: Example of our encoding of trees into AFs: the left-side represents the tree {𝜆, 0, 1, 10, 11}, the right-side is the resulting AF. When applied to trees 𝑇 of infinite height, [𝑇 ] will be encoded into the stable, complete, and admissible extensions of ℱ𝑇 . For the example shown in the figure, the only admissible extension of ℱ𝒯 is the empty one, since [𝑇 ] = ∅. 3. In the proof of 1. above, we reduced a given Σ11 set 𝑋 for 𝒢𝑛 := ℱ𝒯𝑛′ if and only if 𝒯𝑛′ only has paths 𝜋 with to NE∞ 𝜎 by sending 𝑛 to ℱ 𝒯𝑛𝑋 𝑋 . Note that ℱ 𝒯𝑛 has a non- 𝜋(0) = 0 if and only if 𝒯𝑛′ has only one path (see the empty 𝜎 extension if and only if 𝑎𝜆 is in some 𝜎 extension. definition of 𝒯𝑛′ in Remark 3.11) if and only if 𝑛 ∈ 𝑋. Thus sending 𝑛 to ⟨𝑒, 𝑎𝜆 ⟩ where 𝑒 is a computable index This shows the Π11 -hardness of Skept∞𝜎 . 𝑋 for ℱ 𝒯𝑛 shows that Cred∞ 𝜎 is Σ1 -hard. 1 Theorem 4.5. For 𝜎 ∈ {ad, stb, co, infad, infstb, infco} Theorem 4.3. For 𝜎 ∈ {ad, stb, co, infad, infstb, infco}, and for any computable tree 𝒯 , there exists a computable Uni∞ is Π1 -hard. AF ℱ𝑒 so that Spec¬∅ 𝜎 (ℱ𝑒 ) = Spec(𝒯 ). 𝜎 1 Proof. We first consider 𝜎 ∈ {ad, co}. Let 𝑋 ∈ Π11 and Proof. Observe that for the AF ℱ𝑒 = ℱ 𝒯 , it follows let (𝒯𝑛𝜔∖𝑋 )𝑛∈𝜔 be a tree-sequence for its complement. from Lemma 4.1 that the non-empty 𝜎 extensions are all 𝜔∖𝑋 infinite and are in the same Turing degrees as the paths Consider the sequence of AFs (ℱ 𝒯𝑛 )𝑛∈𝜔 . Note that through 𝒯 . ∅ is an admissible extension in any AF and since every 𝜔∖𝑋 argument in ℱ 𝒯𝑛 is attacked, ∅ is also a complete extension. Thus, ℱ 𝒯𝑛 𝜔∖𝑋 has a unique 𝜎 extension if 5. Trees coding extensions in 𝜎(ℱ) and only if 𝒯𝑛𝜔∖𝑋 is well founded if and only if 𝑛 ∈ 𝑋, In this section, we give upper bounds to the complexity of which shows that Uni∞ ad and Unico are Π1 -hard. ∞ 1 Spec¬∅ 𝜎 for 𝜎 ∈ {ad, stb, infad, infstb} as well as giving For the other 𝜎, ∅ is not a 𝜎 extension. We use Theorem upper bounds for the complexity of Uni∞ 𝜎 for any 𝜎 ∈ 3.10 to show Π11 -hardness. Let 𝑋 be any Π11 set. Then {stb, infad, infstb, infco}. We do this by describing how we get from Remark 3.11 a sequence of trees 𝒯𝑛′ so that to computably encode the collection of extensions in 0∞ ∈ [𝒯𝑛′ ] for each 𝑛, and {𝑛 : 𝒯𝑛′ has only one path} 𝜎(ℱ) into the set of paths through a tree. is Π11 -hard. It follows ′ from Lemma 4.1 that this holds if and only if ℱ 𝒯𝑛 has a unique 𝜎 extension, which shows the Π11 -hardness of Uni∞ The admissible case 𝜎 . Given a computable argumentation framework ℱ, we Theorem 4.4. For any 𝜎 ∈ {stb, infstb, infco, infad}, ∞ 1 will describe a computable tree 𝒯 ℱ so that the paths of Skept𝜎 is Π1 -hard. 𝒯 ℱ encode the non-empty admissible extensions in ℱ. Proof. Let 𝑋 be a Π11 set. Then we get from Remark 3.11 We begin with an intuitive description of how a path 𝜋 a sequence of trees 𝒯𝑛′ so that 0∞ ∈ [𝒯𝑛′ ] for each 𝑛, through the tree 𝒯 will encode an admissible extension ℱ and {𝑛 : 𝒯 has only one path} is Π -hard. Then note ′ 1 𝑆, and we give the formal definition of 𝒯 ℱ below. 𝑛 1 that ⟨𝑒, 𝑎0 ⟩ ∈ Skept∞ 𝜎 where 𝑒 is a computable index Branching in 𝒯 ℱ will come in three flavors. The first Since 𝜎 ∈ 𝒯 ℱ , it follows that In𝜎 is conflict-free, so branching is used to give the least element of the admis- 𝑎𝑖 ̸↣ 𝑎𝑗 . Next, observe that 𝑆 defends itself. If 𝑎𝑖 ↣ 𝑎𝑗 sible extension 𝑆. This is to ensure that the extension is and 𝑎𝑗 ∈ 𝑆, then there is some 𝑛 so that 𝑔𝑛 = (𝑎𝑖 , 𝑎𝑗 ). non-empty. If we wished to allow the empty extension, Then consider 𝜎 = 𝜋 ↾𝑛+1 . We must have 𝜎(𝑛) = 𝑘 + 1 we could omit this branching. For any 𝑗 > 0, the branch- for some 𝑘 with 𝑎𝑘 ∈ 𝑆 and 𝑎𝑘 ↣ 𝑎𝑖 . ing on level 2𝑗 serves to code whether or not 𝑗 ∈ 𝑆. Finally, note that both the map from 𝜋 to 𝑆 and from 𝑆 Branching on the odd levels serve to explain how 𝑆 sat- to 𝜋 are computable if ℱ is computable and are inverses isfies the hypothesis of being an admissible extension. If of each other. 𝑎𝑖 ↣ 𝑎𝑗 is the 𝑛th element of some computable enumer- ation of all attacking pairs of arguments, then 𝜎(2𝑛 + 1) Corollary 5.3. For every computable AF ℱ𝑒 , there exists will be 0 if 𝑎𝑗 ∈/ 𝑆 and otherwise will be 𝑘 + 1 where 𝑘 a computable tree 𝒯 so that Spec¬∅ ad (ℱ𝑒 ) = Spec(𝒯 ). is least so that 𝑎𝑘 ∈ 𝑆 and 𝑎𝑘 ↣ 𝑎𝑖 . Proof. It follows immediately from Theorem 5.2 that Let ℱ = (𝐴ℱ , 𝑅ℱ ) be a computable AF. Let (𝑔𝑛 )𝑛∈𝜔 Spec¬∅ ad (ℱ𝑒 ) = Spec(𝒯 ℱ𝑒 ). be a computable sequence of all elements of 𝑅ℱ . If 𝑔𝑛 = (𝑎𝑖 , 𝑎𝑗 ), we denote 𝑎𝑖 by 𝑔𝑛− and 𝑎𝑗 by 𝑔𝑛+ . We now Corollary 5.4. For every computable AF ℱ𝑒 , there exists define the tree 𝒯 ℱ . a computable tree 𝒯̂︀ so that Spec¬∅ infad (ℱ𝑒 ) = Spec(𝒯 ). ̂︀ Definition 5.1. Any given string 𝜎 ∈ 𝜔 <𝜔 defines two Proof. The tree needed here is a slight alteration of the subsets of arguments in 𝐴ℱ : tree 𝒯 ℱ . In 𝒯 ℱ , we made 𝜎(0) tell us the least 𝑘 so • In𝜎 = {𝑎𝜎(0) }∪{𝑎𝑗 : 𝑗 > 0∧𝜎(2𝑗) = 1}∪{𝑎𝑘 : 𝑎𝑘 ∈ 𝑆 so as to ensure that 𝑆 ̸= ∅. We do the same on (∃𝑗)(𝜎(2𝑗 + 1) = 𝑘 + 1)} ∪ {𝑎𝑖 : (∃𝑗)(𝜎(2𝑗 + infinitely many layers, e.g., instead of having 𝜎(2𝑛) be 0 1) > 0 ∧ 𝑔𝑗+ = 𝑎𝑖 )}; or 1 to tell us whether or not 𝑛 ∈ 𝑆, we have 𝜎(2𝑛) tell us the 𝑛th least number 𝑘 so that 𝑎𝑘 ∈ 𝑆. With the tree • Out𝜎 = {𝑎𝑖 : 𝑖 < 𝜎(0)}∪{𝑎𝑗 : 𝑗 > 0∧𝜎(2𝑗) = altered like this, paths are in computable bijection with + 0}∪{𝑎𝑖 : (∃𝑗)(𝜎(2𝑗+1) = 0∧𝑔𝑗 = 𝑎𝑖 )}∪{𝑎𝑖 : the infinite admissible extensions. (∃𝑗)(𝜎(2𝑗 + 1) > 𝑖 + 1 ∧ 𝑎𝑖 ↣ 𝑔𝑗− )}. Corollary 5.5. Uni∞ 1 infad is Π1 . We define 𝒯 ℱ as the set of 𝜎 so that Proof. 𝑒 is in Uniinfad if and only if the tree 𝒯̂︀ in Corollary • In𝜎 is conflict-free; 5.4 has a unique path. By Theorem 3.10, this is a Π11 • In𝜎 ∩ Out𝜎 = ∅ condition. • If 0 < 2𝑗 < |𝜎|, then 𝜎(2𝑗) ∈ {0, 1}; • If 2𝑗 + 1 < |𝜎| and 𝜎(2𝑗 + 1) = 𝑘 + 1, then The stable case 𝑎𝑘 ↣ 𝑔𝑗− . Similarly, we can construct a tree encoding the stable Theorem 5.2. Let ℱ be a (computable) argumentation extensions by making 𝜎(𝑛) = 0 if 𝑎𝑛 ∈ 𝑆 and otherwise framework. Then the non-empty admissible extensions of making 𝜎(𝑛) be 𝑘 + 1 where 𝑘 is least so that 𝑎𝑘 ∈ 𝑆 ℱ are in (computable) bijection with the paths in 𝒯 ℱ . and 𝑎𝑘 ↣ 𝑎𝑛 . Proof. Given a non-empty admissible extension 𝑆 of ℱ, Definition 5.6. Any given string 𝜎 ∈ 𝜔 <𝜔 defines two we define the corresponding path 𝜋 in 𝒯 ℱ as follows. Let subsets of arguments in 𝐴ℱ : 𝜋(0) be the least element of 𝑆. For 𝑗 > 0, let 𝜋(2𝑗) = 1 if 𝑎𝑗 ∈ 𝑆 and 𝜋(2𝑗) = 0 otherwise. Let 𝜋(2𝑛 + 1) be 0 • In𝜎 = {𝑎𝑖 : 𝜎(𝑖) = 0} ∪ {𝑎𝜎(𝑖)−1 : 𝑖 < |𝜎| ∧ if 𝑔𝑛+ ∈ / 𝑆 and be 𝑘 + 1 where 𝑘 is least so that 𝑎𝑘 ∈ 𝑆 𝜎(𝑖) > 0}; and 𝑎𝑘 ↣ 𝑔𝑛− otherwise. It is straightforward to check • Out𝜎 = {𝑎𝑖 : 𝑖 < |𝜎| ∧ 𝜎(𝑖) > 0} ∪ {𝑎𝑖 : that 𝜋 ∈ [𝒯 ℱ ]. (∃𝑗)𝜎(𝑗) > 𝑖 + 1 ∧ 𝑎𝑖 ↣ 𝑎𝑗 )}. Given a path 𝜋 through 𝒯 ℱ , first note that whenever there is some 𝜎 ≺ 𝜋 so that 𝑎𝑛 ∈ In𝜎 , then 𝜋(2𝑛) = 1. We define 𝒯 ℱ as the set of 𝜎 so that This is because whenever 𝜎 ⪯ 𝜏 , then In𝜎 ⊆ In𝜏 . Then • In𝜎 is conflict-free; since 𝜏 := 𝜋 ↾max(|𝜎|,2𝑛+1) is in 𝒯 ℱ , we cannot have 𝜏 (2𝑛) = 0 since • In𝜎 ∩ Out𝜎 = ∅ ⋃︀ 𝑎𝑛 ∈ In𝜏 . Thus 𝜋(2𝑛) = 𝜏 (2𝑛) = 1. It • If 𝑗 < |𝜎| and 𝜎(𝑗) = 𝑘 + 1, then 𝑎𝑘 ↣ 𝑎𝑗 . follows that 𝜎≺𝜋 In𝜎⋃︀= {𝑎𝑛 : 𝜋(2𝑛) = 1}. The same argument shows that 𝜎≺𝜋 Out𝜎 = {𝑎𝑛 : 𝜋(2𝑛) = 0}. Theorem 5.7. Let ℱ be a (computable) argumentation Let 𝑆 = {𝑎𝑛 : 𝜋(2𝑛) = 1}. framework. Then the stable extensions of ℱ are in (com- Note that 𝑆 is conflict-free, since if 𝑎𝑖 , 𝑎𝑗 ∈ 𝑆 then putable) bijection with the paths in 𝒯 ℱ . there is some long enough 𝜎 ≺ 𝜋 so that 𝑎𝑖 , 𝑎𝑗 ∈ In𝜎 . Proof. Given a stable extension 𝑆 of ℱ, we define the • 𝜋(2𝑛) = 0 if 𝑎𝑛 ∈ 𝑆 and otherwise 𝜋(2𝑛) = corresponding path 𝜋 in 𝒯 ℱ as follows. For each 𝑛, let 𝑘 + 1 where 𝑘 is least so 𝑎𝑘 ∈ / 𝑆 + and 𝑎𝑘 ↣ 𝑎𝑛 . 𝜋(𝑛) be 0 if 𝑎𝑛 ∈ 𝑆 and let 𝜋(𝑛) be 𝑘 + 1 where 𝑘 • 𝜋(2𝑛 + 1) = 0 if 𝑎𝑛 ∈/ 𝑆 and otherwise 𝜋(2𝑛 + + is least so that 𝑎𝑘 ∈ 𝑆 and 𝑎𝑘 ↣ 𝑎𝑛 otherwise. It is 1) = 𝑘 + 1 where 𝑘 is least so 𝑎𝑘 ∈ 𝑆 and straightforward to check that 𝜋 ∈ [𝒯 ℱ ]. 𝑎𝑘 ↣ 𝑎𝑛 . Given a path 𝜋 through 𝒯 ℱ , first note that whenever there is some 𝜎 ≺ 𝜋 so that 𝑎𝑛 ∈ In𝜎 , then 𝜋(𝑛) = 0. Note that 𝜋(2𝑛) explains why 𝑎𝑛 is either in 𝑆 or it is This is because whenever 𝜎 ⪯ 𝜏 , then In𝜎 ⊆ In𝜏 . Then not in 𝑓ℱ (𝑆), i.e., 𝑓ℱ (𝑆) ⊆ 𝑆, while 𝜋(2𝑛 + 1) simply since 𝜏 = 𝜋 ↾max(|𝜎|,𝑛+1) is on 𝒯 ℱ , we cannot have verifies that the elements which 𝜋 says are in 𝑆 + are in 𝜏 (𝑛) ̸= 0 since 𝑎𝑛 ⋃︀ ∈ In𝜏 and therefore cannot be in fact in 𝑆 + . Out𝜏 . It follows that 𝜎≺𝜋 In𝜎 = {𝑎𝑛 : 𝜋(𝑛) = 0}. Let Formally, we define 𝒯 ℱ as follows: 𝑆 = {𝑎𝑛 : 𝜋(𝑛) = 0}. Definition 5.11. Any given string 𝜎 ∈ 𝜔 <𝜔 defines four Note that 𝑆 is conflict-free, since if 𝑎𝑖 , 𝑎𝑗 ∈ 𝑆, then subsets of arguments in 𝐴ℱ : 𝑎𝑖 ̸↣ 𝑎𝑗 since 𝜎 = 𝜋 ↾max(𝑖,𝑗)+1 is in 𝒯 ℱ , and thus In𝜎 is conflict-free. Next observe that for any 𝑛, either 𝑎𝑛 ∈ • In𝜎 = {𝑎𝑖 : 𝜎(2𝑖) = 0} ∪ {𝑎𝑘 : (∃𝑗)(𝜎(2𝑗 + 𝑆 or there is some 𝑚 so that 𝑎𝑚 ∈ 𝑆 and 𝑎𝑚 ↣ 𝑎𝑛 . 1) = 𝑘 + 1} In particular, if 𝜋(𝑛) = 0, then 𝑎𝑛 ∈ 𝑆 and otherwise • Out𝜎 = {𝑎𝑖 : 𝜎(2𝑖) ̸= 0} ∪ {𝑎𝑖 : (∃𝑗)𝜎(2𝑗 + 𝑎𝜋(𝑛)−1 ∈ 𝑆 and 𝑎𝜋(𝑛)−1 ↣ 𝑎𝑛 . 1) > 𝑖 + 1 ∧ 𝑎𝑖 ↣ 𝑎𝑗 )} Finally, note that both the map from 𝜎 to 𝑆 and from 𝑆 to 𝜎 are computable if ℱ is computable and are inverses • InSplus𝜎 = {𝑎𝑖 : (∃𝑗)(𝜎(2𝑗) > 𝑖 + 1 ∧ 𝑎𝑖 ↣ of each other. 𝑎𝑗 )} ∪ {𝑎𝑖 : 𝜎(2𝑖 + 1) ̸= 0} • OutSplus𝜎 = {𝑎𝑖 : (∃𝑗)𝜎(2𝑗) = 𝑖 + 1} ∪ {𝑎𝑖 : Corollary 5.8. For any computable AF ℱ𝑒 there exists a 𝜎(2𝑖 + 1) = 0} computable tree 𝒯 so that Spec¬∅ stb (ℱ𝑒 ) = Spec(𝒯 ). We define 𝒯 ℱ as the set of 𝜎 so that Proof. This follows directly from Theorem 5.7 along with the fact that ∅ is never a stable extension. 1. In𝜎 is conflict-free; Corollary 5.9. For any computable AF ℱ𝑒 there exists a 2. In𝜎 ∩ Out𝜎 = ∅; computable tree 𝒯 so that Spec¬∅ infstb (ℱ𝑒 ) = Spec(𝒯 ). 3. InSplus𝜎 ∩ OutSplus𝜎 = ∅; Proof. We add layers of branching to the tree as in Corol- 4. If 𝜎(2𝑗) = 𝑘 + 1, then 𝑎𝑘 ↣ 𝑎𝑗 ; lary 5.4 so that, e.g., 𝜎(2𝑛) = 𝑚 means that 𝑚 is the 𝑛th least number so that 𝑎𝑛 ∈ 𝑆. This produces a tree 𝒯 ℱ ̂︂ 5. If 𝜎(2𝑗 + 1) = 𝑘 + 1, then 𝑎𝑘 ↣ 𝑎𝑗 ; so that the paths are in computable bijection with the 6. For 𝑗, 𝑘 < |𝜎|, if 𝑎𝑘 ∈ OutSplus𝜎 and 𝑎𝑗 ∈ In𝜎 infinite stable extensions of ℱ. then 𝑎𝑗 ̸↣ 𝑎𝑘 ; Corollary 5.10. Uni∞ ∞ 1 stb and Uniinfstb are Π1 . 7. For 𝑛, 𝑚 < |𝜎|, if 𝑎𝑛 ∈ OutSplus𝜎 and 𝑎𝑚 ∈ In𝜎 , then 𝑎𝑛 ̸↣ 𝑎𝑚 (i.e., 𝜎 does not contradict 𝑆 ⊆ Proof. As the paths through 𝒯 ℱ𝑒 are in bijection with 𝑓ℱ (𝑆)). the stable extensions, 𝑒 ∈ Uni∞ stb if and only if 𝒯 ℱ𝑒 has a unique path. As the paths through 𝒯 (see Corollary 5.9) Theorem 5.12. The complete extensions of ℱ are in bi- ̂︀ ℱ are in bijection with the infinite stable extensions in ℱ𝑒 , jection with the set of paths [𝒯 ℱ ]. we have 𝑒 ∈ Uniinfstb if and only if 𝒯̂︀ ℱ𝑒 has a unique path. By Theorem 3.10, these are both Π11 conditions. Proof. Let 𝑆 be any complete extension. We can define 𝜋 from 𝑆 as described at the beginning of this section. It The complete case is straightforward to verify that each condition (1-7) of Definition 5.11 is satisfied by 𝜋 ↾𝑛 for each 𝑛. Given an argumentation framework ℱ, we can similarly Given a path 𝜋 ∈ [𝒯 ℱ ], we can define sets 𝑆 = {𝑖 : construct a tree 𝒯 so that paths through 𝒯 code com- 𝜋(2𝑖) = 0} and 𝑈 = {𝑖 : 𝜋(2𝑖 + 1) ̸= 0}. We note that ℱ ℱ plete extensions. In order to ensure that 𝑓ℱ (𝑆) ⊆ 𝑆, we when 𝜎 ⪯ 𝜏 , In𝜎 ⊆ In𝜏 . It follows from this fact, as in will need the paths in 𝒯 ℱ to not only code sets 𝑆 but the previous theorems, that 𝑆 = ⋃︀ 𝜎≺𝜋 In𝜎 . Similarly, also their attacked sets 𝑆 + . 𝑈 = ⋃︀ InSplus . 𝜎≺𝜋 𝜎 Given an extension 𝑆, we will let 𝜋 ∈ 𝒯 ℱ encode 𝑆 Next we see that 𝑈 = 𝑆 + . If 𝑛 ∈ 𝑈 , then 𝜋(2𝑛+1) ̸= and 𝑆 as follows: + 0 and by condition 5, we have 𝑎𝜋(2𝑛+1)−1 attacks 𝑎𝑛 . But then 𝑎𝜋(2𝑛+1)−1 ∈ In𝜋↾2𝑛+2 , so 𝑎𝜋(2𝑛+1)−1 ∈ 𝑆. Thus 𝑈 ⊆ 𝑆 + . On the other hand if 𝑛 ∈ / 𝑈 , then condition that satisfy a given semantics 𝜎. The computational prob- 6 for all 𝜎 of length > 2𝑛 + 1 ensures that there is no lems we examined were found to be maximally complex, 𝑎𝑗 ∈ 𝑆 so 𝑎𝑗 ↣ 𝑎𝑛 . Thus 𝑆 + ⊆ 𝑈 . properly belonging to the complexity classes of Σ11 and Finally, we verify that 𝑆 is complete. 𝑆 is clearly con-Π11 sets. flict free by Condition 1. Condition 7 ensures that any A plethora of intriguing questions regarding the com- 𝑎𝑚 ∈ 𝑆 is also in 𝑓ℱ (𝑆), since if 𝑛 ∈ / 𝑈 , then 𝑎𝑛 ̸↣ 𝑎𝑚 . plexity of infinite AFs remains open. First, we shall fill the To see that 𝑓ℱ (𝑆) ⊆ 𝑆, note that any 𝑎𝑛 ∈ / 𝑆 has gaps that we left behind (such as proving the Π11 -hardness 𝜋(𝑛) ̸= 0 and 𝑎𝜋(𝑛)−1 ∈ / 𝑆 + and 𝑎𝜋(𝑛)−1 ↣ 𝑎𝑛 by for Skept∞co ). Next, we aim at investigating whether the condition 4. Thus 𝑎𝑛 ∈ / 𝑓ℱ (𝑆). computational problems considered in this paper become more tractable if we restrict to special classes of AFs, such Remark 5.13. The map from paths 𝜋 ∈ [𝒯 ℱ ] to com- as the finitary ones (i.e., those in which each argument plete extensions 𝑆 ⊆ 𝐴ℱ is computable, but to compute receives finitely many attacks only [7]). Finally, future 𝜋 ∈ 𝒯 ℱ we need both 𝑆 and 𝑆 + . Thus, we are able to research will extend our analysis to analogous problems say that for any computable AF ℱ𝑒 , the set of Turing associated with other key semantics for AFs, including degrees of pairs (𝑆, 𝑆 + ) where 𝑆 is a complete exten- grounded, preferred, and ideal semantics. Given that the sion is always Spec(𝒯 ) for a computable tree 𝒯 , but note definitions of these semantics are more intricate than that 𝑆 and 𝑆 + are not generally of the same Turing de- those we examined here, we anticipate the need for addi- gree. Thus, we are currently unable to fully characterize tional techniques to thoroughly analyze them. Spec¬∅ co or Specinfco . ¬∅ Corollary 5.14. Uni∞ 1 infco is Π1 . Acknowledgments Proof. We can alter the tree 𝒯 ℱ𝑒 as in Corollary 5.4 to get Andrews was partially supported by NSF grant DMS- a new tree 𝒯̂︀ so that the paths through 𝒯̂︀ are in bijection 2348792. San Mauro is a member of INDAM-GNSAGA. with the infinite complete extensions. Then 𝑒 ∈ Uni∞ infco if and only if 𝒯̂︀ has a unique path. Theorem 3.10 shows that this is a Π11 condition. References [1] P. Baroni, F. Cerutti, P. E. Dunne, M. Giacomin, Au- Corollary 5.15. Fix 𝜎 ∈ {ad, stb, co, infad, infstb, infco} tomata for infinite argumentation structures, Arti- and suppose that ℱ𝑒 has only countably many non-empty ficial Intelligence 203 (2013) 104–150. 𝜎 extensions. Then there is a hyperarithmetical set 𝑆 so [2] P. M. Dung, On the acceptability of arguments and that {𝑎𝑛 : 𝑛 ∈ 𝑆} is a 𝜎 extension of ℱ𝑒 . its fundamental role in nonmonotonic reasoning, Proof. If 𝜎 ∈ {ad, stb, infad, infstb}, let 𝒯 be a tree so logic programming and n-person games, Artificial that Spec¬∅ intelligence 77 (1995) 321–357. 𝜎 (ℱ𝑒 ) = Spec(𝒯 ). If 𝜎 ∈ {𝑐𝑜, infco}, let 𝒯 be a tree so that the set of Turing degrees of pairs (𝑆, 𝑆+) of [3] A. J. García, G. R. Simari, Defeasible logic program- 𝜎 extensions is exactly Spec(𝒯 ). Then 𝒯 is a computable ming: An argumentative approach, Theory and tree with countably many paths. By a classic result of practice of logic programming 4 (2004) 95–138. Kreisel [21, Theorem 3.9], 𝒯 has a hyperarithmetical [4] P. Baroni, M. Giacomin, G. Guida, Self-stabilizing path, which corresponds to a hyperarithmetical 𝑆 so that defeat status computation: dealing with conflict {𝑎𝑛 : 𝑛 ∈ 𝑆} is a 𝜎 extension of ℱ𝑒 . management in multi-agent systems, Artificial In- telligence 165 (2005) 187–259. [5] B. Verheij, Deflog: on the logical interpretation of 6. Conclusion prima facie justified assumptions, Journal of Logic and Computation 13 (2003) 319–346. In this paper, we initiated a systematic exploration of [6] M. Caminada, N. Oren, Grounded semantics and the complexity issues inherent to infinite argumenta- infinitary argumentation frameworks, in: Proceed- tion frameworks. To pursue this direction, we employed ings of the 26th Benelux Conference on Artificial computability-theoretic techniques which are ideally Intelligence, BNAIC, 2014, pp. 25–32. suited for assessing the complexity of infinite mathemati- [7] R. Baumann, C. Spanring, Infinite argumentation cal objects. Our focus was on the credulous and skeptical frameworks: On the existence and uniqueness of acceptance of arguments, as well as the existence and extensions, in: Advances in Knowledge Represen- uniqueness of extensions, for admissible, complete, and tation, Logic Programming, and Abstract Argumen- stable semantics. We introduced and explored new se- tation: Essays Dedicated to Gerhard Brewka on the mantics that are meaningful exclusively in the infinite Occasion of his 60th Birthday, Springer, 2015, pp. setting, concerning the existence of infinite extensions 281–295. [8] P. Baroni, F. Cerutti, P. E. Dunne, M. Giacomin, Computing with infinite argumentation frame- works: The case of afras, in: Theorie and Applica- tions of Formal Argumentation: First International Workshop, TAFA 2011. Barcelona, Spain, July 16-17, 2011, Springer, 2012, pp. 197–214. [9] S. Bistarelli, F. Santini, et al., Weighted argumenta- tion., FLAP 8 (2021) 1589–1622. [10] P. E. Dunne, Coherence in finite argument systems, Artificial Intelligence 141 (2002) 187–203. [11] P. E. Dunne, The computational complexity of ideal semantics, Artificial Intelligence 173 (2009) 1559– 1591. [12] W. Dvořák, S. Woltran, Complexity of semi-stable and stage semantics in argumentation frameworks, Information Processing Letters 110 (2010) 425–430. [13] V. Brattka, P. Hertling, Handbook of computability and complexity in analysis, Springer, 2021. [14] K. V. Velupillai, Computable foundations for eco- nomics, Routledge, 2012. [15] G. Jäger, J. Rogers, Formal language theory: refin- ing the chomsky hierarchy, Philosophical Trans- actions of the Royal Society B: Biological Sciences 367 (2012) 1956–1970. [16] P. Baroni, M. Giacomin, Semantics of abstract ar- gument systems, Argumentation in artificial intel- ligence (2009) 25–44. [17] P. E. Dunne, M. Wooldridge, Complexity of ab- stract argumentation, Argumentation in artificial intelligence (2009) 85–104. [18] H. Rogers Jr, Theory of recursive functions and effective computability, MIT press, 1987. [19] S. C. Kleene, Arithmetical predicates and function quantifiers, Transactions of the American Mathe- matical Society 79 (1955) 312–340. [20] A. Kechris, Classical descriptive set theory, volume 156, Springer Science & Business Media, 2012. [21] D. Cenzer, Π01 Classes in Computability Theory, in: Studies in Logic and the Foundations of Mathemat- ics, volume 140, Elsevier, 1999, pp. 37–85.