Credulous and skeptical acceptability in probabilistic abstract argumentation: complexity results

Abstract

Probabilistic abstract argumentation combines Dung’s abstract argumentation framework with probability theory in order to model uncertainty in argumentation. In this setting, we address the fundamental problem of computing the probability that an argument is credulously or skeptically acceptable according to a given semantics. Specifically, we focus on the most popular semantics (i.e., admissible, stable, semi-stable, complete, grounded, preferred, ideal, ideal-set), and show that computing the probability that an argument is credulously or skeptically accepted is FP^# P-complete independently from the adopted semantics, in the cases when computing it is not trivial (i.e., when skeptical acceptance is assumed under the admissible and ideal-set semantics).

Keywords

Acceptability probabilistic abstract argumentation complexity

1 Introduction

Several argumentation frameworks have been proposed, with the aim of suitably modeling disputes between two or more parties. Typically, argumentation frameworks model both the possibility of parties to present arguments supporting their theses, and the possibility that some arguments rebut other arguments.

A powerful yet simple argumentation framework is that proposed in the seminal paper [11], called abstract argumentation framework (AAF). An AAF is a representation of a dispute in terms of an argumentation graph 〈A, D〉, where A is the set of nodes (each called argument) and D is the set of edges (each called defeat or, equivalently, attack). Basically, an argument is an abstract entity that may attack and/or be attacked by other arguments, and an attack expresses the fact that an argument is in conflict with another argument.

Several semantics for AAFs, such as admissible, stable, preferred, complete, grounded, semi-stable, ideal-set and ideal, have been proposed [2 , 12] to identify “reasonable” sets of arguments, called extensions. Basically, each of these semantics corresponds to some properties that “certify” whether a set of arguments can be profitably used to support a point of view in a discussion. For instance, under the admissible semantics, a set S of arguments is an extension if S is “conflict-free” (i.e., there is no defeat between arguments in S) and is “robust” against the other arguments (i.e., every argument outside S attacking an argument in S is counterattacked by an argument in S). This means that one using the set of arguments S in a discussion does not contradict her/himself, and can rebut to the arguments possibly presented by the other parties.

As a matter of fact, in the real world, arguments and defeats are often uncertain. For instance, consider an argument a (or a defeat δ) encoding an interpretation or a translation of the description of a fact reported in a reference text. Then, a (or δ) may be uncertain in the sense that the original paragraph may have interpretations other than that encoded by a (or δ).

Thus, several proposals have been made to model uncertainty in AAFs, by considering weights, preferences, or probabilities associated with arguments and/or defeats. One of the most popular approaches based on probability theory for modeling the uncertainty is the so called constellations approach [8 , 31]: the dispute is represented by means of a Probabilistic Argumentation Framework (PrAAF), that consists in a set of alternative scenarios, each represented by an argumentation graph associated with a probability. The various works in the literature investigating PrAAFs can differ in the assumption on how the probability distribution function (pdf) over the scenarios is specified. For instance, in [31], the pdf is defined “extensively”, by enumerating all the possible scenarios and, for each of them, the value of its probability. On the other hand, in [29], the restriction that arguments are independent among them and that defeats are independent among them and conditional to arguments is assumed, and this is exploited to simplify the way probabilities are specified: the pdf is not explicitly specified, as it is implied by the marginal probabilities associated with arguments and defeats.

As regards reasoning over an argumentation framework, in the deterministic setting, two classical problems supporting the reasoning over AAFs have been deeply investigated and used in practical applications:

Ext^sem (S): the problem of deciding whether a set of arguments S is an extension according to the semantics sem;

CA^sem (a): the problem of deciding whether the argument a is credulously acceptable, i.e., it belongs to at least one extension under the semantics sem.

SA^sem (a): the problem of deciding whether the argument a is skeptically acceptable, i.e., it belongs to every extensions under the semantics sem.

Basically, the relevance of these problems is that solving Ext^sem (S) supports the decision on whether presenting a set of arguments in a dispute is a reasonable strategy, while solving CA^sem (a) and SA^sem (a) focuses this analysis on single arguments. In the probabilistic setting, there are multiple scenarios to be taken into account, and an argument a can be acceptable in some scenarios, but not in others. Thus, the natural probabilistic counterparts P-Ext^sem (S), P-CA^sem (a) and P-SA^sem (a) of the above-mentioned problems Ext^sem (S), CA^sem (a) and SA^sem (a) consist in evaluating the overall probability that S is an extension and a is credulously or skeptically acceptable, respectively, where “overall” means summing the probabilities of the scenarios where the property is verified.

The complexity of Ext^sem (S) and P-Ext^sem (S) has been deeply investigated. Specifically, in the probabilistic setting the complexity of P-Ext^sem (S) has been investigated both in the case that the assumption that arguments and defeats are independent holds [19 –21] and in more general cases [22].

As regards CA^sem (a) and SA^sem (a), their complexity has been deeply investigated, showing that it ranges from PTIME to $\prod_{2}^{p}$ -complete, depending on the adopted semantics [6 , 15]. Detailed complexity results from the literature are reported in the first two columns of Table 1.

Table 1
Complexity of CA^sem (a), SA^sem (a), P-CA^sem (a) and P-SA^sem (a).

sem CA^sem(a) SA^sem(a) P-CA^sem(a) P-SA^sem(a)

admissible NP-complete trivial FP^#P-complete trivial

stable NP-complete coNP-complete FP^#P-complete FP^#P-complete

complete NP-complete PTIME FP^#P-complete FP^#P-complete

grounded PTIME PTIME FP^#P-complete FP^#P-complete

semi-stable $\sum_{2}^{p}$ -complete $\prod_{2}^{p}$ -complete FP^#P-complete FP^#P-complete

preferred NP-complete $\prod_{2}^{p}$ -complete FP^#P-complete FP^#P-complete

ideal-set in $Θ_{2}^{p}$ , coNP-h trivial FP^#P-complete trivial

ideal in $Θ_{2}^{p}$ , coNP-h in $Θ_{2}^{p}$ , coNP-h FP^#P-complete FP^#P-complete

sem	CA^sem(a)	SA^sem(a)	P-CA^sem(a)	P-SA^sem(a)
admissible	NP-complete	trivial	FP^#P-complete	trivial
stable	NP-complete	coNP-complete	FP^#P-complete	FP^#P-complete
complete	NP-complete	PTIME	FP^#P-complete	FP^#P-complete
grounded	PTIME	PTIME	FP^#P-complete	FP^#P-complete
semi-stable	$\sum_{2}^{p}$ -complete	$\prod_{2}^{p}$ -complete	FP^#P-complete	FP^#P-complete
preferred	NP-complete	$\prod_{2}^{p}$ -complete	FP^#P-complete	FP^#P-complete
ideal-set	in $Θ_{2}^{p}$ , coNP-h	trivial	FP^#P-complete	trivial
ideal	in $Θ_{2}^{p}$ , coNP-h	in $Θ_{2}^{p}$ , coNP-h	FP^#P-complete	FP^#P-complete

However, to the best of our knowledge no work has been done for characterizing the complexity of P-CA^sem (a) and P-SA^sem (a).

In this paper, we focus on the constellations approach with independence proposed in [29] and analyze the complexity of P-CA^sem (a) and P-SA^sem (a), showing that both of them are FP^#P-complete independently from the adopted semantics (see the second column of Table 1), in the cases when they are not trivial (i.e., P-SA^sem (a) under the admissible and ideal-set semantics). Proving that the problem is intractable backs the usage of alternative strategies for solving P-CA^sem (a) and P-SA^sem (a), such as resorting to Monte-carlo based probability estimation approaches.

2 Preliminaries

In this section, we briefly recall some basic notions about computational complexity, and concisely overview Dung’s abstract argumentation framework, and its probabilistic extension introduced in [29].

2.1 Complexity

The computational complexity of the problem addressed in this paper is related to the complexity classes of counting problems. A counting problem f is a function from strings over a finite alphabet into integers. # P is the complexity class of the functions f such that f counts the number of accepting paths of a nondeterministic polynomial-time Turing machine [33]. Although the problem addressed in the paper is closely related to # P, strictly speaking, it cannot belong to it, since the outputs of our problem are not integers. In fact, we deal with the class FP^#P, that is, the class of functions computable by a polynomial-time Turing machine with a # P oracle. In this regard, note that a function is FP^#P-hard iff it is # P-hard, and thus to prove that a problem is FP^#P-hard it suffices to reduce a # P-hard problem to it.

2.2 Abstract Argumentation

An abstract argumentation framework [11] (AAF) is a pair 〈A, D〉, where A is a finite set, whose elements are referred to as arguments, and D ⊆ A × A is a binary relation over A, whose elements are referred to as defeats (or attacks). An argument is an abstract entity whose role is entirely determined by its relationships with other arguments. Given an AAF $A$ , we also refer to the set of its arguments and the set of its defeats as $Arg (A)$ and $Def (A)$ , respectively.

Given arguments a, b ∈ A, we say that adefeatsb iff there is (a, b) ∈ D. Similarly, a set S ⊆ Adefeats an argument b ∈ A iff there is a ∈ S such that adefeatsb.

A set S ⊆ A of arguments is said to be conflict-free if there are no a, b ∈ S such that adefeatsb. An argument a is said to be acceptable w.r.t. S ⊆ A iff ∀b ∈ A such that bdefeatsa, there is c ∈ S such that cdefeatsb. Given a set S ⊆ A of arguments, we define S⁺ as the set of arguments that are defeated by S, that is, S⁺ = {a ∈ A s.t. S defeats a}.

Several semantics for AAFs have been proposed to identify “reasonable” sets of arguments, called extensions. We consider the following well-known semantics [4 , 12]: admissible (ad), stable (st), complete (co), grounded (gr), semi-stable (sst), preferred (pr), ideal-set (ids), and ideal (ide).

A set S ⊆ A is said to be:

an admissible extension iff S is conflict-free and all its arguments are acceptable w.r.t. S;

a stable extension iff S is conflict-free and S defeats each argument in A \ S;

a complete extension iff S is admissible and S contains all the arguments that are acceptable w.r.t. S;

a grounded extension iff S is a minimal (w.r.t. ⊆) complete set of arguments;

a semi-stable extension iff S is a complete extension where S ∪ S⁺ is maximal (w.r.t. ⊆);

a preferred extension iff S is a maximal (w.r.t. ⊆) admissible set of arguments;

an ideal-set extension iff S is admissible and S is contained in every preferred set of arguments;

an ideal extension iff S is a maximal (w.r.t. ⊆) ideal-set extension;

Example 1. Consider the AAF 〈A, D〉, where the set A of arguments is {a, b, c} and the set D of defeats is {δ₁ = (b, a) , δ₂ = (b, c) , δ₃ = (c, b)}, where δ₂ and δ₃ encode the fact that arguments b and c attack each other. A graphical representation of the AAF 〈A, D〉 is reported in Fig. 1, where arguments are represented as nodes and defeats are represented as edges between nodes. As S = {a, c} is conflict-free and every argument in S is acceptable w.r.t. S, it is the case that S is admissible. It is easy to see that the sets {b}, {c}, and ∅ are admissible extensions as well. Since S is conflict-free and defeats b (the only argument in A\S) it is also a stable extension. As S is maximally admissible, it is a preferred extension, while {c} is not, since a is acceptable w.r.t {c}. It is easy to check that S is complete, while it neither is grounded (since it is not minimally complete, as the empty set is complete) nor ideal or ideal-set (since it is not contained in {b} which is a preferred extension).□

Fig. 1

The AAF 〈A, D〉

Given an AAF $A$ , a set $S \subseteq Arg (A)$ of arguments, an argument $a \in Arg (A)$ and a semantics sem ∈ {ad, st, gr, co, sst, pr, ids, ide }, we define the function accC( $A, sem, a$ ) that returns true if $\exists S \subseteq Arg (A)$ such that a ∈ S and S is an extension according to sem, false otherwise, and the function accS( $A, sem, a$ ) that returns true if $\forall S \subseteq Arg (A)$ such that S is an extension according to sem it holds that a ∈ S and, false otherwise.

Example 2. Consider the AAF 〈A, D〉 introduced in Example 1. The argument a is credulously accepted under the admissible, stable, complete, semi-stable and preferred semantics. a is not credulously accepted under the grounded, ideal-set and ideal semantics. Moreover, the argument a is not skeptically accepted under any of the considered semantics. □

2.3 Probabilistic Abstract Argumentation

We now review the probabilistic abstract argumentation framework proposed in [29].

Definition 1. [PrAAF] A probabilistic argumentation framework (PrAAF) is a tuple 〈A, P_A, D, P_D〉 where 〈A, D〉 is an AAF, and P_A and P_D are, respectively, functions assigning a non-zero 1 probability value to each argument in A and defeat in D, that is, $P_{A} : A \to (0, 1] \cap ℚ$ and $P_{D} : D \to (0, 1] \cap ℚ$ .

Basically, the value assigned by P_A to an argument a represents the probability that a actually occurs, whereas the value assigned by P_D to a defeat (a, b) represents the conditional probability that a defeats b given that both a and b occur.

The meaning of a PrAAF is given in terms of possible worlds, each of them representing a scenario that may occur in the reality. Given a PrAAF $F$ , a possible world is modeled by an AAF which is derived from $F$ by considering only a subset of its arguments and defeats. More formally, given a PrAAF $F = 〈 A, P_{A}, D, P_{D} 〉$ , a possible world w of $F$ is an AAF 〈A′, D′〉 such that A′ ⊆ A and D′ ⊆ D ∩ (A′ × A′). The set of the possible worlds of $F$ will be denoted as $pw (F)$ .

Example 3. As a running example, consider the PrAAF $F = 〈 A, P_{A}, D, P_{D} 〉$ reported in Fig. 2, where A and D are those of Example 1, and P_A (a) =0.9, P_A (b) =0.7, P_A (c) =0.2, P_D (δ₁) =0.9 and P_D (δ₂) = P_D (δ₃) =1. The set $pw (F)$ contains the following possible worlds:

w₁ = 〈 ∅ , ∅ 〉	w₂ = 〈 {a} , ∅ 〉
w₃ = 〈 {b} , ∅ 〉	w₄ = 〈 {c} , ∅ 〉
w₅ = 〈 {a, b} , ∅ 〉	w₆ = 〈 {a, c} , ∅ 〉
w₇ = 〈 {b, c} , ∅ 〉	w₈ = 〈A, ∅ 〉
w₉ = 〈 {a, b} , {δ₁} 〉	w₁₀ = 〈 {b, c} , {δ₃} 〉
w₁₁ = 〈 {b, c} , {δ₂} 〉	w₁₂ = 〈 {b, c} , {δ₂, δ₃} 〉
w₁₃ = 〈A, {δ₁} 〉	w₁₄ = 〈A, {δ₁, δ₃} 〉
w₁₅ = 〈A, {δ₁, δ₂} 〉	w₁₆ = 〈A, D〉
w₁₇ = 〈A, {δ₂} 〉	w₁₈ = 〈A, {δ₃} 〉
w₁₉ = 〈A, {δ₂, δ₃} 〉

Fig. 2

The PrAAF 〈A, P_A, D, P_D〉

□

An interpretation for a PrAAF $F = 〈 A, P_{A}, D, P_{D} 〉$ is a probability distribution function I over the set $pw (F)$ of the possible worlds. Assuming that arguments represent pairwise independent events, and that each defeat represents an event conditioned by the occurrence of its argument events but independent from any other event, the interpretation for the PrAAF $F = 〈 A, P_{A}, D, P_{D} 〉$ is as follows. For each possible world $w \in pw (F)$ , w is assigned by I the probability:

$\begin{matrix} I (w) = \prod_{a \in Arg (w)} P_{A} (a) \times \prod_{a \in A \ Arg (w)} (1 - P_{A} (a)) \times \\ ∥ \times \prod_{δ \in Def (w)} P_{D} (δ) \times \prod_{δ \in \bar{D} (w) \ Def (w)} (1 - P_{D} (δ)) \end{matrix}$ where $\bar{D} (w)$ is the set of defeats that may appear in the possible world w, that is $\bar{D} (w) = D \cap (Arg (w) \times Arg (w))$ . Hence, the probability of a possible world w is given by the product of four contributions: (i) the product of the probabilities of the arguments belonging to w; (ii) the product of the terms one minus the probabilities of a, for each argument a not appearing in w; (iii) the product of the conditional probabilities of the defeats in w (recall that a defeat δ = (a, b) may appear in w only if both a and b are in w); (iv) the product of the terms one minus the conditional probabilities of d, for each defeat d not appearing in w while the arguments involved by d appear in w.

Example 4. Continuing our running example, the interpretation I for

F

is as follows. First of all, observe that, for each possible world

w \in pw (F)

, if both arguments b and c belong to Arg (w) and δ₂ ∉ Def (w) or δ₃ ∉ Def (w), then I (w) =0. The probabilities of the other possible worlds are the following:

I (w₁) =0.024	I (w₂) =0.216
I (w₃) =0.056	I (w₄) =0.006
I (w₅) =0.0504	I (w₆) =0.054
I (w₉) =0.4536	I (w₁₂) =0.014
I (w₁₆) =0.1134	I (w₁₉) =0.0126

Observe that the probabilities of the possible worlds sum up to 1. □

The probability that an argument a is credulously (resp. skeptically) acceptable according to a given semantics sem is defined as the sum of the probabilities of the possible worlds w for which a is credulously (resp. skeptically) acceptable according to sem, i.e., accC(w, sem, a) = true (resp. accS(w, sem, a) = true).

Definition 2. [ $\underset{F}{\Pr {CA}^{sem}} (a)$ and $\underset{F}{\Pr {SA}^{sem}} (a)$ ] Let $F = 〈 A,$ P_A, D, P_D〉 be a PrAAF, a ∈ A an argument, and sem a semantics. The probability $\underset{F}{\Pr {CA}^{sem}} (a)$ that a is credulously acceptable under sem is $\underset{F}{\Pr {CA}^{sem}} (a) = \sum_{w \in pwCAcc (F, a)} I (w),$ where $pwCAcc (F, a) = {w \in pw (F) |$ accC(w, sem, a) =true}, and the probability $\underset{F}{\Pr {SA}^{sem}} (a)$ that a is skeptically acceptable under sem is $\underset{F}{\Pr {SA}^{sem}} (a) = \sum_{w \in pwSAcc (F, a)} I (w),$ where $pwSAcc (F, a) = {w \in pw (F) |$ accS(w, sem, a) =true}

The following example shows usages of this definition.

Example 5. In our running example, the probabilities that the arguments a and b are credulously acceptable w.r.t. the admissible semantics are as follows:

$\begin{matrix} {\Pr CA}_{F}^{ad} (a) = & I (w_{2}) + I (w_{5}) + I (w_{6}) + I (w_{16}) + \\ I (w_{19}) = 0.4464 \end{matrix}$ $\begin{matrix} {\Pr CA}_{F}^{ad} (b) = & I (w_{3}) + I (w_{5}) + I (w_{9}) + I (w_{12}) + I (w_{16}) + \\ I (w_{19}) = 0.8134 \end{matrix}$ Moreover, the probabilities that the arguments a and b are skeptically acceptable w.r.t. the stable semantics are as follows:

${\Pr SA}_{F}^{st} (a) = I (w_{2}) + I (w_{5}) + I (w_{6}) + I (w_{19}) = 0.333$ ${\Pr SA}_{F}^{st} (b) = I (w_{3}) + I (w_{5}) + I (w_{9}) = . 56$ □

Obviously, computing $\underset{F}{\Pr {CA}^{sem}} (a)$ and $\underset{F}{\Pr {SA}^{sem}} (a)$ by directly applying Definition 2.3 would require exponential time, since it relies on summing the probabilities of an exponential number of possible worlds. However, this does not rule out the possibility that efficient strategies for computing $\underset{F}{\Pr {CA}^{sem}} (a)$ and $\underset{F}{\Pr {SA}^{sem}} (a)$ exist. Unfortunately, this is not true in the general case. Indeed, in the next section we show that the problem of computing $\underset{F}{\Pr {CA}^{sem}} (a)$ and $\underset{F}{\Pr {SA}^{sem}} (a)$ is FP^#P-complete in the cases when the problem is not trivial.

Definition 3. [P-CA^sem (a) and P-SA^sem (a)] Let $F = 〈 A,$ P_A, D, P_D〉 be a PrAAF, a ∈ A an argument, and sem a semantics. P-CA^sem (a) is the problem of computing the probability $\underset{F}{\Pr {CA}^{sem}} (a)$ and P-SA^sem (a) is the problem of computing the probability $\underset{F}{\Pr {SA}^{sem}} (a)$ .

3 Complexity of credulous and skeptical acceptability in probabilistic abstract argumentation

In this section we characterize the complexity of P-CA^sem (a) and P-SA^sem (a), by first showing that they are in FP^#P and then showing that they are FP^#P-hard. We do not address the cases of P-SA^sem (a) when sem is either the admissible or the ideal-set semantics as in these cases the empty set of argument is always an extension and therefore for any argument a it holds that PrSA^sem (a) =0.

3.1 Upper bound

Theorem 1. For sem ∈ {ad,st,co,gr,sst,pr,ids, ide}, it holds that P-CA^sem (a) and P-SA^sem (a) are in FP^#P.

Proof. We prove the statement for P-CA^sem (a). A similar reasoning can be applied for showing that P-SA^sem (a) is in FP^#P. First, observe that $\underset{F}{\Pr {CA}^{sem}} (a)$ with sem ∈ {ad, st, co, gr, sst, pr, ids, ide}, can be expressed as a rational number whose denominator d is the product of the denominators of the probabilities of arguments in A and defeats in D. This follows from the definition of $\underset{F}{\Pr {CA}^{sem}} (a)$ and the definition of I (w).

We first prove the statement for sem = semad. First observe that CA^sem (a) is in PTIME for sem = semad. We show that ${PrCA}_{F}^{ad} (a)$ can be computed by a polynomial time algorithm $A$ with access to a # P oracle. Algorithm $A$ first computes d in polynomial time w.r.t. the size of $F$ , then calls a # P oracle to determine the numerator of ${PrCA}_{F}^{ad} (a)$ . The oracle counts the number of accepting paths of a nondeterministic polynomial-time Turing machine M such that:

M nondeterministically guesses a subset of arguments in A and defeats in D so that each leaf of the resulting computation tree is a possible world $w \in pw (F)$ ;

At each leaf, let w be the guessed world, and I (w) its probability, the computation tree is then split again d · I (w) times to reflect the probability of the guessed world (for each $w \in pw (F)$ , I (w) is a rational number whose denominator is d, and I (w) can be computed in polynomial time w.r.t. the size of $F$ );

Finally, M checks in polynomial time if a is an acceptable argument in the world w w.r.t. the admissible semantics.

Thus, the number of accepting paths of M is

\sum_{w \in pwCAcc (F, a)} d \cdot I (w)

, that is

d \cdot \sum_{w \in pwCAcc (F, a)}

I (w), and, due to the definition of

{PrCA}_{F}^{ad} (a)

, d·

{PrCA}_{F}^{ad} (a)

. Hence, the number of accepting paths of M is the numerator n of

{PrCA}_{F}^{ad} (a)

. As a final step, algorithm

A

returns both n and d.

To prove the statement for sem ∈ {st, co, sst, pr, ids, ide} it suffices to reason analogously to the membership proof for the grounded semantics, by considering that CA^sem (a) for those semantics is either in PTIME, in NP, in $Θ_{2}^{p}$ , or in $\sum_{2}^{p}$ .

Specifically, for sem ∈ {st, co, sst, pr, ids, ide}, ${PrCA}_{F}^{sem} (a)$ can be computed by an algorithm $A'$ which behaves as follows. $A'$ first computes (in polynomial time) the denominator d of ${PrCA}_{F}^{sem} (a)$ . Then $A'$ invokes either a # P, # NP, $# Θ_{2}^{p}$ or $# \sum_{2}^{p}$ oracle that counts the number of accepting paths of a non-deterministic Turing machine M′ defined in the same way of M with the difference that the step (iii) of the computation of M is replaced by the invocation of either a PTIME, NP, $Θ_{2}^{p}$ or a $\sum_{2}^{p}$ oracle that checks whether a is an acceptable argument w.r.t. sem in the world w obtained as final leaf of the computation tree.

Therefore, since ${FP}^{# P} = {FP}^{# NP} = {FP}^{# Θ_{2}^{p}} = {FP}^{# \sum_{2}^{p}}$ , then P-CA^sem (a) is in FP^#P. □

3.2 Lower bound

To prove that P-CA^sem (a) is FP^#P-hard we show a reduction from the # P-hard problem # P2CNF, that is the problem of counting the number of satisfying assignments of a CNF formula where each clause consists of exactly 2 positive literals, to P-CA^sem (a).

Definition 4. [PrAAF and pw associated to φ and γ] Let φ = C₁ ∧ C₂ ∧ … C_k be a P2CNF, where X = {X₁, …, X_n} is the set of its propositional variables.

We define the PrAAF associated to φ $(F (φ) = 〈 A, P_{A}, D, P_{D} 〉)$ as follows:

A = {a, c₁, …, c_k, x₁, …, x_n};

D = {(c_i, a) | i ∈ [1 . . k]} ⋃ _{(C_h=X_i∨X_j)∈φ} {(x_i, c_h) , (x_j, c_h)};

P_A (a) =1.0, ∀i ∈ [1 . . k] P_A (c_i) =1.0, and $\forall j \in [1 . . n] P_{A} (x_{j}) = \frac{1}{2}$ ;

P_D (δ) =1.0 for each δ ∈ D.

Moreover, let γ be a truth assignment for the propositional variables x₁, …, x_n. We define as

w (γ, F (φ))

the possible world

w = 〈 A_{w}, D_{w} 〉 \in pw (F (φ))

defined as follows:

A_w = A \ {x_i | i ∈ [1 . . n] ∧ γ (x_i) =false};

D_w = D \ {(x_i, c_j) | i ∈ [1 . . n] ∧ j ∈ [1 . . k] ∧ γ (x_i) = false});

It is easy to see that given a possible world $w \in pw (F (φ))$ the probability of w is $I (w) = \frac{1}{2^{n}}$ . Moreover, it is straightforward to check that for each possible world $w \in pw (F (φ))$ there is a unique truth assignment γ such that $w = w (γ, F (φ))$ .

Example 6. Consider the P2CNF formula φ = (X₁ ∨ X₃) ∧ (X₂ ∨ X₃). The PrAAf $F (φ)$ is reported in Fig. 3(a), where probabilities different from 1.0 are reported next to each node and edge. Moreover, consider the truth assignment γ for X₁, X₂ and X₃ such that γ (X₁) =true, γ (X₂) =true and γ (X₃) =false. The possible world $w (γ, F (φ))$ is reported in Fig. 3(b). □

Fig. 3

Graphical representation of the PrAAF $F (φ)$ (a) and the possible world $w (γ, F (φ))$ (b).

Lemma 1. Let φ = C₁ ∧ C₂ ∧ … C_k be a P2CNF, where X = {X₁, …, X_n} is the set of its propositional variables. For each truth assignment γ for X₁, …, X_n it holds that CAw(γ, F(φ))sem ad(a) is true iff γ (φ) is true.

Proof. We first prove that for each truth assignment γ for X₁, …, X_n the fact that CAw(γ, F(φ))sem ad(a) is true implies that γ (φ) is true.

Reasoning by contradiction assume that there exists a truth assignment γ for X₁, …, X_n such that $w = w (γ, F (φ))$ and CAwsem ad(a) is true while γ (φ) is false.

Since CAwsem ad(a) is true there exists an admissible extension S for w such that a ∈ S. It is easy to see that S∩ {c₁, …, c_k} = ∅, as otherwise S would not be an admissible extension (S would not be conflict-free). Moreover, it is easy to see that there exists a subset {x_{i
₁}, …, x_{i
_h}} of {x₁, …, x_n} such that {x_{i
₁}, …, x_{i
_h}} ⊆ S and for each j ∈ [1 . . k] there is l ∈ [1 . . h] such that:

x_{i
_l} ∈ A_w, and

(x_{i
_l}, c_j) ∈ D_w,

as otherwise S would not be an admissible extension as there would be a c_j attacking a which is not attacked by any argument in S.

Since γ (φ) is false it must be the case that there is a j ∈ [i . . k] such that C_j = X_l ∨ X_h and γ (X_l) = γ (X_h) =false. This implies that x_l ∉ A_w, x_h ∉ A_w, (x_l, c_j) ∉ D_w and (x_h, c_j) ∉ D_w, thus contradicting the fact that S is an admissible extension. Hence, it holds that for each truth assignment γ for x₁, …, x_n the fact that CAw(γ, F(φ))sem ad(a) is true implies that γ (φ) is true.

We now prove that for each truth assignment γ for x₁, …, x_n the fact that γ (φ) is true implies that CAw(γ, F(φ))sem ad(a) is true. Reasoning by contradiction assume that there exists a truth assignment γ for x₁, …, x_n such that $w = w (γ, F (φ))$ and CAwsem ad(a) is false while γ (φ) is true.

Let S be the set of arguments {a} ∪ {x_i | i ∈ [1 . . n] ∧ γ (X_i) = true}. We show that S is an admissible extension reasoning by contradiction. Since S is not an admissible extension it must be the case that there is a j ∈ [1 . . k] such that C_j = X_h ∨ X_l and both x_h ∉ S and x_l ∉ S. Hence, by construction of S it holds that γ (X_h) = γ (X_h) = false which, in turn, implies that γ (φ) = false, thus contradicting that γ is a truth assignment γ for x₁, …, x_n such that γ (φ) is true. This implies that for each truth assignment γ for x₁, …, x_n the fact that γ (φ) is true implies that CAw(γ, F(φ))sem ad(a) is true. □

Lemma 2. Let φ = C₁ ∧ C₂ ∧ … C_k be a P2CNF, where X = {X₁, …, X_n} is the set of its propositional variables. For each truth assignment γ for X₁, …, X_n it holds that CAw(γ, F(φ))sem ad(a) is true iff CAw(γ, F(φ))sem(a), where sem ∈ {st, co, gr, sst, pr, ids, ide}, is true.

Proof. The if part is straightforward since stable, complete, grounded, semi-stable, preferred, ideal-set and ideal extensions are admissible extensions. As regards the proof of the only if part, reasoning by contradiction we assume that there is an admissible extension S such that a ∈ S and there is no extension S′ according to sem, where sem ∈ {st, co, gr, sst, pr, ids, ide}, such that a ∈ S′.

Consider the set of arguments $\hat{S} = S \cup (Arg (w) \cap {x_{1}, \dots, x_{n}})$ , and note that $Arg (w) \ \hat{S} = {c_{1}, \dots, c_{k}}$ . It is straightforward to see that, since S is an admissible extension then $\hat{S}$ is an admissible extension. Moreover, it is easy to see that (i) $\hat{S}$ is a stable extension since it defeats each argument in $Arg (w) \ \hat{S}$ , (ii) $\hat{S}$ is a complete extension since it contains all the argument that are acceptable w.r.t. $\hat{S}$ , (iii) $\hat{S}$ is a preferred extension since $\hat{S}$ is an admissible extension and any argument in $Arg (w) \ \hat{S}$ attacks an argument in $\hat{S}$ , so that for each argument $α \in Arg (w) \ \hat{S}$ it holds that $\hat{S} \cup α$ is not conflict-free. Moreover, observe that $\hat{S}$ is the unique preferred extension for w.

Furthermore, since $\hat{S}$ is a complete extension and since removing any argument from $\hat{S}$ make it loose the property that it contains all the arguments that are acceptable w.r.t. it, it holds that $\hat{S}$ is a grounded extension.

Moreover, since $\hat{S} \cup {\hat{S}}^{+} = Arg (w)$ then there is no complete extension $\bar{S}$ such that $\bar{S} \cup {\bar{S}}^{+} \supset \hat{S} \cup {\hat{S}}^{+}$ . Therefore, since $\hat{S}$ is a complete extension it follows that $\hat{S}$ is a semi-stable extension.

Finally, it is straightforward to see that $\hat{S}$ is an ideal-set and ideal extension for w as it is the unique preferred extension for w.

Hence, for possible world $w \in pw (F (φ))$ CAw(γ, F(φ))sem ad(a) is true only if CAw(γ, F(φ))sem(a) is true, where sem ∈ {st, co, gr, sst, pr, ids, ide}, which completes the proof. □

Theorem 2. For sem ∈ {ad, st, co, gr, sst, pr, ids, ide}, it holds that P-CA^sem (a) is FP^#P-hard.

Proof. Given an instance φ of # P2CNF, we construct an instance of P-CA^sem (a) by defining a PrAAF $F = F (φ)$ as in Definition 4, and we return $2^{n} \cdot (\underset{F}{\Pr {CA}^{sem}} (a))$ .

Since for each possible world $w \in pw (F (φ))$ we have that $I (w) = \frac{1}{2^{n}}$ , from Lemmas 1 and 2 it follows that $2^{n} \cdot (\underset{F}{\Pr {CA}^{sem}} (a))$ is the number of satisfying assignments of φ.

Hence, as the above described reduction from the # P-hard problem # P2CNF to P-CA^sem (a) is a Cook reduction [5], this suffices to prove that P-CA^sem (a) is FP^#P-hard, since a problem is FP^#P-hard iff it is # P-hard. □

Lemma 3.Let φ = C₁ ∧ C₂ ∧ … C_k be a P2CNF, where X = {X₁, …, X_n} is the set of its propositional variables.

For each truth assignment γ for X₁, …, X_n it holds that γ (φ) is true iff SAw(γ, FS (φ))sem(a), where sem ∈ {st, co, gr, sst, pr, ide}, is true.

Proof. We first prove that γ (φ) is true only if SAw(γ, FS (φ))sem(a), where sem ∈ {st, sst}, is true. We reason by contradiction assuming that γ (φ) is true but there is a set of argument $\hat{S}$ such that S is an extension for $w (γ, F_{S} (φ))$ according to sem and $a \notin \hat{S}$ . Lemma 1 and the fact that implies that γ (φ) is true imply that there is an admissible extension S for $w (γ, F_{S} (φ))$ such that a ∈ S. Observe that, for each j ∈ [1 . . k] c_j ∉ S as otherwise S will not be conflict-free (as a ∈ S). Consider the set of argument $S' = {a} \cup {x_{i} | i \in [1 . . n \land x_{i} appears in w (γ, F_{S} (φ))}$ . Since S is an admissible extension for $w (γ, F_{S} (φ))}$ and a ∈ S it holds that for each j ∈ [1 . . k] S defeats c_j and, in turn, S′ defeats c_j. More in detail the latter implies that for each j ∈ [1 . . k] the set $X = {x_{i} | i \in [1 . . n \land x_{i} appears in w (γ, F_{S} (φ))}$ defeats c_j.

We now prove that $\hat{s}$ is not an extension for $w (γ, F_{S} (φ))$ according to semst. Since a ∉ S it must be the case that there is a j ∈ [1 . . k] such that $c_{j} \in \hat{S}$ , as otherwise there will be an argument not belonging to $\hat{S}$ which is not defeated by $\hat{S}$ . Moreover, it must be the case that ∀i ∈ [1 . . n], $x_{i} \in \hat{S}$ since no argument in $w (γ, F_{S} (φ))$ attacks x_i. Hence $X \subseteq \hat{S}$ and therefore, for each j ∈ [1 . . k] it holds that $\hat{S}$ defeats c_j (as X defeats c_j), thus contradicting that $\hat{S}$ is a stable extension (as $\hat{S}$ contains at least a c_j and therefore is not conflict free). Thus, γ (φ) is true only if SAw(γ, FS (φ))sem st(a) is true. It is straightforward to see that the same reasoning can be applied for showing that γ (φ) is true only if SAw(γ, FS (φ))sem sst(a) is true.

We now prove that γ (φ) is true only if SAw(γ, FS (φ))sem(a), where sem ∈ {co, gr, pr, ide}, is true. To this end we show that $S' = {a} \cup {x_{i} | i \in [1 . . n \land x_{i} appears in w (γ, F_{S} (φ))}$ is the unique extension for $w (γ, F_{S} (φ))$ according to semco. First observe that every extension $\hat{S}$ for $w (γ, F_{S} (φ))$ according to semco is such that $\hat{S} \supseteq X$ (as otherwise there will be an argument which is acceptable for $\hat{S}$ which does not belong to $\hat{S}$ ). Moreover, since for each j ∈ [1 . . k], X defeats c_j it holds that $a \in \hat{S}$ as otherwise $\hat{S}$ does not contain an argument which is acceptable w.r.t. $\hat{S}$ . Hence, every extension $\hat{S}$ for $w (γ, F_{S} (φ))$ according to semco is such that $\hat{S} \supseteq S'$ . Finally, the latter implies that for each j ∈ [1 . . k], $c_{j} \notin \hat{S}$ , as otherwise $\hat{S}$ will not be conflict-free. Thus, for each extension $\hat{S}$ for $w (γ, F_{S} (φ))$ according to semco it holds that $\hat{S} = S'$ , thus showing that S′ is the unique extension for $w (γ, F_{S} (φ))$ according to semco.

The fact that S′ is the unique extension for $w (γ, F_{S} (φ))$ according to semco implies that S′ is the unique extension for $w (γ, F_{S} (φ))$ according to sem, where sem ∈ {gr, pr, ide}. Since a ∈ S′, the latter and the fact that S′ is the unique extension for $w (γ, F_{S} (φ))$ according to semco imply that γ (φ) is true only if SAw(γ, FS (φ))sem(a), where sem ∈ {co, gr, pr, ide}, is true.

As regards the proof of the if part, since Lemma 1 ensure that if CAw(γ, F(φ))sem ad(a) is true then γ (φ) is true, it suffices to show that if SAw(γ, FS (φ))sem(a), where sem ∈ {st, co, gr, sst, pr, ide}, is true then there is an admissible extension S such that a ∈ S. Reasoning by contradiction we assume that SAw(γ, FS (φ))sem(a), where sem ∈ {st, co, gr, sst, pr, ide}, is true and there is no admissible extension S such that a ∈ S. This implies that $S' = {a} \cup {x_{i} | i \in [1 . . n] \land x_{i} appears in w (γ, F_{S} (φ))}$ is not an admissible extension (as a ∈ S′). Since S′ is conflict free, it must be the case that there is a j ∈ [1 . . k] such that there is no argument $x \in X = {x_{i} | i \in [1 . . n \land x_{i} appears in w (γ, F_{S} (φ))}$ such that x attacks c_j. Consider the set $\hat{C} = {c_{j} | j \in [1 . . k] \land ∄ x \in X s . t . x attack c_{j}}$ . It is easy to see that the set $\hat{S} = X \cup \hat{C}$ is an extension according tosem, where sem ∈ {st, co, gr, sst, pr, ide}, and $a \notin \hat{S}$ , which contradicts the hypothesis that SAw(γ, FS (φ))sem(a) is true. Therefore SAw(γ, FS (φ))sem(a), where sem ∈ {st, co, gr, sst, pr, ide}, is true implies that γ (φ) is true. □

Theorem 3. For sem ∈ {st, co, gr, sst, pr, ide}, it holds that P-SA^sem (a) is FP^#P-hard.

Proof. Given an instance φ of # P2CNF, we construct an instance of P-SA^sem (a) by defining a PrAAF $F = F (φ)$ as in Definition 4, and we return $2^{n} \cdot (\underset{F}{\Pr {SA}^{sem}} (a))$ .

Since for each possible world $w \in pw (F (φ))$ we have that $I (w) = \frac{1}{2^{n}}$ , from Lemma 3 it follows that $2^{n} \cdot (\underset{F}{\Pr {SA}^{sem}} (a))$ is the number of satisfying assignments of φ.

Hence, as the above described reduction from the # P-hard problem # P2CNF to P-SA^sem (a) is a Cook reduction [5], this suffices to prove that P-SA^sem (a) is FP^#P-hard, since a problem is FP^#P-hard iff it is # P-hard. □

4 Related work

The main state-of-the-art approaches for handling uncertainty in AAFs by relying on probability theory can be classified in two categories, based on the way they interpret the probabilities of the arguments: those adopting the classical constellations approach [8 , 31] and those adopting the recent epistemic one [27 , 32]. As regards the epistemic approach, probabilities and extensions have different semantics, compared with the constellations approach. Specifically, the probability of an argument represents the degree of belief in the argument (the higher the probability, the more the argument is believed), and a key concept is the “rational” probability distribution, that requires that if the belief in an argument is high, then the belief in the arguments attacked by it is low. In this approach, epistemic extensions are considered rather than Dung′s extensions, where an epistemic extension is the set of arguments that are believed to be true to some degree. The interested reader can find a more detailed comparative description of the two categories in [25].

We now focus our attention on the approaches classified as constellations, as the complexity characterization provided in our work refers to this class of PrAAFs. [13] addressed the modeling of jury-based dispute resolutions, and proposed a PrAAF where uncertainty is taken into account by specifying probability distribution functions (pdfs) over possible AAFs and showing how an instance of the proposed PrAAF can be obtained by specifying a probabilistic assumption-based argumentation framework (introduced by themselves). In the same spirit, [31] defined a PrAAF as a pdf over the set of possible AAFs, and introduced a probabilistic version of a fragment of the ASPIC framework [30] that can be used to instantiate the proposed PrAAF. [9] addresses the problem of computing all the subgraphs of an AAF in which an argument a belongs to the grounded extension, and [10] extends it by focusing on computing the probability that an argument a belongs to the grounded extension of a probabilistic abstract argumentation framework. In particular, [10] assumes to receive a joint probability distribution over the arguments as input. In fact, providing a joint probability distribution usually means specifying the probability values for all the possible correlations, i.e., P (a), P (a ∧ b), P (a ∧ b ∧ c) . . . and so on. This is analogous to providing the probabilities for all the possible AAFs (since defeats are considered as certain).

Differently from [13 , 31] proposed a PrAAF where probabilities are directly associated with arguments and defeats, instead of being associated with possible AAFs, and independence among pairs of arguments/defeats is assumed. After claiming that computing the probability P^sem (S) that a set S of arguments is an extension according to sem requires exponential time for every semantics, [29] proposed a Monte-Carlo simulation approach to approximate P^sem (S). [8, 19] build upon [29]: [8] characterizes different semantics from the approach of [29] in terms of probabilistic logic, as a first step in the direction of creating a uniform logical formalization for all the proposed AAFs of the literature, in order to understand and compare the different approaches. [19], instead, showed that computing P^sem (S) is actually tractable for the admissible and stable semantics, but it is FP^#P-complete for other semantics, including complete, grounded, preferred and ideal-set. Furthermore, [20] proposed a Monte-Carlo approach to efficiently estimate P^sem (S) based on the polynomiality results of [19]. In [29], as well as in [13] and [31], P^sem (S) is defined as the sum of the probabilities of the possible AAFs where S is an extension according to semantics sem.

In the above-cited works, probability theory is recognized as a fundamental tool to model uncertainty. However, a deeper understanding of the role of probability theory in abstract argumentation was developed only later in [24, 25], where the justification and the premise perspectives of probabilities of arguments are introduced. According to the former perspective the probability of an argument indicates the probability that it is justified in appearing in the argumentation system. In contrast, the premise perspective views the probability of an argument as the probability that the argument is true based on the degrees to which the premises supporting the argument are believed to be true. Starting from these perspectives, in [25], a formal framework showing the connection among argumentation theory, classical logic, and probability theory was investigated. Furthermore, qualification of attacks is addressed in [26], where an investigation of the meaning of the uncertainty concerning defeats in probabilistic abstract argumentation is provided.

The computational complexity of computing extensions has been thoroughly investigated for classical AAFs [3 , 23] with respect to several semantics (a comprehensive overview of argumentation semantics can be found in [1]). In particular, [16] presents a number of results on the complexity of some decision questions for semi-stable semantics, while [14] focuses on ideal semantics; complexity results for preferred semantics can be found in [17].

Complexity results about skeptical and credulous acceptance under admissible, complete, grounded, stable and preferred semantics have been provided in [6 , 15], while [14] characterizes the complexity of skeptical and credulous acceptance under ideal and ideal-set.

5 Conclusion and future work

Focusing on the constellations approach with independence, as proposed in [29], in this paper we characterized the complexity of P-CA^sem (a) showing that it is FP^#P-complete independently from the adopted semantics. An interesting direction for future work is that of finding tractable cases for P-CA^sem (a) and/or P-SA^sem (a) by identifying structural properties of the argumentation graph that will ensure that P-CA^sem (a) and/or P-SA^sem (a) are solvable in polynomial time.

Footnotes

Assigning probability equal to 0 to arguments/defeats is useless.

References

Baroni

, Caminada

and Giacomin

, An introduction to argumentation semantics, Knowledge Eng Review26(4) (2011), 365–410.

Baroni

and Giacomin

, Semantics of abstract argument systems, In pp, Argumentation in Artificial Intelligence (2009), 25–44.

Booth

, Caminada

, Dunne

P.E.

, Podlaszewski

and Rahwan

, Complexity properties of critical sets of arguments, In Proc of Computational Models of Argument (COMMA), 2014, pp. 173–184.

Caminada

, Semi-stable semantics, In Proc Int Conf Computational Models of Argument (COMMA), 2006, pp. 121–130.

Cook

S.A.

, The complexity of theorem-proving procedures, In Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, Shaker Heights, Ohio, USA, 1971, pp. 151–158.

Coste-Marquis

, Devred

and Marquis

, Symmetric argumentation frameworks, In Proc of Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU) (2005), 317–328.

Dimopoulos

and Torres

, Graph theoretical structures in logic programs and default theories, Theor Comput Sci170(1-2) (1996), 209–244.

Doder

and Woltran

, Probabilistic argumentation frameworks - A logical approach, In Proc Int Conf on Scalable Uncertainty Management (SUM), 2014, pp. 134–147.

Dondio

, Computing the grounded semantics in all the subgraphs of an argumentation framework: An empirical evaluation, In Proc Int Workshop Computational Logic in Multi-Agent Systems (CLIMA), 2013, pp. 119–137.

10.

Dondio

, Toward a computational analysis of probabilistic argumentation frameworks, Cybernetics and Systems45(3) (2014), 254–278.

11.

Minh

D.P.

, On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games, Artif Intell77(2) (1995), 321–358.

12.

Dung

P.M.

, Mancarella

and Toni

, Computing ideal sceptical argumentation, Artif Intell171(10-15) (2007), 642–674.

13.

Dung

P.M.

and Thang

P.M.

, Towards (probabilistic) argumentation for jury-based dispute resolution, In Proc Int Conf Computational Models of Argument (COMMA), 2010, pp. 171–182.

14.

Dunne

P.E.

, The computational complexity of ideal semantics, Artif Intell173(18) (2009).

15.

Dunne

P.E.

and Bench-Capon

T.J.M.

, Coherence in finite argument systems, Artif Intell141(1/2) (2002), 187–203.

16.

Dunne

P.E.

and Caminada

, Computational complexity of semi-stable semantics in abstract argumentation frameworks, In Proc European Conf on Logics in Artificial Intelligence (JELIA), 2008, pp. 153–165.

17.

Dunne

P.E.

and Wooldridge

, Complexity of abstract argumentation, In Argumentation in Artificial Intelligence, 2009, pp. 85–104.

18.

Dvorák

and Woltran

, Complexity of semistable and stage semantics in argumentation frameworks, Inf Process Lett110(11) (2010), 425–430.

19.

Fazzinga

, Flesca

and Parisi

, On the complexity of probabilistic abstract argumentation frameworks, ACM Trans Comput Log (TOCL)16(3) (2015), 22.

20.

Fazzinga

, Flesca

and Parisi

, On efficiently estimating the probability of extensions in abstract argumentation frameworks, Int J Approx Reasoning69 (2016), 106–132.

21.

Fazzinga

, Flesca

, Parisi

and Pietramala

, PARTY: A mobile system for efficiently assessing the probability of extensions in a debate, In Proc Int Conf on Database and Expert Systems Applications (DEXA), 2015, pp. 220–235.

22.

Fazzinga

, Flesca

, Parisi

and Pietramala

, Computing or estimating extension’s probabilities over structured probabilistic argumentation frameworks, Special Issue on Probabilistic and other Quantitative Approaches to Computational Argumentation of the IfCoLog Journal of Logics and their Applications3(2) (2016), 177–200.

23.

Gaggl

S.A.

and Woltran

, The cf2 argumentation semantics revisited, J Log Comput23(5) (2013), 925–949.

24.

Hunter

, Some foundations for probabilistic abstract argumentation, In Proc Int Conf Computational Models of Argument (COMMA), 2012, pp. 117–128.

25.

Hunter

, A probabilistic approach to modelling uncertain logical arguments, Int J Approx Reasoning54(1) (2013), 47–81.

26.

Hunter

, Probabilistic qualification of attack in abstract argumentation, Int J Approx Reasoning55(2) (2014), 607–638.

27.

Hunter

and Thimm

, Probabilistic argumentation with epistemic extensions, In Proc Int Workshop on Defeasible and Ampliative Reasoning (DARe@ECAI), 2014.

28.

Hunter

and Thimm

, Probabilistic argumentation with incomplete information, In Proc European Conf. on Artificial Intelligence (ECAI), 2014, pp. 1033–1034.

29.

, Oren

and Norman

T.J.

, Probabilistic argumentation frameworks, In Proc Int Workshop on Theorie and Applications of Formal Argumentation (TAFA), 2011.

30.

Prakken

, An abstract framework for argumentation with structured arguments, Argument & Computation1(2) (2010), 93–124.

31.

Rienstra

, Towards a probabilistic dung-style argumentation system, In AT, 2012, pp. 138–152.

32.

Thimm

, A probabilistic semantics for abstract argumentation, In Proc European Conf on Artificial Intelligence (ECAI), 2012, pp. 750–755.

33.

Valiant

L.G.

, The complexity of computing the permanent, Theor Comput Sci (TCS)8 (1979), 189–201.