---
title: "Quantitative Reasoning and Structural Complexity for Claim-Centric Argumentation"
authors:
  - "Johannes K. Fichte"
  - "Markus Hecher"
  - "Yasir Mahmood"
  - "Arne Meier"
doi: "10.24963/ijcai.2023/358"
url: "https://ijcai.org/proceedings/2023/358"
pdf: "https://ijcai.org/proceedings/2023/0358.pdf"
venue: "Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence"
year: 2023
pages: "3212-3220"
track: "Main Track"
keywords:
  - "Knowledge Representation and Reasoning: KRR: Computational complexity of reasoning"
  - "Knowledge Representation and Reasoning: KRR: Argumentation"
---

# Quantitative Reasoning and Structural Complexity for Claim-Centric Argumentation

Johannes K. Fichte, Markus Hecher, Yasir Mahmood, Arne Meier

*Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence*, pages 3212-3220. DOI: [10.24963/ijcai.2023/358](https://doi.org/10.24963/ijcai.2023/358)

## Abstract

Argumentation is a well-established formalism for nonmonotonic reasoning and a vibrant area of research in AI. Claim-augmented argumentation frameworks (CAFs) have been introduced to deploy a conclusion-oriented perspective. CAFs expand argumentation frameworks by an additional step which involves retaining claims for an accepted set of arguments. We introduce a novel concept of a justification status for claims, a quantitative measure of extensions supporting a particular claim. The well-studied problems of credulous and skeptical reasoning can then be seen as simply the two endpoints of the spectrum when considered as a justification level of a claim. Furthermore, we explore the parameterized complexity of various reasoning problems for CAFs, including the quantitative reasoning for claim assertions. We begin by presenting a suitable graph representation that includes arguments and their associated claims. Our analysis includes the parameter treewidth, and we present decomposition-guided reductions between reasoning problems in CAF and the validity problem for QBF.

## Full text

## 1 Introduction

Argumentation is a formalism for nonmonotonic reasoning [Atkinson et al., 2017; Rago et al., 2018; Baroni et al., 2018] and a crucial aspect of communication in our everyday life. The theory of argumentation deals with conflicting information by generating and comparing arguments. Moreover, different directions of argumentation have been perused with applications in artificial intelligence [Amgoud and Prade, 2009; Maher, 2016; Rago et al., 2018].

Dung's framework [Dung, 1995] models arguments as abstract entities where the internal structure of an argument is hidden. In this setting, an argumentation framework (AF) is presented by a directed graph where nodes are arguments and arcs depict the attack relationship between arguments. The semantics of AFs is described in terms of sets of arguments that can be simultaneously accepted with respect to a given framework. These sets of arguments are then called extensions of a framework. The credulous (skeptical) reasoning problems for AF ask whether an argument belongs to some (every) extension of a framework under the given semantics. Dung's framework is nowadays acknowledged as the core reasoning mechanism for argumentation, even though it hides all the details of how an argument is constructed. Moreover, AFs do not answer the consequence once a set of arguments has been accepted under a given semantics. To answer this question, it is desirable to explore the structure of an argument. An argument consists of a claim and a support for this claim, e.g., the logic-based approach [Besnard and Hunter, 2008]). In this direction, Dung's framework can be expanded by reinterpreting the set of accepted arguments in terms of their claims.

Claim-augmented argumentation (CAF) introduced by Dvor´ak and Woltran (2020) expands AFs. A CAF extends an AF by assigning a claim to each argument. The semantics for CAFs is defined in terms of the set of claims corresponding to the accepted arguments in an AF. Furthermore, for specific semantics requiring subset maximality, one can either take maximal sets of accepted arguments and then retrieve their claims or already consider maximal sets in terms of accepted claims, for other ideas, see [Dvor´ak et al., 2020]. This leads to two variants of semantics: inherited and claim-based.

The computational complexity of claim-augmented argumentation has been studied for different problems under inherited semantics [Dvor´ak and Woltran, 2020] and claim-based semantics [Dvor´ak et al., 2021]. The main complexity theoretic aspects of CAF include that the verification problem has a higher complexity in many cases than its AF-counterpart. Furthermore, Dvor´ak and Woltran (2020) explored the complexity of reasoning problems for specific sub-classes of frameworks and provided fixed-parameter tractability results. Regarding the parameter treewidth, the authors considered the underlying AF as a graph representation, with the associated claims being irrelevant. Moreover, they also explored another graph representation, namely the incidence graph but only for a subclass of the framework (known as the well-formed CAFs). In this work, we focus on admissible, stable, preferred, and complete semantics and thereby explore the complexity of reasoning problems in CAF under the parameter treewidth. We suitably model claims of an argument to appear in the representation.

A level of justification for claims. In this work, we explore another dimension for the accepted claims, namely the level of justification for a claim and a set of claims, respectively. The concept is based on the fact that contradictory arguments can still agree on their claim(s). So, a claim can be accepted irrespective of which argument for this claim is in the extension.

Figure 1: Claim-centric argumentation framework for Example 2.

![Image](https://ijcai.org/proceedings/2023/fulltext/358/image_000000_4fc62a969807cbf103e8c3d317a2ab969541d0f0f59dd126a6847f3c05426e91.png)

Example 1. Let Ai = (ϕi, c) be arguments for the claim c with different supports, support for claim c is the minimal consistent set ϕ s.t. ϕ |= c): ϕ1 := (x ∧ y) ∧ (¬x ∨ c) and ϕ2 := (¬x ∧ z) ∧ (¬z ∨ c). So, A1 and A2 are mutually inconsistent, attack each other, although both entail claim c.

Credulous reasoning talks about one extension that covers the given claims while skeptical reasoning requires that every extension covers them. These two problems can thus be seen as the diametral scenarios on the reasoning yardstick. However, the extreme case of skeptical reasoning is almost never applicable and credulous reasoning oftentimes does not give any information about preferences. Indeed, a level of justification can be obtained by utilizing quantitative measures on extensions supporting particular claims. This can then be used to implement preferences among claims. Consequently, more subtle reasoning modes are required providing further support for claim acceptance in diverse situations and real-world scenarios.

Example 2. Consider an upcoming election with two candidates A and B (see Fig. 1) where participants are seen as arguments. Arguments w, x, y (resp., z) support candidate A (B) while some arguments also attack those favoring the opponent. For instance, the support of x could be in favor of COVID preventions, while the support of z might entail that the pandemic is over. Furthermore, the support of w could assert that the people should be self-responsible. Arguments w, x are conflicting but both support candidate A (election programs are not always consistent). The admissible extensions of this framework include ∅, {w}, {x}, {z}, {w, y}, {w, z} and the corresponding sets of claims include ∅, {A}, {A}, {B}, {A}, {A,B}. Each candidate is credulously accepted and no candidate is skeptically accepted. Nevertheless, A has higher preference than B as witnessed by the number of extensions with claim A.

Clearly, a more fine-grained, justification-based reasoning is particularly relevant for CAFs. In the end, reasoning should not solely depend on the arguments or motivations favoring claims, but on the actual outcomes (or claims) themselves.

In general, reasoning problems in argumentation frameworks are often of high worst-case complexity [Dunne and Bench-Capon, 2002; Dvoˇr´ak and Woltran, 2010; Dvoˇr´ak, 2012]. To circumvent resulting intractabilities, the toolkit of parameterized complexity has been successfully utilized [Dvoˇr´ak et al., 2012; Fichte et al., 2019; Lampis et al., 2018]. One of the most generally applicable and well-studied structural invariances is the parameter treewidth [Robertson and Seymour, 1986]. Indeed, particularly for argumentation, there has been a long line of theoretical research focussing on how to exploit treewidth [Brochenin et al., 2018; Charwat et al., 2015; Alviano, 2018; Atserias et al., 2011;

![Image](https://ijcai.org/proceedings/2023/fulltext/358/image_000001_38a980924533ac21d45f7f0f7d9897633ed94d1418a229407830746df0eb4bbd.png)

#cnt

Figure 2: Probabilities prob of a framework (see Def. 8) are more finegrained than the classical reasoning modes credulous and skeptical reasoning, which we can easily simulate by counting the number of extensions (#cnt).

prob ≥ 1

prob ∈ [0, 1]

Bacchus et al., 2003]. There are also several works on practical evaluations, e.g., [Dvor´ak et al., 2022; Eiter et al., 2021]. Especially for counting, treewidth established itself as the state-of-the-art [Lagniez et al., 2021; Fichte et al., 2021a].

It is well known that there exists a connection between treewidth and quantified Boolean formulas (QBF) [Pan and Vardi, 2006; Fichte et al., 2020] which is a generic framework in the area of computational complexity [Wrathall, 1976]. In the last decade, research on QBF has provided efficient problem solving techniques resulting in powerful QBF-solvers [Shukla et al., 2019]. The demand of QBFconstructions vastly increases [Shaik and van de Pol, 2022; Jung et al., 2022; Hossain and Laroussinie, 2021] that is why we utilize this target formalism for designing first encodings for CAFs. Accordingly, this allows us to establish new complexity results for CAFs parameterized by treewidth, which we render tight under reasonable complexity assumptions.

Contributions. In more details, we establish the following.

1. We introduce quantitative reasoning that allows finegrained modes between credulous and skeptical reasoning (see Fig. 2). We show why this is particularly useful for CAFs. Our quantitative reasoning approach is also motivated by its "qualitative"-counterpart, namely the statement justifications, which has also been explored (see the related work section of our paper).
2. We present a novel graph structure for CAF that allows a suitable depiction of claims. Structuring these constructions, yields a treewidth-aware reduction from reasoning problems on CAFs to validity of QBFs. Table 1 gives an overview of the results.
3. Utilizing these treewidth-aware encodings, we establish tight runtime bounds for treewidth that cannot be improved under reasonable complexity assumptions.

Related Work. Probabilistic argumentation [Hunter and Thimm, 2017; Fazzinga et al., 2015; Alfano et al., 2020] focuses on weighting arguments with probabilities. This is orthogonal to our setting. Our focus is on the (conditional) probability of an event, similar to the one in Bayesian world. This term is sometimes also called plausibility. Fichte et al. [2022a] studied this topic for answer set programming. One could easily combine these two settings and get probabilistic quantitative reasoning. The ranking-based semantics [Bonzon et al., 2018] focuses on what are called preferences. The known research on the justification status of arguments [Wu and Caminada, 2010; Baroni et al., 2016; Baroni and Riveret, 2019] explores the different levels of acceptance or rejection of arguments. The goal is achieved via the labelling semantics for argumentation frameworks. Furthermore, Baroni et al. (2016) also emphasized statement justification as a topic of independent interest. Nevertheless, their approach explores the status of an argument (or statement) in different extensions, that is, what are the different acceptance labels of an argument. Moreover, the authors explicitly rule out the role played by the cardinality of a label-set for arguments. In this work, our interest is mainly (as the name suggests) the quantitative aspect of the claim justification. The subtle difference between the justification reasoning for arguments versus for claims was noticed by Prakken and Vreeswijk (2002, Example 25) and also discussed recently by Sanjay Modgil (2018, Def. 2.18). Decomposition guided reductions have been studied for abstract argumentation [Fichte et al., 2021b].

Table 1: Overview of results for a given CAF CF = (A,R, cl) where k ∈ {tw(GCF ), tw(GeCF )}. The polynomial factor · poly(|A|) has been omitted due to space reasons. Prefixes have the following meaning: "i-" refers to inherited semantics, #i-cσ asks to count credulous extensions, and i-vσ asks if S ∈ σc(CF), for a given set S of claims. #cntσ (CF,D) asks to count extensions covering D. "▲" / "▼" refers to the established upper / lower bound. "∗": For #cntσ on GCF , |D| is assumed constant.

| Graph   | Prob.                      | σ ∈ - {stab, adm, comp}                                                              | σ ∈ - {pref}                                                                              | σ ∈ - Ref.        |
|---------|----------------------------|--------------------------------------------------------------------------------------|-------------------------------------------------------------------------------------------|-------------------|
| GCF     | #cntσ∗ i-sσ i-cσ #i-cσ i-σ | ▲ 2O(k) ,▼ 2o(k) ▲ 2O(k) ,▼ 2o(k) ▲ 2O(k) ,▼ 2o(k) ▲ 2O(k) ,▼ 2o(k) ▲ 2O(k) ,▼ 2o(k) | ▲ 22O(k) ,▼ 22o(k) ▲ 22O(k) ,▼ 22o(k) ▲ 2O(k) ,▼ 2o(k) ▲ 22O(k) ,▼ 2o(k) ▲ 2O(k) ,▼ 2o(k) | 12/13 15 15 15 16 |
| G eCF   | #cntσ i-vσ                 | ▲ 2O(k) ,▼ 2o(k) ▲ 2O(k) ,▼ 2o(k)                                                    | ▲ 22O(k) ,▼ 22o(k) ▲ 22O(k) ,▼ 22o(k)                                                     | 24/26 28          |

## 2 Preliminaries

We assume familiarity with computational complexity [Pippenger, 1997], graph theory [Bondy and Murty, 2008], and Boolean logic [Biere et al., 2021].

Quantified Boolean Formulas. Let ℓ be a positive integer, which we call (quantifier) rank later, and ⊤ and ⊥ be the constant always evaluating to 1 and 0, respectively. For a Boolean formula F, we abbreviate by var(F) the variables occurring in F and write F(X1, . . . ,Xl) to indicate that X1, . . . , Xl ⊆ var(F). A quantified Boolean formula ϕ (in prenex normal form), qBf for short, is an expression of the form ϕ = Q1X1.Q2X2. · · · QℓXℓ.F(X1, . . . , Xℓ), where for 1 ≤ i ≤ ℓ, we have Qi ∈ {∀, ∃} and Qi ̸= Qi+1, the Xi are disjoint, non-empty sets of Boolean variables, and F is a Boolean formula. We let matrix(ϕ) := F and we say that ϕ is closed if var(matrix(F)) = ⋃i∈ℓ Xi. We evaluate ϕ by ∃x.ϕ ≡ ϕ[x ↦→ 1] ∨ ϕ[x ↦→ 0] and ∀x.ϕ ≡ ϕ[x ↦→ 1]∧ϕ[x ↦→ 0] for a variable x. W.l.o.g. we assume that matrix(ϕ) = ψCNF ∧ψDNF, where ψCNF is in CNF (disjunction of conjunctions of literals) and ψDNF is in DNF (conjunction of disjunctions of literals). Then, depending on Qℓ, either ψCNF or ψCNF is optional, more precisely, ψCNF might be ⊤, if Qℓ = ∀, and ψDNF is allowed to be ⊤, otherwise. The problem ℓ-QBF asks, given a closed qBf ϕ = ∃X1.ϕ′ of rank ℓ, whether ϕ ≡ 1 holds. The problem #ℓ-QBF asks, given a closed qBf ∃X1.ϕ of rank ℓ, to count assignments α to X1 such that ϕ[α] ≡ 1. For brevity, we sometimes omit ℓ.

<!-- formula-not-decoded -->

Tree Decompositions and Treewidth. For a rooted (directed) tree T = (N, A) with root root(T) and a node t ∈ N, we let children(t) be the set of all nodes t′ , which have an edge (t, t′ ) ∈ A. Let G = (V, E) be a graph. A tree decomposition (TD) of a graph G is a pair T = (T, χ), where T is a rooted tree, and χ is a mapping that assigns to each node t of T a set χ(t) ⊆ V , called a bag, such that:

Then, define width(T ) :=maxt of T |χ(t)|-1. The treewidth tw(G) of G is the minimum width(T ) over all tree decompositions T of G. Observe that for every vertex v ∈ V , there is a unique node t∗ with v ∈ χ(t∗ ) such that either t∗ = root(T) or there is a node t of T with children(t) = {t∗ } and v /∈ χ(t). We refer to the node t∗ by last(v). For arbitrary but fixed w ≥ 1, it is feasible in linear time to decide if a graph has treewidth at most w and, if so, to compute a TD of width w [Bodlaender, 1996]. In this work, we assume only TDs (T, χ), where for every node t of T , we have that |children(t)| ≤ 2. Such a TD can be obtained from any TD in linear time without increasing the width [Bodlaender and Koster, 2008].

Treewidth and qBfs. For a given qBf ϕ with matrix(ϕ) = ψCNF ∧ ψDNF, we define the primal graph Gϕ := Gmatrix(ϕ), whose vertices are var(matrix(ϕ)). Two vertices of Gϕ are adjoined by an edge, whenever the corresponding variables share a clause or term of ψCNF or ψDNF, respectively.

Let tower(i, p) be tower(i-1, 2p ) if i &gt; 0 and p otherwise. Further, we assume that poly(n) is any polynomial for given positive integer n. The following result is known for QBF.

Proposition 3 (Chen, 2004). For any arbitrary qBf ϕ of quantifier rank ℓ &gt; 0, the problem ℓ-QBF can be solved in time tower(ℓ,O(tw(Gφ))) · poly(|var(ϕ)|).

Assuming the exponential time hypothesis (ETH) [Impagliazzo et al., 2001], one cannot significantly improve this runtime. The ETH implies that SAT = 1-QBF can not be decided in time better than 2o(|var(φ)|) for a formula φ.

Proposition 4 (Fichte et al., 2020). Under ETH, for any arbitrary qBf φ of quantifier rank ℓ &gt; 0, problem ℓ-QBF cannot be solved in time tower(ℓ, o(tw(Gφ))) · poly(|var(φ)|).

Abstract Argumentation. We use Dung's argumentation framework (1995) and consider only non-empty and finite sets of arguments A. An (argumentation) framework (AF) is a directed graph F = (A,R), where A is a set of arguments and R ⊆ A × A, a pair of arguments representing direct attacks of arguments. An argument a ∈ E, is called defended by E in F if for every (a′ , a) ∈ R, there exists a′′ ∈ E such that (a′′ , a′ ) ∈ R. The family defF (E) is defined by defF (E) := { a | A ∈ A, a is defended by E in F }. In abstract argumentation, one strives for computing so-called extensions, which are subsets E ⊆ A of the arguments that have certain properties. The set E of arguments is called conflict-free in E if (E × E) ∩ R = ∅; E is admissible in F if (1) E is conflict-free in F , and (2) every a ∈ E is defended by E in F. Let E+ R := E ∪ {a | (b, a) ∈ R, b ∈ E } and E be admissible. Then, E is (1) complete in F if defF (E) = E; (2) preferred in F, if no E′ ⊃ E exists that is admissible in F; (3) stable in F if every a ∈ A \ E is attacked by some a′ ∈ E. For a semantics σ ∈ {cf, adm, comp, pref, stab}, we write σ(F) for the set of all extensions of semantics σ in F.

Let F = (A, R) be an AF. Then, problem σ asks if σ(F ) ̸= ∅. The problems cσ and sσ question for a∈A, whether a is in some E ∈ σ(F) ("credulously accepted") or every E ∈ σ(F) ("skeptically accepted"), respectively.

TDs for AFs. Consider for AF F = (A,R) the primal graph GF , where we simply drop the direction of every edge, i.e., GF := (A,R′ ) where R′ := { {u, v} | (u, v) ∈ R }. For any TD T = (T, χ) of GF and any node t of T , we let Rt := R∩ { (a, b) | a, b ∈ χ(t) } be the bag attacks of t.

Let F = (A, R) be an AF and T = (T, χ) be a TD of GF . Stable Extensions. Stable extensions can be computed via DG reduction to SAT. For each argument a ∈ A, a variable ea determines whether a is in the extension or not. This gives rise to extension variables E := { ea | ea ∈ A }. Moreover, the formula confR(E) := ∧(a,b)∈R(¬ea ∨¬eb), ensures conflict-freeness and already preserves the treewidth. Towards a DG reduction, let dta be auxiliary variables for every node t of T and argument a ∈ A to indicate whether a is attacked ("defeated") by b ∈ χ(t) of the extension. This leads to defeated variables Vd := {dta | a ∈ A, t in T} and DG reduction Rstab(F, T ) := ∃E, Vd.confR(E) ∧ φstab(E, Vd) where CNF φstab(E, Vd) comprises Formulas (1) and (2):

Decomposition-Guided Reductions for AFs. Inspired by related work [Fichte et al., 2021b], a decomposition-guided (DG) reduction R is a function that takes both a problem instance I and a TD T = (T, χ) of GI, and returns a qBf φ. The way a DG reduction is constructed, it has to yield a TD T ′ = (T, χ′ ) of Gφ. So, the idea of such a DG reduction is to construct φ from a TD node's point of view. Thereby, for each node t of T, the constructed bag χ′ (t) functionally depends on the original bag χ(t), but also on the constructed bags χ′ (t1), . . . , χ′ (to) of its child nodes {t1, . . . , to} = children(t). This gives rise to a function f that takes a TD node t, its bag χ(t) and a set χ′ (children(t)) = { χ′ (ti) | ti ∈ children(t) } of constructed bags for the child nodes of t. Then, since the width(T ) is bounded by O(maxt of T (|χ(t)|)), also the treewidth of the resulting qBf is at most O(maxt of T {|f(t, χ(t), χ′ (children(t))|}).

<!-- formula-not-decoded -->

Admissible Extensions. Towards a DG reduction, auxiliary variables of the form na for every argument a ∈ A indicate whether a never attacks an argument in the extension. These no-attacking variables N := {na | a ∈ A} are used to define Radm(F, T ) := ∃E, Vd,N.confR(E)∧φadm(E,D,N), where φadm(E, Vd, N) consists of Formulas (1), and (3)-(6):

| ¬na ∨ ¬eb            | for every (a, b) ∈ R (3)   |
|----------------------|----------------------------|
| ea ∨ na ∨ dlast(a) a | for every a ∈ A (4)        |
| ¬na ∨ ¬ea            | for every a ∈ A (5)        |
| a                    | for every a A (6)          |

¬na ∨ ¬dlast(a)

for every a ∈ A (6)

As above, this reduction linearly preserves the (tree)width. Reductions for further semantics can be constructed similarly. For σ ∈ {stab, adm, comp, pref}, its DG reduction is given by Rσ .

Claim-Centric Argumentation. We formalize CAFs next.

Definition 5. A claim-augmented framework (CAF) CF := (A, R, cl) consists of an AF (A, R) and a function cl : A → C assigning claims to each argument in A, where C is a set of claims. Extend cl to sets by cl(E) := { cl(a) | a∈E }.

Semantics for CAF. Following [Dvor´ak andWoltran, 2020], we define the inherited (i-semantics) for CAFs.

Definition 6. Let CF = (A,R, cl) be a CAF where F = (A, R) denotes the underlying AF, and σ be an AF-semantics. Then we define i-σ semantics as σc(CF) := {cl(E) | E ∈ σ(F)}. Moreover, for a set S of claims, we call E ∈ σ(F) with cl(E) := S as a σc-realization of S in CF.

In this work, we focus on reasoning problems in claimcentric argumentation. Given a CAF CF = (A,R, cl), let the primal graph GCF := G(A,R). Further, the problem i-σ asks whether σc(CF) ̸= ∅. The problem i-cσ (resp., i-sσ) for inherited semantics asks whether a given claim c is in some (all) claim sets S ∈ σc(CF). For a given set S ⊆ C of claims, the verification problem i-vσ asks if S ∈ σc(CF).

## 3 Quantitative Claim-Based Reasoning

The two dominant reasoning modes in abstract argumentation are called credulous and skeptical reasoning, as defined in the previous section. While these classical forms of reasoning are well-established and useful in many cases, oftentimes one wants to have a more precise mode of reasoning that is located between both extreme cases. Indeed, credulous reasoning is rather easy to fulfill, as having already one extension over some entity of choice (argument or claim) satisfies its conditions; so, many entities will be credulously accepted. On the other hand, skeptical reasoning is overly skeptical, since having an entity in every extension is very hard to satisfy.

In order to mitigate these issues, we propose an intermediate reasoning mode that is more fine-grained and naturally adheres to quantitative (probabilistic) aspects of argumentation. Accordingly, instead of asking whether an entity of interest is in some or all extensions, a natural generalization is to ask whether the entity is in the vast majority (e.g., 70% or 80%, of the extensions). This way, one can still draw reasonable consequences from quantitative reasoning modes, without satisfying skeptical reasoning. Clearly, depending on the use case, quantitative reasoning could also be applied to query arguments in a minority of (e.g., 10%) the extensions.

Quantitative reasoning is formalized below, thereby conceptually relying on extension counting [Fichte et al., 2019] as its core. Observe that counting does not imply extension enumeration. Indeed, though state-of-the-art systems are capable of counting extensions one can probably not enumerate efficiently (e.g., exceeding the number of atoms in the universe) [Lagniez et al., 2021; Fichte et al., 2021a].

Definition 7 (Claim-Based Counting). Let CF = (A,R, cl) be a CAF, C be the set of claims and σ be a semantics. Moreover, let D be a claim assertion, i.e., a set of literals over C. Problem #cntσ(CF,D) counts extensions E fulfilling D, defined as D ∩ C ⊆ cl(E) ("cover claims') and { c | ¬c ∈ D } ∩ cl(E) = ∅ ("prevent disregarded claims").

For a set D of claim assertions, we denote by cl(D) the set of claims appearing in D. That is, cl(D) = {c | c ∈ C ∩ D} ∪ {c | c ∈ C, ¬c ∈ D}. Notice that the special case of D=∅, i.e., the problem #cntσ(CF, ∅) amounts to plain extension counting. This problem can be used to reason about the probability of a set of claims being covered by an arbitrary extension, yielding quantitative reasoning under claims.

Definition 8 (Probability of Claim Fulfillment). Let CF = (A, R, cl) be a CAF, C be the set of claims, σ be a semantics, and D be a claim assertion over C. The probability of D being fulfilled, is defined as probσ(CF,D) := #cntσ (CF,D) #cntσ (CF,∅) .

These counting-based definitions now allow us to reason about the degree of fulfilling claim assertions, which results in quantitative reasoning. This degree of fulfillment can then be used for accepting claim assertions depending on whether its probability exceeds a certain threshold.

Example 9. Reconsider the CAF in Example 2. The admissible extensions of this framework include ∅, {w}, {x}, {z}, {w, y}, {w, z} and the corresponding admissible sets of claims are ∅, {A}, {A}, {B}, {A}, {A, B}. Then A has higher preference than B: precisely, probadm(CF, {A}) = 46 , while probadm(CF, {B}) = 26 . Also for preferred semantics this preference holds, since probpref (CF, {A}) = 1 and probpref (CF, {B}) = 13 .

## 3.1 DGReductions for Quantitative Reasoning

Now, we proceed towards DG reductions for computing the probability of claim fulfillment for a fixed-size set D of claim assertions. We do this by presenting modifications to the reductions from Section 2 since CAFs generalize AFs. Note that it is known that credulous (i-cσ) and skeptical reasoning (i-sσ) are both FPT [Dvor´ak and Woltran, 2020] when parameterized by treewidth of the primal graph of AFs. After proving that both of these problems are subcases of quantitative reasoning, we improve known FPT-results by providing DG reductions that allow us to prove tight runtime bounds.

To this end, let CF = (A,R, cl) be a CAF, T = (T, χ) be a TD of GCF , and let E := {ea | a ∈ A} denote the extension variables as before. Then for each claim c ∈ D ∩ C the formula cov(c,E) := ∨a∈A,cl(a)=c ea guarantees that at least one argument a with cl(a) = c is in the extension. Similarly, for each d ∈ C such that ¬d ∈ D the formula ¬cov(d,E) guarantees that no argument a with cl(a) = d is in the extension. Clearly, cov(c,E) does not preserve the treewidth since different arguments can have claim c. To preserve the treewidth linearly, we split cov(c, E) considering the TD T . We use variables of the form xtc for each claim c over D and every node t of T to indicate whether the claim c is covered by some argument a in the extension. This leads to claim variables XD := {xtc | t in T, c ∈ cl(D)}. Finally, let φcl(E, XD) be the CNF consisting of Formulas (7)-(9):

<!-- formula-not-decoded -->

Intuitively, Formulas (7) guide the information regarding a claim c along the TD and the Formula (8) (resp., (9)) ensures that some (no) argument with the claim c is in the extension.

Claim-based counting for a fixed set D and semantics σ ∈ {stab, adm, comp, pref} can be solved by appending formula φcl(E, XD) to each Rσ, resulting in DG reduction Rcb σ . Then, the probability probσ(CF,D) of fulfilling D can be obtained by computing #cntσ(CF,D) and #cntσ(CF, ∅). Correctness of the resulting DG reductions is shown below.

Theorem 10 (Correctness). Let CF = (A,R, cl) be a CAF, D be a set of claim assertions, and T = (T, χ) be a TD of GCF . Then, DG reduction Rcb σ (CF, T ) for σ ∈ {stab, adm, comp, pref} is correct, i.e., #cntσ(CF,D) on CF coincides with #SAT (#2-QBF) on ψσ = Rcb σ (CF, T ).

The presented DG reductions yield the following results.

Theorem 11 (TW-Awareness). Let CF = (A,R, cl) be a CAF, D be a set of claim assertions of constant size r, and T = (T, χ) be a TD of GCF of width k. Then, the DG reduction Rcb σ (CF, T ) for σ ∈ {stab, adm, comp, pref} constructs a qBf ψσ s.t. tw(Gmatrix(ψσ)) ∈ O(k).

The following theorems provide the running time bounds for solving the reasoning problems.

Theorem 12 (Runtime UB). Let CF = (A,R, cl) be a CAF and D be a set of claim assertions of constant size r. Then, for σ ∈ {stab, adm, comp} (resp., pref), the problem #cntσ(CF,D) (#cntpref(CF,D)) can be solved in time 2O(k) · poly(|A|) (tower(2,O(k)) · poly(|A|)).

Interestingly, it is not expected that one can significantly improve (decrease) the treewidth in these DG reductions. The result follows because of the following theorem together with the fact that CAF expands AF.

Theorem 13 (Runtime LB). Let CF = (A,R, cl) be a CAF and D be a set of claim assertions. Then, for σ ∈ {stab, adm, comp} (resp., pref) the problem #cntσ(CF, D) (#cntpref (CF,D)) can not be solved in time 2o(k) · poly(|A|) (tower(2, o(k)) · poly(|A|)), where k = tw(GCF)).

Theorem 14 (TW-LB). Let CF = (A,R, cl) be a CAF, D be a set of claim assertions, and T be a TD of GCF of width k. Under ETH, DG reduction Rcb σ (CF, T ) for σ ∈ {stab, adm, comp, pref} cannot be significantly improved, i.e., there is no reduction R′ from #cntσ(CF,D) (resp., #cntpref(CF,D)) to #SAT (#2-QBF) yielding a qBf ψ in time 2o(k) · poly(|A|) (tower(2, o(k)) · poly(|A|)) with tw(Gmatrix(ψ)) ∈ o(k).

Figure 3: (1) GCF and its TD (2) for CF of Example 17. (3) A dense claim-centric argumentation framework whose incidence graph (4) is a tree (see Example 21).

![Image](https://ijcai.org/proceedings/2023/fulltext/358/image_000002_5c30cf9b33d4463c0f67e26bcc284e62f0950bcfabee5607d7d8ee70954caf0e.png)

Notice that the problems i-cσ and i-sσ are simply the corner cases of quantitative reasoning. Indeed, for a semantics σ, a given claim c is credulously (skeptically) accepted using inherited semantics, i.e., c ∈ i-cσ(CF) (c ∈ i-sσ(CF)) iff #cntσ(CF, {c}) ≥ 1 (#cntσ(CF, {¬c}) = 0). Moreover, #cntσ(CF, {c}) computes the number of extensions that cover the claim c (i.e., #i-cσ).

Corollary 15. Let σ ∈ {stab, adm, comp, pref}. Then, the runtime bounds for problems i-sσ, i-cσ and #i-cσ as specified in Table 1 hold.

Finally, for the claim-based extension existence (i-σ) the FPT-results and precise runtimes utilizing treewidth are established via the following corollary.

Corollary 16. Let σ ∈ {stab, adm, comp, pref}. Then, the runtime bounds for i-σ as specified in Table 1 hold.

Next, we present an example for a DG reduction.

Example 17 (DG reduction). Let T be the TD (with set of bags {1, 2} and root(T) = 1) as presented in Figure 3 (1) and (2). To achieve a DG reduction, first observe the following sets: E = {ew, ex, ey, ez}, Vd = {d1w , d1x , d2x , d2y , d2z } and XD = {x1A, x2A} (for the claim D = {A}). Then the reduction Rcb stab (CF, T ) yields ∃E, Vd,X.Φ where Φ is the conjunction of following formulas.

<!-- formula-not-decoded -->

The stable extension {x} covers A and yields a sat. assignment α for Φ, where α(ℓ) = 1 for ℓ ∈ {ex, dtw , duy , duz , xtA} and α(ℓ) = 0 otherwise. Two further stable extensions of CF {w, y} and {w, z} also yield sat. assignments for Φ.

## 4 AClaim-based Graph for Tractability

Recall that the results in Sect. 3 concern a claim assertion set of fixed size. For a set D of arbitrary size, the presented DG reductions do not linearly preserve the treewidth as witnessed by Formulas (8) and (9). In other words, the given assertions can only be verified at the root node of the given TD as there is no way of associating claims to the arguments otherwise. For extension verification (i-vσ), the treewidth of the primal graph is insufficient for tractability [Dvor´ak andWoltran, 2020].

To mitigate these shortcomings, we present an extended primal graph for CAFs modeling the structure of claim functions explicitly, which then yields further tractability results.

Figure 4: (Left) Extended Primal Graph (GeCF ) for CAF in Example 19 (Middle) Two claim-centric argumentation frameworks having the same incidence graph (Right) for Example 20.

![Image](https://ijcai.org/proceedings/2023/fulltext/358/image_000003_9023352f60966537c2927ec3d4ddf0a84d7814031603600ad874909c0c8cb2ec.png)

Definition 18 (Extended Primal Graph). Let CF = (A,R, cl) be a CAF with cl(A) = C. Then, the extended primal graph G eCF := (V,E) of CF is defined as: V := A ∪ C, E := {{a, b} | (a, b) ∈ R} ∪ {{a, c} | cl(a) = c}.

In other words, we expand the primal graph of an AF to capture the claim-centric focus via simply connecting arguments to their claims. The representation of claims allows us to relate a set of claims with their arguments and vice versa.

Example 19 (G eCF ). The CAF from Example 2 admits the extended primal graph as depicted in Figure 4 (Left).

There exists the notion of incidence graph for a subclass well-formed (arguments with the same claims attack the same arguments) of CAFs [Dvor´ak and Woltran, 2020]. Given a well-formed CF = (A,R, cl) with cl(A) = C, its incidence graph is defined as Gi := (A∪C,Ei), where Ei := { {a, cl(a)} | a ∈ A } ∪ { {c, a} | (b, a) ∈ R, cl(b) = c }. We argue that the incidence graph when extended from wellformed CAFs to the general case is not a suitable candidate for representing claims. Indeed, such a graph results in information loss regarding attacks between arguments.

Example 20. Consider the two CAFs and their (proposed) incidence graph as depicted in Figure 4. Then, both frameworks have the same incidence graph although the attack (y, x) only appears in one of them.

Furthermore, as the following example illustrates, a dense CAF may result in an incidence graph with low treewidth.

Example 21. Let CF be the CAF as depicted in Fig. 3 (3) and (4). Clearly, CF can be dense, but its (proposed) incidence graph is already a tree and therefore of treewidth 1.

We move on towards DG reductions based on extended primal graphs (denoted as G eCF for a given CF). Here, we reuse the notation from before and also the formulas where applicable. Associate the set of accepted claims with the accepted arguments. Let CF = (A, R, cl) be a CAF with C = cl(A) and T = (T, χ) be a TD of G eCF . Let E := {ea | a ∈ A} and X′ := {xc | c ∈ C} denote the extension and claim variables, respectively. Then, we let act(E,X′ ) := ∧c∈C (xc ↔ cov(c,E)), where cov(c,E) := ∨a∈A,cl(a)=c ea as before. Intuitively, the formula act(E,X′ ) states that an extension E activates a set X′ of claim variables and vice versa. Notice that the formula act(E,X′ ) does not preserve the treewidth and we split it in the same way as the formula cov(c, E).

To split act(E,X′ ), we let X := {xtc | c ∈ C, t in T} denote the activation variables, and define φact(E, X) by:

<!-- formula-not-decoded -->

Form. (10) guide the acceptance status of each claim along the decomposition. These are the same as Form. (7), but written for each claim c ∈ C. Then, claim-based counting for D and semantics σ ∈ {stab, adm, comp, pref} can be solved by appending φact(E,X) as well as Form. (8), (9) to each Rσ, resulting in DG reduction Re-cb σ . Having established DG reductions for linking claims and arguments, we can strengthen results from Sect. 3.1 to arbitrary sets of claim assertions.

## 4.1 Quantitative Reasoning for ClaimAssertions

We prove that treewidth of the extended primal graph of a CAF allows for FPT-algorithm for evaluating the probability of claim fulfilment for an arbitrary set D of claim assertions. Correctness is established similarly to Theorem 10.

Theorem 22 (Correctness). Let CF = (A, R, cl) be a CAF, D be a set of claim assertions, and T = (T, χ) be a TD of G eCF . Then, DG reduction Re-cb σ (CF, T ) for σ ∈ {stab, adm, comp, pref} is correct, i.e., #cntσ(CF,D) on CF coincides with #SAT (#2-QBF) on ψσ = Re-cb σ (CF, T ).

The presented DG reductions yield the following results.

Theorem 23 (TW-Awareness). Let CF = (A,R, cl) be a CAF, D be a set of claim assertions and T = (T, χ) be a TD of G eCF of width k. Then, the DG reduction Re-cb σ (CF, T ) for σ ∈ {stab, adm, comp, pref} constructs a qBf ψσ s.t. tw(Gmatrix(ψσ)) ∈ O(k).

Proof (Sketch). We construct a TD T ′ = (T, χ′ ) of Gψσ in same way as in proof of Theorem 11. The only difference now is the presence of the formula φact. Recall that the graph G eCF allows edges {a, c} for each a ∈ A with cl(a) = c. As evident from Formulas (10), the variables xt′ c are only added for the children bags with c ∈ χt′ . We present the proof for stab, the argument for other semantics follows the same lines. For every node t of T, we let χ′ (t) := χ(t) ∪ {ea, xtc , dta | a ∈ At, c ∈ Ct} ∪ {xt′ c , dt′ a | a ∈ At ∩At′ , c ∈ Ct ∩Ct′ , t′ ∈ children(t)}, where At := χ(t) ∩ A and Ct := χ(t) ∩ C. Since |children(t)| ≤ 2, we have that |χ′ (t)| ≤ 5 · |χ(t)|.

Now, we provide the runtime bounds for the problems.

Theorem 24 (Runtime UB). Let CF = (A,R, cl) be a CAF and D be a set of claim assertions. Then, for σ ∈ {stab, adm, comp} (resp., pref), the problem #cntσ(CF, D) (#cntpref(CF,D)) can be solved in time 2O(k) · poly(|A|) (tower(2,O(k)) · poly(|A|)).

Before proving the lower bounds for #cntσ(CF,D) for a set D of claim assertions, we connect the verification problem with quantitative reasoning. Clearly, verification (i-vσ) can be seen as a subcase of the quantitative reasoning. Let S ⊆ C be a set of claims, then we let D := {c | c ∈ S}∪{¬c | c ∈ C, c ̸∈ S}. Then, for each σ ∈ {stab, adm, comp, pref}: S ∈ i-vσ iff #cntσ(CF,D) &gt; 0. Moreover, the DG reductions for quantitative reasoning also yield results for counting the extensions of a CF covering the given set S (i.e., #cntσ(CF, D)). The next theorem establishes runtime lower bounds for i-vσ implying the similar bounds for #cntσ(CF,D).

Theorem 25 (i-vσ LB). Let CF = (A,R, cl) be a CAF and σ ∈ {stab, adm, comp} (resp., pref). Then the problem i-vσ

can not be solved in time 2o(k) · poly(|A|) (tower(2, o(k)) · poly(|A|)), where k = tw(GCF ).

Proof (Sketch). We establish reductions from 3SAT (resp., spref ) to i-vσ that linearly preserve the treewidth. Then, i-vσ (resp., i-vpref ) can be solved in time 2o(k) · poly(|A|) (tower(2, o(k)) · poly(|A|)), where k = tw(GCF ) iff 3SAT (spref ) can be solved in time 2o(k) · poly(|A|) (tower(2, o(k)) · poly(|A|)), which is a contradiction to known results.

Theorem 26 (Runtime LB). Let CF = (A,R, cl) be a CAF and D be a set of claim assertions. Then, for σ ∈ {stab, adm, comp} (resp., pref) the problem #cntσ(CF, D) (#cntpref (CF,D)) can not be solved in time 2o(k) · poly(|A|) (tower(2, o(k)) · poly(|A|)), where k = tw(G eCF ).

Again, it is not expected that one can significantly improve (decrease) the treewidth in these DG reductions.

Theorem 27 (TW-LB). Let CF = (A,R, cl) be a CAF, D be a set of claim assertions and T be a TD of G eCF of width k. Under ETH, the DG reduction Re-cb σ (CF, T ) for σ ∈ {stab, adm, comp, pref} cannot be significantly improved, i.e., there is no reduction R′ from#cntσ(CF,D) (#cntpref(CF,D)) to#SAT (#2-QBF) yielding a qBf ψ in time 2o(k) · poly(|A|) (tower(2, o(k)) · poly(|A|)) with tw(Gψ) ∈ o(k).

The corollary establishes the tight runtime bounds for i-vσ. Corollary 28. Let σ ∈ {stab, adm, comp, pref}. Then, the runtime bounds for problems i-vσ as specified in Table 1 hold.

## 5 Conclusion

We introduce a quantitative mode of reasoning in claim-centric argumentation for CAFs that allows for precise reasoning between the purely binary credulous and skeptical reasoning problems. We provide precise computational bounds for the structural restriction treewidth, which is crucial in the quantitative world when considering effects in practical solving. We establish these results by the concept of DG reductions from CAFs under various semantics to SAT/2-QBF. Interestingly, for claim assertions of constant size, the runtime bounds for probσ(CF,D) match those for skeptical reasoning. However, for arbitrary claim assertions, the treewidth of the primal graph for CAFs does not suffice, but the treewidth of the extended primal graph does.

As future work, studying further semantics such as semiSt and stag and Claim-level semantics [Dvor´ak et al., 2021] provide interesting questions. We also believe that investigating stricter parameters, for which recently results on QBFs have been obtained [Fichte et al., 2023a], might be of theoretical interest. Since counting and conditional probabilities are relevant for navigating in search spaces [Fichte et al., 2022b], it could be interesting to use our measures here to provide capacities to navigate within extensions of CAFs. Finally, we believe that utilizing DG reductions in a practical setting could be interesting due to the practical effect of treewidth on counting [Hecher, 2022; Fichte et al., 2023b; Dewoprabowo et al., 2022].

## Acknowledgements

Authors are stated in alphabetical order. The work was supported by ELLIIT funded by the Swedish government, by the Austrian Science Fund (FWF) grants J4656, P32830, and Y1329, Society for Research Funding Lower Austria (GFF) grant ExzF-0004, Vienna Science and Technology Fund (WWTF) grants ICT19-060 and ICT19-065, by the European Union's Horizon Europe research and innovation programme within project ENEXA (101070305), and the German Research Organisation (DFG) project ME4279/3-1 (511769688).

## References

1. [Alfano et al., 2020] Gianvincenzo Alfano, Marco Calautti, Sergio Greco, Francesco Parisi, and Irina Trubitsyna. Ex- plainable acceptance in probabilistic abstract argumenta- tion: Complexity and approximation. In KR'20, pages 33-43. IJCAI Organization, 2020.
2. [Alviano, 2018] Mario Alviano. The Pyglaf Argumentation Reasoner. In ICLP'17, volume 58, pages 2:1-2:3. Dagstuhl Publishing, 2018.
3. [Amgoud and Prade, 2009] Leila Amgoud and Henri Prade. Using arguments for making and explaining decisions. Ar- tificial Intelligence, 173(3-4):413-436, 2009.
4. [Atkinson et al., 2017] Katie Atkinson, Pietro Baroni, Massi- miliano Giacomin, Anthony Hunter, Henry Prakken, Chris Reed, Guillermo Ricardo Simari, Matthias Thimm, and Serena Villata. Towards artificial argumentation. AI Mag., 38(3):25-36, 2017.
5. [Atserias et al., 2011] Albert Atserias, Johannes Klaus Fichte, and Marc Thurley. Clause-learning algorithms with many restarts and bounded-width resolution. Journal of Artificial Intelligence Research, 40:353-373, 2011.
6. [Bacchus et al., 2003] Fahiem Bacchus, Shannon Dalmao, and Toniann Pitassi. Algorithms and complexity results for #SAT and Bayesian inference. In FOCS'03, pages 340-351, 2003.
7. [Baroni and Riveret, 2019] Pietro Baroni and Régis Riveret. Enhancing statement evaluation in argumentation via multi- labelling systems. J. Artif. Intell. Res., 66:793-860, 2019.
8. [Baroni et al., 2016] Pietro Baroni, Guido Governatori, Ho- Pun Lam, and Régis Riveret. On the justification of state- ments in argumentation-based reasoning. In KR'16, pages 521-524. The AAAI Press, 2016.
9. [Baroni et al., 2018] Pietro Baroni, Dov Gabbay, Massimil- iano Giacomin, and Leendert van der Torre, editors. Hand- book of Formal Argumentation. College Publications, 2018.
10. [Besnard and Hunter, 2008] Philippe Besnard and Anthony Hunter. Elements of Argumentation. MIT Press, 2008.
11. [Biere et al., 2021] Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh, editors. Handbook of Satisfiabil- ity -Second Edition, volume 336 of Frontiers in Artificial Intelligence and Applications. IOS Press, 2021.
12. [Bodlaender and Koster, 2008] Hans L. Bodlaender and Arie M. C. A. Koster. Combinatorial optimization on graphs of bounded treewidth. Comput. J., 51(3):255-269, 2008.
13. [Bodlaender, 1996] Hans L. Bodlaender. A linear-time algo- rithm for finding tree-decompositions of small treewidth. SIAM J. Comput., 25(6):1305-1317, 1996.
14. [Bondy and Murty, 2008] J. Adrian Bondy and Uppaluri S. R. Murty. Graph Theory. Graduate Texts in Mathematics. Springer, 2008.
15. [Bonzon et al., 2018] Elise Bonzon, Jérôme Delobelle, Sébastien Konieczny, and Nicolas Maudet. Combining extension-based semantics and ranking-based semantics for abstract argumentation. In KR'18, pages 118-127. The AAAI Press, 2018.
16. [Brochenin et al., 2018] Remia Brochenin, Thomas Linsbich- ler, Marcoa Maratea, Johannes P. Wallner, and Stefan Woltran. Abstract solvers for Dung's argumentation frame- works. Argument & Computation, 9(1):41-72, 2018.
17. [Charwat et al., 2015] Günther Charwat, Wolfgang Dvořák, Sarah A. Gaggl, Johannes P. Wallner, and Stefan Woltran. Methods for solving reasoning problems in abstract argu- mentation -a survey. Artificial Intelligence, 220:28-63, 2015.
18. [Chen, 2004] Hubie Chen. Quantified constraint satisfaction and bounded treewidth. In ECAI'04, pages 161-165. IOS Press, 2004.
19. [Dewoprabowo et al., 2022] Ridhwan Dewoprabowo, Jo- hannes Klaus Fichte, Piotr Jerzy Gorczyca, and Markus Hecher. A practical account into counting dung's exten- sions by dynamic programming. In LPNMR'22, pages 387-400. Springer Verlag, 2022.
20. [Dung, 1995] Phan Minh Dung. On the acceptability of argu- ments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artificial Intelli- gence, 77(2):321-357, 1995.
21. [Dunne and Bench-Capon, 2002] Paul E. Dunne and Trevor J. M. Bench-Capon. Coherence in finite argument systems. Artificial Intelligence, 141(1/2):187-203, 2002.
22. [Dvorák and Woltran, 2020] Wolfgang Dvorák and Stefan Woltran. Complexity of abstract argumentation under a claim-centric view. Artificial Intelligence, 285:1-22, 2020.
23. [Dvorák et al., 2020] Wolfgang Dvorák, Anna Rapberger, and Stefan Woltran. Argumentation semantics under a claim-centric view: Properties, expressiveness and relation to setafs. In KR'20, pages 341-350, 2020.
24. [Dvorák et al., 2021] Wolfgang Dvorák, Alexander Greßler, Anna Rapberger, and Stefan Woltran. The complexity land- scape of claim-augmented argumentation frameworks. In AAAI'21, pages 6296-6303. The AAAI Press, 2021.
25. [Dvorák et al., 2022] Wolfgang Dvorák, Markus Hecher, Matthias König, André Schidler, Stefan Szeider, and Stefan Woltran. Tractable Abstract Argumentation via Backdoor- Treewidth. In AAAI, pages 5608-5615. AAAI Press, 2022.
26. [Dvořák, 2012] Wolfgang Dvořák. Computational aspects of abstract argumentation. PhD thesis, TU Wien, 2012.
27. [Dvořák and Woltran, 2010] W. Dvořák and S. Woltran. Complexity of semi-stable and stage semantics in argu- mentation frameworks. Information Processing Letters, 110(11):425-430, 2010.
28. [Dvořák et al., 2012] W. Dvořák, R. Pichler, and S. Woltran. Towards fixed-parameter tractable algorithms for abstract argumentation. Artificial Intelligence, 186:1-37, 2012.
29. [Eiter et al., 2021] Thomas Eiter, Markus Hecher, and Rafael Kiesel. Treewidth-aware cycle breaking for algebraic an- swer set counting. In KR'21, pages 269-279. IJCAI Orga- nization, 2021.
30. [Fazzinga et al., 2015] Bettina Fazzinga, Sergio Flesca, and Francesco Parisi. On the complexity of probabilistic ab- stract argumentation frameworks. ACM Trans. Comput. Log., 16(3):22:1-22:39, 2015.
31. [Fichte et al., 2019] Johannes K. Fichte, Markus Hecher, and Arne Meier. Counting complexity for reasoning in abstract argumentation. In AAAI'19, pages 2827-2834. The AAAI Press, 2019.
32. [Fichte et al., 2020] Johannes Klaus Fichte, Markus Hecher, and Andreas Pfandler. Lower Bounds for QBFs of Bounded Treewidth. In LICS, pages 410-424. ACM, 2020.
33. [Fichte et al., 2021a] Johannes Klaus Fichte, Markus Hecher, and Florim Hamiti. The Model Counting Competition 2020. ACM J. Exp. Algorithmics, 26:13:1-13:26, 2021.
34. [Fichte et al., 2021b] Johannes Klaus Fichte, Markus Hecher, Yasir Mahmood, and Arne Meier. Decomposition-guided reductions for argumentation and treewidth. In IJCAI'21, pages 1880-1886. IJCAI Organization, 2021.
35. [Fichte et al., 2022a] Johannes K Fichte, Markus Hecher, Mo- hamed A Nadeem, and TU Dresden. Plausibility reasoning via projected answer set counting-a hybrid approach. In IJCAI'22, pages 2620-2626. IJCAI Organization, 2022.
36. [Fichte et al., 2022b] Johannes Klaus Fichte, Sarah Alice Gaggl, and Dominik Rusovac. Rushing and strolling among answer sets -navigation made easy. Proceedings of the AAAI Conference on Artificial Intelligence, 36(5):5651- 5659, Jun. 2022.
37. [Fichte et al., 2023a] Johannes K. Fichte, Robert Ganian, Markus Hecher, Sebastian Ordyniak, and Friedrich Slivovsky. Structure-aware lower bounds and broaden- ing the horizon of tractability for QBF. In LICS'23. ACM, 2023.
38. [Fichte et al., 2023b] Johannes K. Fichte, Markus Hecher, Michael Morak, Patrick Thier, and Stefan Woltran. Solv- ing projected model counting by utilizing treewidth and its limits. Artificial Intelligence, 314:103810, 2023.
39. [Hecher, 2022] Markus Hecher. Treewidth-aware reductions of normal ASP to SAT -is normal ASP harder than SAT after all? Artif. Intell., 304:103651, 2022.
40. [Hossain and Laroussinie, 2021] Akash Hossain and Franc ¸ois Laroussinie. QCTL model-checking with QBF solvers. Inf. Comput., 280:104642, 2021.
41. [Hunter and Thimm, 2017] Anthony Hunter and Matthias Thimm. Probabilistic reasoning with abstract argumen- tation frameworks. J. Artif. Intell. Res., 59:565-611, 2017.
42. [Impagliazzo et al., 2001] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512- 530, 2001.
43. [Jung et al., 2022] Jean Christoph Jung, Valentin Mayer- Eichberger, and Abdallah Saffidine. QBF Programming with the Modeling Language Bule. In SAT'22, volume 236 of Leibniz International Proceedings in Informatics (LIPIcs), pages 31:1-31:14. Dagstuhl Publishing, 2022.
44. [Lagniez et al., 2021] Jean-Marie Lagniez, Emmanuel Lonca, Jean-Guy Mailly, and Julien Rossit. Design and results of ICCMA 2021. CoRR, abs/2109.08884, 2021.
45. [Lampis et al., 2018] Michael Lampis, Stefan Mengel, and Valia Mitsou. QBF as an alternative to Courcelle's theorem. In SAT'18, pages 235-252. Springer Verlag, 2018.
46. [Maher, 2016] Michael J Maher. Resistance to corruption of strategic argumentation. In Dale Schuurmans and Michael Wellman, editors, AAAI'16, pages 1030-1036. The AAAI Press, 2016.
47. [Pan and Vardi, 2006] Guoqiang Pan and Moshe Y. Vardi. Fixed-parameter hierarchies inside PSPACE. In LICS, pages 27-36. IEEE Computer Society, 2006.
48. [Pippenger, 1997] Nicholas Pippenger. Theories of com- putability. Cambridge University Press, 1997.
49. [Prakken and Vreeswijk, 2002] Henry Prakken and Gerard Vreeswijk. Logics for Defeasible Argumentation, pages 219-318. Springer Verlag, 2002.
50. [Rago et al., 2018] Antonio Rago, Oana Cocarascu, and Francesca Toni. Argumentation-based recommendations: Fantastic explanations and how to find them. In IJCAI'18, pages 1949-1955. IJCAI Organization, 2018.
51. [Robertson and Seymour, 1986] Neil Robertson and Paul D. Seymour. Graph minors. II. algorithmic aspects of tree- width. J. Algorithms, 7(3):309-322, 1986.
52. [Sanjay Modgil, 2018] Henry Prakken Sanjay Modgil. Hand- book of Formal Argumentation, chapter Abstract rule-based argumentation, pages 286-361. College Publications, 2018.
53. [Shaik and van de Pol, 2022] Irfansha Shaik and Jaco van de Pol. Classical Planning as QBF without Grounding. In ICAPS'22, pages 329-337. The AAAI Press, 2022.
54. [Shukla et al., 2019] Ankit Shukla, Armin Biere, Luca Pulina, and Martina Seidl. A survey on applications of quantified boolean formulas. In ICTAI, pages 78-84. IEEE, 2019.
55. [Wrathall, 1976] Celia Wrathall. Complete sets and the polynomial-time hierarchy. Theor. Comput. Sci., 3(1):23- 33, 1976.
56. [Wu and Caminada, 2010] Yining Wu and Martin Caminada. A labelling based justification status of arguments. Studies in Logic, 3:12-29, 01 2010.