# forgetting_an_argument__66a8628f.pdf

The Thirty-Fourth AAAI Conference on Artiﬁcial Intelligence (AAAI-20)

Forgetting an Argument

Ringo Baumann Department of Computer Science Leipzig University Germany

Dov Gabbay Department of Informatics King s College London United Kingdom

Odinaldo Rodrigues Department of Informatics King s College London United Kingdom

The notion of forgetting, as considered in the famous paper by Lin and Reiter in 1994 has been extensively studied in classical logic and more recently, in non-monotonic formalisms like logic programming. In this paper, we convey the idea of forgetting to another major AI formalism, namely Dungstyle argumentation frameworks. Our approach is axiomaticdriven and not limited to any speciﬁc semantics: we propose semantical and syntactical desiderata encoding different criteria for what forgetting an argument might mean; analyze how these criteria relate to each other; and check whether the criteria can be satisﬁed in general. The analysis is done for a number of widely used argumentation semantics. Our investigation shows that almost all desiderata are individually satisﬁable. However, combinations of semantical and/or syntactical conditions reveal a much more interesting landscape. For instance, we found that the ad hoc approach to forgetting an argument, i.e., by the syntactical removal of the argument and all of its associated attacks, is too restrictive and only compatible with the two weakest semantical desiderata. Amongst the several interesting combinations identiﬁed, we showed that one satisﬁes a notion of minimal change and presented an algorithm that given an AF F and argument x, constructs a suitable AF G satisfying the conditions in the combination.

1 Introduction

Hiding relevant information as well as discarding irrelevant information are tasks which are performed by humans in a straightforward way. The need for a formalisation of the latter was recognised by Lin and Reiter in the context of reasoning about actions (Lin and Reiter 1994). Lin and Reiter were concerned about how to update a given knowledge base to remove (or forget ) facts which no longer remained true after actions were executed. Since then the topic, usually referred to as forgetting (and also known as variable elimination), has been extensively studied in the ﬁeld of knowledge representation and reasoning for many major formalisms like propositional logic, ﬁrst order logic and description logics as well as non-monotonic formalisms such as answer set programming (see (Eiter and Kern-Isberner 2018; Delgrande 2017; Gonc alves, Knorr, and Leite 2016a) for recent overviews). Applications of forgetting include query

Copyright 2020, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

answering, belief update and decision making (see (Lang, Liberatore, and Marquis 2003) for more details). Forgetting for a logical formalism can be roughly described as follows. Given a knowledge base K in this formalism and a variable x deemed irrelevant, the result of forgetting x in K is a knowledge base K , s.t.

LR1. The variable x does not occur in K .

LR2. All logical consequences of K are logical consequences of K.

LR3. All logical consequences of K that do not contain x are logical consequences of K .

Lin and Reiter showed that (LR1) (LR3) can be fulﬁlled via a simple syntactic transformation. For the case of propositional logic, a possible construction dating back to (Boole 1854) involves replacing every formula φ in K with the disjunction of the formulas obtained from φ by substituting x by true and false, respectively. In this paper we study the notion of forgetting in the realm of Dung s Abstract Argumentation Frameworks (AFs) (Dung 1995), in which one of the chief concerns is the handling of conﬂicts amongst arguments. A large number of semantics expressing acceptable positions for AFs (so-called extensions) have been subsequently introduced (see (Baroni, Caminada, and Giacomin 2018) for a good overview). In recent years, the community started to investigate the effects of changes to an argumentation framework. One extensively studied issue is the so-called enforcing problem (Baumann and Brewka 2010; de Saint-Cyr et al. 2016; Wallner, Niskanen, and J arvisalo 2017), which is concerned with how to manipulate an argumentation framework in such a way that a certain desired set of arguments becomes an extension. Another closely related line of research is the principle-based study of revision operators (Coste-Marquis et al. 2014; Baumann and Brewka 2015; Diller et al. 2018) based on a reformulation of the famous AGM postulates for belief revision (Alchourr on, G ardenfors, and Makinson 1985). Perhaps surprisingly, how to forget single arguments has not yet received much attention. The most straightfoward way of forgetting an argument is simply by removing it from the argumentation framework (as considered in (Bisquert et al. 2011)). Whilst such a syntactical approach obviously guarantees that the extensions of the resulting AF

will not contain the argument, it leaves the precise semantical relationship between the input and output frameworks unclear. The following motivating examples show some undesired effects of the syntactical removal of arguments and some possible alternatives. For an overview of argumentation semantics and reasoning modes, see Section 2. Example 1 (Forgetting Everything Credulously Accepted). The graph below represents two AFs F and Fx, s.t. x is an argument in F but not in Fx. The preferred extensions of F are {x,b} and {x,c}. Hence, b and c are credulously accepted in F. The syntactical removal of x guarantees the semantical removal of x but has the side-effect that neither the credulous acceptance of b nor that of c survive since Fx s sole preferred extension is empty.

If we were to delete the argument a1 in addition to x we would preserve the credulous acceptance of b and c since the preferred extensions of (Fx)a1 would be {b} and {c}. Example 2 (Forgetting Everything Sceptically Accepted). F s sole preferred extension is {a,x,d1,d3}, and hence the arguments a, x, d1, and d3 are all sceptically accepted under the preferred semantics. The removal of x does not preserve any sceptical acceptance since Fx s sole preferred extension is empty. If we were to delete the argument a in-

x c d1 d2 d3

stead, we would still be able to forget x semantically as well as to preserve the sceptical acceptance of d1 and d3 since the preferred extensions of Fa would be {b1,d1,d3} and {b2,d1,d3}. Example 3 (Accepting the Unacceptable). The unique preferred extension of F is {a,x}. The syntactical removal of x replaces the former extension with {a,c}. This means that the removal prevents the acceptance of x but yields the sceptical and credulous acceptance of c (previously unaccepted).

If we were to ﬁnd an argument n which attacked both x and c and added it to F, then we would end up with the unique preferred extension {a} = {a,x} {x} which precisely does the job in terms of both acceptance modes.

The objective of the examples above is not to show how to achieve the syntactical/semantical removal of an argument, as there are multiple possibilities, but rather that we need to reason about possible constraints on the result of the forgetting operation. The rest of the paper is organized as follows. We provide some background material in Section 2. This is followed by our main contributions, summarised below.

Inspired by forgetting in other logical formalisms we identify reasonable semantical and syntactical properties for Dung-style AFs, and then show how they relate to each other. (Section 3)

We then analyze the individual and joint satisﬁability of conditions. We consider all 24 suitable combinations of syntactical and semantical criteria and identify that 9 are non-trivial combinations that are simultaneously satisﬁable. Moreover, we identify -minimal sets of conditions that are not simultaneously satisﬁable. These unsatisﬁable sets represent general restrictions on the simultaneous satisﬁablity of forgetting desiderata. (Section 4)

We then single out one promising combination under one of the most important argumentation semantics, namely the stable semantics, and provide a sound algorithm that given any AF F will compute an updated AF F satisfying the conditions in the combination as well as a particular notion of minimal change to the AF. (Section 5)

The paper concludes with a discussion, comparisons with related work and directions for future work in Section 6.

2 Background Argumentation Theory Argumentation Frameworks and Semantics

In what follows, we ﬁx an inﬁnite background set U. An abstract argumentation framework (AF) (Dung 1995) is a directed graph F = (A,R) where A U is a set of arguments and R A A represents attacks between them. This means, for a,b A, if (a,b) R we say that a attacks b or a is an attacker of b. Moreover, a set E defends an argument a if any attacker of a is attacked by some argument of E. In this paper we consider ﬁnite AFs only and use the symbol F to denote the set all ﬁnite AFs. Moreover, for a set E A we use E + for {b (a,b) R,a E} and deﬁne E = E E+. Given an AF F = (B,S), we use A(F) to refer to the set B and R(F) to refer to the relation S. For two AFs F and G, we deﬁne the expansion of F by G, in symbols F G, as expected: F G = (A(F) A(G),R(F) R(G)). Finally, the restriction of an AF F to a set of arguments C U is deﬁned as F C = (A(F) C,R(F) (C C)). An extension-based semantics σ F 22U is a function which assigns to any AF F a set of sets of arguments σ(F) 2A(F). Each set of arguments E σ(F) is considered to be acceptable with respect to F and is called a σ-extension. The most basic requirements of an extension are called conﬂict-freeness (cf ) and admissibility (ad). Other well-studied semantics include stage (stg), stable (stb), semi-stable (ss), complete (co), preferred (pr), grounded (gr), ideal (il) and eager (eg). The requirements

of each semantics are summarised below. A recent overview of argumentation semantics can be found in (Baroni, Caminada, and Giacomin 2018). Deﬁnition 1. Let F = (A,R) be an AF and E A. 1. E cf (F) iff for no a,b E, (a,b) R, 2. E ad(F) iff E cf (F) and E defends all its elements, 3. E co(F) iff E ad(F) and for any a A defended by E, a E, 4. E stg(F) iff E cf (F) and for no I cf (F),E I ,

5. E stb(F) iff E cf (F) and E = A, 6. E ss(F) iff E ad(F) and for no I ad(F),E I , 7. E pr(F) iff E co(F) and for no I co(F), E I, 8. E gr(F) iff E co(F) and for any I co(F), E I, 9. E il(F) iff E co(F), E pr(F) and there is no I co(F) satisfying I pr(F) s.t. E I, 10. E eg(F) iff E co(F), E ss(F) and there is no I co(F) satisfying I ss(F) s.t. E I. In this paper, we consider the semantics 4 10, that is, the term considered semantics is used as a shorthand for the stage, stable, semi-stable, preferred, grounded, ideal and eager semantics.

Deﬁnedness, Acceptance and Realizability If σ(F) for any F F, then we say that the semantics σ is universally deﬁned, otherwise we say that σ collapses. All considered semantics are universally deﬁned, with the exception of the stable semantics. This means that there are AFs F s.t. stb(F) = . If σ(F) = 1, for any F F, then we say that σ is uniquely deﬁned. The grounded, ideal and eager semantics are uniquely deﬁned (cf. (Baumann and Spanring 2015) for an overview). With respect to the acceptability of arguments, we consider two standard reasoning modes. Given a semantics σ, an AF F, and an argument a A(F), we say that a is credulously accepted w.r.t. σ if a σ(F) and that a is sceptically accepted w.r.t. σ if σ(F) and a σ(F). We say that a set of sets E 2U is realizable w.r.t. a semantics σ if there is an AF F s.t. σ(F) = E. In this paper, we frequently use the facts that for any of the considered semantics a realizable set E has to be a -antichain and that only the stable semantics may realize , due its ability to collapse (Dunne et al. 2015).

3 Desiderata for Forgetting As already mentioned in Section 1, apart from simply removing an argument and all attacks involving it (Bisquert et al. 2011), the notion of forgetting in AFs has never been considered in a principled way as done in (Lin and Reiter 1994) and (Eiter and Wang 2008) for classical logic or logic programming, respectively. We start our investigation by proposing reasonable/desirable properties of a forgetting operation. Given an AF F and an argument x U, we use forgetσ(F,x) to denote the set of AFs representing suitable candidate AFs for the result of forgetting the argument x in F under the semantics σ. Formally, it is a function

forgetσ F U 2F mapping a pair (F,x) to a subset forgetσ(F,x) of F. Whenever the semantics σ and the AF F are clear from the context, we will omit them and simply speak about forgetting x. The notion of suitability will be made precise via the following three blocks of desiderata, each considering a different aspect of the problem. We want to emphasize that the following lists do not express any preference amongst the desiderata. In practice, different criteria will apply to different contexts and there may be very good reasons to pick one criterium over another. The ﬁrst two blocks are semantical in nature: e1 e4 concern the relationship between the old and the new set of extensions of the AF and r1 r4 deal with properties regarding sceptical and credulous reasoning. Finally, s1 s3 are purely syntactical. If a function forgetσ always returns at least one suitable AF G w.r.t. desideratum d (i.e. forgetσ(F,x) 1 for any F F and x U), we say that forgetσ satisﬁes d or that the desideratum d is satisﬁable under σ. Desiderata 1. Given an AF F and an argument x U. For G forgetσ(F,x) we require:

e1. σ(G) = {E {x} E σ(F)}, (Reiter condition) e2. for any AF H , s.t. x A(H ) we have: σ(G H ) = {E {x} E σ(F H )}. (strong Reiter condition) e3. σ(G) = {T(E) E σ(F)} with T σ(F) 2U and E T(E) E {x} (weak Reiter condition) e4. σ(G) = σ(F) {E E σ(F),x E} (remove x-contaminated extensions)

e1 requires that the only argument to be removed from any of the previous extensions is x itself (if x is in the extension). This so-called Reiter condition can be strengthened (e2) or weakened (e3) as follows. e2 stipulates that the Reiter condition carries over to any future expansion of F by an AF H which does not contain x. e3 weakens e1 in the sense that it allows other arguments besides x to be removed from each of the previous extensions. Finally, e4 stipulates that the extensions of the new AF should be exactly those in σ(F) that do not contain x. Desiderata 2. Given an AF F and an argument x U. For G forgetσ(F,x) we require: r1. x σ(G) (x is not scept. accepted) r2. x σ(G) (x is not cred. accepted) r3. σ(G) = ( σ(F)) {x} (rigid scept. acceptance) r4. σ(G) = ( σ(F)) {x} (rigid cred. acceptance) The ﬁrst two desiderata r1 and r2 say that the argument x should not be sceptically (resp., credulously) accepted after it is forgotten. r3 and r4 strengthen r1 and r2, resp., in the sense that they precisely determine the resulting set of sceptically or credulously accepted arguments, i.e., except for x, any former argument sceptically (resp., credulously) accepted remains sceptically (resp., credulously) accepted and only those arguments are sceptically (resp., credulously) accepted. Notice that e1 e4 and r1 r4 do not necessarily enforce the removal of the argument to be forgotten from the AF. They are in nature semantical desiderata and even allow the

potential addition of new arguments. The addition of new arguments is completely reasonable in the context of argumentation because it is what normally happens during a debate, where in general arguments do not simply disappear. Instead, opponents aim to obliterate an adversarial argument by putting forward a new argument that directly or indirectly undermines it (this was illustrated in Example 3). Moreover, from a technical point of view, constructing an AF yielding a given set of extensions E typically requires additional arguments different from those in E (Baumann et al. 2016). However, in practice, it is the context of the application that will determine what criteria are appropriate and we do not express any preference here. Finally, we present the syntactical desiderata s1 s3. As before, s1 does not prevent the addition of new arguments, but s2 and s3 do. All of s1 s3 require the actual removal of the argument to forget from the argumentation framework. In the same token as the addition of a new argument, removal of an argument could be justiﬁable for many reasons, e.g., questions about its legitimacy, the reliability of its source, or inconsistency (in the case of arguments expressed in a logical language).

Desiderata 3. Given an AF F and an argument x U. For G forgetσ(F,x) we require:

s1. x A(G) (x is not contained) s2. A(G) = A(F) {x} (precise set of arguments) s3. G = F A(F) {x} (rigid AF)

More precisely, s1 only requires that x does not belong to the set of arguments of the new AF. s2 strengthens s1 by requiring that nothing except x is removed from the set of arguments of the previous AF and no new arguments are added. Neither s1 nor s2 stipulate any conditions on the attack relation. s3 strengthens s2 further by also requiring the preservation of all attacks not involving x. The previous syntactical conditions become progressively stronger. Indeed there are further relationships between all introduced conditions as shown next.

Proposition 1. For σ {stg,stb,ss,pr,gr,il,eg} and conditions c and c in the diagram below, a path from c to c indicates that any function forgetσ satisfying c under σ also satisﬁes c under σ. Moreover, only these relations hold.

Figure 1: Dependencies

Proof: We start with the valid relations. Since A(F A(F) {x}) = A(F) {x} we immediately obtain s3 s2 and moreover, since x A(F) {x}, s2 s1

holds. Furthermore, since extensions of G are necessarily subsets of A(G), x A(G) implies that x σ(G), and hence s1 r2. If for any AF H s.t. x A(H ) we have σ(G H ) = {E {x} E σ(F H )} (e2), then taking H = ( , ) gives us σ(G) = {E {x} E σ(F)}, so clearly e2 e1. Moreover, e1 guarantees e3, if we take T(E) = E {x}. Thus, e1 e3. For any suitable function T, {T(E) E σ(F)} {E {x} E σ(F)} and obviously we have that x {E {x} E σ(F)}, so e3 r2. Similarly, x σ(F) {E E σ(F),x E}, so e4 r2. If σ(G) is non-empty, then σ(G) σ(G). Hence, r2 r1 for any of the considered semantics with the exception of stb. Finally, x ( σ(F)) {x} and x ( σ(F)) {x}, and hence r3 r1 and r4 r2. In order to complete the proof, one would need to show that the non-existence of a path from condition c to condition c implies the existence of a function forgetσ satisfying c under σ, but not c . For example, let G = ( , ) and consider the constant function forgetσ(F,x) = {G}. Obviously, forgetσ satisﬁes s1 as x = A(G). However, the AF F = ({y}, ) shows that forgetσ does not satisfy s1, since A(F) {x} = {y} {x} = {y} = A(G). For space reasons, we will not show all of these cases in this paper.

Whenever there is no path from the condition c to the condition c in the diagram of Figure 1, we will say that c is non-trivial w.r.t. c. Otherwise we will say that the combination of c and c is trivial.

4 Individual and Combined Satisﬁability Clearly, the strong Reiter condition e2 is a very desirable property for any forgetting operation. Its logic programming analogue (so-called strong persistence) was ﬁrstly introduced in (Knorr and Alferes 2014) and further investigated in (Gonc alves, Knorr, and Leite 2016b). They showed that it is not always possible to forget variables from a program while obeying this property. In the same spirit, we start by analysing the individual satisﬁability of all conditions from the outset. However, unlike (Gonc alves, Knorr, and Leite 2016b), which concentrated on the study of necessary and sufﬁcient conditions for the satisﬁability of strong persistence, we will focus on the simultaneous satisﬁability of criteria and possible constructions of forgetting operations.

Satisﬁability of Individual Conditions The following proposition shows that the majority of the desiderata is individually satisﬁable under all semantics considered in this paper. Proposition 2. Let σ {stg,stb,ss,pr,gr,il,eg} and d {e3,r1,r2,r3,r4,s1,s2,s3}. It holds that desideratum d is satisﬁable under σ. Proof: In order to prove this assertion it sufﬁces to present a speciﬁc function forgetσ, s.t. for any F F and x U, there is an AF G forgetσ(F,x) fulﬁlling desideratum d. By Proposition 1, the satisﬁability of s3 implies the

satisﬁability of s1, s2 and r2 and the satisﬁability of r3 implies the satisﬁability of r1. Therefore, it sufﬁces to show that desiderata s3, r3, r4 and e3 are satisﬁable under σ. (s3): It is easy to see that the AF G = F A(F) {x} satisﬁes s3, and there are no conditions on σ, so s3 is satisﬁable under σ. (r3,r4): Consider the AFs Gr3 = (( σ(F)) {x}, ) and Gr4 = (( σ(F)) {x}, ). We have that σ(Gr3) = {( σ(F)) {x}} and σ(Gr4) = {( σ(F)) {x}}. Recall that for any set E, {E} = {E} = E. Hence, σ(Gr3) = {( σ(F)) {x}} = ( σ(F)) {x} as required. Therefore, Gr3 forgetσ(F,x), and hence r3 is satisﬁable under σ. forgetσ(F,x) = {Gr4} can be constructed analogously and proves r4 s satisﬁability under σ. (e3): If σ(F) = we deﬁne F = G and there is nothing to show. Otherwise, σ(F) = {E1,...,En} for some natural number n. Deﬁne Ge3 = ( 1 i n Ei {x}, ). We have σ(Ge3) = { 1 i n Ei {x}}. This means, we consider the constant function T(E) = 1 i n Ei {x}. Obviously, 1 i n Ei {x} Ej {x} for any 1 j n proving the satisﬁability of e3 under σ.

Condition e1 can only be satisﬁed under certain semantics. Proposition 3. Given σ {gr,il,eg}, τ {stb,stg,ss,pr}. Desideratum e1 is satisﬁable under σ, but not under τ. Proof: The satisﬁability of e1 under σ is quite straigthforward. The semantics gr, il and eg have a unique extension. So let σ(F) = {E}. Then the function forgetσ(F,x) = {(E {x}, )} does the job. In order to show e1 s unsatisﬁability under τ we use the representational limits of the considered argumentation semantics τ. Consider the AF F = ({a,b,x},{(a,x),(x,a)}), with τ(F) = {{a,b},{x,b}}. For the Reiter condition e1 to be satisﬁed, a candidate AF G would have to have τ(G) = {{a,b},{b}}, but this is not possible, since τ(G) does not happen to be a -antichain and hence cannot be realized w.r.t. τ. Therefore, forgetτ(F,x) = , so e1 is not satisﬁable under τ.

Proposition 4 shows that the strong Reiter condition e2 is unsatisﬁable for any of the considered semantics, and it is hence arguably too strong. Proposition 4. Let σ {stg,stb,ss,pr,gr,il,eg}. Condition e2 is unsatisﬁable under σ. Proof: From Proposition 1, we know that the satisﬁability of e2 under semantics σ {stg,stb,ss,pr} implies the satisﬁability of e1 under semantics σ {stg,stb,ss,pr}. But by Proposition 3, e1 is not satisﬁable under semantics σ {stg,stb,ss,pr}. Therefore, e2 is also not satisﬁable under semantics σ {stg,stb,ss,pr}. Consider a semantics σ {gr,il,eg} and the AF F = ({a,x},{(x,a)}). Striving for a contradiction we assume the existence of an AF G, s.t. for any AF H with x A(H ) we have: σ(G H ) = {E {x} E σ(F H )}. Let us consider ﬁrst H1 = ({a,b},{(a,b)}). σ(F H1) = {{x,b}}. Consequently, σ(G H1) = {{b}}. Since {b} has to be admissible in G H1, we have that

(b,b) R(G) (due to conﬂict-freeness) and moreover, (b,a) R(G) (due to defence). Furthermore, a,b A(G) follows. Consider now H2 = ({a},{(a,a)}). Thus, σ(F H2) = {{x}} implying that σ(G H2) = { }. Since {b} is not admissible in G H2 we deduce that there is a further argument c attacking b without being counterattacked. Note that the argument c cannot coincide with a since we already know that (b,a) R(G). This means, we further conclude c A(G), (c,b) R(G) (attacker) and (b,c) R(G) (not counterattacked). Finally, let us consider again H1. We already know that σ(G H1) = {{b}} which cannot be true since {b} does not defend itself against c. This is a contradiction!

The last proposition of this section is about the removal of extensions. It turns out that the elimination of extensions containing a given argument can be only successfully accomplished under the stable semantics. Proposition 5. Given σ {stb}, τ {stg,ss,pr,gr,il,eg}. Condition e4 is satisﬁable under σ, but not under τ. Proof: The satisﬁability of e4 under the stable semantics is an immediate consequence of Proposition 8 (see its proof for more details). All of the other semantics τ do not possess witnessing functions forgetτ because they are all universally deﬁned. In case of the AF F = ({x}, ) the condition e4 would require the realizability of the empty set of extensions. Consequently, forgetτ(F,x) = proving the unsatisﬁability of e4 under τ.

Due to limitations in space we will omit all subsequent proofs with the exception of the proof of Proposition 8, which is required by the above proof.

Combining Syntactical and Semantical Conditions We have seen from Figure 1 that the satisﬁability of some conditions imply the satisﬁability of others. For example, the satisﬁability of s3 implies the satisﬁability of s2. This means that the combination {s2,s3} is also satisﬁable (recall we called these combinations trivial). We now consider the satisﬁability of some non-trivial combinations. Proposition 6 shows the compatibility of all combinations of a semantical and syntactical condition. The strongest syntactical condition s3 is incompatible with most of the semantical conditions and can only be trivially combined with r1 and r2 (for forgetting x under sceptical and credulous reasoning, respectively). Its weaker counterpart s2, which unlike s3 does not constrain the attack relation, can however be combined with all reasoning conditions r1 r4. The weakest syntactical condition s1 can in addition satisfy the weak Reiter condition e3 under any of the considered semantics as well as condition e4 (the forgetting of extensions containing the argument to forget) under the stable semantics. Under the grounded, ideal and eager semantics, s1 and s2 can also be combined with e1, and s2 can be combined with e3. Proposition 6. Figure 2 summarizes the compatibility under semantics σ {stg,stb,ss,pr,gr,il,eg}. A /

in cell (l,c) indicates whether or not the conditions in line l and column c are simultaneously satisﬁable under σ. The symbol τ restricts the satisﬁability to the semantics gr, il and eg and the symbol stb to the stb semantics only, respectively. The combinations in a dark background are trivial.

r1 r2 r3 r4 e1 e2 e3 e4 s1 τ stb s2 τ τ s3

Figure 2: Compatibility of syntactical/semantical conditions

Limits of Non-trivial Combinations A subsequent question is whether one may add further criteria to a compatible syntactical and semantical combination taken from Figure 2. It turns out that there are serious inherent restrictions applying to any semantics. More precisely, there are minimal sets of criteria that cannot be simultaneously satisﬁed. Proposition 7. No set of conditions in the set UNSAT = {{e2},{e4,e1},{e4,e3},{e4,r3},{e4,r4},{r3,r4}} is satisﬁable under any of the considered semantics. We already know from Proposition 6 that e4 is not compatible with s2 or s3 and it is only compatible with s1 under the stable semantics. The proposition above goes one step further to state that e4 is not compatible with any form of the Reiter conditions e1, e2 and e3 (e2 being itself independently unsatisﬁable, by Proposition 4). In addition, the proposition states that e4 is not compatible with the rigid forms of sceptical and credulous acceptance r3 and r4, respectively. Finally, the proposition also states that in the forgetting of an argument x, it is not possible to simultaneously preserve both the sceptical and credulous acceptances of all other arguments. As a corollary we have that no superset of any of the sets of conditions in UNSAT is satisﬁable either.

5 Construction Method The choice of the combination of the conditions depends on the particular application in mind. In this section we illustrate how to construct a desired forgetting operation for one selected combination dealing with the popular stable semantics. The investigation of the construction of other valid combinations is left for future work. Before showing the construction method, we discuss the principle of vacuity which is a well-known concept in belief contraction (Alchourr on, G ardenfors, and Makinson 1985). Roughly speaking, the axiom of vacuity requires that a knowledge base is left untouched by any contraction by a belief that is not included in it. In the context of the forget operation, the vacuity principle requires that the intial AF F is not changed if the argument x to forget is irrelevant to the imposed conditions. This of course may mean different things. We consider the following principles: that x is not sceptically (resp. credulously) accepted in F; and that x is not contained in A(F) at all.

Desiderata 4. Given an AF F and an argument x U. For G forgetσ(F,x) we require: v1. If x σ(F), then F = G. (scept. vacuity) v2. If x σ(F), then F = G. (cred. vacuity) v3. If x A(F), then F = G. (argument vacuity) We have already shown that Desiderata s1 and e4 are simultaneously satisﬁable under the stable semantics (Proposition 6). On top of s1 and e4, we could choose to add one of the vacuity conditions v1 v3. However, it turns out that v1 and v2 are too strong. This can be seen as follows: If x A(F), but it is not sceptically or credulously accepted in F, then v1 and v2 would force F = G, and hence x A(G), violating s1. This means, the only viable option would be v3. Although we do not explore this issue further in this paper, v1 and v2 are indeed compatible with some other nontrivial combinations. Algorithm 1 shows how a function forgetstb that simultaneously satisﬁes s1, e4 and v3 can be constructed.

Algorithm 1: Construct G forgetstb(F,x)

Input : AF F; argument x U Output: AF G satisfying {s1,e4,v3}

1 Function compute G(F,x)

2 if x / A(F) then G F;

4 G0 F A(F) {x};

5 A = A(G0); R R(G0);

6 foreach Ei stb(G0) stb(F) do

7 Let ai be a fresh argument s.t. ai / A(F) A;

8 A A {ai}; R R {(ai,ai)}

9 foreach y stb(G0) Ei do

10 R R {(y,ai)};

11 G (A,R);

12 return G;

Before formally proving that Algorithm 1 indeed does what promised we start with an exemplifying run. Example 4. Consider the AF F whose restriction to {a,b,c,d,e} results in G0. stb(F) = {{b,x,e},{a,c,d},{a,c,e}} and stb(G0) = {{b,e},{b,d},{a,c,d},{a,c,e}}. Since stb(G0) stb(F) = {{b,e},{b,d}} = {E1,E2} the algorithm goes through the loop in lines 6 10 twice. Let n1 be the fresh argument chosen for E1 (line 7). We obtain A = {a,b,c,d,e,n1} and R = R(G0) {(n1,n1)} {(a,n1),(c,n1),(d,n1)} (lines 8 and 9 10), depicted in G1. Proceeding to E2, we take the new argument n2. As before, this cycle sets A = {a,b,c,d,e,n1,n2} and R = R {(n2,n2),(a,n2),(c,n2),(e,n2)} as shown in G2 = (A,R) which is returned by the function as the AF G (lines 11 and 12). Note that stb(G) = {{a,c,d},{a,c,e}} as required.

Proposition 8. Let G = compute G(F,x). Then G satisﬁes conditions s1, e4 and v3 under the stable semantics.

Proof: s1 is satisﬁed by the construction of G in Algorithm 1, lines 4 11. Moreover, condition v3 is ensured by line 2. The proof that G also satisﬁes e4, i.e., stb(G) = stb(F) {E E stb(F),x E} mainly relies on two wellknown properties listed below.1 Let us consider the disjoint union stb(F) = E x Ex, where E x = {E stb(F) x E} and Ex = {E stb(F) x E}. 1.Preservation of extensions not containing x. Given an AF F and its restriction F A(F) {x}. We have E x stb (F A(F) {x}). 2.Elimination of single extensions. For any H and any E stb(H ) we have stb(H ) = stb(H ) {E} where A(H ) = A(H ) {n} and R(H ) = R(H ) {(a,n) a ( stb(H) {n}) E} for a fresh argument n, i.e. n / A(H ). Given these two points, it is easy to see that i) any additional occurring stable extension Ei of G0, i.e. an Ei that is not stable in F will be removed (lines 6 10) and ii) every stable extension in E x is preserved as a stable extension of G. This is because E x stb(G0) and for every addition of a new argument ni, there exists an attack from every argument y stb(G0) Ei into ni. Consequently, since stb(G0) forms a -antichain it is guaranteed that every extension of E x contains an argument attacking ni in G (lines 9 10).

6 Discussion and Conclusion

The paper takes previous work on forgetting in propositional logic and logic programming as a basis and studies the notion of forgetting in the context of abstract argumentation in general. In particular, we introduced several semantical and syntactical desiderata for a forgetting operation, provided a rigorous investigation of the satisﬁability of combinations of these conditions as well as some impossibility results, and illustrated how a forgetting operation for a particular combination of conditions and semantics can be constructed. We considered seven well-known argumentation semantics and showed that many of our results hold independently of the particular semantics employed. In addition, we investigated a number of relevant issues arising in speciﬁc semantics.

1A procedure to eliminate unwanted stable extensions was ﬁrst presented in (Dunne et al. 2015) and studied in a principled way in (Baumann and Brewka 2019).

In the area of logic programming many approaches to forgetting have been proposed. In (Zhang and Foo 2006) forgetting is implemented by simply removing from a logic program all rules containing the atom to be forgotten. This is purely syntactical in nature, and hence similar to our condition s3. (Eiter and Wang 2008) provided a comprehensive and principled study of forgetting in answer set programming, proposing ﬁve desirable properties covering semantical and syntactical aspects of the operation as well as different construction methods. Eiter and Wang observed that the Reiter condition e1 is unsatisﬁable in the context of ASP and proposed the use of the so-called minimal answer sets. This approach guarantees the antichain property of the resulting set which leads to the realizability under the stable model semantics. However, this idea is not directly applicable to Dung-style AFs. For example, the set {{a1,a2,x},{a1,a4,a5},{a2,a3,a5}} under e1 becomes {{a1,a2},{a1,a4,a5},{a2,a3,a5}}, which is realizable for ASP, but not under the stable semantics, because it violates the so-called tightness (Dunne et al. 2015). In (Knorr and Alferes 2014), the notion of strong persistence was introduced. As mentioned in Section 4, strong persistence is analogous to our condition e2 in the context of logic programming. A good overview of the study of the forgetting in the area of Answer Set Programming is given in (Gonc alves, Knorr, and Leite 2016b). The same authors showed that strong persistence is not satisﬁable in general in (Gonc alves, Knorr, and Leite 2016a), and discussed some alternatives. In the context of abstract argumentation, the most similar work to ours is that of (Bisquert et al. 2011). There, the so-called expansive and narrowing changes were proposed that result from the purely syntactical removal of an argument and its corresponding attacks (this corresponds to our desideratum s3). Although the authors provided a preliminary investigation of these changes, the investigation did not consider any further semantical desiderata nor any syntactical strengthenings of s3. Our paper therefore provides the ﬁrst systematic and comprehensive account of the study of the forgetting operation in abstract argumentation. Our function forgetσ(F,x) returns a set of suitable candidates for the result of forgetting the argument x in F. This is akin to the famous postulates in belief revision, for example, which dictate the behaviour of revision operations in general without uniquely deﬁning any particular operation (Alchourr on, G ardenfors, and Makinson 1985). In the same spirit, our desiderata do not determine one unique forgetting operation. A speciﬁc forgetting operation may be deﬁned in several ways, the most obvious of which is the hard encoding of the operation via the addition of an axiom enforcing uniqueness. Alternatively, one could simply redeﬁne the range of the forgetting function or consider a two-step procedure whereby some of the conditions we introduced would lay the foundations of the operation and a selection function guided by speciﬁc desirable criteria, e.g., some notion of minimality, etc, would pick exactly one AF from the candidate options. A further natural question to ask is how to extend our results to the forgetting of sets of arguments. Obviously,

one could iteratively forget each argument in the set, but this would not necessarily constitute an efﬁcient or informationally economical way to perform the operation. Finally, a further in-depth analysis of construction methods for interesting combinations of forgetting conditions is also worthwhile. (Baumann et al. 2017) recently proposed the notion of relativized equivalence which allows one to specify untouchable arguments, i.e., arguments that cannot be disputed, and ask for simpliﬁcations. This seems to be an interesting feature that would allow the forgetting of arguments while simultaneously protecting others.

Acknowledgements

This work was supported by a postdoc fellowship of the German Academic Exchange Service (DAAD 57407370).

Alchourr on, C. E.; G ardenfors, P.; and Makinson, D. 1985. On the logic of theory change: Partial meet contraction and revision functions. Journal of Symbolic Logic 50(2):510 530.

Baroni, P.; Caminada, M.; and Giacomin, M. 2018. Abstract argumentation frameworks and their semantics. In Baroni, P.; Gabbay, D.; Giacomin, M.; and van der Torre, L., eds., Handbook of Formal Argumentation. College Publications. chapter 4.

Baumann, R., and Brewka, G. 2010. Expanding argumentation frameworks: Enforcing and monotonicity results. In Computational Models of Argument: Proceedings of COMMA 2010, Desenzano del Garda, Italy, September 8-10, 2010., 75 86.

Baumann, R., and Brewka, G. 2015. AGM meets abstract argumentation: Expansion and revision for Dung frameworks. In Proceedings of the 24th International Conference on Artiﬁcial Intelligence, IJCAI 15, 2734 2740. AAAI Press.

Baumann, R., and Brewka, G. 2019. Extension removal in abstract argumentation - An axiomatic approach. In In Proceedings of the Thirty-Third Conference on Artiﬁcial Intelligence, AAAI 2019, 2670 2677.

Baumann, R., and Spanring, C. 2015. Inﬁnite argumentation frameworks - On the existence and uniqueness of extensions. In Essays Dedicated to Gerhard Brewka on the Occasion of His 60th Birthday, volume 9060, 281 295. Springer.

Baumann, R.; Dvor ak, W.; Linsbichler, T.; Spanring, C.; Strass, H.; and Woltran, S. 2016. On rejected arguments and implicit conﬂicts: The hidden power of argumentation semantics. Artiﬁcial Intelligence 241:244 284.

Baumann, R.; Dvor ak, W.; Linsbichler, T.; and Woltran, S. 2017. A general notion of equivalence for abstract argumentation. In Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI -17), 800 806.

Bisquert, P.; Cayrol, C.; de Saint-Cyr, F. D.; and Lagasquie Schiex, M. 2011. Change in argumentation systems: Exploring the interest of removing an argument. In Scalable Uncertainty Management - 5th International Conference, SUM 2011, 275 288.

Boole, G. 1854. An Investigation of The Laws of Thought on Which are Founded the Mathematical Theories of Logic and Probabilities. London: Macmillan. Coste-Marquis, S.; Konieczny, S.; Mailly, J.; and Marquis, P. 2014. On the revision of argumentation systems: Minimal change of arguments statuses. In Principles of Knowledge Representation and Reasoning: Proceedings of the Fourteenth International Conference, KR 2014, Vienna, Austria, July 20-24, 2014. de Saint-Cyr, F. D.; Bisquert, P.; Cayrol, C.; and Lagasquie Schiex, M. 2016. Argumentation update in YALLA (yet another logic language for argumentation). International Journal of Approximate Reasoning 75:57 92. Delgrande, J. P. 2017. A knowledge level account of forgetting. Journal of Artiﬁcial Intelligence Research 60:1165 1213. Diller, M.; Haret, A.; Linsbichler, T.; R ummele, S.; and Woltran, S. 2018. An extension-based approach to belief revision in abstract argumentation. International Journal of Approximate Reasoning 93:395 423. Dung, P. M. 1995. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artiﬁcial Intelligence 77(2):321 357. Dunne, P. E.; Dvoˇr ak, W.; Linsbichler, T.; and Woltran, S. 2015. Characteristics of multiple viewpoints in abstract argumentation. Artiﬁcial Intelligence 228:153 178. Eiter, T., and Kern-Isberner, G. 2018. A brief survey on forgetting from a knowledge representation and reasoning perspective. KI - K unstliche Intelligenz. Eiter, T., and Wang, K. 2008. Semantic forgetting in answer set programming. Artiﬁcial Intelligence 172(14):1644 1672. Gonc alves, R.; Knorr, M.; and Leite, J. 2016a. The ultimate guide to forgetting in answer set programming. In Principles of Knowledge Representation and Reasoning: Proceedings of the Fifteenth International Conference, KR 2016, 135 144. Gonc alves, R.; Knorr, M.; and Leite, J. 2016b. You can t always forget what you want: On the limits of forgetting in answer set programming. In ECAI 2016 - 22nd European Conference on Artiﬁcial Intelligence, 957 965. Knorr, M., and Alferes, J. J. 2014. Preserving strong equivalence while forgetting. In Proceedings of the 14th European Conference on Logics in Artiﬁcial Intelligence (JELIA-14), 412 425. Lang, J.; Liberatore, P.; and Marquis, P. 2003. Propositional independence: Formula-variable independence and forgetting. Journal of Artiﬁcial Intelligence Research 18:391 443. Lin, F., and Reiter, R. 1994. Forget it. In Working Notes of AAAI Fall Symposium on Relevance, 154 159. Wallner, J. P.; Niskanen, A.; and J arvisalo, M. 2017. Complexity results and algorithms for extension enforcement in abstract argumentation. Journal of Artiﬁcial Intelligence Research 60:1 40. Zhang, Y., and Foo, N. Y. 2006. Solving logic program conﬂict through strong and weak forgettings. Artiﬁcial Intelligence 170(8-9):739 778.