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

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.

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.

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

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.

It follows immediately that

The following simple lemma explains the interaction between i-supports for a statement and its complement.

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. ¬αi∈N). Therefore I∪N is inconsistent. From Lemma 3, it follows that I is an i-support of ¬s. Hence we could conclude ¬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.

Let I be a partial interpretation over S. Define

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

The following theorem shows that the grounded (resp. preferred) extensions of the simple argumentation frameworks capture the BW-grounded model (resp. BESWW-preferred models).

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.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}s∈S) 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 s∈S 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 σs≡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 ¬s, s∈S, 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.

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

TDΩ(Π)={s∈S∣there 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.5

Lemma 5.

Let Ω⊆S. The following equation holds:

lfp(TDΩ)={s∈S∣there is a support tree τ for s wrt D such that base(τ)⊆¬Ω}

Proof.

See Appendix A.2. □

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.