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 dificulty of computing an extension in a given semantics and show that these problems give rise to a rich class of complexities.
NMR 2024, 22nd International Workshop on Nonmonotonic Reasoning November 2-4, 2024, Hanoi, Vietnam ⋆A condensed version of this article was submitted to SAFA 2024 and an expanded version was submitted to FCR 2024. * Corresponding author. † These authors contributed equally. $ andrews@math.wisc.edu (U. Andrews); luca.sanmauro@gmail.com (L. San Mauro) https://math.wisc.edu/~andrews (U. Andrews); https://www.lucasanmauro.com/ (L. San Mauro) © 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License
Attribution 4.0 International (CC BY 4.0).
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
extento 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 diferent 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., [
The present paper, we argue, provides compelling ev- are well-understood in the finite setting: admissible, comidence of the benefits of viewing infinite AFs through plete, and stable semantics (abbreviated by ad, stb, co, recomputability 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(ℱ ) if ↣̸ , for all , ∈ ). Then, for ∈ complexity. cf(ℱ ),
Section 2 briefly reviews the main semantic concepts from argumentation theory that are relevant to this paper, along with the fundamental computational problems associated with them. In Section 3, we introduce the key 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 wellinvolves suitably encoding trees into AFs. Our main re- known computational problems related to : sults are collected in Tables 2 and 3. • ∈ ad(ℱ ) if is self-defending (i.e., ⊆
ℱ ()); • ∈ co(ℱ ) if is a fixed point of (i.e., =
ℱ ()); • ∈ stb(ℱ ), if attacks all arguments outside of it (i.e., + = ℱ ∖ ).
some key concepts of Dung-style argumentation theory,
focusing on the semantics notions considered in this
paper and the fundamental computational problems
associated with them (the surveys [
An argumentation framework (AF) ℱ is a pair (ℱ , ℱ ) consisting of a set ℱ of arguments and an attack relation ℱ ⊆ ℱ × ℱ . If some argument attacks some argument , we may write ↣ instead of (, ) ∈ ℱ . Collections of arguments ⊆ ℱ are called extensions. For an extension , the symbols + and − denote, respectively, the arguments that attacks and the arguments that attack : + = { : (∃ ∈ )( ↣ − = { : (∃ ∈ )( ↣ )}; )}. 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 (for credulous acceptance) is the decision problem whose accepting instances are the pairs (ℱ , ) so that ∈ for some ∈ (ℱ ); • Skept (for skeptical acceptance) is the decision problem whose accepting instances are the pairs (ℱ , ) so that ∈ for all ∈ (ℱ ); • Exist is the decision problem whose accepting
instances are the AFs ℱ so that (ℱ ) ̸= ∅; • NE is the decision problem whose instances are
the AFs ℱ so that (ℱ ) ∖ {∅} ̸= ∅; • Uni is the decision problem whose accepting
instances are the AFs ℱ so that | (ℱ )| = 1.
In formal argumentation theory, evaluating the
computational complexity of the aforementioned problems for
various semantics has been a noteworthy research thread
for more than 20 years[
Computational problems for finite AFs. -c denotes complete- in computability theory requiring that paths be infinite.
In this section, we introduce computable AFs and we
revisit the computational problems of the last section
through the lens of computability theory. We aim at
conveying the main ideas without delving into too many
technical details. A more formal and comprehensive
exposition of the fundamentals of computability theory can
be found, e.g., in the textbooks [
of natural numbers by . Since there is no risk of ambiguity, we simply refer to the elements of as numbers. The symbol denotes the set of all functions from to .
of as infinite sequences of numbers (where the + 1th bit of
∈ will be the output of the function on input ). We denote by 0∞ the infinite sequence consisting of only 0’s (or, equivalently, the constant function to 0).
The restriction of an infinite sequence ∈ to its first bits is denoted by ↾ .
We use standard notation and terminology about strings: The set of all finite strings of numbers is denoted by <. The symbol denotes the empty string. The concatenation of strings ,
is denoted by ⌢ . The ⌢ length of a string is denoted by | |. If there is so that = , we say that is a prefix
of and we write ⪯ . Similarly, if ∈ and = ↾ for some , we write ≺ . a set ⊆ it will be convenient to encode pairs of numbers into single numbers. The pairing function does this. Fix : common habit of denoting (, ) by ⟨, ⟩. × → to be a computable bijection. We adopt the
The encodings discussed in Section 4 heavily rely on the dificulty of calculating paths through trees. As is common in computability theory, we say that a tree is
< closed under prefixes. We picture trees growing upwards, with ⌢ to the left of ⌢, whenever < . A path ∈ through a tree ⊆ < is an infinite sequence so that ↾ ∈ , for all numbers . The set of paths through a tree is denoted by [ ]. is well-founded if [ ] = ∅ and otherwise is illfounded. Note that we follow the standard terminology 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 of strings := { } ∪ {,
⌢1 : (∀ < | |)( () = 0)} }. is an ill-founded tree with [ ] = {0∞}.
If contains strings of arbitrary length, then has infinite height . Note that there are trees of infinite height which are well-founded, e.g., = { } ∪ {⌢ : | | ≤ 3.2. Computable argumentation
frameworks A basic problem that one encounters when attempting to calibrate the algorithmic complexity of infinite AFs is that of describing infinite objects in a finitary way. Computability theory ofers a wide range of tools designed for this endeavour. Here, we will concentrate on AFs that are computably presentable, in the sense that there are Turing machines (or, equivalently, modern computer programs) that, in finitely many steps, decide whether a given pair of arguments belongs to the attack relation. partial computable functions from to {0, 1}.
Notation. Let (Φ)∈ be a uniform enumeration of all Definition 3.1.
A number is a computable index for an AF ℱ = (ℱ , ℱ ) with ℱ = { : ∈ } so that Φ(⟨, ⟩) = {︃1 0 if ↣ otherwise.
An AF ℱ is computable, if it has a computable index ∈ .
We use the notation ℱ to refer to the AF with computable index (note that every computable AF possesses stb co NP-c
NP-c ness for the class .
Skept coNP-c NP-c NP-c In order to formulate our problems as subsets of , infinitely many computable indices.). Remark 3.2. The collection of computable indices for AFs just defined is noncomputable (in particular, any index for a non-total computable function Φ cannot be a computable index for an argumentation framework). There are alternative indexings that circumvent this issue; yet, adopting another indexing would not alter the complexity of the computational problems we analyze, though it would make the proofs slightly more cumbersome. Hence, we opt for the simplicity of Definition 3.1.
We also introduce new semantics which make sense only in the infinite setting. This is motivated by the idea that, given an infinite AF, we might hope for our accepted sets to give us infinitely much information.
1. ∈ infad(ℱ ) if and only if ∈ ad(ℱ ) and is
infinite; 2. ∈ infco(ℱ ) if and only if ∈ co(ℱ ) and is
infinite; 3. ∈ infstb(ℱ ) if and only if ∈ stb(ℱ ) and is
infinite.
only infinite extensions, we consider that a given infinite AF may contain a single argument so that attacks every other argument, and every other argument attacks . We imagine that is a statement of extreme solipsism denying the truth of any other statement. While {} is a stable extension, it represents a negligible fraction of arguments, and we may prefer not to accept it. In an infinite AF, any finite set is as negligible as {}, so we may prefer to accept only infinite extensions.
problems of Definition 3.3 are those of the Σ11 and Π11 sets.
The Σ11 sets are formally defined as those subsets of that are definable in the language of second-order arithmetic using a single second-order existential quantifier ranging over subsets of followed by number quantifiers and the ifrst order functions and relations (+, · , <, 0, 1, ∈); for more details, see [18, §16]. Π11 sets are the complements of Σ11 sets.
Proposition 3.4. Cred∞, Exist∞, and NE∞ are Σ11, for ∈ {ad, stb, co, infad, infstb, infco}.
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 defcomplexity 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 sufices to see that the condition ∈ (ℱ) can be denaturally represented as subsets of , which are suitable ifned 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 quanti1. Cred∞ := {⟨, ⟩ : (∃ ∈ (ℱ))( ∈ )}; ifers 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 quantiifers over numbers.
1 Proposition 3.5. Skept∞ is Π1, whenever is in {ad, stb, co, infad, in1fstb, infco}. Furthermore, for ∈ {ad, co}, Uni∞ is Π1.
Proof. The definition of Skept∞ in Definition 3.3 uses a single universal set-quantifier followed by only number quantifiers in the definition of (ℱ).
For ∈ {ad, co}, ∈ Uni∞ if and only if there are not two diferent extensions (as there is always at least one extension). This is defined by the negation of the following formula: (∃1∃2)(∃ ∈ 1∖2 ∧ 1 ∈ (ℱ) ∧ 2 ∈ (ℱ)).
Note that ∃1∃2 can be replaced by a single existential quantifier by encoding the pair (1, 2) as a single set {⟨1, ⟩ : ∈ 1} ∪ {⟨2, ⟩ : ∈ 2}. This shows that Uni∞ is the complement of a Σ11 set, thus is Π1.
1 Remark 3.6. The above argument does not sufice to show that Unis∞tb is also Π11, since some AFs have no stable extension. The most obvious definition says there exists one stable extension and there does not exist two, which gives a definition which is a conjunction of a Σ11 and a Π11 condition, i.e., a so-called d-Σ11 definition. This is analogous to the fact that in the finite case Unistb is DPcomplete. Similarly, the argument above does not show that Uni∞ is Π11 for ∈ {infad, infstb, infco}. Yet, it is true that Uni∞ is Π11 for ∈ {stb, infad, infstb, infco} as we show below in Corollaries 5.5,5.10, and 5.14.
We note that knowing that a problem is Σ11 does not necessarily mean the problem is complicated. This only gives an upper-bound for its complexity. Sometimes, a simpler definition is achievable. As an example, we consider Credcf := {⟨, ⟩ : (∃ ∈ cf(ℱ))( ∈ )}.
Theorem 3.7 (Kleene [
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 sufices to check whether is non-self-defeating, i.e., the subtle part of this example. ̸↣ , which is equivalent to checking the computable fact that Φ(⟨, ⟩) = 0. In contrast, we will show that for the computational problems associated to the admissible, stable, and complete semantics, the use of the quantifier ranging over all sets cannot be avoided.
theorem by Kleene which ofers a natural way of representing Σ11 sets:
Theorem 3.7 along with Definition 3.8 suggest a natural approach for gauging the complexity of the computational problems of Definition 3.3. Namely, given another Σ11 (or Π11) set , we translate the question asking whether ∈ to the question of if the tree is ill-founded (resp., well-founded), and then we need to computably find an instance of our computational problem which should be accepted if and only if is ill-founded (resp., well-founded). This involves coding a tree, or more precisely, the collection of paths through a tree into the extensions in an argumentation framework. 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 deciding which computable trees in < are ill-founded (or well-founded) is as hard as any other Σ11 (resp., Π1) 1 problem.
Theorem 3.7 gives a reason to consider the Σ11 sets as the natural infinite analogs of the NP problems. Namely, given an ill-founded computable tree and a sequence which is a path through , it is relatively simple to check that ∈ [ ] (it requires checking infinitely many simple facts: ↾ ∈ , for each ), but finding a sequence ∈ [ ]—or even knowing whether there exists a sequence ∈ [ ]—is a far harder problem.
of the computational problems described in Definition
Definition 3.8. Let Γ be a complexity class (e.g., Γ ∈ {Σ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 Γ, then it is Γ-complete.
Proposition 3.9. It follows from Theorem 3.7 that the 1 set of indices for ill-founded computable trees is a Σ1complete set. Similarly, the set of indices for well-founded computable trees is a Π11-complete set.
useful below to examine Uni∞.
Theorem 3.10 ([20, Theorem 18.11]). The set UB of in1 dices for computable trees with exactly one path is a Π1complete set.
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
Remark 3.12. As noted before, the Σ11 sets are natural analogs in the infinitary setting of the NP sets, and the Π11 sets are the natural analogs of the coNP sets. With the exception of Skeptc∞o and Unis∞tb , Table 2 follows this translation from Table 1 for the first three rows. These two results mark surprising diferences in the infinite setting.
The trivial entries are due to the fact that ∅ is always an admissible extension and the grounded extension is always a complete extension. 3.3. Spectra of extensions
ity of the problem of finding a extension in a given AF ℱ .
Definition 3.13. For each ∈ and semantics , let Spec¬∅(ℱ) be the set of Turing degrees of non-empty sets ⊆ so that { : ∈ } is a extension in ℱ.
The notion Spec¬∅(ℱ) exactly captures the dificulty of computing a non-empty extension in ℱ. We will be relating the problem of computing a extension in ℱ to the problem of finding a path through a particular tree. So, we define the analogous notion of the spectrum of a tree.
Definition 3.14. Given any computable tree , we let Spec( ) be set of Turing degrees of paths ∈ [ ].
Table 3 collects our results on spectra of extensions. stb co infad infstb infco
Cred∞ Π11-c 4.4,3.5 Π11-c * , 3.5 For any computable tree , there is a computable argumen- pose that is admissible. Observe that and cannot ad stb co infad infstb infco
Spec¬∅ Exactly Spec( ) Exactly Spec( ) Any Spec( ) Exactly Spec( ) Exactly Spec( )
Any Spec( ) of ℱ is computable and consists of { :
∈ }∪{ : Theorem 4.2. The following hold: tation framework ℱ so that Spec( ) = Spec¬∅(ℱ). When ∈ {ad, stb, infad, infstb}, the converse also holds. Namely, for every , there is a computable tree so that Spec¬∅(ℱ) = per bound for the complete or infinite complete cases.
Spec( ). We do not know how to attain a corresponding up
Given a tree ⊆ <, we will define an argumentation framework ℱ = ( , ). The set of arguments all and only the following edges: ∈ } ∪ {}. The attack relation of ℱ contains For all ∈ , 1. ↣ 2. ↣ 3. ↣ 4. ↣ 5. ↣ 6. ↣ ; ; . , if | | = | | + 1; , if | | = | | + 1 and ̸⪯ ; for every ∈ ; Notation. For ∈ [ ], let be the set { : ≺ }.
Lemma 4.1. A non-empty extension of ℱ is stable if is complete if is admissible if is exactly for some ∈ [ ].
Proof. Stable always implies complete, which always implies admissible. It is straightforward to check that is stable for any
∈ [ ], so we need only show that any non-empty admissible extension is exactly some . Supbe in since these are self-defeating. So some since is non-empty. Note that since ↣
, we must have ∈ . Next, observe that if
∈ , then there must be some so that ⌢ ∈ : this is because some element of must defend from and such an element must be an with | | = | | + 1. But it must have ≺ as otherwise would attack . It follows that
∈ contains for some cannot properly contain , so = .
∈ [ ]. Since is stable,
We are now in a position to obtain hardness results for the computational problems described in Definition 3.3.
1. for
∈ {ad, stb, co, infad, infstb, infco}, NE∞ is Σ11-hard; 2. for
hard; 3. for is Σ11-hard.
1 ∈ {stb, infad, infstb, infco}, Exist∞ is Σ1∈ {ad, stb, co, infad, infstb, infco}, Cred∞ Σ11-hard.
Proof. 1. Let ∈ Σ11 and let ( )∈ be a tree
1 sequence for , as given by Theorem 3.7. To show Σ1hardness, we need to produce a computable function so that ∈ if and only if () ∈ NE∞. We let
() be a computable index for ℱ . Then Lemma 4.1 shows that ∈ if and only if is ill-founded if and only if ℱ has a non-empty extension for each
∈ {ad, stb, co, infad, infstb, infco}.
2. For each of these , the empty set is not a extension, so Exist∞ = NE∞, which we showed above is 0
1 10 11 10 0 10 0 11 1 11 1 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 [ ] = ∅. { , 0, 1, 10, 11}, the right-side is the to NE∞ by sending to ℱ . Note that ℱ has a non- (0) = 0 if and only if ′ has only one path (see the 3. In the proof of 1. above, we reduced a given Σ11 set
for ℱ shows that Cred∞ is Σ11-hard. empty extension if and only if is in some extension.
Thus sending to ⟨, ⟩ where is a computable index Uni∞ is Π11-hard.
Theorem 4.3. For ∈ {ad, stb, co, infad, infstb, infco}, Proof.
We first consider let (
∖ )∈ be a tree-sequence for its complement.
Consider the sequence of AFs (ℱ ∅ is an admissible extension in any AF and since every
)∈. Note that ∖ ∈ {ad, co}. Let ∈ Π11 and argument in ℱ extension. Thus, ℱ ∖ ∖ is attacked, ∅ is also a complete
has a unique extension if the Π11-hardness of Uni∞. which shows that Unia∞d and Unic∞o are Π11-hard. and only if
∖ is well founded if and only if ∈ ,
For the other , ∅ is not a extension. We use Theorem 3.10 to show Π1-hardness. Let be any Π11 set. Then
1 we get from Remark 3.11 a sequence of trees ′ so that 0∞ ∈ [′] for each , and { : ′ has only one path} is Π11-hard. It follows from Lemma 4.1 that this holds if and only if ℱ ′ has a unique extension, which shows Theorem 4.4. For any Skept∞ is Π11-hard.
∈ {stb, infstb, infco, infad}, Proof. Let be a Π11 set. Then we get from Remark 3.11 a sequence of trees ′ so that 0∞ and { : ′ has only one path} is Π11-hard. Then note that ⟨, 0⟩ ∈ Skept∞ where is a computable index for := ℱ′ if and only if ′ only has paths
with This shows the Π11-hardness of Skept∞. definition of ′ in Remark 3.11) if and only if ∈ .
Theorem 4.5. For
∈ {ad, stb, co, infad, infstb, infco} AF ℱ so that Spec¬∅(ℱ) = Spec( ). and for any computable tree , there exists a computable Proof. Observe that for the AF ℱ = ℱ , it follows from Lemma 4.1 that the non-empty extensions are all infinite and are in the same Turing degrees as the paths through . 5. Trees coding extensions in (ℱ )
Spec¬∅ for
∈ {ad, stb, infad, infstb} as well as giving upper bounds for the complexity of Uni∞ for any ∈ {stb, infad, infstb, infco}. We do this by describing how to computably encode the collection of extensions in (ℱ ) into the set of paths through a tree.
Given a computable argumentation framework ℱ
, we will describe a computable tree ℱ so that the paths of ℱ encode the non-empty admissible extensions in ℱ We begin with an intuitive description of how a path . ∈ [′] for each , through the tree ℱ will encode an admissible extension
, and we give the formal definition of ℱ below.
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 enumeration 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 Speca¬d∅(ℱ) = Spec( ). is least so that ∈ and ↣ . Proof. It follows immediately from Theorem 5.2 that
Let ℱ = (ℱ , ℱ ) be a computable AF. Let ()∈ be a computable sequence of all elements of ℱ . If = Speca¬d∅(ℱ) = Spec( ℱ ). (, ), we denote by − and by + . We now define the tree ℱ .
Corollary 5.4. For every computable AF ℱ, there exists a computable tree ̂︀ so that Speci¬nf∅ad(ℱ) = Spec(̂︀ ).
Definition 5.1. Any given string ∈ < defines two subsets of arguments in ℱ : • Out = { : < (0)}∪{ : > 0∧ (2) = 0}∪{ : (∃)( (2+1) = 0∧+ = )}∪{ : (∃)( (2 + 1) > + 1 ∧ ↣ − )}.
Proof. Given a non-empty admissible extension of ℱ , we define the corresponding path in ℱ as follows. Let (0) be the least element of . For > 0, let (2) = 1 if ∈ and (2) = 0 otherwise. Let (2 + 1) be 0 if + ∈/ and be + 1 where is least so that ∈ and ↣ − otherwise. It is straightforward to check that ∈ [ ℱ ].
Given a path through ℱ , first note that whenever there is some ≺ so that ∈ In , then (2) = 1.
This is because whenever ⪯ , then In ⊆ In . Then since := ↾ max(| |,2+1) is in ℱ , we cannot have (2) = 0 since ∈ In . Thus (2) = (2) = 1. It follows that ⋃︀ ≺ In = { : (2) = 1}. The same argument shows that ⋃︀ ≺ Out = { : (2) = 0}.
Let = { : (2) = 1}.
Note that is conflict-free, since if , ∈ then there is some long enough ≺ so that , ∈ In .
1 Corollary 5.5. Unii∞nfad is Π1.
Proof. is in Uniinfad if and only if the tree ̂︀ in Corollary
1 5.4 has a unique path. By Theorem 3.10, this is a Π1 condition.
extensions by making () = 0 if ∈ and otherwise making () be + 1 where is least so that ∈ and ↣ .
Definition 5.6. Any given string ∈ < defines two subsets of arguments in ℱ : • In = { : () = 0} ∪ { ()− 1 : < | | ∧ () > 0}; • Out = { : < | | ∧ () > 0} ∪ { : (∃) () > + 1 ∧ ↣ )}.
We define ℱ as the set of so that • In is conflict-free; • In ∩ Out = ∅ • If < | | and () = + 1, then ↣ .
Theorem 5.7. Let ℱ be a (computable) argumentation framework. Then the stable extensions of ℱ are in (computable) bijection with the paths in ℱ .
Out . It follows that ⋃︀ = { : () = 0}. is least so that ∈ and ↣ straightforward to check that Proof. Given a stable extension of ℱ corresponding path in ℱ as follows. For each , let () be 0 if ∈ and let () be + 1 where , we define the otherwise. It is This is because whenever ⪯ , then In ⊆
Given a path through ℱ , first note that whenever there is some ≺ so that ∈ In , then () = 0. In . Then since () ̸= 0 since ∈ In and therefore cannot be in = ↾ max(| |,+1) is on ℱ , we cannot have ∈ [ is conflict-free. Next observe that for any , either ∈ .
In particular, if () = 0, then ∈ and otherwise ()− 1 ∈ and ()− 1 ↣ .
Finally, note that both the map from to and from to are computable if ℱ is computable and are inverses computable tree so that Specs¬tb∅(ℱ) = Spec( ). Corollary 5.8. For any computable AF ℱ there exists a Proof. This follows directly from Theorem 5.7 along with the fact that ∅ is never a stable extension.
Corollary 5.9. For any computable AF ℱ there exists a computable tree so that Speci¬nf∅stb(ℱ) = Spec( ). Proof. We add layers of branching to the tree as in Corollary 5.4 so that, e.g., (2) = means that is the th least number so that ∈ . This produces a tree ̂ ︂ℱ so that the paths are in computable bijection with the infinite stable extensions of ℱ .
1 Corollary 5.10. Unis∞tb and Unii∞nfstb are Π1.
Proof. As the paths through ℱ are in bijection with the stable extensions, ∈ Unis∞tb if and only if ℱ has a are in bijection with the infinite stable extensions in unique path. As the paths through ̂︀ ℱ (see Corollary 5.9) By Theorem 3.10, these are both Π11 conditions. we have ∈ Uniinfstb if and only if ̂︀ ℱ has a unique path.
Given an argumentation framework ℱ
, we can similarly and + as follows: also their attacked sets +. plete extensions. In order to ensure that ℱ () ⊆ will need the paths in ℱ to not only code sets but
, we
Given an extension , we will let ∈ ℱ encode construct a tree ℱ so that paths through ℱ code com- (2) = 0} and = { : (2 + 1) ̸= 0}. We note that ↣
. • (2) = 0 if ∈ and otherwise (2) = + 1 where is least so ∈/ + and ↣
. • (2 + 1) = 0 if ∈/ + and otherwise (2 +
1) = + 1 where is least so ∈ and
Note that (2) explains why is either in or it is not in ℱ (), i.e., ℱ () ⊆ verifies that the elements which says are in + are in
, while (2 + 1) simply fact in +.
Formally, we define ℱ as follows: Definition 5.11. subsets of arguments in ℱ :
Any given string ∈ < defines four • In = { : (2) = 0
} ∪ { : (∃)( (2 + 1) = + 1
} 1) > + 1 ∧ ↣
)} • Out = { : (2) ̸= 0
} ∪ { : (∃) (2 + (2 + 1) = 0
} )} ∪ { : (2 + 1) ̸= 0
} • InSplus
= { : (∃)( (2) > + 1 ∧ ↣ • OutSplus = { : (∃) (2) = + 1
} ∪ { : We define ℱ as the set of so that 1. In is conflict-free; 2. In ∩ Out = ∅; 3. InSplus ∩ OutSplus = ∅; 4. If (2) = + 1, then ↣
; 5. If (2 + 1) = + 1, then ↣
; then ↣̸
; then ↣̸ ℱ ()). 6. For , < | |, if ∈ OutSplus and ∈ In 7. For , < | |, if ∈ OutSplus and ∈ In ,
(i.e., does not contradict ⊆ ℱ, jection with the set of paths [ ℱ ].
Theorem 5.12. The complete extensions of ℱ are in biProof. Let be any complete extension. We can define from as described at the beginning of this section. It is straightforward to verify that each condition (1-7) of
↾ for each .
Given a path ∈ [ ℱ ], we can define sets = { : = ⋃︀
≺ InSplus . when ⪯ , In ⊆ the previous theorems, that = ⋃︀
In . It follows from this fact, as in ≺ In . Similarly,
Next we see that = +. If ∈ , then (2+1) ̸= 0 and by condition 5, we have (2+1)− 1 attacks . But then (2+1)− 1 ∈ In ↾ 2+2 , so (2+1)− 1 ∈ . Thus ⊆ 6 for all of length > 2 + 1 ensures that there is no +. On the other hand if ∈/ , then condition ∈ so ↣ . Thus + ⊆ .
Finally, we verify that is complete. is clearly conΠ11 sets. that satisfy a given semantics . The computational problems we examined were found to be maximally complex, properly belonging to the complexity classes of Σ11 and lfict free by Condition 1. Condition 7 ensures that any
∈ is also in ℱ (), since if ∈/ , then ↣̸ To see that ℱ () ⊆ , note that any ∈/ has
. condition 4. Thus ∈/ ℱ (). () ̸= 0 and ()− 1 ∈/ + and ()− 1 ↣
by Remark 5.13. The map from paths plete extensions ⊆
ℱ is computable, but to compute
∈ ℱ we need both and +. Thus, we are able to
say that for any computable AF ℱ, the set of Turing
degrees of pairs (, +) where is a complete
extension is always Spec( ) for a computable tree , but note
plexity of infinite AFs remains open. First, we shall fill the
gaps that we left behind (such as proving the Π11-hardness
for Skeptc∞o ). Next, we aim at investigating whether the
computational problems considered in this paper become
more tractable if we restrict to special classes of AFs, such
receives finitely many attacks only [
Specc¬o∅ or Speci¬nf∅co.
1 Corollary 5.14. Unii∞nfco is Π1. that this is a Π11 condition.
Proof. We can alter the tree ℱ as in Corollary 5.4 to get a new tree ̂︀ so that the paths through ̂︀ are in bijection with the infinite complete extensions. Then ∈ Unii∞nfco if and only if ̂︀ has a unique path. Theorem 3.10 shows Corollary 5.15. Fix ∈ {ad, stb, co, infad, infstb, infco} and suppose that ℱ has only countably many non-empty extensions. Then there is a hyperarithmetical set so that { : ∈ } is a extension of ℱ.
Proof. If
∈ {ad, stb, infad, infstb}, let be a tree so that Spec¬∅(ℱ) = Spec( ). If
∈ {, infco}, let be a tree so that the set of Turing degrees of pairs (, +) of extensions is exactly Spec( ). Then is a computable tree with countably many paths. By a classic result of Kreisel [21, Theorem 3.9], has a hyperarithmetical path, which corresponds to a hyperarithmetical so that { : ∈ } is a extension of ℱ.
In this paper, we initiated a systematic exploration of the complexity issues inherent to infinite argumentation frameworks. To pursue this direction, we employed computability-theoretic techniques which are ideally suited for assessing the complexity of infinite mathematical objects. Our focus was on the credulous and skeptical acceptance of arguments, as well as the existence and uniqueness of extensions, for admissible, complete, and stable semantics. We introduced and explored new semantics that are meaningful exclusively in the infinite setting, concerning the existence of infinite extensions
281–295.