AGM Meets Abstract Argumentation: Expansion and Revision for Dung Frameworks

1 Introduction

The goal of this paper is to bring together two important subareas of knowledge representation, namely belief revision and argumentation. Belief revision addresses the following question: given a knowledge base KB, represented in a suitable formal knowledge representation language, and a new piece of information I, what is the result of incorporating I into KB (the revision of KB with I)? This is nontrivial, as I may be inconsistent with KB. The most influential approach in this area is the AGM-theory of belief revision, named after its founders Alchourron, G¨ardenfors, and Makinson. AGMtheory was originally defined for classical propositional logic. It is based on 8 postulates for revision meant to prescribe the behaviour of rational revision operators. It also comprises an account of how such operators can be constructed based on so-called epistemic entrenchment orderings of formulas. In the meantime, AGM-style revision has been extended to default logic [Williams and Antoniou, 1998], description logics

∗We acknowledge support by DFG (BR 1817/7-1 and FOR 1513).

[Qi and Yang, 2008], Horn clause logic [Delgrande and Peppas, 2015], and logic programming [Delgrande et al., 2008; 2013].

Argumentation is based on the idea that reasoning with potentially conflicting information can adequately be modelled by (1) constructing arguments based on the available information, and (2) selecting an adequate subset of the generated arguments which, intuitively speaking, fit together in an adequate manner, thus representing a rational, coherent view of the issues at hand. In his seminal paper [Dung, 1995] Dung has shown that the second step, namely the selection of acceptable arguments, can be analyzed independently of the actual structure of the arguments. He introduced abstract argumentation frameworks (AFs) which are basically graphs representing attack relations among abstract arguments. A semantics then assigns to each AF a collection of argument sets, called extensions, which represent the different coherent views an agent may adopt based on the AF. Different intuitions about the extensions are captured in different semantics (we introduce 9 such semantics in the background section).

Although some work on AF revision already exists [Cayrol et al., 2010; Coste-Marquis et al., 2014a; 2014b], to the best of our knowledge this paper presents the first attempt to define AGM-style expansion 1 and revision operators which firstly, allow for the integration of arbitrary AFs and secondly, respect strong equivalence. The latter can be seen as the non-monotonic analogue of ordinary equivalence in classical logic since it respects the so-called substitution principle (cf. [Truszczynski, 2006] for more details).

To achieve this, several intermediate steps and theoretical foundations are necessary. In the following we list the decisive points also representing the main contributions of this paper:

1. Instead of using σ-extensions (which are the base for all other revision approaches available in the literature) we introduce the notion of k-models. Roughly speaking, a kmodel of an AF F corresponds to a dynamical evolvement of F respecting the non-redundant information of F.
2. 2.We then define satisfiability, (monotonic!) consequence and ordinary equivalence in terms of the newly introduced models which allows us to rephrase the AGM-postulates in a straightforward manner.

1 Contrary to revision, expansion just adds new information without taking care of inconsistency.

1. The reformulation respects strong equivalence as required since it turns out that (analogously to SE-models and logic programs) ordinary equivalence w.r.t. k-models matches strong equivalence.
2. In the next step we need an expansion operator for AFs. Whereas defining expansion for propositional logic is trivial, this turns out to be surprisingly difficult for AFs. The difficulty is to decide whether, and if so how, the intersection of k-models is realizable via a single AF. We provide a constructive method for expansion and study the question of realizability including characterization theorems.
3. Finally, we turn to revision. Due to realizability results we argue and show that classical distance-based approaches referring to the set of models are unsuitable. We then present a specific revision operator satisfying all postulates as well as a family of operators satisfying at least six of them.

The paper is organized as follows. Sect. 2 provides the necessary background on AFs as well as on AGM-theory. In Sect. 3 we introduce the family of Dung logics and perform a first analysis including realizability results. Sect. 4 introduces our expansion operator. Based on AF consequence and AF expansion, we can then reformulate in Sect. 5 the AGM postulates. Furthermore, we illustrate why usual semantical characterizations based on distance among models do not work for AFs, and we introduce a specific revision operator satisfying all 8 postulates. An outlook on further operators is presented as well. Sect. 6 discusses related work and concludes.

2 Background

2.1 Abstract Argumentation Theory

An argumentation framework (AF) is a pair F = (A,R). A, the set of arguments, is a finite subset of a fixed infinite background set U, and R ⊆ A × A. The set of all AFs is denoted by A . Given AFs F = (A, R) and F ′ = (A′ , R′ ) we write F ⊆ F ′ for A ⊆ A′ and R ⊆ R′ . Similarly, F ∪F ′ or F∆F ′ is defined component-wise. We say a attacks b in F whenever (a, b) ∈ R. An argument a ∈ A is defended by a set A′ ⊆ A in F if for each b ∈ A with (b, a) ∈ R, b is attacked by some a′ ∈ A′ in F. For a set E ⊆ A we use R+ F (E) or simply, E+ for E ∪ {b | (a, b) ∈ R, a ∈ E}. Furthermore, we say that a set A′ ⊆ A is conflict-free in F if there are no arguments a, b ∈ A′ such that a attacks b. The set of all conflict-free sets of an AF F is denoted by cf (F).

A semantics σ is a function which assigns to any AF F = (A, R) a set of sets of arguments denoted by σ(F ) ⊆ 2A. Each one of them, a so-called σ-extension, is considered to be acceptable with respect to F . We consider nine prominent semantics, namely admissible, complete, preferred, semi-stable, stable, stage, grounded, ideal and eager semantics (abbreviated by ad, co, pr, ss, stb, stg, gr, id and eg respectively). For recent overviews we refer the reader to [Baroni and Giacomin, 2009; Baroni et al., 2011].

Definition 1. Let F = (A,R) be an AF and E ⊆ A.

• 1.E ∈ ad(F) iff E ∈ cf (F) and E defends all its elements,
• 2.E ∈ co(F) iff E ∈ cf (F) and for any a ∈ A defended by E in F, a ∈ E,
• 3.E ∈ pr(F) iff E ∈ ad(F) and for no E′ ∈ ad(F), E ⊊ E′ ,
• E ∈ ss(F) iff E ∈ ad(F) and for no E′ ∈ ad(F), E+ ⊊ E′+,
• E ∈ stb(F) iff E ∈ cf (F) and E+ = A,
• E ∈ stg(F) iff E ∈ cf (F) and for no E′ ∈ cf (F), E+ ⊊ E′+,
• 7.E ∈ gr(F) iff E ∈ co(F) and for no E′ ∈ co(F), E′ ⊊ E,
• 8.E ∈ id(F) iff E ∈ ad(F), E ⊆ ⋂ pr(F) and there is no E′ ∈ ad(F) satisfying E′ ⊆ ⋂ pr(F) s.t. E ⊊ E′ ,
• 9.E ∈ eg(F) iff E ∈ ad(F), E ⊆ ⋂ ss(F) and there is no E′ ∈ ad(F) satisfying E′ ⊆ ⋂ ss(F) s.t. E ⊊ E′ .

It is well-known that for nonmonotonic formalisms standard notions of equivalence (possession of the same extensions) are insufficient to guarantee replaceability, and notions of strong equivalence are needed. Strong equivalence under some semantics σ (denoted ≡σE ) can be decided via so-called kernels. A kernel is a function k : A ↦→ A where each k(F) = F k is obtained from F by deleting certain redundant attacks. We call an AF F k-r-free iff F = F k . The following kernels will be used throughout the paper.

Definition 2. Given an AF F = (A,R) and a semantics σ. We define σ-kernels F k(σ) = (A, Rk(σ) ) whereby

1. Rk(stb) = R \ {(a, b) |a ̸= b, (a, a) ∈ R},
2. Rk(ad) = R \ {(a, b) |a ̸= b, (a, a) ∈ R, {(b, a), (b, b)} ∩ R ̸= ∅},
3. Rk(gr) = R \ {(a, b) |a ̸= b, (b, b) ∈ R, {(a, a), (b, a)} ∩ R ̸= ∅},
4. Rk(co) = R \ {(a, b) |a ̸= b, (a, a), (b, b) ∈ R},

We use K as a shorthand for {k (stb), k (ad ), k (gr ), k (co)}. Furthermore, the term any considered kernel (k) is an abbreviation for any considered kernel (k) introduced in Definition 2. Recent overviews on relations between different equivalence notions can be found in [Baumann and Brewka, 2013; 2015; Baumann, 2014a]. As already mentioned, kernels can be used to decide strong equivalence. Observe that one single kernel may serve for different semantics.

Theorem 1. [Oikarinen and Woltran, 2011; Baumann and Woltran, 2014] For any AFs F and G we have:

1. F ≡σE G ⇔ F k(σ) = G k(σ) for any σ ∈ {stb, ad, co, gr},
2. 2.F ≡τE G ⇔ F k(ad) = G k(ad) for any τ ∈ {pr, id, ss, eg} and
3. F ≡stg E G ⇔F k(stb) = G k(stb) .

2.2 Belief Change - AGM

Belief Change is extensively studied in the AI-community. The influential AGM-model [Alchourr´on et al., 1985] provides criteria addressing the problem of how current beliefs should be changed in the light of removing old or adding new beliefs. In the following we list 2 the famous eight postulates for the latter case, so-called belief revision.

• R1 K ∗ φ is a belief set,
• R2 φ ∈ K ∗ φ,
• R3 K ∗ φ ⊆ K + φ,

2 In the postulates, K ∗ φ is the result of revising a deductively closed set of sentences (a so-called belief set) K by a formula φ. Furthermore, K⊥ denotes the inconsistent belief set. K + φ, the expansion of K by φ, is Cn(K ∪ {φ}).

• R5 K ∗ φ = K⊥ ⇔ |= ¬φ,
• R6 |= φ↔ψ ⇒K ∗ φ = K ∗ ψ,
• R7 K ∗ (φ ∧ ψ) ⊆ (K ∗ φ) + ψ,

3 Monotonic Dung-Logics

In the following we introduce a family of monotonic logics, so-called Dung-logic. These logics formalize reasoning purely on the level of AFs, e.g., they allow us to determine whether one AF is a consequence of another. We therefore introduce the notion of a k-model which in turn determines an abstract consequence relation |=k constituting Lk Dung = (A , |=k ).

Our notion of a model may seem unusual at first. Intuitively, a k-model of F is any dynamic argumentation scenario respecting the information of F modulo redundancy, as encoded by k. This means, a k-model is itself an AF which satisfies at least the required information, but may have more information than encoded by F. Note that this is not as far from classical logic as it may seem: propositional models can be represented as formulas (namely as conjunctions of literals), and thus propositional formulas can be viewed as models of propositional formulas. Importantly, it turns out that ordinary equivalence w.r.t. Dung-logics, i.e. F |=k G and G |=k F, perfectly matches strong (!) equivalence w.r.t. certain semantics σ. This is crucial as it allows us to do classical AGM-style revision for the non-monotonic theory of abstract AFs.

We proceed with basic definitions and some first results.

Definition 3. Given an AF F and a set of AFs F. The set of k-models is defined as Mod k (F) = {G ∈ A | F k ⊆ G k } and Mod k (F) = ⋂F∈F Mod k (F ), respectively. We say

To simplify notation, we drop braces if F = {F}. The same applies to Definition 4. We state some first properties applying to all considered kernels. The empty framework F∅ = (∅, ∅) is k-tautological since F k ∅ = F∅. Furthermore, no other framework is k-tautological. Any single AF F is k-satisfiable since F k ⊆ F k . Whereas any infinite set of AFs F can be shown to be k-unsatisfiable the following examples show that finite sets may or may not be k -satisfiable. Moreover, satisfiability depends on the considered kernel k .

Example 1. Consider the following AFs F1, F2 and F3:

For all considered kernels and all i ∈ {1, 2, 3} we have F k i = Fi and obviously F1, F2 ⊆ F3. Consequently, F3 ∈ Mod k ({F1, F2}). Consider now F4, F5 and F6:

For any σ ∈ {ad, gr, co} we state that F = {F1, F4} is k(σ)-satisfiable since F k(σ) 1 , F k(σ) 4 ⊆ F k(σ) 6 = F6. Note that any potential k(stb)-model G of F must possess at least the attack (b, a) as well as the self-loop (b, b). In any case, (b, a) /∈ G k(stb) , i.e. F k(stb) 1 ̸⊆ G k(stb) proving the k(stb)-unsatisfiability of F. Similarly, one may verify Mod k ({F1, F5}) = ∅ for any considered kernel.

Having the different notions of a model at hand we may define the associated consequence relations and operations.

Definition 4. The k-consequence relation |=k ⊆ 2A × A is defined as follows: F |=k G iff Mod k (F) ⊆ Mod k (G). The k-consequence operation Cn k : 2A → 2A is given by: F ↦→ Cn k (F) = {G | F |=k G}. A Dung-logic Lk Dung is given by (A , |=k ) or (A , Cn k ), respectively.

The following proposition shows that the defined operations are indeed monotonic consequence operations, i.e. the conditions of a closure operator are satisfied.

We introduce the notion of ordinary equivalence as usual and prove the relation to strong equivalence.

Definition 5. Two AFs F,G are k-equivalent (for short, F ≡k G) iff F |=k G and G |=k F.

Theorem 3. For any AFs F and G we have:

Finally, we define realizability which is a decisive point for belief expansion as well as revision.

Definition 6. A set M is k-realizable iff there exists a set of AFs F such that Mod k (F) = M.

Note that the existence of k-tautological or k-unsatisfiable sets implies k-realizability of the set of all AFs A or ∅, respectively. The former is witnessed by the empty framework F∅ whereas the latter is exemplified by the AFs F1 and F5 depicted in Example 1. For convenience, we use ⊥ for a k-unsatisfiable "framework", i.e. Mod k (⊥) = ∅.

The question whether certain nontrivial sets are realizable is central for belief expansion as well as revision. Analogously to fragments of classical logic like Horn logic or 2-CNFs where sets of models are realizable if and only if certain properties are satisfied 3 we present the following characterization theorem for realizability. The decisive properties are very similar to so-called filters in the context of partial ordered sets (see [Davey and Priestley, 1990] for a very good introduction). Roughly speaking, the sets have to be upward closed and must possess a least element w.r.t. the subset relation. Note that both properties are relativised to kernels. Consequently, the "least" element is uniquely determined up to k-equivalence only.

3 For Horn logic we have closedness under intersection whereas in case of 2-CNFs closedness under majority operation is required (cf. [Marek, 2009] for more details).

Theorem 4. A setMis k-realizable iff

Due to space restrictions we stop our meta-logical considerations of Dung-logics at this point. An in-depth analysis will be done elsewhere. So far, we mention that all consequence relations are not finitary and furthermore, the logics neither possess the compactness property nor the Craig interpolation property (cf. [Barwise, 1982] for more information). It will be interesting to study whether the mentioned features are satisfied in case of infinite AFs. The main difficulty here is that abstract properties satisfied for finite AFs do not necessarily carry over to infinite ones. A systematic study has begun only recently (cf. [Baumann and Spanring, 2014] for an overview regarding existence and uniqueness of σ-extensions or [Baumann, 2014b, Section 4.1.3] for splitting properties).

4 Belief Expansion for Dung-logics

In the AGM-approach, belief expansion is prior to belief revision in the sense that the latter makes reference to the former. In classical logic, expansion is straightforward from a technical point of view since the intersection of the models can be simply realized by taking the conjunction of the given formulas. It is the main outcome of this section that even in case of Dung-logics the intersection of k-models is k-realizable by a single AF. Consider the following definition.

Note that k-expansion is defined semantically. In consideration of the characterization theorem for realizability (Theorem 4) it suffices to check whether the intersection of k -models satisfies upward-closedness as well as the existence of a least element. Whereas the first property is straightforward, the second one has to be shown one by one for each considered kernel. Moreover, we provide not only an existence result for k-expansions but a constructive one. More precisely, the k-expansion of two AFs can be defined via the union of their corresponding kernels, provided the intersection of their kmodels is non-empty:

We mention that the result can be generalized to arbitrary finite intersections of k-models representing iterative k-expansion. Before turning to an example, one final question in consideration of Theorem 5 must be answered, namely how to decide efficiently whether Mod k (F) ∩ Mod k (G) ̸= ∅, or equivalently, Mod k (F +k G) ̸= ∅. The following lemma transfers the semantical question of a non-empty intersection of k-models to a syntactic comparison of frameworks, namely in terms of k-r-freeness. This means, from now on we are equipped with a shortcut.

Example 2. Consider the following AFs F and G.

How does the k-expansion F +k G look like? In case of k = k(gr) we observe the k-r-freeness of F k ∪ G k . Due to Theorem 5 and Lemma 6 we have:

Finally, for any σ ∈ {stb, ad, co} one may check that F k(σ) ∪G k(σ) is not k(σ)-r-free implying that F+k(σ) G = ⊥.

We conclude this section by listing some (desirable) properties satisfied for k-expansion. Particularly noteworthy is the last property, namely that k-equivalence is even a congruence for k-expansion. This means, complete syntax independency is guaranteed.

Theorem 7. Given AFs F,G and H and let k ∈ K, then:

1. F +k G is an AF,
2. F +k G |=k G,
3. F |=k G ⇒F +k G ≡k F,
4. F |=k G ⇒F +k H |=k G +k H,
5. F ≡k G,H ≡k I ⇒F +k H ≡k G +k I .

5 Belief Revision for Dung-logics

In the AGM-model, belief revision is a more fine-grained operation than expansion since it provides us in addition with a meaningful result whenever the outcome of expansion is unsatisfiable. In the first part of this section we rephrase the classical AGM-axioms for Dung-logics. We then show and argue that standard distance-based methods as used in classical logic are inadequate in case of Dung-logics. This is mainly due to the fact that arbitrary sets of models may not be realizable, as shown in Theorem 4. We then proceed with a specific k(stb)-revision operator satisfying all required axioms. At the end of this section we briefly discuss and give an outlook for possible k-revision operators for the other kernels considered in this paper.

5.1 Postulates for Belief Revision

In the following we list k-revision axioms for AFs adopted from the AGM-model. In the following let F,G,H and I AFs.

• R1 F ∗k G is an AF,
• R2 F ∗k G |=k G,
• R3 F +k G |=k F ∗k G,
• R4 F +k G is k-satisfiable ⇒ F ∗k G |=k F +k G,
• R5 F ∗k G is k-satisfiable ⇔G is k-satisfiable,

Definition 8. A function ∗k : A ×A →A where (F,G) ↦→ F ∗k G is called a k-revision iff axioms R1-R8 are satisfied.

5.2 Standard Approaches are Problematic

One main assumption of belief revision is that of minimal change. More precisely, if we have to change our current beliefs we want to give up as few old beliefs as possible. In terms of models, this would amount to the following: revising an AF F by another framework G is given by an AF F ∗k G comprising those k-models of G that are closest to those of F. Indeed, for classical logic different notions of closeness have been provided via different distance-based approaches. These distances are often specified via the so-called symmetric difference ∆ (cf. [Dalal, 1988; Satoh, 1988; Winslett, 1988; Williams, 1994] among others). The following definition reflects a Satoh-like operation based on set containment.

Definition 9. Given two AFs F and G. We define k-

Satoh-operator F ◦kS G semantically via Mod k (F ◦kS G) = {H ∈ Mod k (G) | ∃I ∈ Mod k (F) s.t.,

Observe that some axioms like R2 and R3 are immediately clear by definition. Despite of this partial success, the following example shows that the Satoh-operator is not a suitable revision operator since the realizability of the required set of models is not guaranteed. This means, axiom R1 is violated.

Example 3. Let k = k(stb)4 . Consider the AFs F and G.

Observe that F and G are k-r-free. Consequently, any kmodel of F or G has to contain F or G, respectively. Hence, the self-loops (a, a) and (c, c) are included in any symmetric difference of k-models of F and G. Consider now F ′ and G ′ .

Observe that F ′ ∈ Mod k (G ◦kS F) since F ′ ∈ Mod k (F), G ′ ∈ Mod k (G) and F ′∆G ′ = {(a, a), (c, c)}. Moreover, if Mod k (G ◦kS F) is k-realizable, then it has to satisfy upwardsclosedness (statement 1, Theorem 4). Consequently, (F ′ )k = F has to be a k-model of G ◦kS F since (F ′ )k = ((F ′ )k )k . This is a contradiction since for any I ∈ Mod k (G) we have {(a, a), (a, b), (c, c)} ⊆ F∆I violating the ⊆-minimality.

The requirement of realizability is the main problem for approaches which define the revision operator semantically via distances between models. The semantical definition may select too few and too many models at the same time. Too few in the light of upward-closedness (as shown in Example 3) and too many in consideration of the requirement of the existence of a least element. More precisely, distances may select different minimal (w.r.t. kernel-relativised subset relation) models. We remark that even if realizability would be given or enforced 5 there are no compelling reasons why the remaining axioms should be satisfied for a distance-based approach. For instance, how to ensure compatibility between expansion and revision for distance-based approaches as required in axioms R7 and R8?

4 We mention that counter-examples can be given for all kernels considered in this paper.

5 This can be done via a subsequent procedure which completes (in the sense of upwards-closedness) the set of models and/or selects a certain minimal model.

5.3 ARevision Operator for k(stb)

In view of the problematic nature of defining a revision operator semantically, we pursue a different strategy in this section, namely constructing the result of revision syntactically. Consequently, in this case, axiom R1 is no longer problematic. to axioms R2 and R3 we have: F +k G |=k F ∗k G |=k G.

The construction is guided by the following reflections. Due Therefore, we deduce that the kernel of the revision has to be between the kernels of the new piece of information and the corresponding expansion. Formally, G k ⊆ (F ∗k G )k ⊆ (F +k G )k . Furthermore, due to axiom R4 we even have (F +k G )k ⊆ (F ∗k G )k if k-expansion is k-satisfiable. Fortunately, due to Lemma 6 and Theorem 5 we may infer even more, namely: Firstly, k-satisfiability of F +k G is fulfilled if F k ∪G k is k-r-free and secondly, if k-satisfiability is given, then F +k G is even k-realizable by F k ∪ G k . Altogether, G k ⊆ (F ∗k G )k ⊆ F k ∪G k . Consequently, a promising approach is to define F ∗k G as G k ∪X given that G ̸= ⊥ (axiom R5). Furthermore, due to the assumption of minimal change, the framework X should maintain as much information as possible of F . And finally, by axiom R6 the construction has to be insensitive w.r.t. k-equivalence. This means, only nonredundant information counts leading to X ⊆ F k . Note that there is no a priori reason for X being uniquely determined. Therefore we consider the set of maximal k-r-free frameworks first as defined in the following.

Definition 10. Given two AFs F and G. We define the set of maximal k-r-free sets w.r.t. F and G as follows:

In order to illustrate that Mk FG may indeed possess more than one element we give the following example.

Example 4. Consider the following two AFs F and G:

Observe that F and G are k-r-free for all considered kernels. In order to determineMk FG we have to check whether (a, a), (b, b) or both can be added to G without loosing k-r-freeness. The following three candidates have to be considered.

For σ ∈ {ad , co, gr } we obtain Mk (σ) FG = {I1, I2}, i.e. I1 and I2 are k(σ)-r-free. Furthermore,Mk(stb) FG = {I2}.

In consideration of the example above, one may start to think about other frameworks F and G witnessing the plurality of Mk (stb) FG . It is the surprising result of this section that this search will never succeed.

Due to this uniqueness result along with the considerations at the beginning of this subsection we are now equipped with a potential as well as uniquely determined candidate meeting the conditions of a revision function according to Definition 8.

It remains to be shown that this operator satisfies the postulates. The following theorem provides a positive answer:

We close this section by giving an example.

Example 5. Consider again the AFs F and G presented in Example 2. We already observed that F k ∪ G k is not k-rfree in case of k = k(stb). Consequently, F +k G does not provide a meaningful result (Lemma 6) in contrast to F ∗k G according to Definition 11.

Revising in reverse order results in the following framework.

5.4 Towards Revision Operators for Other Kernels

In order to obtain similar k-revisions in case of the admissible, grounded and complete kernel we have to deal with the plurality of Mk FG as demonstrated in Example 4. An obvious idea, namely introducing a selection function sel returning a suitable candidate fromMk FG , will be quickly sketched in the following.

Definition 12. Let k ∈ K. A k-sel-operator is a function ◦k sel : A ×A →A with (F,G) ↦→F ◦k sel G = sel (Mk FG ) where sel : 2A →A .

Which properties should sel satisfy with regard to R1-R8? The following proposition shows that the first six postulates are satisfied for any function sel , i.e. no further requirements are needed.

Proposition 10. Any k-sel -operator satisfies R1 - R6.

The fulfillment of axioms R7 and R8 requires further properties. For instance, a certain kind of subset-compatibility of sel appears to be necessary. More precisely, for two sets of AFs F and G where F ⊆ G and sel (G) ∈ F we should obtain sel (G) = sel (F). The study of sufficient conditions ensuring the last two axioms will be part of future work.

6 RelatedWork and Conclusions

In this paper we combined abstract argumentation with AGMlike belief change. To this end, we introduced a family of so-called Dung logics for reasoning over AFs under different semantics. We presented some initial meta-logical results for these logics including the issue of realizability. Since belief expansion is prior to belief revision we considered the former first. Although the semantic characterization of this operator was straightforward, the proof of the existence of corresponding AFs possessing the required sets of models turned out to be rather difficult. Finally, we studied the existence of revision operators respecting the rephrased AGM postulates. We presented a specific revision operator satisfying all postulates as well as a family of operators satisfying at least six of them.

Our approach shows some similarity with the way AGM revision was applied to logic programs under answer set semantics in [Delgrande et al., 2008]. Delgrande and colleagues used so-called SE-models, which were earlier developed in the context of the logic of here and there and which capture strong equivalence for logic programs. Here we introduced k-models, constituting Dung-logics, capturing strong equivalence for AFs. Note that although AFs can be interpreted as restricted sub-classes of logic programs it is not reasonable to consider revision of two AFs in the logic programming setup. To mention two reasons: firstly, strongly equivalent AFs are not necessarily strongly equivalent in the context of logic programs and secondly, the resulting revision may be realizable w.r.t. logic programs but not in case of AFs.

As mentioned in the Introduction, some earlier work on revising Dung AFs exists. The problem how the set of extensions changes if one single argument is added was studied in [Cayrol et al., 2010]. The related question whether it is possible (and if so how) to modify an AF in such a way that a desired set of arguments becomes an extension was considered in [Baumann and Brewka, 2010]. Both works did not consider AGM postulates. Interestingly, in [Cayrol et al., 2010] the authors noticed that AGM-style revision would require "... consistency and inference notions that are not explicitly present in an abstract argumentation system.". Our paper provides exactly these missing notions.

Coste-Marquis and colleagues propose a revision approach via axioms inspired by the AGM postulates [Coste-Marquis et al., 2014a]. Here, a revision operator maps an AF F together with a revision formula φ to a set of AFs. More precisely, the formula φ specifies which arguments are to be accepted and which are not. Then, a two step procedure is performed. Firstly, φ-compatible extensions which are as close as possible to former extensions of F are selected. Thereby, closeness is measured in terms of minimal change of argument statuses. Then, (due to realizability issues) the outcome of revision is a set of AFs, s.t. the union of their extensions consists of all selected extensions. Interestingly, the authors do not allow the addition of new arguments, i.e. revised AFs are obtained by modifying the attack relation only.

In a subsequent work by the same authors [Coste-Marquis et al., 2014b] a similar approach based on the translation of Dung frameworks to propositional logic is considered. This translation allows one to draw advantage of standard propositional revision operators. The main difference to the previous work is that the semantics of the revising formula changed from credolous to sceptical acceptance.

Regarding future work, an obvious next step is the further study of revision operators as briefly sketched in Sect. 5.4. Moreover, it would be interesting to apply our approach to recent generalizations of Dung AFs like extended argumentation frameworks (EAFs) [Modgil, 2009] or abstract dialectical frameworks (ADFs) [Brewka et al., 2013].