Paper deep dive
Complexity of Grounded Semantics and Preferred Semantics in Finitary Argumentation Frameworks
Jinfan Xu, Jieting Luo
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 10/10/2026, 2:52:22 AM
Summary
This paper analyzes the computational complexity of grounded and preferred semantics in computably finitary Abstract Argumentation Frameworks (AFs). It maps five standard decision problems (credulous acceptance, skeptical acceptance, extension existence, uniqueness, and non-empty existence) across the arithmetical and analytical hierarchies. For grounded semantics, credulous and skeptical acceptance are shown to be Sigma_1^0-complete, as is non-empty existence, while existence and uniqueness are trivial. For preferred semantics, credulous acceptance is Pi_1^0-complete and non-empty existence is Sigma_2^0-complete. However, skeptical acceptance remains Pi_1^1-complete and uniqueness is Sigma_2^1-complete, demonstrating that finitarity does not fully reduce the complexity of all problems to the arithmetical hierarchy.
Entities (13)
Relation Signals (14)
Skeptical Acceptance → appliesto → Grounded Semantics
confidence 95% · For grounded semantics, credulous and skeptical acceptance are already known to be Σ10-complete.
Non-empty Existence → appliesto → Preferred Semantics
confidence 95% · NE_pref is Σ20-c.
Credulous Acceptance → appliesto → Grounded Semantics
confidence 95% · For grounded semantics, credulous and skeptical acceptance are already known to be Σ10-complete.
Skeptical Acceptance → appliesto → Preferred Semantics
confidence 95% · leaving Skep_pref in Π11
Credulous Acceptance → appliesto → Preferred Semantics
confidence 95% · For preferred semantics... Cred_pref is shown to be in Π10-c
Uniqueness → appliesto → Preferred Semantics
confidence 95% · UniPref in Σ21-c.
Credulous Acceptance → hascomplexity → Pi_1^0-complete
confidence 95% · Cred_pref is shown to be in Π10-c
Grounded Semantics → hascomplexity → Sigma_1^0-complete
confidence 95% · For grounded semantics, credulous and skeptical acceptance are already known to be Σ10-complete.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Abstract argumentation frameworks (AFs) introduced by Dung provide a formal foundation for non-monotonic reasoning in artificial intelligence. While decision problems for general infinite AFs typically reside at high levels of the analytical hierarchy ($\Sigma_1^1$ or $\Pi_1^1$), restricting the framework to be computably finitary reduces some of the complexity to the arithmetical hierarchy. In this paper, we present a complexity mapping of grounded and preferred semantics in computably finitary AFs across standard decision problems: credulous acceptance ($\Cred$), skeptical acceptance ($\Skep$), extension existence ($\Ex$), uniqueness ($\Uni$), and non-empty existence ($\NE$). For grounded semantics, credulous and skeptical acceptance are already known to be $\Sigma_1^0$-complete. We show that non-empty existence is also $\Sigma_1^0$-complete, whereas existence and uniqueness are trivial. These classifications are understood within the domain of valid computably finitary representations. For preferred semantics, using a computably finitely branching computation tree, $\Cred_{\pref}$ is shown to be in $\Pi_1^0$-c and $\NE_{\pref}$ is $\Sigma_2^0$-c. However, it is insufficient to reduce universal quantification and global uniqueness, leaving $\Skep_{\pref}$ in $\Pi_1^1$ and $\UniPref$ in $\Sigma_2^1$-c. Our results show the precise boundary where finitarity succeeds to bring reasoning down to the arithmetical hierarchy and where second-order quantification forces problems back into the analytical hierarchy.
Tags
Links
- Source: https://arxiv.org/abs/2610.12008v1
- Canonical: https://arxiv.org/abs/2610.12008v1
Trouble viewing inline? Open PDF directly →
Full Text
45,830 characters extracted from source content.
Expand or collapse full text
Complexity of Grounded Semantics and Preferred Semantics in Finitary Argumentation Frameworks Xu Jinfan Luo Jieting Affiliation: School of Philosophy, Zhejiang University Abstract Abstract argumentation frameworks (AFs) introduced by Dung provide a formal foundation for non-monotonic reasoning in artificial intelligence. While decision problems for general infinite AFs typically reside at high levels of the analytical hierarchy (Σ11 _1^1 or Π11 _1^1), restricting the framework to be computably finitary reduces some of the complexity to the arithmetical hierarchy. In this paper, we present a complexity mapping of grounded and preferred semantics in computably finitary AFs across standard decision problems: credulous acceptance (Cred), skeptical acceptance (Skep), extension existence (Exists), uniqueness (Uni), and non-empty existence (NE). For grounded semantics, credulous and skeptical acceptance are already known to be Σ10 _1^0-complete. We show that non-empty existence is also Σ10 _1^0-complete, whereas existence and uniqueness are trivial. These classifications are understood within the domain of valid computably finitary representations. For preferred semantics, using a computably finitely branching computation tree, CredCred_pref is shown to be in Π10 _1^0-c and NENE_pref is Σ20 _2^0-c. However, it is insufficient to reduce universal quantification and global uniqueness, leaving SkepSkep_pref in Π11 _1^1 and UniUni_pref in Σ21 _2^1-c. Our results show the precise boundary where finitarity succeeds to bring reasoning down to the arithmetical hierarchy and where second-order quantification forces problems back into the analytical hierarchy. Keywords: Abstract Argumentation Finitary AFs Computability Theory 1 Introduction Abstract Argumentation Frameworks (AFs), introduced by Dung [6], have become a fundamental part of formal reasoning in artificial intelligence. While the computational properties of finite AFs are well-understood, recent years have witnessed a surge of interest in infinite argumentation frameworks (IAF). Infinite AFs enable the formal modeling of domains involving infinite events, continuous temporal reasoning, or infinite debate games; however, they introduce substantial computational challenges. As shown by Andrews and San Mauro [2], standard reasoning tasks in general infinite AFs often reside at the upper levels of the analytical hierarchy (e.g., being Π11 _1^1- or Σ11 _1^1-complete), rendering them algorithmically intractable in the general case. Nevertheless, many realistic infinite scenarios satisfy a natural structural constraint known as the finitary restriction: although the total pool of arguments may be infinite, each individual argument is attacked by at most finitely many predecessors. This structural property provides a powerful graphical tool. In finitary AFs, the defense space of an argument can be modeled as a finitely branching tree. By exploiting classical logical tools, such as the ω-continuity of Dung’s characteristic operator and König’s Lemma, the computational complexity of several core semantics drops from the analytical hierarchy down to the arithmetical hierarchy. Andrews and San Mauro have already established upper and lower bounds for credulous and skeptical acceptance in computably finitary AFs [1]. In particular, grounded acceptance is Σ10 _1^0-complete within the domain of valid representations. Building on these results, this paper studies grounded and preferred semantics across five decision problems. For grounded semantics, we recall the acceptance classification and prove that non-empty existence (NEcfinNE_grd^cfin) is Σ10 _1^0-complete; existence and uniqueness are trivial. For preferred semantics, we use the correspondence between admissible sets and preferred extensions to obtain Π10 _1^0-completeness of credulous acceptance and Σ20 _2^0-completeness of non-empty existence. We also study the analytical complexity of skeptical acceptance and uniqueness under preferred semantics. 2 Computability Theoretic Background In this section, we present the necessary foundations of recursion theory and descriptive complexity used to classify decision problems on infinite structures. We assume all elements of our domain can be effectively encoded as natural numbers ω. 2.1 Numbers, Strings, and Trees To formulate our problems as subsets of ω, it is convenient to encode pairs of numbers into single numbers. For this purpose, we fix a computable bijection p:ω×ω→ωp:ω×ω→ω and adopt the standard notation ⟨x,y⟩ x,y for p(x,y)p(x,y). Furthermore, given a finite set A=x1,x2,…,xn⊆ωA=\x_1,x_2,…,x_n\ ω, its canonical index is defined as y=2x1+2x2+⋯+2xn.y=2^x_1+2^x_2+·s+2^x_n. We let DyD_y denote the finite set whose canonical index is y. By leveraging canonical indices, we can quantify over all finite subsets of an argumentation framework. We denote the set of all finite strings of natural numbers by ω<ω^<ω, and the set of all infinite strings by ω^ω. A string σ is called a prefix of τ, written as σ⪯τσ τ, if τ extends σ. If neither σ⪯τσ τ nor τ⪯στ σ holds, σ and τ are said to be incomparable. The restriction of an infinite string π∈ωπ∈ω^ω to its first n bits is denoted by π↾nπ _n. A tree is a set T⊆ω<ωT ω^<ω that is closed under prefixes. An infinite string π∈ωπ∈ω^ω is called a path through T if every finite prefix of π belongs to T (i.e., σ∈Tσ∈ T for all σ≺πσ π, or π↾n∈Tπ _n∈ T for all numbers n). We denote the set of all paths through T by [T][T]. A tree T is said to have infinite height if it contains strings of arbitrarily large finite lengths. 2.2 The Arithmetical Hierarchy: Quantifying over Numbers The arithmetical hierarchy classifies subsets of ωkω^k based on the number of alternating first-order quantifiers (∃,∀∃,∀) required to define them over a computable predicate. Let R⊆ωk+nR ω^k+n be a recursive (computable) relation. • A set S⊆ωkS ω^k is in the class Σn0 _n^0 if there exists a recursive relation R such that: S=x→∣∃y1∀y2∃y3…QynR(x→,y1,…,yn)S=\ x ∃ y_1∀ y_2∃ y_3… Qy_nR( x,y_1,…,y_n)\ where the quantifier string contains n alternating quantifiers, and Q is ∃ if n is odd and ∀ if n is even. • A set S⊆ωkS ω^k is in the class Πn0 _n^0 if its complement is in Σn0 _n^0. Formally: S=x→∣∀y1∃y2∀y3…QynR(x→,y1,…,yn)S=\ x ∀ y_1∃ y_2∀ y_3… Qy_nR( x,y_1,…,y_n)\ where Q is ∀ if n is odd and ∃ if n is even. • The class Δn0 _n^0 is defined as the intersection Σn0∩Πn0 _n^0∩ _n^0, representing properties that are structurally equivalent to both formats at level n. 2.3 The Analytical Hierarchy: Quantifying over Sets When the definition of a problem requires quantifying over all possible infinite sets or functions, the arithmetical hierarchy is no longer sufficient to classify its complexity. In these instances, we move into the analytical hierarchy. The fundamental distinction between these hierarchies lies in the domain of quantification. While the arithmetical hierarchy is restricted to quantification over individuals (first-order quantification, e.g., ∃n∈ω∃ n∈ω), the analytical hierarchy allows for quantification over subsets of individuals (second-order quantification, e.g., ∃S⊆ω∃ S ω). Definition 1 (Analytical Hierarchy) A set S⊆ωkS ω^k belongs to the class Σn1 _n^1 or Πn1 _n^1 if it can be defined by a second-order formula of the form: S=x→∣(Q1X1)(Q2X2)…(QnXn)Φ(x→,X1,…,Xn)S=\ x (Q_1X_1)(Q_2X_2)…(Q_nX_n) ( x,X_1,…,X_n)\ where: • X1,X2,…,XnX_1,X_2,…,X_n are second-order variables ranging over subsets of ω (or functions from ω to ω). • Q1,Q2,…,QnQ_1,Q_2,…,Q_n are alternating second-order quantifiers (∃1,∀1∃^1,∀^1). • Φ is an arithmetical formula containing only first-order quantifiers. A set is Σn1 _n^1 if Q1=∃1Q_1=∃^1, and it is Πn1 _n^1 if Q1=∀1Q_1=∀^1. 3 Argumentation Theoretic Background 3.1 Abstract Argumentation An argumentation framework (AF) is a pair ℱ=⟨A,R⟩F= A,R , where A is a set of arguments and R⊆A×AR A× A is a binary relation representing attacks. For a,b∈Aa,b∈ A, we say a attacks b if (a,b)∈R(a,b)∈ R. A set S⊆AS A is conflict-free if there are no a,b∈Sa,b∈ S such that (a,b)∈R(a,b)∈ R. A set S⊆AS A defends an argument a∈Aa∈ A if for every b∈Ab∈ A that attacks a, there exists some c∈Sc∈ S that attacks b. Definition 2 (Characteristic Function) The characteristic function Γℱ:2A→2A _F:2^A→ 2^A is defined as Γℱ(S)=a∈A∣S defends a _F(S)=\a∈ A S defends a\. 3.2 Argumentation Semantics In the extension-based approach to argumentation, a semantics σ associates with every AF ℱ=⟨A,R⟩F= A,R a set of extensions σ(ℱ)⊆2Aσ(F) 2^A. We follow the standard definitions introduced by Dung. Definition 3 (Admissible-based Semantics) Let ℱ=⟨A,R⟩F= A,R be an AF and S⊆AS A be a conflict-free set. • S is admissible (S∈(ℱ)S (F)) if S defends all its elements, i.e., S⊆Γℱ(S)S _F(S). • S is a complete extension (S∈(ℱ)S (F)) if it is a fixed point of the characteristic function, i.e., S=Γℱ(S)S= _F(S). • S is the grounded extension (S=(ℱ)S=grd(F)) if it is the least fixed point of Γℱ _F. • S is a preferred extension (S∈(ℱ)S (F)) if it is a maximal (w.r.t. ⊆ ) admissible set. While the existence of preferred and grounded extensions is guaranteed in any AF (including infinite ones) by Zorn’s Lemma and the Knaster-Tarski theorem respectively, the complexity of identifying these sets varies significantly depending on the graph’s topology. 3.3 Computably Finitary AFs and Computational Problems We focus on computably finitary AFs, which are infinite structures where the local interaction is effectively bounded. Definition 4 (Finitary AF) An AF ℱ=⟨A,R⟩F= A,R is finitary if for every a∈Aa∈ A, the set of its attackers (a)=b∈A∣(b,a)∈RAtt(a)=\b∈ A (b,a)∈ R\ is finite. Definition 5 (Computably Finitary AF) An argumentation framework ℱ=⟨A,R⟩F= A,R , where A is the set of arguments and R⊆A×AR A× A is the attack relation, is said to be computably finitary if it satisfies the following two conditions [1]: 1. Recursive Set of Arguments: The set A is a recursive set. Formally, a set A⊆ωA ω is recursive (or decidable) if its characteristic function χA:ω→0,1 _A:ω→\0,1\ is a total computable function, defined as: χA(n)=1if n∈A0if n∉A _A(n)= cases1&if n∈ A\\ 0&if n∉ A cases In the context of infinite argumentation, A is typically identified with the set of natural numbers ω. 2. Computable Attackers: There exists a total computable function f:A→ωf:A→ω such that for every argument a∈Aa∈ A, f(a)f(a) returns the canonical index of the finite set of its attackers, (a)=b∈A∣(b,a)∈RAtt(a)=\b∈ A (b,a)∈ R\. Following the methodology of Andrews and San Mauro [2], we analyze five fundamental decision problems for each semantics σ: 1. Credulous Acceptance (CredσCred_σ): Given ℱF and x∈Ax∈ A, is x contained in at least one S∈σ(ℱ)S∈σ(F)? 2. Skeptical Acceptance (SkepσSkep_σ): Given ℱF and x∈Ax∈ A, is x contained in every S∈σ(ℱ)S∈σ(F)? 3. Existence (ExistsσExists_σ): Does there exist a set S∈σ(ℱ)S∈σ(F)? (Note: for grounded/preferred, this is trivial). 4. Non-empty Existence (NEσNE_σ): Does there exist a non-empty set S∈σ(ℱ)S∈σ(F)? 5. Uniqueness (UniσUni_σ): Is there exactly one set S∈σ(ℱ)S∈σ(F)? For the computably finitary representation, fix a standard enumeration (φe)e∈ω( _e)_e∈ω of the partial computable functions and let Tot=e∈ω∣φe is total.Tot=\e∈ω _e is total\. For each e∈Tote , let ℱeF_e have argument set A=ax∣x∈ωA=\a_x x∈ω\, with the finite attacker set of axa_x encoded by Dφe(x)D_ _e(x). Here a set of numerical codes is identified with the corresponding set of arguments, so that ℱe(ax)=ay∣y∈Dφe(x).Att_F_e(a_x)=\a_y y∈ D_ _e(x)\. Thus, a valid index provides an effective finite list of all attackers of each argument. Complexity classifications below are understood within TotTot (or Tot×ωTot×ω for acceptance): the upper-bound formulas need only agree with the decision problems on valid indices, and hardness reductions must always produce valid indices. They do not include the complexity of testing whether an arbitrary index belongs to TotTot. We code the decision problems as follows: 1. Credσcfin:=⟨e,n⟩∣e∈Tot,(∃S∈σ(ℱe))(an∈S)Cred_σ^cfin:=\ e,n e ,\ (∃ S∈σ(F_e))(a_n∈ S)\; 2. Skepσcfin:=⟨e,n⟩∣e∈Tot,(∀S∈σ(ℱe))(an∈S)Skep_σ^cfin:=\ e,n e ,\ (∀ S∈σ(F_e))(a_n∈ S)\; 3. Existsσcfin:=e∈Tot∣σ(ℱe)≠∅Exists_σ^cfin:=\e σ(F_e)≠ \; 4. NEσcfin:=e∈Tot∣(∃S∈σ(ℱe))(S≠∅)NE_σ^cfin:=\e (∃ S∈σ(F_e))(S≠ )\; 5. Uniσcfin:=e∈Tot∣|σ(ℱe)|=1Uni_σ^cfin:=\e |σ(F_e)|=1\. For grounded semantics, σ(ℱe)σ(F_e) in these definitions is the singleton (ℱe)\grd(F_e)\. We omit the superscript cfincfin when the representation is clear from context. We also write Credσ(ℱe)Cred_σ(F_e) and Skepσ(ℱe)Skep_σ(F_e) for the corresponding sets of accepted arguments. 4 Grounded Semantics We begin with grounded semantics. The grounded extension G is the least fixed point of Γℱ(S)=a∈A∣S defends a _F(S)=\a∈ A S defends a\. Lemma 1 (ω-continuity by Dung [6]) If ℱF is finitary, Γℱ _F is ω-continuous, i.e., Γ(⋃Si)=⋃Γ(Si) ( S_i)= (S_i). Consequently, G=⋃n<ωΓn(∅)G= _n<ω ^n( ). Proposition 1 Let ℱ=⟨A,R⟩F= A,R be a computably finitary argumentation framework. For any argument x∈Ax∈ A and any finite step n∈ωn∈ω, the predicate x∈Γℱn(∅)x∈ _F^n( ) is decidable (Δ10 _1^0). Proof We proceed by induction on n. • Base Case (n=0n=0): By definition, Γℱ0(∅)=∅ _F^0( )= . The predicate x∈∅x∈ always evaluates to false, which is trivially decidable. • Inductive Step: Assume that for a given n∈ωn∈ω, the predicate y∈Γℱn(∅)y∈ _F^n( ) is decidable for all y∈Ay∈ A. The next iteration of the characteristic operator is defined as: Γℱn+1(∅)=x∈A∣∀y∈A((y,x)∈R→∃z∈Γℱn(∅)((z,y)∈R)) _F^n+1( )=\x∈ A ∀ y∈ A((y,x)∈ R→∃ z∈ _F^n( )((z,y)∈ R))\ Since ℱF is computably finitary, the set (x)Att(x) is finite and its canonical index can be effectively computed. Thus, the universal quantification over y reduces to a finite check over the explicit members of (x)Att(x). For each individual attacker y∈(x)y (x), we must check if y is counter-attacked by some element currently in Γℱn(∅) _F^n( ). This is equivalent to verifying whether (y)∩Γℱn(∅)≠∅Att(y)∩ _F^n( )≠ . Again, because ℱF is computably finitary, (y)Att(y) is a finite, computable set. By the inductive hypothesis, membership in Γℱn(∅) _F^n( ) is decidable. Therefore, testing whether the finite set (y)Att(y) contains at least one element belonging to Γℱn(∅) _F^n( ) takes finite time and is decidable. Thus, the entire predicate x∈Γℱn+1(∅)x∈ _F^n+1( ) is decidable (Δ10 _1^0). By mathematical induction, the predicate x∈Γℱn(∅)x∈ _F^n( ) is decidable for any n∈ωn∈ω. 4.1 Credulous and Skeptical Acceptance Andrews and San Mauro have already established upper and lower bounds for credulous and skeptical acceptance in computably finitary AFs. Their construction for complete semantics directly uses the grounded extension to encode computably enumerable sets, yielding Σ10 _1^0-completeness of grounded acceptance within Tot×ωTot×ω [1]. Since the grounded extension is unique, credulous and skeptical acceptance coincide. The upper bound can also be seen from ω-continuity and Proposition 1: ax∈(ℱe)⟺∃n∈ω(ax∈Γℱen(∅)).a_x (F_e) ∃ n∈ω\; (a_x∈ _F_e^n( ) ). On valid indices, the finite-stage predicate is decidable uniformly in e,x,ne,x,n. Equivalently, a finite computation witnessing membership at some stage can be effectively verified. Hence CredcfinCred_grd^cfin and SkepcfinSkep_grd^cfin are Σ10 _1^0-complete within Tot×ωTot×ω. 4.2 Non-empty Existence Proposition 2 (Non-empty existence under grounded semantics) Under the computably finitary representation, NEcfinNE_grd^cfin is Σ10 _1^0-complete within TotTot. Proof First observe that, for every argumentation framework ℱF, (ℱ)≠∅⟺Γℱ(∅)≠∅⟺∃a∈A(ℱ(a)=∅).grd(F)≠ _F( )≠ ∃ a∈ A\; (Att_F(a)= ). Indeed, Γℱ(∅) _F( ) consists precisely of the unattacked arguments and is contained in the grounded extension. If there are no unattacked arguments, then Γℱ(∅)=∅ _F( )= , so ∅ is already a fixed point and (ℱ)=∅grd(F)= . For e∈Tote , the attacker set of axa_x is encoded by Dφe(x)D_ _e(x), and therefore e∈NEcfin⟺∃x∈ω(Dφe(x)=∅).e _grd^cfin ∃ x∈ω\; (D_ _e(x)= ). Given a valid index e and an argument code x, we can compute this finite set and decide whether it is empty. More explicitly, the condition can be expressed as the existence of x and a finite computation in which φe(x) _e(x) halts with output 00, the canonical index of the empty set. This gives a Σ10 _1^0 definition on the valid representation domain. For Σ10 _1^0-hardness, we give a many-one reduction from the halting set K=e∣φe(e) eventually halts.K=\e _e(e) eventually halts\. Given e, construct a framework ℱf(e)F_f(e) with argument set an∣n∈ω\a_n n∈ω\. For each s∈ωs∈ω, set (a2s)=∅,if φe(e) halts within the first s steps,a2s+1,otherwise,Att(a_2s)= cases ,&if _e(e) halts within the first s steps,\\ \a_2s+1\,&otherwise, cases and set (a2s+1)=a2s+1Att(a_2s+1)=\a_2s+1\. Given e and s, simulating φe(e) _e(e) for the finite number of steps s suffices to compute these attacker sets. Their canonical indices are respectively 00 or 22s+12^2s+1 for a2sa_2s, and 22s+12^2s+1 for a2s+1a_2s+1. The construction is uniform, so the s-m-n theorem yields a total computable index map f, with f(e)∈Totf(e) for every e. If e∈Ke∈ K and φe(e) _e(e) halts within t steps, then a2sa_2s is unattacked for every s≥ts≥ t, and hence (ℱf(e))≠∅grd(F_f(e))≠ . If e∉Ke∉ K, every a2sa_2s is attacked by a2s+1a_2s+1, and every a2s+1a_2s+1 attacks itself. Thus there are no unattacked arguments and (ℱf(e))=∅grd(F_f(e))= . Consequently, e∈K⟺f(e)∈NEcfin.e∈ K f(e) _grd^cfin. Therefore NEcfinNE_grd^cfin is Σ10 _1^0-complete within TotTot. 4.3 Existence and Uniqueness Since every argumentation framework has exactly one grounded extension, both ExistscfinExists_grd^cfin and UnicfinUni_grd^cfin are trivial on the valid representation domain: every e∈Tote is a positive instance. 5 Preferred Semantics We now turn to preferred semantics. A preferred extension is a maximal (w.r.t. ⊆ ) admissible set. Because every chain of admissible sets has an upper bound, by Zorn’s Lemma, a preferred extension always exists, and any argument contained in an admissible set is also contained in at least one preferred extension. Lemma 2 Let ℱ=⟨A,R⟩F= A,R be an argumentation framework. For any admissible set S0∈(ℱ)S_0 (F), there exists a preferred extension E∈(ℱ)E (F) such that S0⊆ES_0 E. Proof Let ℳ=S∈(ℱ)∣S0⊆SM=\S (F) S_0 S\ be the collection of all admissible sets containing S0S_0. The poset ⟨ℳ,⊆⟩ , is partially ordered by set inclusion. We show that every totally ordered chain in ℳM has an upper bound in ℳM. Let ⊆ℳC be an arbitrary totally ordered chain, and consider its union U=⋃X∈XU= _X X. Clearly, U is an upper bound of every X∈X under set inclusion. To establish that U∈ℳU , we must prove that U is an admissible set (i.e., conflict-free and self-defending): • Conflict-freeness of U: Suppose for contradiction that U is not conflict-free. Then, there exist a,b∈Ua,b∈ U such that (a,b)∈R(a,b)∈ R. By definition of the union, there exist Xa,Xb∈X_a,X_b such that a∈Xaa∈ X_a and b∈Xbb∈ X_b. Since C is a totally ordered chain, we must have either Xa⊆XbX_a X_b or Xb⊆XaX_b X_a. Assume Xa⊆XbX_a X_b, which implies a,b∈Xba,b∈ X_b. However, since Xb∈⊆ℳX_b , XbX_b is admissible and must be conflict-free, contradicting (a,b)∈R(a,b)∈ R. Thus, U is conflict-free. • Self-defense of U: Let a∈Ua∈ U be an arbitrary argument, and suppose there exists y∈Ay∈ A such that (y,a)∈R(y,a)∈ R. Since a∈Ua∈ U, there exists some Xa∈X_a such that a∈Xaa∈ X_a. Since XaX_a is admissible, it defends a, meaning there exists z∈Xaz∈ X_a such that (z,y)∈R(z,y)∈ R. Since Xa⊆UX_a U, we have z∈Uz∈ U. Thus, U defends all its elements. Since U is both conflict-free and self-defending, U∈(ℱ)U (F). Furthermore, since S0⊆XS_0 X for all X∈X , we have S0⊆US_0 U, which guarantees U∈ℳU . By Zorn’s Lemma, ⟨ℳ,⊆⟩ , contains at least one maximal element E. By definition, E is an admissible set containing S0S_0. The maximality of E in ℳM ensures that E∈(ℱ)E (F). For proving the upper bound complexity of decision problems SkepSkep_pref and UniUni_pref, we will utilize the technique from [1, 1] to build a bridge between paths in a computably finitary tree and admissible sets, as well as König’s Lemma. Definition 6 Any given string σ∈ω<ωσ∈ω^<ω defines two subsets of arguments in ℱF: • Inσ=D∪aj:σ(2j)=1∪ak:(∃j)(σ(2j+1)=k+1)∪ai:(∃j)(σ(2j+1)>0∧gj+=ai)In_σ=D∪\a_j:σ(2j)=1\∪\a_k:(∃ j)(σ(2j+1)=k+1)\∪\a_i:(∃ j)(σ(2j+1)>0 g_j^+=a_i)\; • Outσ=E∪aj:σ(2j)=0∪ai:(∃j)(σ(2j+1)>i+1∧ai↣gj−)∪ai:(∃j)(σ(2j+1)=0∧gj+=ai)Out_σ=E∪\a_j:σ(2j)=0\∪\a_i:(∃ j)(σ(2j+1)>i+1 a_i g_j^-)\∪\a_i:(∃ j)(σ(2j+1)=0 g_j^+=a_i)\. We define TℱT_F as the set of σ such that • InσIn_σ does not contain elements ai↣aja_i a_j with i,j<|σ|i,j<|σ|; • Inσ∩Outσ∩ai:i<|σ|=∅In_σ _σ∩\a_i:i<|σ|\= ; • If 2j<|σ|2j<|σ|, then σ(2j)∈0,1σ(2j)∈\0,1\; • If 2j+1<|σ|2j+1<|σ| and σ(2j+1)=k+1σ(2j+1)=k+1, then ak↣gj−a_k g_j^-. Note that if ℱF is computable, then TℱT_F is computable, and if ℱF is computably finitary, then TℱT_F is computably finitely branching. Theorem 5.1 Let ℱ=⟨A,R⟩F= A,R be a computably finitary argumentation framework and x∈Ax∈ A. There exists a non-empty admissible set S∈(ℱ)S (F) with x∈Sx∈ S if and only if the computation tree TℱT_F contains an infinite path π∈[Tℱ]π∈[T_F]. Proof See [1] for a complete proof. Lemma 3 (König’s Lemma) Let T be an infinite tree. If every node in T has a finite number of children (i.e., T is finitely branching), then T contains at least one infinite path. 5.1 Credulous Acceptance Lemma 4 Let ℱ=⟨A,R⟩F= A,R be an argumentation framework. An argument x∈Ax∈ A is credulously accepted under the preferred semantics iff it is credulously accepted under the admissible semantics. That is, Cred(ℱ)=Cred(ℱ)Cred_pref(F)=Cred_adm(F) Proof We establish the identity by bidirectional inclusion: • (⊆ ) Let x∈Cred(ℱ)x _pref(F). There exists a preferred extension E∈(ℱ)E (F) containing x. Since every preferred extension is admissible by definition (E∈(ℱ)E (F)), E serves as a witnessing admissible set. Thus, x∈Cred(ℱ)x _adm(F). • (⊇ ) Let x∈Cred(ℱ)x _adm(F). There exists an admissible set S0∈(ℱ)S_0 (F) containing x. By Lemma 2, there exists a preferred extension E∈(ℱ)E (F) such that S0⊆ES_0 E. Since x∈S0x∈ S_0, we have x∈Ex∈ E, which implies x∈Cred(ℱ)x _pref(F). Theorem 5.2 In a computably finitary AF ℱF, Cred(ℱ)Cred_pref(F) is Π10 _1^0-complete. Proof In Dung’s abstract argumentation frameworks, By Lemma 4, for any argument x∈Ax∈ A, x belongs to some preferred extension E∈(ℱ)E (F) if x belongs to some admissible set S∈(ℱ)S (F). Thus, we have Cred(ℱ)=Cred(ℱ)Cred_pref(F)=Cred_adm(F). By the established results [2], while CredCred_adm is Σ11 _1^1-complete for general infinite frameworks, introducing the computably finitary restriction reduces its complexity to Π10 _1^0. Due to the extensional identity Cred(ℱ)=Cred(ℱ)Cred_pref(F)=Cred_adm(F), the Π10 _1^0-completeness of CredCred_pref follows immediately. 5.2 Non-empty Existence Lemma 5 Let ℱ=⟨A,R⟩F= A,R be an argumentation framework. There exists a non-empty preferred extension E∈(ℱ)E (F) iff there exists a non-empty admissible set S∈(ℱ)S (F). Proof We prove the equivalence in both directions: (⟹)( ) Assume there exists a non-empty preferred extension E∈(ℱ)E (F). Since every preferred extension is an admissible set, E∈(ℱ)E (F). Because E≠∅E≠ , it immediately serves as a witnessing non-empty admissible set. (⟸)( ) Assume there exists a non-empty admissible set S0∈(ℱ)S_0 (F). By Lemma 2, there exists a preferred extension E∈(ℱ)E (F) such that S0⊆ES_0 E. Since S0≠∅S_0≠ , it follows immediately that E≠∅E≠ . Theorem 5.3 In a computably finitary AF ℱF, the non-empty existence problem under preferred semantics (NENE_pref) is Σ20 _2^0-complete. Proof By Lemma 5, an argumentation framework ℱF contains a non-empty preferred extension if and only if it contains a non-empty admissible set. This equivalence immediately establishes an equivalence between the decision problems of non-empty existence under preferred and admissible semantics. That is,NE=NENE_pref=NE_adm. Since the non-empty existence problem under admissible semantics (NENE_adm) has already been established as Σ20 _2^0-complete in computably finitary AFs, it follows directly that NENE_pref is also Σ20 _2^0-c. 5.3 Skeptical Acceptance So far all problems remain arithmetical; skeptical acceptance is the turning point. Under the preferred semantics, an argument is skeptically accepted if and only if it belongs to every preferred extension (defined as maximal admissible sets under set inclusion). Lemma 6 A path P∈[Tℱ]P∈[T_F] corresponds to a preferred extension iff for every n∈ωn∈ω, and for every child node τ of P↾nP n in TℱT_F: If τ≠P↾(n+1), then the subtree rooted at τ contains no infinite path.If τ≠ P (n+1), then the subtree rooted at $τ$ contains no infinite path. Proof Let P,T∈[Tℱ]P,T∈[T_F] be two infinite paths corresponding to admissible sets S and S′S , respectively. The set inclusion S⊂S′S⊂ S corresponds to P(2n)=1⟹T(2n)=1P(2n)=1 T(2n)=1, which also corresponds to P and T share a prefix. Thus, the maximality of an admissible set S (i.e., S is a preferred extension) can be characterized by TℱT_F as a path where there is no divergent infinite branch. Theorem 5.4 In a computably finitary argumentation framework ℱF, the skeptical acceptance problem under preferred semantics (SkepSkep_pref) is in Π11 _1^1. Proof An argument x∈Ax∈ A fails to be skeptically accepted with respect to preferred semantics (x∉Skep(ℱ)x _pref(F)) if and only if there exists a preferred extension E∈(ℱ)E (F) such that x∉Ex∉ E. The admissible sets correspond to the set of infinite paths [Tℱ][T_F] through a computation tree TℱT^F. Using Lemma 6, the non-skeptical acceptance problem x∉Skep(ℱ)x _pref(F) is equivalent to the assertion: There exists an infinite path P∈[Tℱ]P∈[T_F] such that its corresponding admissible set excludes argument x, and for any node σ=P↾nσ=P n, every child τ≠P↾(n+1)τ≠ P (n+1) roots a subtree (Tℱ)τ(T_F)_τ that eventually dies out (i.e., contains no infinite paths). The condition that a sub-tree contains no infinite paths is a Π10 _1^0 property by König’s Lemma. However, asserting the existence of an infinite path P with a maximality condition that evaluates infinitely many subtrees introduces an existential quantification over infinite paths (∃P∈[Tℱ]∃ P∈[T_F]), placing the non-skeptical acceptance problem in the Σ11 _1^1 level of the analytical hierarchy. Taking the complement, the skeptical acceptance problem x∈Skep(ℱ)x _pref(F) is expressible as a Π11 _1^1 formula. 5.4 The Uniqueness Problem Lemma 7 Let ℱ=⟨A,R⟩F= A,R be an argumentation framework. ℱF has a unique preferred extension iff there exists E∈(ℱ)E (F), for all S∈(ℱ)S (F), S⊆ES E. Proof Proof is straightforward by the definition of preferred extensions. Theorem 5.5 In a computably finitary argumentation framework ℱF, the uniqueness problem for preferred extensions (UniUni_pref) is in Σ21 _2^1. Proof Let TℱT_F be the computable, finitely branching tree whose infinite paths [Tℱ][T_F] correspond to all admissible sets in ℱF. Encoding argument membership(i.e., let S be an admissible set and P be its corresponding path, argument an∈S⇔P(2n)=1a_n∈ S P(2n)=1), a framework ℱF belongs to UniUni_pref if and only if there exists a witness path P∈[Tℱ]P∈[T_F] such that every path T∈[Tℱ]T∈[T_F] is contained in P. Formally: ℱ∈Uni⇔∃P∈[Tℱ]∀T∈[Tℱ]∀n∈ω(T(2n)=1⟹P(2n)=1)F _pref ∃ P∈[T_F]\;∀ T∈[T_F]\;∀ n∈ω\; (T(2n)=1 P(2n)=1 ) Analyzing the quantifier complexity of this formalization: 1. The inner relation ∀n∈ω(T(2n)=1⟹P(2n)=1)∀ n∈ω\, (T(2n)=1 P(2n)=1 ) evaluates a universal quantifier over the natural numbers on a decidable relation, forming a Π10 _1^0 predicate. 2. Universal quantification over all infinite paths T∈[Tℱ]T∈[T_F] adds a universal second-order quantifier. 3. Existential quantification over the witness path P∈[Tℱ]P∈[T_F] adds an existential second-order quantifier. Consequently, the quantifier prefix takes the form ∃P∀T∀n∃ P\,∀ T\,∀ n, which places the uniqueness problem UniUni_pref precisely in the Σ21 _2^1 tier of the analytical hierarchy. Theorem 5.6 (Σ21 _2^1-Hardness of Uniqueness) In computably finitary argumentation frameworks, the uniqueness problem for preferred extensions UniUni_pref is Σ21 _2^1-hard. Proof We reduce a canonical Σ21 _2^1-complete set ℰE to UniUni_pref. Let e∈ℰe be represented as: e∈ℰ⇔∃P∈2ω∀T∈2ω∃n∈ωR(e,P↾n,T↾n)e ∃ P∈ 2^ω\,∀ T∈ 2^ω\,∃ n∈ω\;R(e,P n,T n) where R is a computable relation over finite sequences. We construct an infinite argumentation framework ℱe=⟨A,⟩F_e= A,Att corresponding to e. The set of arguments A is defined as: A=pσ,eσP∣σ∈2<ω∪tτ,eτT∣τ∈2<ω∪UA=\p_σ,e^P_σ σ∈ 2^<ω\∪\t_τ,e^T_τ τ∈ 2^<ω\∪\U\ where pσp_σ and tτt_τ represent finite path choices in the candidate tree P and challenger tree T respectively, eσPe^P_σ and eτTe^T_τ act as enforcer arguments, and U is the global dominator argument. The attack relation Att consists of the following pairs for all σ,τ∈2<ωσ,τ∈ 2^<ω: 1. pσ⋅0↔pσ⋅1p_σ· 0 p_σ· 1 and tτ⋅0↔tτ⋅1t_τ· 0 t_τ· 1. 2. eσP→pσe^P_σ→ p_σ with children counter-attacking pσ⋅0→eσPp_σ· 0→ e^P_σ and pσ⋅1→eσPp_σ· 1→ e^P_σ. Similarly, eτT→tτe^T_τ→ t_τ with tτ⋅0→eτTt_τ· 0→ e^T_τ and tτ⋅1→eτTt_τ· 1→ e^T_τ. 3. For |σ|=|τ|=n|σ|=|τ|=n, if R(e,σ,τ)R(e,σ,τ) holds (is True), then pσ→tτp_σ→ t_τ. 4. For all τ∈2<ωτ∈ 2^<ω, tτ→Ut_τ→ U. Conversely, U attacks all non-root tree arguments: U→pσ,eσP,tτ,eτTU→ p_σ,e^P_σ,t_τ,e^T_τ for all σ≠∅,τ≠∅σ≠ ,τ≠ . eσPe^P_σpσp_σpσ⋅0p_σ· 0pσ⋅1p_σ· 1pσ⋅0→eσPp_σ· 0→ e^P_σ P-Tree (Witness)eτTe^T_τtτt_τtτ⋅0t_τ· 0tτ⋅1t_τ· 1tτ⋅1→eτTt_τ· 1→ e^T_τ T-Tree (Challenger)UUR(e,σ,τ)=TrueR(e,σ,τ)=Truetτ→Ut_τ→ U We show that e∈ℰ⇔ℱe∈Unie _e _pref. (⇒ ) Suppose e∈ℰe . Then there exists a witness path P∗∈2ωP^*∈ 2^ω such that for every challenger path T∈2ωT∈ 2^ω, there is an integer nTn_T where R(e,P∗↾nT,T↾nT)R(e,P^* n_T,T n_T) holds. Let SP∗=pP∗↾k∣k∈ωS_P^*=\p_P^* k k∈ω\. For any path T, the attack pP∗↾nT→tT↾nTp_P^* n_T→ t_T n_T defeats argument tT↾nTt_T n_T. Consequently, tT↾nTt_T n_T fails to defend against eT↾nT−1Te^T_T n_T-1, which in turn defeats tT↾nT−1t_T n_T-1. By induction, this collapse propagates upward to the root, destroying all admissible sets along T. Since every challenger node tτt_τ is either directly defeated by SP∗S_P^* or falls to a cascading collapse, no tτt_τ survives to attack U. Thus, SP∗S_P^* defends U, making U admissible. The set E∗=SP∗∪UE^*=S_P^*∪\U\ forms a preferred extension. Since U∈E∗U∈ E^* defeats all alternative candidate paths in the P-tree and T-tree, E∗E^* is the unique preferred extension of ℱeF_e. (⇐ ) Suppose e∉ℰe . Then for every path P∈2ωP∈ 2^ω, there exists a counter-path TP∈2ωT_P∈ 2^ω such that R(e,P↾n,TP↾n)R(e,P n,T_P n) is False for all n∈ωn∈ω. For any candidate path P, the argument set SP=pP↾k∣k∈ωS_P=\p_P k k∈ω\ fails to launch any attack against TPT_P. Thus, the nodes tTP↾n∣n∈ω\t_T_P n n∈ω\ remain undefeated and self-defending against their enforcers. Since these nodes continuously attack U (tTP↾n→Ut_T_P n→ U), U can never be defended and cannot belong to any admissible set. Without U to eliminate competing choices, each distinct path P∈2ωP∈ 2^ω paired with its counter-path TPT_P yields a distinct preferred extension: EP=pP↾k∣k∈ω∪tTP↾n∣n∈ωE_P=\p_P k k∈ω\∪\t_T_P n n∈ω\ Because there are uncountably many choices for P, ℱeF_e possesses uncountably many preferred extensions. Hence, ℱe∉UniF_e _pref. This completes the reduction and proves that UniUni_pref is Σ21 _2^1-hard. Theorem 5.7 UniUni_pref is Σ21 _2^1-complete. Proof Hardness follows from Theorem 5.6 (reduction from the canonical Σ21 _2^1-complete problem). For membership, ℱ∈UniF _pref if and only if there exists a preferred extension E1E_1 such that all preferred extensions E2E_2 equal E1E_1. Since being a preferred extension is a Π11 _1^1 property, as in Theorem 5.5, the predicate ∃1E1(Pref(E1)∧∀1E2(Pref(E2)→E1=E2))∃^1E_1(Pref(E_1) ∀^1E_2(Pref(E_2)→ E_1=E_2)) contains two alternating second-order quantifiers (∃1∀1∃^1∀^1), placing UniUni_pref in Σ21 _2^1. 6 Related Work The formal study of computability and expressiveness in infinite argumentation was pioneered by Dung [6], who established fundamental properties such as the ω-continuity of the characteristic function in finitary frameworks. Baumann and Spanring [5]established the theoretical baseline for unrestricted AFs (UAFs), examining whether fundamental semantic properties hold when argument sets are infinite. A key structural challenge in UAFs is the emergence of infinitely ascending Strongly Connected Component chains, which break the classical SCC-recursive schema [4]. To address these, Andrews and San Mauro [3] proposed repairs using compactness techniques and ordinal-indexing. The computational landscape transitions significantly when moving from finite graphs to infinite structures: Firstly, in Unrestricted IAFs, complexity shifts to the analytical hierarchy. Decidability for primary semantics (admissible, stable, complete) inhabits Σ11 _1^1-completeness or Π11 _1^1-completeness [2]. Then, under finitary restrictions, the characteristic operator becomes ω-continuous, causing a complexity collapse into the arithmetical hierarchy [1]. Andrews and San Mauro further showed that stable extensions can code arbitrary Π10 _1^0 classes, proving that IAFs are computationally universal for tree-search problems [2]. 7 Conclusions In this paper, we establish a computational classification for computably finitary AFs: • Grounded Semantics: Credulous and skeptical acceptance coincide and are Σ10 _1^0-complete within Tot×ωTot×ω, as established by Andrews and San Mauro [1]. Proposition 2 shows that non-empty existence is Σ10 _1^0-complete within TotTot. Existence and uniqueness are trivial on valid indices. • Preferred Semantics: Some problems like CredCred_pref (Π10 _1^0-c) and NENE_pref (Σ20 _2^0-c) remain arithmetical. In contrast, others escape the arithmetical hierarchy: universal quantification over infinite extensions pushes SkepSkep_pref to Π11 _1^1, while ruling out competing infinite branches renders UniUni_pref Σ21 _2^1-c. Several directions remain open. While we showed Skep∈Π11Skep_pref∈ _1^1, its exact completeness level within the analytical hierarchy is still undetermined. Finally, it remains to investigate whether similar collapses occur for other semantics. References [1] U. Andrews and L. S. Mauro (2025) Complexity in finitary argumentation (extended version). arXiv preprint arXiv:2508.16986. Cited by: §1, §4.1, §5, §6, 1st item, Definition 5, Proof. [2] U. Andrews and L. San Mauro (2024) On computational problems for infinite argumentation frameworks: the complexity of finding acceptable extensions. Cited by: §1, §3.3, §6, Proof. [3] U. Andrews and L. San Mauro (2025) On the complexity of the grounded semantics for infinite argumentation frameworks. In Proceedings Twentieth Conference on Theoretical Aspects of Rationality and Knowledge, Düsseldorf, Germany, July 14-16, 2025, A. Bjorndahl (Ed.), Electronic Proceedings in Theoretical Computer Science, Vol. 437, p. 112–127. External Links: Document Cited by: §6. [4] R. Baumann and C. Spanring (2015) Infinite argumentation frameworks: on the existence and uniqueness of extensions. In Advances in Knowledge Representation, Logic Programming, and Abstract Argumentation: Essays Dedicated to Gerhard Brewka on the Occasion of his 60th Birthday, p. 281–295. Cited by: §6. [5] R. Baumann and C. Spanring (2017) A study of unrestricted abstract argumentation frameworks. In International Joint Conference on Artificial Intelligence, External Links: Link Cited by: §6. [6] P. M. Dung (1995) On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artificial intelligence 77 (2), p. 321–357. Cited by: §1, §6, Lemma 1.