Representing the semantics of abstract dialectical frameworks based on arguments and attacks

Abstract

Abstract dialectical frameworks have been proposed as a generalization of the abstract argumentation frameworks. The semantics of abstract dialectical frameworks is defined by identifying different classes of models. In this paper, we show that the semantics of abstract dialectical frameworks could naturally be defined based on simple notions of arguments and attacks like in abstract argumentation. This insight allows us to adapt directly the semantical concepts in abstract argumentation to abstract dialectical frameworks that not only capture the standard semantics of abstract dialectical frameworks, but also suggest other new semantics based on the idea of “rejection as assumption” (raa) (similar to the concept of “negation as assumption” in assumption-based argumentation and logic programming) like the well-founded semantics or the raa-preferential semantics.

Keywords

Abstract argumentation abstract dialectical frameworks

1. Introduction

There are many generalizations of the abstract argumentation frameworks [9]. Cayrol and Lagasquie-Schiex [8] presented bipolar argumentation frameworks in which arguments can also support each other. Modgil [16], Baroni, Cerutti, Giacomin and Guida [2], Hanh, Dung, Hung and Thang [14], Gabbay [11] introduced attack on attacks on attacks. Nielsen and Parson [17] studied attacks from sets of arguments. Amgoud and Cayrol [1], Bench-Capon and Atkinson [3] introduced preferences between arguments. A prominent generalization of abstract argumentation is the abstract dialectical frameworks introduced by Brewka and Woltran [7]. There have been very active research on the semantics of ADFs [5–7,20–22]. The semantics of abstract dialectical frameworks are defined by identifying different classes of models that are fixed points of the Brewka and Woltran operator [6,7]. A closer look at the fixed-point-model-semantics of ADFs reveals that they could be characterized by how a justification (or argument) for the acceptance of a statement is viewed.

Example 1.
For illustration, consider the following ADF $D_{0}$ $\begin{matrix} a [a] b [\neg a] \end{matrix}$ stating that
a is accepted (resp. rejected) if a is accepted (resp. rejected), and

b is accepted (resp. rejected) if a is rejected (resp. accepted).

The semantics of $D_{0}$ depends on whether the condition “a is accepted (resp. rejected) if a is accepted (resp. rejected)” is considered vacuous or not.

If such condition is considered vacuous (as it is the case according to the stable semantics [6]), ${a}$ therefore does not provide any justification for accepting a. As there is no other justification for a, a is considered rejected and consequently b accepted.

In contrast, according to the semantics based on the fixed points of the Brewka–Woltran operator [6,7], the condition “a is accepted (resp. rejected) if a is accepted (resp. rejected)” is not viewed as vacuous and hence ${a}$ , ${\neg a}$ provide justifications for a and $\neg a$ respectively. Therefore there are two preferred models ${a}$ , ${\neg a}$ while the grounded model is empty.

The above discussion suggests that the semantics of ADFs is characterized by how the notion of a justification (or argument) for a statement is viewed.

In logic programming, stable models [13] arguably represent the most prominent approach to the negation-as-assumption view where negation-as-failure literals are viewed as assumptions [4,9,10]. Other approaches are the partial stable models, the three-valued stable models and the well-founded model [12,18,19]. It is well-known that all the four approaches could be captured by the extensions of argumentation frameworks whose arguments are proof trees constructed from the logic program rules where negation-as-failure literals are considered as assumptions [9,15,23].

As the stable models of ADFs [6] originate from stable models in logic programming, it indeed also adopts a similar view of “rejection as assumption” (raa) where rejected statements are viewed as assumptions. Formally, we will show that semantically, ADFs could be represented by argumentation frameworks referred to as normal argumentation frameworks, whose arguments are support trees for statements in ADFs where rejected statements are viewed as assumptions and the stable models of ADFs are captured by the stable extensions of normal argumentation frameworks. This insight sugests that the other extensions of the normal argumentation frameworks could be viewed as representing new semantics of ADFs where the grounded extension could be viewed as the most skeptical one that we refer to as well-founded semantics of ADFs to distinguish it from the BW-grounded model defined in [6], while the preferred extensions are referred to as “rejection-as-assumption” (raa)-preferential semantics.

It turns out that both the BW-grounded model defined in [7] as well as the BESWW-preferred models introduced in [6] are also naturally captured by the extensions of simple argumentation frameworks whose arguments are supports (or justifications) constructed directly from the acceptance conditions of statements in ADFs.
Example 2.
Consider the ADF $D_{1}$ $\begin{matrix} a [a] b [\neg c, \neg a] c [\neg b, \neg a] d [\neg d] \end{matrix}$

The BW-grounded model [7] is empty while the BESWW-preferred models [6] are ${a, \neg b, \neg c}$ , ${\neg a, \neg b, c}$ , ${\neg a, b, \neg c}$ .

There is no stable model. The well-founded semantics gives ${\neg a}$ . The raa-preferred semantics gives ${\neg a, \neg b, c}$ , ${\neg a, b, \neg c}$ .

Our results are represented in Fig. 1.

Fig. 1.
Classification of ADF semantics.

The paper is organized in 7 sections including this introduction. In the next section, we recall the key concepts of the AFs and ADFs. In the following section, we present the simple argumentation frameworks whose extensions capture the classes of BW-grounded and BESWW-complete models of ADFs. In Section 4, we first argue that the stable models of ADFs are based on a view of “rejection as assumption” by giving an equivalent characterization of them that reflect the view of “rejection as assumption” in a more direct way. We then proceed to show that stable models of ADFs are captured by stable extensions of normal argumentation frameworks with arguments being support trees whose leaves are labelled by assumptions represented by rejected statements. As an immediate consequence, we present two new semantics based on the grounded and preferred extensions of normal argumentation frameworks.We conclude in Section 5. We give the detailed proofs of the theorems and lemmas in the Appendix. We acknowledge the supports we got from the reviewers and colleagues in the Acknowledgements section.
2. Preliminaries

2.1. Argumentation framework

An abstract argumentation framework (AF) [9] is a pair $(AR, att)$ where $AR$ is a set of arguments and $att \subseteq AR \times AR$ is the attack relation between arguments. An argument $A \in AR$ attacks an argument $B \in AR$ if $(A, B) \in att$ . A is called an attacker of B if A attacks B.

A set of arguments $S \subseteq AR$ attacks B if there exists $A \in S$ such that A attacks B.

S defends A if S attacks each attacker of A.

S is conflict-free if it does not attack any of its own arguments.

S is admissible if it is conflict-free and defends each of its arguments.

The characteristic function of $AF$ is defined by $F_{AF} (S) = {A \in AR ∣ S defends A}$ .

Given an $AF = (AR, att)$ , a set of arguments $S \subseteq AR$ is

a stable extension of $AF$ if it is conflict-free and attacks each argument $A \notin S$ ;

a preferred extension of $AF$ if it is a maximal (wrt set inclusion) admissible set of arguments;

a complete extension of $AF$ if it is admissible and contains each argument it defends (or equivalently a conflict-free fixed point of $F_{AF}$ );

a grounded extension of $AF$ if it is the least complete extension (or equivalently the least fixed point of $F_{AF}$ ).

It is well-known that stable extensions are preferred extensions but not vice versa. While stable extensions may not exist, grounded extension and preferred extensions always exist.

2.2. Abstract dialectical framework (ADF)

An abstract dialectical framework (ADF) [7] is a triple $D = (S, L, C)$ where

S is a finite set of statements (positions, nodes),

$L \subseteq S \times S$ is a set of links,

$C = {C_{s}}_{s \in S}$ is a set of total functions $C_{s} : 2^{par (s)} \to {in, out}$ , one for each $s \in S$ .1

¹
$par (s)$ is the set of all parents of s where r is a parent of s if there is a direct link from r to s.

$C_{s}$ is called the acceptance condition of s.

The intuition of the acceptance condition $C_{s} (X) = in$ (resp. $C_{s} (X) = out$ ) is that when the statements in X are accepted (i.e. true) and those in $par (s) ∖ X$ are rejected (i.e. false) then s should be accepted (resp. rejected).

When s is rejected, we often say that the complement of s denoted by $\neg s$ , is accepted.

Let X be a set of statements.

A partial interpretation of X is a set of assertions of the form $Π \cup \neg Ω$ such that $Π, Ω \subseteq X$ and $Π \cap Ω = \emptyset$ where $\neg Ω = {\neg q ∣ q \in Ω}$ .

A full interpretation I of X is a partial interpretation of X such that for each statement $s \in X$ , either s or $\neg s$ belongs to I.

The set of all partial interpretations of X is denoted by ${PI}_{X}$ . Similarly, the set of all full interpretations of X is denoted by ${FI}_{X}$ .

A set $K \subseteq X \cup \neg X$ is said to be inconsistent if $\exists s \in X$ such that ${s, \neg s} \subseteq K$ .

It is obvious that the acceptance function $C_{s}$ of any ADF $D = (S, L, C)$ could equivalently be defined as a total function $C_{s} : {FI}_{par (s)} \to {in, out}$ .

Often it is convenient to represent the acceptance conditions as propositional formulas. For this reason and from now on, an ADF is represented as a pair $(S, {σ_{s}}_{s \in S})$ with $σ_{s}$ being a propositional formula where there exists a link from a node r to s if r appears in $σ_{s}$ [6].

Definition 1 ([6]).

An abstract dialectical framework (ADF) is a pair $D = (S, C)$ where

S is a finite set of statements (positions,nodes),

$C = {σ_{s}}_{s \in S}$ is a set of propositional formulas over S where acceptance function $C_{s}$ is defined by: $\begin{matrix} \forall I \in {FI}_{par (s)} : C_{s} (I) = in iff I ⊧ σ_{s} \end{matrix}$

Remark 1.
From now on, whenever we mention an ADF, we refer to the above Definition 1.
Remark 2.
We often present an ADF as a collection of expressions of the form $s [σ_{s}]$ , one for each $s \in S$ like in Examples 1, 2.

Let $X \subseteq S$ . The restriction on X of a partial interpretation I of S is defined by: $\begin{matrix} I ↓ X = I \cap (X \cup \neg X) \end{matrix}$
Definition 2.
Let $D = (S, C)$ , $C = {σ_{s}}_{s \in S}$ be an ADF and $I = Π \cup \neg Ω$ , $Π, Ω \subseteq S$ , be a full interpretation of S.

I is said to be a model of D iff for each $s \in S$ , $I ⊧ σ_{s}$ iff $s \in Π$ .

The semantics of ADFs are defined by identifying classes of models based on an operator $Γ_{D}$ , referred to as the BW-operator in this paper, defined on partial interpretation I as follows [6,7]: $\begin{array}{l} Γ_{D} (I) = Π \cup \neg Ω where \\ Π = {s ∣ \forall J \in {FI}_{S} : if J \supseteq I then J ⊧ σ_{s}} \\ Ω = {s ∣ \forall J \in {FI}_{S} : if J \supseteq I then J ⊧ \neg σ_{s}} \end{array}$

Let $I \in {PI}_{S}$ , i.e. I be a partial interpretation of S, and σ be a propositional formula over S. We write $\begin{matrix} I ⊧ σ iff \forall J \in {FI}_{S} : if J \supseteq I then J ⊧ σ \end{matrix}$
Remark 3.
It is obvious that for each $I \in {PI}_{S}$ , for each $s \in S$ , $I ⊧ σ_{s}$ iff $I ↓ par (s) ⊧ σ_{s}$ .

Hence for each $I \in {PI}_{par (s)}$ and each $s \in S$ , $I ⊧ σ_{s}$ iff $\forall J \in {FI}_{par (s)}$ : if $J \supseteq I$ then $J ⊧ σ_{s}$ .

The following lemma follows immediately from the definition of $Γ_{D}$ .
Lemma 1.
Let $D = (S, {σ_{s}}_{s \in S})$ be an ADF and I be a partial interpretation of S. It holds that $\begin{matrix} Γ_{D} (I) = {s ∣ I ⊧ σ_{s}} \cup {\neg s ∣ I ⊧ \neg σ_{s}} \end{matrix}$

As for any ADF D, $Γ_{D}$ is monotonic (wrt set inclusion), it has a least fixed point representing the BW-grounded model of D [7].

The BW-grounded model of D represents the most skeptical semantics of ADFs. More creduluous semantics are represented by the BESWW-complete models of D defined as the fixed points of $Γ_{D}$ [6]. The BESWW-preferred models of D are then defined as the maximal fixpoints of $Γ_{D}$ .

Stable semantics of ADFs is defined in [6] and will be recalled later.
3. Simple argumentation frameworks and fixed points of BW-operators

We present in this section the simple argumentation frameworks whose extensions capture the classes of BW-grounded and BESWW-complete models of ADFs.

We first introduce the concept of immediate supports of a statement.

Definition 3 (i-supports).

A partial interpretation $M \in {PI}_{par (s)}$ is said to be an immediate support (or just i-support for short) for s wrt ADF $D = (S, {σ_{s}}_{s \in S})$ iff $M ⊧ σ_{s}$ .

M is said to be an i-support for $\neg s$ wrt D iff $M ⊧ \neg σ_{s}$ .

Remark 4.
For convenience, we refer to statements or their complements (also often referred to as their negation) as assertions. A positive assertion about a statement s is s itself while a negative assertion about s is the negation of s. The complement of an assertion α is denoted by $\neg α$ .2
²
Note again that the complement of $\neg s$ (resp. s) is s (resp. $\neg s$ ).

It follows immediately that
Lemma 2.
Let M be an i-support for an assertion α about a statement s. Then any partial interpretation $I \in {PI}_{par (s)}$ such that $M \subseteq I$ , is also an i-support for α.

The following simple lemma explains the interaction between i-supports for a statement and its complement.
Lemma 3.
Let $D = (S, {σ_{s}}_{s \in S})$ be an ADF and α be an assertion about a statement s and M be a partial interpretation over $par (s)$ .

M is an i-support for α iff for each i-support N of $\neg α$ , $M \cup N$ is inconsistent.
Proof.
The “only-if-direction” is obvious. We only need to prove the other direction.

Suppose for each i-support N of $\neg α$ , $M \cup N$ is inconsistent. Therefore, for each full interpretation $I \in {FI}_{par (s)}$ such that $M \subseteq I$ , I can not be an i-support of $\neg α$ (otherwise $M \cup I = I$ is inconsistent, contradicting the fact that I is an interpretation).

Let $α = s$ . Since I can not be an i-support of $\neg α$ and $\neg α \equiv \neg s$ , $I ⊭ \neg σ_{s}$ . Hence $I ⊧ σ_{s}$ . Therefore $M ⊧ σ_{s}$ , i.e. M is an i-support of α.

Let $α = \neg s$ . Since I can not be an i-support of $\neg α$ and $\neg α \equiv s$ , $I ⊭ σ_{s}$ . Hence $I ⊧ \neg σ_{s}$ . Therefore $M ⊧ \neg σ_{s}$ , i.e. M is an i-support of $\neg s$ and hence M is an i-support of α. □

We can view an i-support J of an assertion α as an “argument” $(J, α)$ for α. Lemma 3 allows us to establish the attack relation between arguments.

Let $I = {α_{1}, \dots, α_{n}}$ be a partial interpretation. Suppose we have accepted “arguments” $(J_{1}, α_{1}), \dots, (J_{n}, α_{n})$ . Further let s be some statement such that each “argument” $(N, s)$ supporting s, is “attacked” by some argument $(J_{i}, α_{i})$ (i.e. $\neg α_{i} \in N$ ). Therefore $I \cup N$ is inconsistent. From Lemma 3, it follows that I is an i-support of $\neg s$ . Hence we could conclude $\neg s$ .
Example 3.
Consider an ADF $D = (S, {σ_{s}}_{s \in S})$ , and $σ_{s} = \neg a \lor \neg b$ for some $s \in S$ . It is obvious that any i-support for s contains either $\neg a$ or $\neg b$ . Suppose you have accepted a set $A$ of arguments such that both a and b are supported by some arguments in $A$ . Since any i-support for s contains either $\neg a$ or $\neg b$ , it is “attacked” by some argument in $A$ . We hence would expect $A$ to sanction the conclusion $\neg s$ .

In other words, if each possible “argument” supporting s is “attacked” by accepted “arguments” then $\neg s$ should be accepted. This insight allows us to give a rather simple argumentation frameworks whose extensions capture the BW-grounded and BESWW-complete models.
Definition 4 (Simple argumentation frameworks).

Let $D = (S, C)$ be an ADF. The simple argumentation framework of D, denoted by ${SAF}_{D} = ({SAR}_{D}, {satt}_{D})$ , is defined as follows:

Each argument $A \in {SAR}_{D}$ has one of the following forms:

$A = (M, s)$ where s is a statement from S and M is an i-support for s.

$A = ({\neg s}, \neg s)$ where s is a statement from S.

Note that arguments of the form $({\neg s}, \neg s)$ are often written as $[\neg s]$ .

For any argument

A = (B, α)

from

{SAR}_{D}

, the conclusion and base of A, denoted by

cnl (A)

and

base (A)

respectively, are defined by

cnl (A) = α

and

base (A) = B

An argument A from ${SAR}_{D}$ attacks an argument B from ${SAR}_{D}$ (i.e. $(A, B) \in {satt}_{D}$ ) iff $\neg cnl (A) \in base (B)$ .

Remark 5.
For a set $A \subseteq {SAR}_{D}$ , $cnl (A)$ denotes the set of all conclusions of arguments in $A$ .
Example 4.
Let $D_{0}$ be the ADF in Example 1.
${SAF}_{D} = ({SAR}_{D}, {satt}_{D})$ where

${SAR}_{D} = {A_{0}, A_{1}, B_{0}, B_{1}}$ where $A_{0} = [\neg a]$ , $A_{1} = ({a}, a)$ , $B_{0} = [\neg b]$ , $B_{1} = ({\neg a}, b)$ .

${satt}_{D} = {(A_{0}, A_{1}), (A_{1}, A_{0}), (A_{1}, B_{1}), (B_{1}, B_{0})}$ .

The grounded extension of ${SAF}_{D}$ is empty. The BW-grounded model is also empty.

There are two preferred extensions ${A_{0}, B_{1}}$ and ${A_{1}, B_{0}}$ whose conclusions correspond to the BESWW-preferred models ${\neg a, b}$ and ${a, \neg b}$ respectively.

Let I be a partial interpretation over S. Define $\begin{matrix} A_{I} = {A \in {SAR}_{D} ∣ base (A) \subseteq I} \end{matrix}$
Example 5.
Let us continue Example 4.

Let $I_{0} = \emptyset$ . Then $A_{I_{0}} = \emptyset$ .

Let $I_{1} = {\neg a, b}$ . Then $A_{I_{1}} = {[\neg a], ({\neg a}, b)} = {A_{0}, B_{1}}$ .

Let $I_{2} = {a, \neg b}$ . Then $A_{I_{2}} = {({a}, a), [\neg b]} = {A_{1}, B_{0}}$ .

The following theorem shows that the BESWW-complete models are captured by the complete extensions of the simple argumentation frameworks.
Theorem 1.

Let $A$ be a complete extension of ${SAF}_{D}$ . Then $cnl (A)$ is a fixed-point of $Γ_{D}$ (and hence a BESWW-complete model of D).

Let I be a BESWW-complete model of D (and hence a fixed-point of $Γ_{D}$ ). Then $A_{I}$ is a complete extension of ${SAF}_{D}$ and $cnl (A_{I}) = I$ .

Proof.
See Appendix A.3. □

The following theorem shows that the grounded (resp. preferred) extensions of the simple argumentation frameworks capture the BW-grounded model (resp. BESWW-preferred models). Theorem 2.
Let D be an ADF.
Let M be the BW-grounded model of D and G be the grounded extension of ${SAF}_{D}$ . It holds that $\begin{matrix} cnl (G) = M . \end{matrix}$

Let M be the BESWW-preferred model of D. Then $A_{M}$ is a preferred extension of ${SAF}_{D}$ .

Let E be a preferred extension of ${SAF}_{D}$ . Then $cnl (E)$ is a BESWW-preferred model of D.

Proof.
See Appendix A.3. □

4. Rejection as assumption and normal argumentation frameworks

We first argue that the stable models of ADFs are based on a view of “rejection as assumption” by giving an equivalent characterization of them that reflect the view of “rejection as assumption” in a more direct way.

We then proceed to show that stable models of ADFs are captured by stable extensions of normal argumentation frameworks with arguments being support trees whose leaves are labelled by assumptions represented by rejected statements. The insight suggests two new semantics based on the grounded and preferred extensions of normal argumentation frameworks.

4.1. Stable models of ADFs

Let $D = (S, C)$ , $C = {σ_{s}}_{s \in S}$ be an ADF and $I = Π \cup \neg Ω$ , $Π, Ω \subseteq S$ , be a full interpretation of S.

The reduct of D wrt I [6] is the ADF $D^{I} = (Π, C^{I})$ , $C^{I} = {σ_{s} [false / x : x \in Ω]}_{s \in Π}$ .3

³
$σ_{s} [false / x : x \in Ω]$ is the formula obtained from $σ_{s}$ by replacing each occurrence of statement $x \in Ω$ by the value false.

Remark 6.

Note that $C^{I}$ contains a formula $σ_{s} [false / x : x \in Ω]$ only for $s \in Π$ .

Definition 5 ([6]).

I is said to be a stable model of D iff

I is a model of D, and

Π is the BW-grounded model of the reduct $D^{I}$ .

Example 6.
Consider the ADF $D_{0}$ in Example 1 recalled below for ease of reference. $\begin{matrix} b [\neg a] a [a] \end{matrix}$ Let $I = {\neg a, b}$ . It is clear that I is a model of D. Further it is not difficult to see that $C_{b} [false / a] \equiv true$ . Therefore $D^{I} = {b [true]}$ . Obviously ${b}$ is the BW-grounded model of $D^{I}$ . Hence I is a stable model of D.

Looking at Definition 5, one may wonder whether the condition that I is a model of D could be dropped. The following example shows that the answer is no.
Example 7.
Let D be the ADF defined by $\begin{matrix} a [\neg b] b [a] \end{matrix}$ Let $I = {a, \neg b}$ . It is not difficult to see that $C_{a} [false / b] \equiv true$ . Therefore $D^{I} = {a [true]}$ . Obviously ${a}$ is the BW-grounded model of $D^{I}$ . But I is not a model of D and hence not a stable model of D.

The intuition of the stable models is rather simple: An interpretation $I = Π \cup \neg Ω$ is stable iff assuming that the statements in Ω are rejected (i.e. false) would lead to the acceptance of the statements in Π.

This idea can be formalized in two steps:

Construct a revised reduct of the ADF in which the statements in Ω are replaced by $false$ .

Show that the revised reduct derives exactly the statements in Π.

Let $Ω \subseteq S$ and $D = (S, C)$ .

The Ω-reduct of D is the ADF $D_{Ω} = (S, C_{Ω})$ , $C_{Ω} = {σ_{s} [false / r : r \in Ω]}_{s \in S}$ .
Remark 7.
Note that in contrast to reducts, the Ω-reducts have the same set of statements like the original ADFs and hence the acceptance function $C_{Ω}$ contains a formula $σ_{s} [false / r : r \in Ω]$ for each statement in S.

We next introduce a generalization of a well-known immediate-consequence operator in definite logic programming: $\begin{matrix} for Π \subseteq S : T_{D} (Π) = {s \in S ∣ Π ⊧ σ_{s}} \end{matrix}$

It is clear that $T_{D}$ is monotonic.4
⁴
I.e. for $Π \subseteq Π^{'} \subseteq S : T_{D} (Π) \subseteq T_{D} (Π^{'})$ .

We next present an obvious but helpful lemma.
Lemma 4.
Let $D = (S, C)$ , $C = {σ_{s}}_{s \in S}$ be an ADF and $Π, Ω \subseteq S$ such that $Π \cup Ω = S$ and $Π \cap Ω = \emptyset$ . Further let σ be a propositional formula over S and I be a partial interpretation over Π. The following property holds: $\begin{matrix} I ⊧ σ [false / x : x \in Ω] iff I \cup \neg Ω ⊧ σ \end{matrix}$

The following theorem captures the intuition of stable models explained shortly above. Theorem 3.
Let $D = (S, C)$ , $C = {σ_{s}}_{s \in S}$ be an ADF and $M = Π \cup \neg Ω$ , $Π, Ω \subseteq S$ , be a full interpretation of S. Let $D_{Ω} = (S, C_{Ω})$ .

M is a stable model of D iff Π is the least-fixed point of $T_{D_{Ω}}$ .
Proof.
See Appendix A.1. □
Convention 1.
For ease of reference and understanding, from now on, whenever we refer to a stable model of an ADF D, we mean a full interpretation $M = Π \cup \neg Ω$ s.t. Π is the least fixed point of $T_{D_{Ω}}$ .
Example 8.
Consider again the ADF $D_{0}$ in Example 1 recalled below for ease of reference. $\begin{matrix} b [\neg a] a [a] \end{matrix}$ Let $M = {\neg a, b}$ and $Ω = {a}$ .

It is not difficult to see that $C_{b} [false / a] \equiv true$ and $C_{a} [false / a] \equiv false$ . Therefore $D_{Ω} = {b [true], a [false]}$ . Obviously ${b}$ is the least fixed point of $D_{Ω}$ . Hence M is a stable model of D.

4.2. Support trees

The intuition of the “rejection-as-assumption” view is captured by considering arguments as support trees where rejected assignments label the leaves of the trees.

Definition 6 (Support trees).

A support tree for an assertion α w.r.t. an ADF $D = (S, {σ_{s}}_{s \in S})$ is a finite tree τ with nodes labeled by assertions from $S \cup \neg S$ such that

the root is labeled by α;

every non-leaf node N of τ is labeled by some statement $s \in S$ such that if N has n children labeled by $φ_{1}, \dots, φ_{n}$ then ${φ_{1}, \dots, φ_{n}}$ is an i-support of s;

every leaf-node of τ is labeled with some negative assertion $\neg s \in \neg S$ or a statement s with $σ_{s} \equiv true$ .

α is often referred to as the conclusion of τ and denoted by

cnl (τ)

. Furthermore the set of all negative assertions labeling the leaves of τ is called the base of τ and denoted by

base (τ)

Remark 8.
It is easy to see that if the conclusion of a support tree τ is a negative assertion $\neg s$ , $s \in S$ , then τ consists only of its root that is labelled by $\neg s$ . Abusing the notation for simplicity, we also denote such trees by $[\neg s]$ .
Remark 9.
The set of the conclusions of support trees belonging to a set E of support trees is denoted by $cnl (E)$ .

For illustration, Fig. 2 gives all support trees of the ADF $D_{1}$ in Example 2.

Fig. 2.
Support trees.

Let $Ω, Π \subseteq S$ s.t. $Π \cap Ω = \emptyset$ . From Lemma 4 and the definition of the T-operator, it follows immediately that $\begin{matrix} T_{D_{Ω}} (Π) = {s \in S ∣ there is an i-support J of s wrt D such that J \subseteq \neg Ω \cup Π}^{5} \end{matrix}$

There is a close connection between the least fixed point of $T_{D_{Ω}}$ operator and the notion of support tree.
⁵
It is obvious to see that $s \in T_{D_{Ω}} (Π)$ iff $Π ⊧ σ_{s} [false / r : r \in Ω]$ iff $Π \cap par (s) ⊧ σ_{s} [false / r : r \in Ω]$ iff $Π \cap par (s) \cup \neg Ω ⊧ σ_{s}$ iff $Π \cap par (s) \cup \neg (Ω \cap par (s)) ⊧ σ_{s}$ . It is clear that $Π \cap par (s) \cup \neg (Ω \cap par (s))$ is an i-support of s.

Lemma 5.
Let $Ω \subseteq S$ . The following equation holds: $\begin{matrix} lfp (T_{D_{Ω}}) = {s \in S ∣ there is a support tree τ for s wrt D such that base (τ) \subseteq \neg Ω} \end{matrix}$
Proof.
See Appendix A.2. □
4.3. Normal argumentation frameworks

Definition 7 (Normal AFs).

Let $D = (S, {σ_{s}}_{s \in S})$ be an ADF. Define the normal argumentation framework of D, denoted by ${AF}_{D} = ({AR}_{D}, {att}_{D})$ , as follows:

${AR}_{D}$ consists of all support trees wrt D.

An argument A from ${AR}_{D}$ attacks an argument B from ${AR}_{D}$ (i.e. $(A, B) \in {att}_{D}$ ) iff $\neg concl (A) \in base (B)$ .

Remark 10.
Note that there are no positive assertions in the base of any argument in ${AR}_{D}$ . Therefore arguments of the form $[\neg s]$ never attack any other arguments in ${AR}_{D}$ .
Example 9.
The normal argumentation framework ${AF}_{D} = ({AR}_{D}, {att}_{D})$ of the ADF $D_{1}$ in Example 2 is given by:
The arguments are given in Fig. 2.

${att}_{D} = {(B_{1}, B_{0}), (C_{1}, C_{0}), (B_{1}, C_{1}), (C_{1}, B_{1}), (D_{1}, D_{0}), (D_{1}, D_{1})}$ .

The grounded extension is ${A}$ .

There are two preferred extensions: ${A, B_{1}, C_{0}}$ , ${A, C_{1}, B_{0}}$ .

There is no stable extension.

We will show next that for any ADF D the stable extensions of the normal argumentation frameworks ${AF}_{D}$ capture the BESWW-stable models. Theorem 4.
Let ${AF}_{D}$ be the normal argumentation framework of an ADF $D = (S, C)$ .
Let $M = Π \cup \neg Ω$ be a stable model of D. Then $\begin{matrix} E = {τ ∣ τ is a support tree wrt D such that base (τ) \subseteq \neg Ω} \end{matrix}$ is a stable extension of ${AF}_{D}$ .

Let E be a stable extension of ${AF}_{D}$ . Then $cnl (E)$ is a stable model of D.

Proof.
See Appendix A.2. □

4.4. New “Rejection as assumption” (RAA) – Semantics

As stable models represent a credulous approach to semantics of ADFs based on the intuition of “rejected statements as assumptions”, there are other approaches based on different classes of extensions of the normal argumentation frameworks of the respective ADFs. For example, the set of preferred extensions define a new kind of credulous semantics generalizing the partial stable models in logic programming [15,19] while a new skeptical semantics for ADFs is defined by the grounded extension of their normal argumentation frameworks generalizing the well-founded semantics of logic programming [12].

Definition 8 (New semantics).

Let D be an ADF.

The well-founded semantics of D is defined by the grounded extension of the normal argumentation framework ${AF}_{D}$ .

The raa-preferential semantics of D is defined by the set of preferred extensions of the normal argumentation framework ${AF}_{D}$ .

Example 10.
Let us continue with Example 9. The well-founded semantics is represented by the grounded extension ${A}$ while the raa-preferential semantics is represented by the preferred extensions ${A, B_{1}, C_{0}}$ , ${A, C_{1}, B_{0}}$ .

Note that the stable semantics is not defined as there is no stable extension.

5. Discussion and conclusion

We have showed that the semantics of ADFs could naturally be based on arguments and attacks. In other words, semantically, ADFs could be viewed as instances of abstract argumentation. The new insight allows us to adapt the standard concepts of abstract argumentation to ADFs in a straightforward and intuitive way. It also suggests new natural semantics for ADFs like the well-founded semantics or the rejection-as-assumptions (raa)-preferential semantics. This is not unlike the situation in logic programming where the semantical concepts in abstract argumentation help to explain and unify the semantics of logic programming.

Footnotes

Acknowledgements

Many thanks to Gerhard Brewka and Hannes Strass for many very helpful comments, especially for pointing out a mistake in an earlier version of this paper. Many thanks to the anonymous reviewers 1, 2 for the critical and constructive comments and suggestions. Thanks also to Sarah Gaggl for her cooperative spirit.

Appendix

References

Amgoud and

Cayrol, Inferring from inconsistency in preference-based argumentation frameworks, J. Autom. Reasoning 29(2) (2002), 125–169. doi:10.1023/A:1021603608656.

Baroni,

Cerutti,

Giacomin and

Guida, Encompassing attacks to attacks in abstract argumentation frameworks, in: ECSQARU, 2009, 2009, pp. 83–94.

T.J.M.

Bench-Capon and

Atkinson, Abstract argumentation and values, in: Argumentation in AI, Springer Verlag, 2009.

Bondarenko,

P.M.

Dung,

R.A.

Kowalski and

Toni, An abstract, argumentation-theoretic approach to default reasoning, Artif. Intell. 93 (1997), 63–101. doi:10.1016/S0004-3702(97)00015-5.

Brewka,

P.E.

Dunne and

Woltran, Relating the semantics of abstract dialectical framework and standard AFs, in: Proc. IJCAI 2011, 2011.

Brewka,

Ellmauthaler,

Strass,

J.P.

Wallner and

Woltran, Abstract dialectical frameworks revisited, in: Proc. IJCAI/AAAI 2013, 2013.

Brewka and

Woltran, Abstract dialectical frameworks, in: Proc. of KR 2010, AAAI Press, 2010, pp. 102–111.

Cayrol and

Lagasquie-Schiex, Bipolar abstract argumentation system, in: Argumentation in AI, Springer Verlag, 2009.

P.M.

Dung, On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games, Artif. Intell. 77(2) (1995), 321–358. doi:10.1016/0004-3702(94)00041-X.

10.

Eshghi and

R.A.

Kowalski, Abduction compared with negation by failure, in: Logic Programming: Proceedings of the Sixth International Conference, The MIT Press, Cambridge, and Massachusetts, 1989, pp. 234–254.

11.

D.M.

Gabbay, Equational approach to argumentation networks, Argument and Computation 3(2–3) (2012), 87–142. doi:10.1080/19462166.2012.704398.

12.

A.V.

Gelder,

K.A.

Ross and

J.S.

Schlipf, The well-founded semantics for general logic programs, J. of ACM 38(3) (1991), 630–650.

13.

Gelfond and

Lifschitz, The stable model semantics for logic programming, in: Proc. of 5th ICLP, MIT Press, 1988, pp. 1070–1080.

14.

D.D.

Hanh,

P.M.

Dung,

N.D.

Hung and

P.M.

Thang, Inductive defence for skeptical semantics of extended argumentation, J. of Logic and Computation 21(2) (2011), 307–349. doi:10.1093/logcom/exq018.

15.

A.C.

Kakas and

Mancarella, Preferred extensions are partial stable models, Journal of Logic Programming 14 (1992), 341–348. doi:10.1016/0743-1066(92)90015-U.

16.

Modgil, Reasoning about preferences in argumentation frameworks, Artif. Intell. 173(9–10) (2009), 901–934. doi:10.1016/j.artint.2009.02.001.

17.

Nielsen and

Parsons, A generalization of Dung’s abstract framework for argumentation: Arguing with sets of attacking argments, in: Argumentation in Multi-Agent Systems, LNCS, Vol. 4766, 2006, pp. 54–73. doi:10.1007/978-3-540-75526-5_4.

18.

T.C.

Przymunsinski, The well-founded semantics coincides with the three-valued stable semantics, Fundamenta Informaticae 13(4) (1990), 445–463.

19.

Sacca and

Zaniolo, Stable models and nondeterminism for logic programs with negation, in: Proc. of the ACM SIGMOD-SIGACT Symposium on Principles of Database Systems, 1990, pp. 205–217.

20.

Strass, Approximating operators and semantics of abstract dialectical frameworks, Artificial Intelligence 205 (2013), 39–70.

21.

Strass, Expressiveness of two-valued semantics for ADF, JAIR (2015).

22.

Strass and

P.W.

Wallner, Analyzing the computational complexity of abstract dialectical frameworks via approximation fixpoint theory, Artificial Intelligence 226 (2015), 34–74. doi:10.1016/j.artint.2015.05.003.

23.

Wu,

Caminada and

D.M.

Gabbay, Complete extensions in argumentation coincide with 3-valued stable models in logic programming, Studia Logica 93 (2009), 383–403. doi:10.1007/s11225-009-9210-5.

Representing the semantics of abstract dialectical frameworks based on arguments and attacks

Abstract

Keywords

1. Introduction

2.1. Argumentation framework

2.2. Abstract dialectical framework (ADF)

1 par ( s ) is the set of all parents of s where r is a parent of s if there is a direct link from r to s.

Definition 3 (i-supports).

4.1. Stable models of ADFs

3 σ s [ false / x : x ∈ Ω ] is the formula obtained from σ s by replacing each occurrence of statement x ∈ Ω by the value false.

Definition 6 (Support trees).

Definition 7 (Normal AFs).

Definition 8 (New semantics).

Footnotes

Acknowledgements

Appendix

References

¹
$par (s)$ is the set of all parents of s where r is a parent of s if there is a direct link from r to s.

³
$σ_{s} [false / x : x \in Ω]$ is the formula obtained from $σ_{s}$ by replacing each occurrence of statement $x \in Ω$ by the value false.