=Paper=
{{Paper
|id=Vol-3835/paper1
|storemode=property
|title=On Computational Problems for Infinite Argumentation Frameworks: The Complexity of Finding Acceptable Extensions
|pdfUrl=https://ceur-ws.org/Vol-3835/paper1.pdf
|volume=Vol-3835
|authors=Uri Andrews,Luca San Mauro
|dblpUrl=https://dblp.org/rec/conf/nmr/AndrewsM24
}}
==On Computational Problems for Infinite Argumentation Frameworks: The Complexity of Finding Acceptable Extensions==
https://ceur-ws.org/Vol-3835/paper1.pdf
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.