You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

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.

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 [57,2022]. 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 D0

a[a]b[¬a]
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 D0 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}, {¬a} provide justifications for a and ¬a respectively. Therefore there are two preferred models {a}, {¬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 D1

a[a]b[¬c,¬a]c[¬b,¬a]d[¬d]

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

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

Our results are represented in Fig. 1.

Fig. 1.

Classification of ADF semantics.

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 attAR×AR is the attack relation between arguments. An argument AAR attacks an argument BAR if (A,B)att. A is called an attacker of B if A attacks B.

A set of arguments SAR attacks B if there exists AS 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 FAF(S)={AARS defends A}.

Given an AF=(AR,att), a set of arguments SAR is

  • a stable extension of AF if it is conflict-free and attacks each argument AS;

  • 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 FAF);

  • a grounded extension of AF if it is the least complete extension (or equivalently the least fixed point of FAF).

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),

  • LS×S is a set of links,

  • C={Cs}sS is a set of total functions Cs:2par(s){in,out}, one for each sS.1

    Cs is called the acceptance condition of s.

The intuition of the acceptance condition Cs(X)=in (resp. Cs(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 ¬s, is accepted.

Let X be a set of statements.

A partial interpretation of X is a set of assertions of the form Π¬Ω such that Π,ΩX and ΠΩ= where ¬Ω={¬qqΩ}.

A full interpretation I of X is a partial interpretation of X such that for each statement sX, either s or ¬s belongs to I.

The set of all partial interpretations of X is denoted by PIX. Similarly, the set of all full interpretations of X is denoted by FIX.

A set KX¬X is said to be inconsistent if sX such that {s,¬s}K.

It is obvious that the acceptance function Cs of any ADF D=(S,L,C) could equivalently be defined as a total function Cs:FIpar(s){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}sS) 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

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}sS is a set of propositional formulas over S where acceptance function Cs is defined by:

    IFIpar(s):Cs(I)=iniffIσs

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 sS like in Examples 1, 2.

Let XS. The restriction on X of a partial interpretation I of S is defined by:

IX=I(X¬X)

Definition 2.

Let D=(S,C), C={σs}sS be an ADF and I=Π¬Ω, Π,ΩS, be a full interpretation of S.

I is said to be a model of D iff for each sS, Iσs iff sΠ.

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]:

ΓD(I)=Π¬ΩwhereΠ={sJFIS:if JI then Jσs}Ω={sJFIS:if JI then J¬σs}

Let IPIS, i.e. I be a partial interpretation of S, and σ be a propositional formula over S. We write

IσiffJFIS:if JIthen Jσ

Remark 3.

It is obvious that for each IPIS, for each sS, Iσs iff Ipar(s)σs.

Hence for each IPIpar(s) and each sS, Iσs iff JFIpar(s): if JI then Jσs.

The following lemma follows immediately from the definition of ΓD.

Lemma 1.

Let D=(S,{σs}sS) be an ADF and I be a partial interpretation of S. It holds that

ΓD(I)={sIσs}{¬sI¬σs}

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

Definition 3(i-supports).

A partial interpretation MPIpar(s) is said to be an immediate support (or just i-support for short) for s wrt ADF D=(S,{σs}sS) iff Mσs.

M is said to be an i-support for ¬s wrt D iff M¬σ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 ¬α.2

It follows immediately that

Lemma 2.

Let M be an i-support for an assertion α about a statement s. Then any partial interpretation IPIpar(s) such that MI, 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}sS) 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 ¬α, MN is inconsistent.

Proof.

The “only-if-direction” is obvious. We only need to prove the other direction.

Suppose for each i-support N of ¬α, MN is inconsistent. Therefore, for each full interpretation IFIpar(s) such that MI, I can not be an i-support of ¬α (otherwise MI=I is inconsistent, contradicting the fact that I is an interpretation).

Let α=s. Since I can not be an i-support of ¬α and ¬α¬s, I¬σs. Hence Iσs. Therefore Mσs, i.e. M is an i-support of α.

Let α=¬s. Since I can not be an i-support of ¬α and ¬αs, Iσs. Hence I¬σs. Therefore M¬σs, i.e. M is an i-support of ¬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,,αn} be a partial interpretation. Suppose we have accepted “arguments” (J1,α1),,(Jn,αn). Further let s be some statement such that each “argument” (N,s) supporting s, is “attacked” by some argument (Ji,αi) (i.e. ¬αiN). Therefore IN is inconsistent. From Lemma 3, it follows that I is an i-support of ¬s. Hence we could conclude ¬s.

Example 3.

Consider an ADF D=(S,{σs}sS), and σs=¬a¬b for some sS. It is obvious that any i-support for s contains either ¬a or ¬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 ¬a or ¬b, it is “attacked” by some argument in A. We hence would expect A to sanction the conclusion ¬s.

In other words, if each possible “argument” supporting s is “attacked” by accepted “arguments” then ¬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

Definition 4(Simple argumentation frameworks).

Let D=(S,C) be an ADF. The simple argumentation framework of D, denoted by SAFD=(SARD,sattD), is defined as follows:

  • 1. Each argument ASARD has one of the following forms:

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

    • (b) A=({¬s},¬s) where s is a statement from S.

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

    For any argument A=(B,α) from SARD, the conclusion and base of A, denoted by cnl(A) and base(A) respectively, are defined by cnl(A)=α and base(A)=B.

  • 2. An argument A from SARD attacks an argument B from SARD (i.e. (A,B)sattD) iff ¬cnl(A)base(B).

Remark 5.

For a set ASARD, cnl(A) denotes the set of all conclusions of arguments in A.

Example 4.

Let D0 be the ADF in Example 1.

  • SAFD=(SARD,sattD) where

    • SARD={A0,A1,B0,B1} where A0=[¬a], A1=({a},a), B0=[¬b], B1=({¬a},b).

    • sattD={(A0,A1),(A1,A0),(A1,B1),(B1,B0)}.

  • The grounded extension of SAFD is empty. The BW-grounded model is also empty.

  • There are two preferred extensions {A0,B1} and {A1,B0} whose conclusions correspond to the BESWW-preferred models {¬a,b} and {a,¬b} respectively.

Let I be a partial interpretation over S. Define

AI={ASARDbase(A)I}

Example 5.

Let us continue Example 4.

Let I0=. Then AI0=.

Let I1={¬a,b}. Then AI1={[¬a],({¬a},b)}={A0,B1}.

Let I2={a,¬b}. Then AI2={({a},a),[¬b]}={A1,B0}.

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

Theorem 1.

  • 1. Let A be a complete extension of SAFD. Then cnl(A) is a fixed-point of ΓD (and hence a BESWW-complete model of D).

  • 2. Let I be a BESWW-complete model of D (and hence a fixed-point of ΓD). Then AI is a complete extension of SAFD and cnl(AI)=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.

  • 1. Let M be the BW-grounded model of D and G be the grounded extension of SAFD. It holds that

    cnl(G)=M.

  • 2. Let M be the BESWW-preferred model of D. Then AM is a preferred extension of SAFD.

  • 3. Let E be a preferred extension of SAFD. 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}sS be an ADF and I=Π¬Ω, Π,ΩS, be a full interpretation of S.

The reduct of D wrt I [6] is the ADF DI=(Π,CI), CI={σs[false/x:xΩ]}sΠ.3

Remark 6.

Note that CI contains a formula σs[false/x:xΩ] only for sΠ.

Definition 5

Definition 5([6]).

I is said to be a stable model of D iff

  • 1. I is a model of D, and

  • 2. Π is the BW-grounded model of the reduct DI.

Example 6.

Consider the ADF D0 in Example 1 recalled below for ease of reference.

b[¬a]a[a]
Let I={¬a,b}. It is clear that I is a model of D. Further it is not difficult to see that Cb[false/a]true. Therefore DI={b[true]}. Obviously {b} is the BW-grounded model of DI. 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

a[¬b]b[a]
Let I={a,¬b}. It is not difficult to see that Ca[false/b]true. Therefore DI={a[true]}. Obviously {a} is the BW-grounded model of DI. 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=Π¬Ω 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 ΩS and D=(S,C).

The Ω-reduct of D is the ADF DΩ=(S,CΩ), CΩ={σs[false/r:rΩ]}sS.

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Ω] for each statement in S.

We next introduce a generalization of a well-known immediate-consequence operator in definite logic programming:

for ΠS:TD(Π)={sSΠσs}

It is clear that TD is monotonic.4

We next present an obvious but helpful lemma.

Lemma 4.

Let D=(S,C), C={σs}sS be an ADF and Π,ΩS such that ΠΩ=S and ΠΩ=. Further let σ be a propositional formula over S and I be a partial interpretation over Π. The following property holds:

Iσ[false/x:xΩ]iffI¬Ωσ

The following theorem captures the intuition of stable models explained shortly above.

Theorem 3.

Let D=(S,C), C={σs}sS be an ADF and M=Π¬Ω, Π,Ω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 TDΩ.

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=Π¬Ω s.t. Π is the least fixed point of TDΩ.

Example 8.

Consider again the ADF D0 in Example 1 recalled below for ease of reference.

b[¬a]a[a]
Let M={¬a,b} and Ω={a}.

It is not difficult to see that Cb[false/a]true and Ca[false/a]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

Definition 6(Support trees).

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

  • 1. the root is labeled by α;

  • 2. every non-leaf node N of τ is labeled by some statement sS such that if N has n children labeled by φ1,,φn then {φ1,,φn} is an i-support of s;

  • 3. every leaf-node of τ is labeled with some negative assertion ¬s¬S or a statement s with σstrue.

α 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 ¬s, sS, then τ consists only of its root that is labelled by ¬s. Abusing the notation for simplicity, we also denote such trees by [¬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 D1 in Example 2.

Fig. 2.

Support trees.

Support trees.

Let Ω,ΠS s.t. ΠΩ=. From Lemma 4 and the definition of the T-operator, it follows immediately that

TDΩ(Π)={sSthere is an i-support J of s wrt D such that J¬ΩΠ}5

There is a close connection between the least fixed point of TDΩ operator and the notion of support tree.

Lemma 5.

Let ΩS. The following equation holds:

lfp(TDΩ)={sSthere is a support tree τ for s wrt D such that base(τ)¬Ω}

Proof.

See Appendix A.2. □

4.3.Normal argumentation frameworks

Definition 7

Definition 7(Normal AFs).

Let D=(S,{σs}sS) be an ADF. Define the normal argumentation framework of D, denoted by AFD=(ARD,attD), as follows:

  • 1. ARD consists of all support trees wrt D.

  • 2. An argument A from ARD attacks an argument B from ARD (i.e. (A,B)attD) iff ¬concl(A)base(B).

Remark 10.

Note that there are no positive assertions in the base of any argument in ARD. Therefore arguments of the form [¬s] never attack any other arguments in ARD.

Example 9.

The normal argumentation framework AFD=(ARD,attD) of the ADF D1 in Example 2 is given by:

  • The arguments are given in Fig. 2.

  • attD={(B1,B0),(C1,C0),(B1,C1),(C1,B1),(D1,D0),(D1,D1)}.

The grounded extension is {A}.

There are two preferred extensions: {A,B1,C0}, {A,C1,B0}.

There is no stable extension.

We will show next that for any ADF D the stable extensions of the normal argumentation frameworks AFD capture the BESWW-stable models.

Theorem 4.

Let AFD be the normal argumentation framework of an ADF D=(S,C).

  • 1. Let M=Π¬Ω be a stable model of D. Then

    E={ττ is a support tree wrt D such that base(τ)¬Ω}
    is a stable extension of AFD.

  • 2. Let E be a stable extension of AFD. 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

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 AFD.

  • The raa-preferential semantics of D is defined by the set of preferred extensions of the normal argumentation framework AFD.

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,B1,C0}, {A,C1,B0}.

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.

Notes

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.

2 Note again that the complement of ¬s (resp. s) is s (resp. ¬s).

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

4 I.e. for ΠΠS:TD(Π)TD(Π).

5 It is obvious to see that sTDΩ(Π) iff Πσs[false/r:rΩ] iff Πpar(s)σs[false/r:rΩ] iff Πpar(s)¬Ωσs iff Πpar(s)¬(Ωpar(s))σs. It is clear that Πpar(s)¬(Ωpar(s)) is an i-support of s.

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.

Appendices

Appendix

A.1.Revised definition of stable models

Theorem 3.

Let D=(S,C), C={σs}sS be an ADF and M=Π¬Ω, Π,Ω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 TDΩ.

Proof.

  • 1. Suppose Π is the least-fixed point of TDΩ.

    Let xΩ. Since CΩ(x) contains only statements from Π, it is clear that either ΠCΩ(x) or Π¬CΩ(x) holds.

    Since Π is a fixed point of TDΩ, it follows that Π¬CΩ(x) holds. Thus, the following holds:

    (EQ)sS:ΠCΩ(s)iffsΠ
    • (a) We first show that M is a model of D.

      From the definition of CΩ(s) and Lemma 4, it follows that for each sS, sΠ iff ΠCΩ(s) iff MC(s).

      M is hence a model of D.

    • (b) Let M0= and Mk+1=ΓDM(Mk) and Π0= and Πk+1=TDΩ(Πk).

      We show by induction that for all k0, Mk=Πk.

      It is clear that M0=Π0. Suppose Mk=Πk. We show that Mk+1=Πk+1. From ΠiΠ for all i0, it follows immediately that Πk+1={sΠΠkCΩ(s)}.

      From the assertion (EQ) and Mk=ΠkΠ and CM(s)=CΩ(s) for sΠ, it follows that sΠ, Mk¬CΩ(s).

      From Mk+1={sΠMkCM(s)}{¬s¬ΠMk¬CM(s)}={sΠMkCΩ(s)}{¬s¬ΠMk¬CΩ(s)}={sΠΠkCΩ(s)}=Πk+1.

      Therefore Π=k0Mk.

    We have proved that M is a stable model of D.

  • 2. Suppose M is a stable model of D.

    Let M0= and Mk+1=ΓDM(Mk) and J0= and Jk+1=TDΩ(Jk).

    Since M is a stable model of D, Π=k0Mk.

    We show by induction that for all k0, Mk=Jk.

    It is clear that M0=J0. Suppose Mk=Jk.

    Mk+1={sΠMkCM(s)}.

    Since CM(s), sΠ, contains only statements from Π and CM(s)=CΩ(s), it follows immediately that Mk+1={sΠMkCM(s)}={sΠJkCΩ(s)}Jk+1.

    Suppose Mk+1Jk+1. Let sJk+1Mk+1. Therefore, JkCΩ(s). From Jk=MkΠ, it follows that ΠCΩ(s) and hence MC(s) (from Lemma 4). Since M is a model of D, it follows that sΠ. From Mk=Jk, and CM(s)=CΩ(s), it follows that MkCM(s). Thus sMk+1 (contradiction).

    From Π=k0Mk, it follows that Π=k0Jk. Hence Π is the least-fixed point of TDΩ. □

A.2.Stable models are stable extensions

Lemma 5.

Let ΩS. The following equation holds:

lfp(TDΩ)={sSthere is a support tree τ for s wrt D such that base(τ)¬Ω}

Proof.

  • 1. Let Πk=TDΩk(), k0. We show by induction that for each k0,

    Πk{sSthere is a support tree τfor s wrt D such that base(τ)¬Ω}.

    It is obvious that the inequality holds for k=0.

    Πk+1=TΩ(Πk)={sSthere is an i-support J of s wrt D such that J¬ΩΠk}.

    Let sΠk+1 and J be an i-support of s such that J={s1,,sn,¬ω1,,¬ωm} such that {s1,,sn}Πk and {¬ω1,,¬ωm}¬Ω.

    From the induction hypothesis, there are support trees τ1,,τn s.t. cnl(τi)=si and base(τi)¬Ω, 1in.

    Let τ be the tree with root labelled by s and let the children of the root be labelled by s1,,sn, ¬ω1,,¬ωm where s1,,sn are themself the roots of support trees τ1,,τn. It is obvious that τ is a support tree for s such that base(τ)¬Ω.

  • 2. We show lfp(TΩ){sSthere is a support tree τfor s wrt D such that base(τ)¬Ω}.

    Let τ be a support tree for sS such that base(τ)¬Ω.

    The height of τ denoted by h(τ), is the number of nodes of the longest path from the root to a node in τ.

    We prove by induction on h(τ) that slfp(TΩ).

    Let τ be a tree of height 0 and base(τ)¬Ω. It follows immediately that C(s)true. It is obvious that sTΩ().

    Let τ be a tree of height k+1 and base(τ)¬Ω.

    Let s1,,sn, ¬ω1,,¬ωm be the labels of the children of the root of τ. Let τ1,,τn be the subtrees of τ whose roots are the children s1,,sn of the root of τ. It is clear that the heights of τ1,,τn are less than or equal to k and their bases are subsets of ¬Ω. It follows from the induction hypothesis that silfp(TΩ), 1in. Therefore for each i, there is ji s.t. siTΩji(). Let j=max{j1,,jn}. Thus for each i, siTΩj().

    Since {s1,,sn,¬ω1,,¬ωm} is an i-support of s, it follows that sTΩj+1()lfp(TΩ). □

Theorem 4.

Let AFD be the normal argumentation framework of an ADF D=(S,C).

  • 1. Let M=Π¬Ω be a stable model of D. Then

    E={ττis a support tree wrt D such that base(τ)¬Ω}
    is a stable extension of AFD.

  • 2. Let E be a stable extension of AFD. Then cnl(E) is a BESWW-stable model of D.

Proof.

We apply Convention 1 in both parts of the proof.

  • 1. Let DΩ=(S,CΩ) and Πk=TDΩk().

    From Convention 1 and Lemma 5, it follows that the following equations hold:

    M=Π¬Ω=lfp(TΩ)¬Ω={sSthere is a support tree τ for s such that base(τ)¬Ω}¬Ω={cnl(τ)τ is a support tree such that base(τ)¬Ω}.

    It is clear that M=cnl(E).

    We show that E is a stable extension of AFD. From M=cnl(E), it is clear that E is conflict-free. Let XARDE. Therefore base(X)¬Ω. Thus there exists sΠ such that ¬sbase(X). Since M=cnl(E), there is an argument AE with cnl(A)=s. Therefore A attacks X.

    We have proved that E is a stable extension of AFD.

  • 2. Let ¬Ω={¬s[¬s]E}.

    We first show that for each support tree τ, the following assertion holds:

    (AS)τEiffbase(τ)¬Ω

    Let β be a support tree β such that base(β)¬Ω. Suppose βE. Therefore E attacks β. Hence τE such that τ attacks β. Therefore ¬cnl(τ)base(β)¬Ω. Hence [¬cnl(τ)]E. Thus E is not conflict-free (contradiction!). Therefore we have proved that if base(β)¬Ω, then βE.

    Suppose βE. It is easy to see that each attack against a subargument of β is an attack against β. Therefore all subarguments of the form [¬s] of β belong to E. Hence base(τ)¬Ω.

    Let M=Π¬Ω where Π={sSτE:cnl(τ)=s}. It follows immediately from assertion (AS) that

    Π={sSthere is support tree τ of s wrt D such that base(β)¬Ω}.

    From Lemma 5, lfp(TΩ)=Π. M is hence a stable model. □

A.3.BW-grounded and BESWW-preferred models are grounded and preferred extensions

Lemma 6.

Let I be a partial interpretation over S that is a fixed-point of ΓD. Furthermore let αI. Then there exists an argument (B,α)SARD such that BI.

Proof.

Let α=s, sS. Therefore Iσs. Let M=Ipar(s). It is clear that M is an i-support of s. Hence (M,s)SARD.

Let α=¬s. Obviously {¬s}I and ({¬s},s)SARD. □

Lemma 7.

Let A be a complete extension of SAFD. The following properties hold:

  • 1. cnl(A) is consistent.

  • 2. [¬s]A iff cnl(A)par(s) is an i-support of ¬s.

  • 3. Let (M,s)SARD, sS. It holds that (M,s)A iff Mcnl(A).

Proof.

  • 1. Suppose cnl(A) is inconsistent. Hence sS:{s,¬s}cnl(A). Therefore there are arguments of both form (M,s), [¬s] in A. Since (M,s) attacks [¬s], A is not conflict-free. Contradiction, as A is a complete extension.

  • 2. Let sS. Since A is complete, it holds that:

    [¬s]A iff

    • for each B=(X,s)SAFD, there exists XBA attacking B iff

    • for each B=(X,s)SAFD, there exists αcnl(A) such that ¬αX iff

    • for each B=(X,s)SAFD, cnl(A)X is inconsistent iff

    • for each B=(X,s)SAFD, MX is inconsistent where M=cnl(A)par(s) (since X is a partial interpretation of par(s)) iff

    • M is an i-support of ¬s (from Lemma 3).

  • 3.
    • (a) Let (M,s)A, sS. Let αM. We show that αcnl(A).

      There are two cases:

      • αS. Therefore [¬α] attacks (M,s). Since A is complete, there exists BA attacking [¬α]. It is obvious that cnl(B)=α. Hence αcnl(A).

      • α=¬t, tS. Let B be the set of all arguments of the form (X,t). It is clear that B contains all arguments attacking (M,s) at α. B also contains all arguments attacking [¬t]. Since A is complete, A attacks each BB. Therefore [¬t] is defended by A. Since A is complete, [¬t]A. Therefore α=¬tcnl(A).

      Therefore Mcnl(A).

    • (b) Let Mcnl(A). Let C be an attack against (M,s). Let β=cnl(C). There are two cases:

      • βS. Therefore ¬βMcnl(A). Therefore [¬β]A. Hence C attacks [¬β]. Since A is complete, there exists BA s.t. B attacks C.

      • β=¬t, tS (i.e. C=[¬t]). Therefore tMcnl(A). Therefore there exists BA s.t. cnl(B)=t. Hence B attacks C.

      We have proved that there exists BA s.t. B attacks C. Therefore A defends (M,s) against each attack against (M,s). Since A is complete, (M,s)A. □

Theorem 1.

  • 1. Let A be a complete extension of SAFD. Then cnl(A) is a fixed-point of ΓD.

  • 2. Let I be a partial interpretation over S that is a fixed-point of ΓD. Then cnl(AI)=I and AI is a complete extension of SAFD.

Proof.

  • 1. Let I=cnl(A). We show I=ΓD(I). Let αI.

    • α=¬s and sS. From Lemma 7, it follows immediately that:

      ¬sI iff [¬s]A iff Ipar(s) is an i-support of ¬s iff ¬sΓD(I).

    • α=s and sS. From Lemma 7, it follows immediately that:

      sI iff (M,s)A iff MI iff Ipar(s) is an i-support of s iff sΓD(I).

  • 2. Since I is a fixed point of ΓD, it is obvious from Lemma 6 that Icnl(AI).

    We show cnl(AI)I.

    Let ¬scnl(AI), sS. Hence [¬s]AI. Thus ¬sI (from the definition of AI).

    Let scnl(AI), sS. Hence (M,s)AI. Hence Mσs.

    From MI, it follows Iσs. Thus sI.

    We have proved that I=cnl(AI).

    • (a) We show that AI is admissible.

      Since I is consistent, AI is conflict-free.

      Let BSARD such that B attacks AI. We show that AI attacks B. There are two cases:

      • B=[¬r] for rS. Therefore B attacks an argument (M,s)AI. Thus rM. From the definition of AI, it follows MI. Hence rI. Since I is a fixed point of ΓD, it follows from Lemma 6 that there exists an argument C=(X,r)AI. Therefore C attacks B. Hence AI attacks B.

      • B=(N,r), rS. Therefore B attacks the argument [¬r]AI. From the definition of AI, it follows that ¬rI. Let Y=Ipar(r). Since I is a fixed point of ΓD, it is clear that Y¬σr. Therefore for any i-support J for r, JY is inconsistent. Since N is an i-support for r, NY is inconsistent. Let t be an assertion such that tY and ¬tN. From YI, it follows that tI. From Lemma 6 it follows that there exists argument AtAI such that cnl(At)=t. Hence At attacks B. Thus AI attacks B.

    • (b) Let A be an argument defended by AI. We show that AAI.

      There are two cases:

      • i. A=[¬z].

        Let B be the set of all arguments of the form (Z,z). It is clear that each argument in B attacks A. For each BB, there exists XBAI attacking B. Let N={cnl(XB)BB}cnl(AI)=I. It is clear that for each i-support J for z, NJ is inconsistent. Therefore N¬σz. From NI and I is a fixed point of ΓD, it follows ¬zI. Therefore A=[¬z]AI.

      • ii. A=(M,s).

        Let αM. We show that αcnl(AI). There are two cases:

        • αS. Therefore [¬α] attacks A. Therefore there exists an argument BAI s.t. cnl(B)=α. Hence αcnl(AI).

        • α=¬t and tS. Let A=[¬t]. It is clear that each attack against A is an attack against A. Hence A is defended by AI. From the previous case 2(b-i), we have A=[¬t]AI. Hence ¬tcnl(AI). We have proved αcnl(AI).

        Hence Mcnl(AI)=I. Hence AAI. □

Lemma 8.

Let E be a complete extension of SAFD. It holds that:

Acnl(E)=E

Proof.

Let sS.

[¬s]Acnl(E) iff ¬scnl(E) iff [¬s]E.

(M,s)Acnl(E) iff Mcnl(E) iff (from Lemma 7) (M,s)E. □

Theorem 2.

Let D be an ADF.

  • 1. Let M be the BW-grounded model of D and G be the grounded extension of SAFD. It holds that:

    cnl(G)=M.

  • 2. Let M be the BESWW-preferred model of D. Then AM is a preferred extension of SAFD.

  • 3. Let E be a preferred extension of SAFD. Then cnl(E) is a BESWW-preferred model of D.

Proof.

  • 1. Let G be the grounded extension of SAFD. From Theorem 1, cnl(G) is a fixed point of ΓD.

    Since M is the least fixed point of the ΓD, it follows that Mcnl(G). Therefore AMAcnl(G). From Lemma 8, Acnl(G)=G. From Theorem 1, it follows that AM is a complete extension. Since G is grounded, it follows that AM=G. From Theorem 1, it follows that cnl(AM)=M. Hence M=cnl(G).

  • 2. From Theorem 1, AM is a complete extension of SAFD. Let E be a preferred extension of SAFD s.t. AME. Therefore cnl(AM)cnl(E). Since M=cnl(AM) (Theorem 1), and cnl(E) is a fixed point of ΓD (Theorem 1), it follows that M=cnl(E). Therefore AM=Acnl(E)=E (Lemma 8) implying that AM is a preferred extension of SAFD.

  • 3. Let E be a preferred extension of SAFD. Then cnl(E) is a fixed point of ΓD. Let M be a preferred model of D s.t. cnl(E)M. Therefore Acnl(E)AM. From Acnl(E)=E (Lemma 8), it follows that E=AM. From cnl(AM)=M (Theorem 1), it follows that cnl(E)=cnl(AM) is a preferred model of D. □

References

[1] 

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

[2] 

P. Baroni, F. Cerutti, M. Giacomin and G. Guida, Encompassing attacks to attacks in abstract argumentation frameworks, in: ECSQARU, 2009, 2009, pp. 83–94.

[3] 

T.J.M. Bench-Capon and K. Atkinson, Abstract argumentation and values, in: Argumentation in AI, Springer Verlag, 2009.

[4] 

A. Bondarenko, P.M. Dung, R.A. Kowalski and F. Toni, An abstract, argumentation-theoretic approach to default reasoning, Artif. Intell. 93 (1997), 63–101. doi:10.1016/S0004-3702(97)00015-5.

[5] 

G. Brewka, P.E. Dunne and S. Woltran, Relating the semantics of abstract dialectical framework and standard AFs, in: Proc. IJCAI 2011, 2011.

[6] 

G. Brewka, S. Ellmauthaler, H. Strass, J.P. Wallner and S. Woltran, Abstract dialectical frameworks revisited, in: Proc. IJCAI/AAAI 2013, 2013.

[7] 

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

[8] 

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

[9] 

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] 

K. 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] 

M. Gelfond and V. 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 P. Mancarella, Preferred extensions are partial stable models, Journal of Logic Programming 14 (1992), 341–348. doi:10.1016/0743-1066(92)90015-U.

[16] 

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

[17] 

S. Nielsen and S. 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] 

D. Sacca and C. 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] 

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

[21] 

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

[22] 

H. 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] 

Y. Wu, M. 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.