# forgetting_in_modular_answer_set_programming__427f3f5d.pdf

The Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19)

Forgetting in Modular Answer Set Programming

Ricardo Gonc alves,1 Tomi Janhunen,2 Matthias Knorr,1 Jo ao Leite,1 Stefan Woltran3

1Universidade Nova de Lisboa 2Aalto University 3Vienna University of Technology

Modular programming facilitates the creation and reuse of large software, and has recently gathered considerable interest in the context of Answer Set Programming (ASP). In this setting, forgetting, or the elimination of middle variables no longer deemed relevant, is of importance as it allows one to, e.g., simplify a program, make it more declarative, or even hide some of its parts without affecting the consequences for those parts that are relevant. While forgetting in the context of ASP has been extensively studied, its known limitations make it unsuitable to be used in Modular ASP. In this paper, we present a novel class of forgetting operators and show that such operators can always be successfully applied in Modular ASP to forget all kinds of atoms input, output and hidden overcoming the impossibility results that exist for general ASP. Additionally, we investigate conditions under which this class of operators preserves the module theorem in Modular ASP, thus ensuring that answer sets of modules can still be composed, and how the module theorem can always be preserved if we further allow the reconfiguration of modules.

1 Introduction Modularity in Answer Set Programming (ASP) (Dao-Tran et al. 2009; Harrison and Lierler 2016; Baral, Dzifcak, and Takahashi 2006; Janhunen et al. 2009; Oikarinen and Janhunen 2008), just as in many other programming paradigms, is a fundamental concept to ease the creation and reuse of large programs. In one of the most significant general approaches to modularity the so-called programming-in-thelarge compositional operators are provided for combining separate and independent modules, i.e., essentially answer set programs extended with well-defined input/output interfaces, based on standard semantics. The compositionality of the semantics of individual modules is ensured by the socalled module theorem (Janhunen et al. 2009). The operation of forgetting, which aims at eliminating a set of variables from a knowledge base while preserving all relationships (direct and indirect) between the remaining variables, has recently gained a lot of attention, not only because it is useful, e.g., as a means to clean up a theory by eliminating all auxiliary variables that have no relevant declarative meaning, but also because it may be necessary,

Copyright c 2019, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

e.g., as a means to deal with privacy and legal issues such as to eliminate illegally obtained data, or to comply with the recently enacted right to be forgotten (European Union 2016). Whereas forgetting in the context of classical logic is essentially a solved problem (Bledsoe and Hines 1980; Weber 1986; Middeldorp, Okui, and Ida 1996; Lang, Liberatore, and Marquis 2003; Moinard 2007; Gabbay, Schmidt, and Szalas 2008), new challenging issues arise when it is considered in the context of a non-monotonic logic based language such as ASP (Zhang and Foo 2006; Eiter and Wang 2008; Wong 2009; Wang, Wang, and Zhang 2013; Knorr and Alferes 2014; Wang et al. 2014; Delgrande and Wang 2015; Gonc alves, Knorr, and Leite 2016b). According to (Goncalves, Knorr, and Leite 2016a), forgetting in ASP is best captured by strong persistence (Knorr and Alferes 2014), a property inspired by strong equivalence, which requires that there be a correspondence between the answer sets of a program before and after forgetting a set of atoms, and that such correspondence be preserved in the presence of additional rules not containing the atoms to be forgotten. However, it has also been shown that, in ASP, it is not always possible to forget and satisfy strong persistence (Gonc alves, Knorr, and Leite 2016b). What about forgetting in Modular ASP? Do the same negative results hold, and sometimes it is simply impossible to forget while satisfying strong persistence? Is strong persistence an adequate requirement in the case of Modular ASP? Can forgetting be reconciled with the module theorem? Investigating forgetting in the context of Modular ASP is the central topic of this paper. Our main contributions are:

We argue that, given that the input of a module is just a set of facts, strong persistence is too strong when forgetting in Modular ASP, and that it is more suitable to rely on uniform equivalence (Sagiv 1988; Eiter and Fink 2003) for a weaker form of persistence, say uniform persistence, which has not been considered before.

We thoroughly investigate forgetting in ASP under uniform equivalence, including formalizing uniform persistence and showing that, unlike with strong persistence, it is always possible to forget under this new property.

We show that no previously known class of forgetting operators satisfies uniform persistence, which leads us to introduce a new class of forgetting operators that satisfies

uniform persistence, and investigate its other properties.

We employ the newly introduced class of operators to forget in a prominent approach of modular ASP, DLPfunctions (Janhunen et al. 2009), and show how it can adequately be used to forget input, output, and hidden atoms from a module, while obeying uniform persistence.

We also show that, not unexpectedly, the module theorem no longer holds in general after forgetting.

To overcome the latter problem, we investigate ways to modify modules so that the module theorem can be preserved while forgetting under uniform persistence i.e., ways to reconfigure ASP modules by merging and splitting modules, so that we can properly forget while preserving the compositionality of stable models of modules.

2 Preliminaries We start by recalling some notions about logic programs. An (extended) rule r is an expression of the form

a1 . . . an b1, ..., bm, not c1, ..., not ck, not not d1, ..., not not dl , (1)

where a1, . . . , an, b1, . . . , bm, c1, . . . , ck, and d1, . . . , dl are atoms of a given propositional alphabet A. Note that double negation is standard in the context of forgetting in ASP. We also write such rules as A B, not C, not not D where A = {a1, . . . , an}, B = {b1, . . . , bm}, C = {c1, . . . , ck}, and D = {d1, . . . , dl}. An (extended) logic program is a finite set of rules. By A(P) we denote the set of atoms appearing in P and by Ce the class of extended programs. We call r disjunctive if D = ; normal if, additionally, A has at most one element; Horn if on top of that C = ; and fact if also B = . The classes of disjunctive, normal and Horn programs, Cd, Cn, and CH, are then defined as usual. Given a program P and an interpretation I, i.e., a set I A, the reduct P I is defined as P I = {A B | A B, not C, not not D P, C I = , D I}. An interpretation I is a model of a rule A B if A I = whenever B I; I is a model of a reduct R if it satisfies every rule of R; I is a minimal model of the reduct R if I is a model of R and there is no model I of R s.t. I I; and I is an answer set of an extended program P if it is a minimal model of the reduct P I. The set of all answer sets of a program P is denoted by AS(P). Given a set of atoms V , the V -exclusion of a set of sets M, denoted M V , is {X\V | X M}. Two programs P1 and P2 are said to be equivalent if AS(P1) = AS(P2), strongly equivalent, denoted by P1 P2, if AS(P1 R) = AS(P2 R) for any R Ce, and uniformly equivalent, denoted by P1 u P2, if AS(P1 R) = AS(P2 R), for any set of facts R. An HT-interpretation is a pair X, Y s.t. X Y A. Given a program P, an HT-interpretation X, Y is an HTmodel of P if Y |= P and X |= P Y , where |= stands for the classical satisfaction relation for rules. The set of all HTmodels of P is denoted by HT (P). Also, Y AS(P) iff Y, Y HT (P) and there is no X Y s.t. X, Y HT (P). Also, HT (P1) = HT (P2) precisely when P1 P2 (Lifschitz, Pearce, and Valverde 2001). Given a set of

atoms V , the V -exclusion of a set of HT-interpretations M, M V , is { X\V, Y \V | X, Y M}. A forgetting operator over a class C of programs over A is a partial function f : C 2A C s.t. the result of forgetting about V from P, f(P, V ), is a program over A(P)\V , for each P C and V A. We denote the domain of f by C(f) and usually we focus on C = Ce, and leave C implicit. The operator f is called closed for C C(f) if f(P, V ) C , for every P C and V A. A class F of forgetting operators (over C) is a set of forgetting operators f s.t. C(f) C. We recall notions of modules using ELP-functions, a generalization of DLP-functions (Janhunen et al. 2009).1 An ELP-function, Π, is a quadruple P, I, O, H , where I, O, and H are pairwise distinct sets of input atoms, output atoms, and hidden atoms, respectively, and P is a logic program s.t. for each rule A B, not C, not not D of P,

1. A B C D I O H, and

2. if A = , then A (O H) = .

Input atoms and output atoms are also called visible atoms. An interpretation for an ELP-function Π = P, I, O, H is an arbitrary set M A(Π), where A(Π) = I O H. We denote by Ai(Π), Ao(Π), Ah(Π), and by Mi, Mo, Mh the subsets of A(Π) and M restricted to elements in I, O, and H, respectively. Given ELP-function Π = P, I, O, H and interpretation M, the reduct of Π w.r.t. M is the ELPfunction ΠM = P M, I, O, H , where P M is the reduct of P w.r.t. M. An interpretation N is a model of ΠM iff N is a model of P M. A model N of ΠM is I-minimal iff there is no model N of ΠM such that N i = Ni and N N. An interpretation M is a stable model2 of Π iff M is an Iminimal model of ΠM. The set of all stable models of Π is denoted by SM(Π). We have M SM(Π) iff M AS(P Mi) (Lierler and Truszczynski 2011). Given a program P and a set of atoms S, the set of defining rules for S is Def P (S) = {A B, not C, not not D P | A S = }. Two ELP-functions Π1 = P1, I1, O1, H1 and Π2 = P2, I2, O2, H2 respect the input/output interfaces of each other iff (1) (I1 O1 H1) H2 = ; (2) (I2 O2 H2) H1 = ; (3) O1 O2 = ; (4) Def P1(O1) = Def P1 P2(O1), and (5) Def P2(O2) = Def P1 P2(O2). Let Π1 = P1, I1, O1, H1 and Π2 = P2, I2, O2, H2 be ELP-functions that respect the input/output interfaces of each other. The composition Π1 Π2 is defined as

P1 P2, (I1 \ O2) (I2 \ O1), O1 O2, H1 H2 .

The join of modules builds on this composition imposing further restrictions. The positive dependency graph of an ELP-function Π = P, I, O, H is the pair DG+(Π) = O H, 1 , where b 1 a holds for a, b (O H) iff there is a rule A B, not C, not not D P s.t. a A and b B. The reflexive and transitive closure of 1 provides the dependency relation over output and hidden atoms.

1While we limit our generalization to extended logic programs to the necessary notions for individual modules, we do not foresee major difficulties for other aspects left out of scope of this paper. 2We reserve the term answer set for programs and the term stable model for ELP-functions to ease the reading.

A strongly connected component (SCC) S of DG+(Π) is a maximal set S Ao(Π) Ah(Π) s.t. b a for all pairs a, b S. If Π1 Π2 is defined, then Π1 and Π2 are mutually dependent iff DG+(Π1 Π2) has an SCC S s.t. S Ao(Π1) = and S Ao(Π2) = , and mutually independent otherwise. Thus, given ELP-functions Π1 and Π2, if the composition Π1 Π2 is defined and Π1 and Π2 are mutually independent, then the join Π1 Π2 of Π1 and Π2 is defined and coincides with Π1 Π2 (Janhunen et al. 2009).

3 Forgetting under Uniform Persistence Arguably, among the many properties for forgetting in ASP, strong persistence is the one that should intuitively hold, since it imposes the preservation of all original direct and indirect dependencies between atoms not to be forgotten. Here and in the sequel, F is a class of forgetting operators.

(SP) F satisfies Strong Persistence if, for each f F, P C(f) and V A, we have AS(f(P, V ) R) = AS(P R) V , for all programs R C(f) with A(R) A\V .

Essentially, (SP) requires that the answer sets of f(P, V ) correspond to those of P, no matter what programs R over A\V we add to both, which is closely related to the concept of strong equivalence. However, this property is rather demanding, witnessed by the fact that it cannot always be satisfied (Gonc alves, Knorr, and Leite 2016b). On the other hand, in the case of a module, i.e., an ELP-function, its program P is fixed, and we only vary the input, which is closely related to considering a fixed ASP program, encoding the declarative specification of a problem, and only varying the instances corresponding to the specific problem to be solved. This is captured by the notion of uniform equivalence, which weakens strong equivalence by considering that only facts can be added. To investigate forgetting in such cases, we introduce Uniform Persistence, (UP), obtained from (SP) by restricting the varying programs R to sets of facts.

(UP) F satisfies Uniform Persistence if, for each f F, P C(f) and V A, we have AS(f(P, V ) R) = AS(P R) V , for all sets of facts R with A(R) A\V .

Having introduced (UP) as the desired property for forgetting in ELP-functions, we now turn our attention to which forgetting operator to use. Unfortunately, none of the existing classes mentioned in the literature3 satisfy (UP).4

Theorem 1 None of the classes F of forgetting operators studied in (Goncalves, Knorr, and Leite 2016a; Gonc alves et al. 2017) satisfy (UP).

Due to this negative result and the fact that it is not always possible to forget while satisfying (SP), the question that arises is whether this is actually different for (UP), given that it is less demanding in its requirements.

3Cf. the survey on forgetting in ASP (Goncalves, Knorr, and Leite 2016a), (Gonc alves et al. 2017), and references therein. 4Note that the result in (Goncalves, Knorr, and Leite 2016a) (Fig. 1) indicating that class FSas satisfies (SP), the generalization of (UP), is in fact not entirely accurate, since the only known operator in FSas is not defined for a class of programs, but rather for instances of forgetting.

Example 1 Consider program P used in the impossibility result for (SP) (Gonc alves, Knorr, and Leite 2016b): a p b q p not q q not p Adding program R = {a ; b }, it is shown there that any result of forgetting {p, q} from P, f(P, {p, q}), that satisfies (SP) is required to have an HT-model ab, ab 5. At the same time, since {a, b} (modulo {p, q}) is not an answer set of P, we must have X, ab HT (f(P, {p, q})) for at least one X {a, b}, to prevent {a, b} from being an answer set of f(P, {p, q}). It is then shown that due to different programs R, X, ab HT (f(P, {p, q})) for any such X, thus causing a contradiction. However, in the case of X = , R = {a b; b a} is used, which is not a set of facts and thus not relevant w.r.t. (UP). In fact, given the only possible four sets of facts over {a, b} to be considered for R, we can verify that P = {a not b; a not not a, b; b not a; b not not b, a} is a result of forgetting {p, q} from P for which the condition of (UP) is satisfied. A naive approach to define a class of forgetting operators that satisfies (UP) would be to use relativized uniform equivalence (Eiter, Fink, and Woltran 2007), which is close in spirit to (UP). However, this would not work, for the same reasons that a similar approach based on relativized strong equivalence fails to capture (SP) (Gonc alves et al. 2017). Instead, we define a class of forgetting operators that satisfies (UP), dubbed FUP, whose more involved definition that we will gently introduce in an incremental way builds on the manipulation of HT-models given an input program P and a set of atoms V A(P) to forget. To this end, we aim at devising a mapping from HT (P) to the set of HTmodels of the result of forgetting, f(P, V ), for any operator f FUP. This mapping can be illustrated as follows. Example 2 The program P from Ex. 1 has 15 HT-models: bq, bq bq, abq b, abpq abp, abpq ap, ap abq, abq bq, abpq abq, abpq ap, abp , abpq ap, abpq abpq, abpq abp, abp a, abpq ab, abpq The HT-models for the proposed result P of forgetting are a, a , b, b , , ab and ab, ab . But how could we determine the latter set of HT-models for any P and V ? Given the HT-models listed above, the set HT (P) V contains extra tuples such as a, ab and b, ab . Thus, a more involved analysis of HT-models is in order. By the definition of (UP), an answer set Y of f(P, V ) R corresponds to an answer set Y A of P R, for some A V . We will therefore collect all HT-models X, Y A in HT (P) with the same Y and join them in blocks separated by the varying A. To this end, we first characterize all the different total HT-models of P, namely, for each Y A\V : Sel Y P,V = {A V | Y A, Y A HT (P)}.

Example 3 Given the HT-models (Ex. 2) for P of Ex. 1 and V = {p, q}, we obtain Sel P,V = , Sel{a} P,V = {{p}},

Sel{b} P,V = {{q}}, and Sel{a,b} P,V = {{p}, {q}, {p, q}}.

5We follow a common convention and abbreviate sets in HTinterpretations such as {a, b} with the sequence of its elements, ab.

Clearly, the total models to be considered in the result of forgetting should be restricted to those Y s.t. Sel Y P,V is non-empty. But not all these sets should be considered.

Example 4 Let P be a program over A = {a, b, p, q} s.t. its HT-models of the form X, {a, b} A with A V = {p, q} are ab, abp , abp, abp , abp, abpq , and abpq, abpq . We have that Sel{a,b} P,V = {{p}, {p, q}}. Nevertheless, the nontotal models ab, abp and abp, abpq do not allow {a, b, p} and {a, b, p, q} to be answer sets of P R, for any R over A\V = {a, b}. So, although Sel{a,b} P,V = , the set {a, b} should not be a possible answer set of the forgetting result.6

Taking this observation into account, we define the set of total models for the result of forgetting V from P:

T P,V = {Y A\V | there exists A Sel Y P,V s.t.

Y A , Y A / HT(P) for every A A}.

Example 5 Based on the HT-models of P listed in Ex. 2, the sets Sel Y P,V identified in Ex. 3, and V = {p, q}, we observe that T P,V = {{a}, {b}, {a, b}}. In each of the three cases, the condition in the definition of T P,V is satisfied by some element of Sel Y P,V . For Y = {a, b} in particular, the set A can be either {p} or {q}, but not {p, q}. Given T P,V , we expect three total HT-models for the result of forgetting {p, q} from P, i.e., the ones indicated in Ex. 2 for P .

The crucial question now is how to extract the non-total HT-models for the result of forgetting in general. For this purpose, for each A Sel Y P,V , we first consider the nontotal HT-models of P of the form X, Y A :

N Y,A P,V = {X\V | X, Y A HT (P) and X = Y A}.

Example 6 Continuing Ex. 5, these non-total models, in particular those relevant for the desired result , ab , are:

N {a,b},{p} P,V = {{a}}, N {a,b},{q} P,V = {{b}}, and

N {a,b},{p,q} P,V = { , {a}, {b}, {a, b}}.

Now, since HT-models of facts never include , Y for any Y , we know that any HT-model , Y of P will not occur in HT (P R) for any (non-empty) set of facts R. Hence, either one of the N Y,A P,V is empty, in which case P itself has an answer set Y modulo V and the result of forgetting should have an answer set Y , or N Y,A P,V for any A results in an HT-model , Y for the result of forgetting, which is why , ab HT (P ) in Ex. 2 holds. Generalizing this observation, whenever there is a set X s.t. each N Y,A P,V contains an element X with X X , then adding X as facts to P cannot result in an answer set of P, and thus, X, Y should be part of the forgetting result. In Ex. 6, the only such set X is indeed X = .

6Similar considerations have been used in the context of relativized equivalence (Eiter, Fink, and Woltran 2007) and in forgetting (Gonc alves, Knorr, and Leite 2016b).

We thus collect all sets N Y,A P,V for each Y , define tuples over this set of sets, and intersections over these tuples. The latter correspond to the maximal subsets X, which suffices for uniform equivalence (Eiter, Fink, and Woltran 2007). Definition 1 Let P be a program, V A, and Y A\V . Consider the indexed family of sets SY P,V = {N Y,i P,V }i I where I = Sel Y P,V . For each tuple (Xi)i I such that Xi

N Y,i P,V , we define the intersection of its sets as T

i I Xi. We denote by SInt Y P,V the set of all such intersections.

The resulting intersections indeed correspond to sets X pointed out in the preceding discussion. Therefore, we obtain the definition of FUP by combining the total models based on T P,V and the non-total ones based on SInt Y P,V , but naturally restricted to those cases where the corresponding total model exists. Definition 2 (UP-Forgetting) Let FUP be the class of forgetting operators defined as:

{f |HT (f(P, V ))=({ Y, Y | Y T P,V }

{ X, Y | Y T P,V and X SInt Y P,V })

for all P C(f) and V A}.

Example 7 Recall P from Ex. 1. Following the discussion after Ex. 6, we can verify that the result of forgetting about V = {p, q} from P according to FUP has the expected HTmodels (cf. Ex. 2): a, a , b, b , , ab , and ab, ab . The definition of FUP characterizes the HT-models of a result of forgetting for any f FUP, but not an actual program. This may raise the question whether there actually is such an operator, and we can answer this question positively. Theorem 2 There exists f such that f FUP. The construction underlying the result relies on the notion of counter-models in HT (Cabalar and Ferraris 2007), which has been used for defining forgetting operators before (Wang, Wang, and Zhang 2013; Wang et al. 2014). While the definition of UP-Forgetting itself is certainly non-trivial, it turns out that for the case of Horn programs, a considerably simpler definition can be used. Proposition 1 Let f be in FUP. Then, for every V A:

HT (f(P, V )) = HT (P) V for each P CH.

This result serves as further indication that UP-Forgetting is well-defined, given that essentially all classes of forgetting operators coincide with this definition for the class of Horn programs (Goncalves, Knorr, and Leite 2016a). We are able to show that FUP indeed satisfies (UP) which guarantees that, unlike for the property (SP), it is always possible to forget satisfying (UP). Theorem 3 FUP satisfies (UP). Despite (SP) being the property that best captures the essence of forgetting in ASP in general, of which (UP) is the weaker version that is sufficient when dealing with modules, other properties have been investigated in the literature (cf. (Goncalves, Knorr, and Leite 2016a)). We obtain that FUP satisfies the following properties.

Proposition 2 FUP satisfies (s C), (w E), (SE), (CP), (w C), (ECe), (ECH), but not (W), (PP), (SI), (SP), (ECd), (ECn).

Given the close connection between the class FUP and uniform equivalence (cf. Thm. 3), it is not surprising that some properties of forgetting that are closely connected to strong equivalence are not satisfied by FUP, notably (PP) and (SI), which are satisfied by the class of forgetting operators defined for forgetting w.r.t. (SP) when forgetting is possible (Gonc alves, Knorr, and Leite 2016b). Finally, we obtain that deciding whether a program is the result of forgetting for f FUP is in ΠP 3 .

Theorem 4 Given programs P, Q, and V A, deciding whether P f(Q, V ) for f FUP is in ΠP 3 .

Note that the same problem for the classes of forgetting operators that approximate forgetting under (SP) is ΠP 3 - complete (Gonc alves et al. 2017). Also, by (Wang et al. 2014) and Prop. 1, if Q is Horn, then this problem is in ΠP 1 .

4 Forgetting in Modules

We now turn our attention to the use of FUP to forget in modules i.e., ELP-functions. Towards characterizing results of forgetting in modules, the notion of equivalence between ELP-functions modular equivalence (Janhunen et al. 2009) needs to first be adapted, since it is too strong as it requires the existence of a bijection between stable models of different ELP-functions, which is not possible in general when reducing the language, as illustrated by the next example.

Example 8 Take Π = {a ; b not not b}, , {a}, {b} with SM(Π) = {{a}, {a, b}}. Forgetting b should yield, e.g., Π = {a }, , {a}, with SM(Π ) = {{a}}, but then no bijection between SM(Π) and SM(Π ) is possible.

Therefore, we introduce a novel notion of equivalence for program modules according to which two modules are V - equivalent if they coincide on I and O ignoring V , and if their stable models coincide ignoring V .

Definition 3 (V-Equivalence) Let Π1 and Π2 be ELPfunctions, and V a set of atoms. Then, Π1 and Π2 are V - equivalent, denoted by Π1 V Π2, iff

1. Ai(Π1)\V = Ai(Π2)\V and Ao(Π1)\V = Ao(Π2)\V ; 2. SM(Π1) V = SM(Π2) V .

Forgetting from each of the pairwise disjoint sets of atoms considered in a module input, output and hidden needs to be characterised in turn. Additionally, in the case of input and output atoms, we also consider hiding them useful when atoms are not declaratively meaningful outside the module, or should not be shown and discuss its difference with respect to forgetting them. We start by showing that the hidden atoms of an ELPfunction can be forgotten without affecting its behavior perceived in terms of visible atoms, ensuring that we can deal with cases when we are not allowed to express a certain piece of information in terms of our hidden atoms, or do not want to show it to someone who wants to visualize the program of a module.

Theorem 5 (Forgetting hidden atoms) Given a set V H of hidden atoms to forget, an ELP-function Π = P, I, O, H is V -equivalent to any ELP-function Π = f(P, V ), I, O, H\V based on a uniformly persistent forgetting operator f FUP.

But forgetting is also applicable to the visible elements of a module. For instance, whenever output atoms are no longer used by other modules, they can effectively be removed without affecting the behavior of the module.

Theorem 6 (Forgetting output atoms) Given a set V O of output atoms to forget, an ELP-function Π = P, I, O, H is V -equivalent to any ELP-function Π = f(P, V ), I, O\V, H based on a uniformly persistent forgetting operator f FUP.

An alternative to forgetting output atoms is hiding them. Given an ELP-function Π = P, I, O, H and a set V O of output atoms, we could create an ELP-function P, I, O\V, H V where the atoms of V are simply hidden. This would be computationally cheap since P would not change, but could be regarded insufficient under the strict interpretation of forgetting V , i.e., the elements of V should not appear in the result at all. Nevertheless, we derive the following counterpart to Thm. 6.

Theorem 7 (Hiding output atoms) Given a set V O of output atoms to hide, an ELP-function Π = P, I, O, H is V -equivalent to the ELP-function Π = P, I, O\V, H V .

Thus, both hiding and forgetting output atoms yields V - equivalent ELP-functions. Turning to forgetting (or hiding) of input atoms, no analogous result exists without making changes to the program.

Example 9 Take Π = {a b}, {b}, {a}, . Then, SM(Π) = { , {a, b}}, but moving b from I to H yields Π with SM(Π ) = {{}}, which is not {b}-equivalent.

Nevertheless, if we allow programs to change, such V - equivalent ELP-functions can be constructed using the idea of an input generator (cf. (Oikarinen and Janhunen 2006, Thm. 4)), easily encodable with extended rules, and we can forget about input atoms from ELP-functions as follows.

Theorem 8 (Forgetting input atoms) Given a set V I of input atoms to forget, an ELP-function Π = P, I, O, H is V -equivalent to any

Π = f(P {a not not a | a V }, V ), I\V, O, H

based on a uniformly persistent forgetting operator f FUP.

This construction of Π can also be used to hide input atoms.

Theorem 9 (Hiding input atoms) Given a set V I of input atoms to hide, an ELP-function Π = P, I, O, H is V -equivalent to Π = P {a not not a | a V }, I\V, O, H V .

Combining these results, we can now define a general notion of a module resulting from forgetting elements of single parts of a module s interface. From now on, we assume that some forgetting operator f FUP has been fixed.

Definition 4 Given an ELP-function Π = P, I, O, H and a set V of atoms to forget, we denote by Π\V the resulting ELP-function f(P {a not not a | a I V }, V ), I\V, O\V, H\V .

We can show that this notion indeed fits the expectations.

Corollary 1 For an ELP-function Π and a set of atoms V A(Π), we have SM(Π\V ) = SM(Π) V .

And it follows that we can forget sets of atoms iteratively.

Proposition 3 Let Π be an ELP-function and V A(Π). Then, if V1 V2 = V and V1 V2 = , we have

SM(Π\V ) = SM((Π\V1)\V2) = SM((Π\V2)\V1).

In (Janhunen et al. 2009), it is shown, through the module theorem, that the stable model semantics of modules is fully compositional, which should be preserved under forgetting. In the case of two modules Π1 = P1, I1, O1, H1 and Π2 = P2, I2, O2, H2 that do not mention each other s hidden atoms and their join Π1 Π2 is defined (coincides with the composition Π1 Π2), the module theorem states that SM(Π) = SM(Π1) SM(Π2) where the join of sets of stable models captured by the operator contains M1 M2 whenever M1 SM(Π1), M2 SM(Π2), and M1 and M2 are compatible, i.e., M1 (I2 O2) = M2 (I1 O1) so that M1 and M2 coincide on visible atoms. Limited to forgetting atoms that are not shared by two modules, if we consider two modules whose join is defined, then the module theorem can be preserved while forgetting.

Theorem 10 If Π is an ELP-function obtained as a join of two ELP-functions Π1 and Π2, and V A(Π) is a set of atoms to forget s.t. V (I1 O1) (I2 O2) = , then SM(Π\V ) = SM(Π1\V ) SM(Π2\V ).

We can generalize this result to deal with cases where atoms to be forgotten appear in more than two modules.

Theorem 11 If Π is an ELP-function obtained as a join of n ELP-functions Π1, . . . , Πn, and V A(Π) is a set of atoms to forget s.t., for all i, j {1, . . . , n}, i = j, V (Ii Oi) (Ij Oj) = , then SM(Π\V ) = n i=1 SM(Πi\V ).

Yet, if we lift the restrictions on where the atoms to forget appear, we lose a full correspondent to the module theorem.

Theorem 12 If Π is an ELP-function obtained as a join of two ELP-functions Π1 and Π2, and V A(Π) is a set of atoms to forget, then SM(Π\V ) n i=1 SM(Πi\V ).

Only one of the two inclusions one would expect actually holds, and this is not by chance. In general, it is possible that modules Π1\V and Π2\V possess compatible stable models M1 and M2 such that M = M1 M2 SM(Π1\V ) SM(Π2\V ) but M SM(Π\V ) as illustrated next.

Example 10 Let us consider ELP-functions Π1 = {a b}, {b}, {a}, and Π2 = {b not c}, {c}, {b}, and their join Π = P, {c}, {a, b}, with P = P1 P2 for the respective sets of rules P1 and P2 of Π1 and Π2. As regards forgetting V = {b}, we have Π1\V = {a not not a}, , {a}, , Π2\V = , {c}, , , and Π\V = {a not c}, {c}, {a}, . It remains to observe

that M1 = SM(Π1\V ), M2 = SM(Π2\V ), and M1 M2 SM(Π\V ) = {{a}, {c}} although M1 and M2 are (trivially) compatible. The example suggests that it is not safe to use f FUP to forget shared atoms that inherently change the I/O interface between the modules. The same is also true for hiding. Example 11 Consider again Ex. 10. We obtain the three modules in each of which b has been hidden as follows: Π 1 = {a b; b not not b}, , {a}, {b} , Π 2 = {b not c}, {c}, , {b} and (Π1 Π2) = {a b; b not c}, {c}, {a}, {b} . But then Π 1 and Π 2 do not respect the input/output interfaces of each other. We could circumvent this by renaming one of the occurrences of b, but we would also lose the prior dependency of a on c.

5 Module Reconfiguration Preserving the compositionality of stable models of modules while forgetting is desirable by the very idea of modular ASP: we want users to define ASP modules that can be composed into larger programs/modules. However, as we have seen, the module theorem no longer works entirely whenever some atom to be forgotten is shared by two modules. In such cases, one alternative is to somehow modify the modules so that these atoms cease to occur in the visible components of different modules, i.e., reconfigure ASP modules by merging and splitting modules, so that we can forget while preserving the compositionality of stable models of modules. Of course, for this to be feasible, we must have access to the modules in question (by communication, or because we own the modules). This may require sharing some information about some module, which may not always be desirable, but, arguably, whenever possible, this is a reasonable trade-off for being able to forget atoms from modules while preserving (UP) and the module theorem. One way to address the problem, provided all involved modules are mutually independent and their composition is defined, is to join all the modules that contain such atoms. Let Π be an ELP-function obtained as a join of n ELPfunctions Π1, . . . , Πn, and V A(Π) a set of atoms to forget. Consider the following relation on N = {1, . . . , n}: i V j iff V (Ii Oi) (Ij Oj) = . This relation identifies those ELP-functions that share atoms to forget, i.e., that can cause problems with the module theorem. We denote by V the reflexive and transitive closure of V on N. Since V is clearly a symmetric relation, its reflexive and transitive closure, V , is an equivalence relation on N. We can therefore consider the quotient set N\ V , i.e., the set of equivalence classes defined by V on N. We then consider, for each e N\ V , the ELP-function Πe = F

i e Πi, the join of those ELP-functions corresponding to the considered equivalence class. This allows us to prove a relaxed version of the module theorem. Theorem 13 Let Π be an ELP-function obtained as a join of n ELP-functions Π1, . . . , Πn, and V A(Π) a set of atoms to forget. Let N = {1, . . . , n}, and consider V the equivalence relation on N as defined previously, and N\ V = {e1, . . . , ek} the respective quotient set. Then, SM(Π\V ) = k i=1 SM(Πei\V ).

This shows that joining those modules that share atoms to be forgotten allows for the preservation of the module theorem. Joining entire modules is not ideal. However, it may happen that only part of a module is relevant to the shared atom to be forgotten, in which case we can use the operation of decomposing (or splitting) modules to do a more fine-grained recomposition of modules that still preserves the module theorem. Towards this end, we adapt the necessary notions to introduce module decomposition (Janhunen et al. 2009). Given an ELP-function Π = P, I, O, H , let SCC+(Π) denote the set of strongly connected components of DG+(Π). The dependency relation can be lifted to SCC+(Π) by setting S1 S2 iff there are atoms a1 S1 and a2 S2 s.t. a1 a2. It is easy to check that is well-defined over SCC+(Π), i.e., it does not depend on the chosen a1 S1 and a2 S2, and that SCC+(Π), is a partially ordered set, i.e., is reflexive, transitive, and antisymmetric. For each S SCC+(Π) we consider the ELPfunction ΠS = Def P (S), A(Def P (S))\S, S O, S H . Some of these modules ΠS, however, may share hidden atoms, and therefore cannot be joined. To overcome this, such components of SCC+(Π) need to be identified.

Definition 5 Given an ELP-function Π = P, I, O, H , components S1, S2 SCC+(Π) do not respect the hidden atoms of each other, denoted by S1 h S2, if and only if S1 = S2 and (at least) one of the following conditions holds:

1. there is h Ah(ΠS1) such that h Ai(ΠS2), 2. there is h Ah(ΠS2) such that h Ai(ΠS1), 3. there are h1 Ah(ΠS1) and h2 Ah(ΠS2) such that both occur in some integrity constraint of Π.

It is clear that the relation h is irreflexive and symmetric on SCC+(Π) for every ELP-function Π. If we consider the reflexive and transitive closure of h, denoted by h, we obtain an equivalence relation. A repartition of SCC+(Π) can then be obtained by considering the quotient set SCC+(Π)\ h, i.e., the set of equivalence classes of h over SCC+(Π), which can be used to decompose Π.

Definition 6 Given an ELP-function Π = P, I, O, H , the decomposition induced by SCC+(Π) and h includes an ELP-function Π0 = IC0(P), A(IC0(P)) (I \A(P)), , where IC0(P) = { B, not C, not not D P | (B C D) H = } and, for each S SCC+(Π)\ h, an ELP-function ΠS = Def P (S) ICS(P), A(Def P (S) ICS(P))\S, S O, S H , where S = S S and ICS(P) = { B, not C, not not D P | (B C D) (S H) = }.

The module Π0 keeps track of integrity constraints as well as input atoms that are not mentioned by the rules of P. We can adapt straightforwardly (from (Janhunen et al. 2009)) that this decomposition of an ELP-function is valid.

Proposition 4 Given an ELP-function Π = P, I, O, H , then Π = Π0 (F

S SCC+(Π)\ h ΠS).

We now show that this decomposition can be used to allow forgetting while still preserving the module theorem. Let Π1 = P1, I1, O1, H1 and Π2 = P2, I2, O2, H2 be two ELP-functions such that their join is defined. Since

Prop. 3 shows that we can forget a set of atoms by forgetting iteratively every atom in the set, we focus on forgetting a single atom p. Suppose that p is shared by the two modules, i.e., p (I1 O1) (I2 O2), and recall that we cannot guarantee that forgetting p separately in Π1 and Π2 preserves the module theorem. We first consider the set of components of the decomposition of Π1 that are relevant for atom p, i.e., R(Π1, p) = {S SCC+(Π1)\ h | p Ao(ΠS) Ai(ΠS)}. We denote by Πp 1 the union of the ELP-functions in R(Π1, p), i.e., Πp 1 = F R(Π1, p), by R(Π1, p) the set of components of the decomposition of Π1 that are not relevant for p, i.e., R(Π1, p) = {S SCC+(Π1)\ h | S / R(Π1, p)}, and by Πp 1 the union of the ELP-functions in R(Π1, p), i.e., Πp 1 = F R(Π1, p). The decomposition of Π1 can then be used to obtain a restricted version of the module theorem. Theorem 14 (Reconfiguration) Let Π be an ELP-function obtained as a join of two ELP-functions Π1 and Π2, and let p (Ai(Π1) Ao(Π1)) (Ai(Π2) Ao(Π2)). Then,

SM(Π\{p}) = SM(Πp 1\{p}) SM((Π2 Πp 1)\{p}). Thus, to allow forgetting in modules and preserve the module theorem, we can essentially decompose certain modules and reconfigure them in such a way that all rules on the considered shared atom occur in a single module.

6 Conclusions In this paper, we thoroughly investigated the operation of forgetting in the context of modular ASP. We began by observing that strong persistence (SP) the property usually taken to best characterize forgetting in ASP, which cannot always be guaranteed is too strong when we consider modular ASP. Given the structure of modules in the context of modular ASP, namely their restricted interface, a weaker notion of persistence based on uniform equivalence is sufficient to properly characterise forgetting in this case, which led us to introduce uniform persistence (UP). We showed that, unlike with (SP), it is always possible to to forget under (UP). Perhaps surprisingly, we also showed that, in general, none of the operators defined in the literature satisfies this weaker form of persistence, which led us to introduce the class of forgetting operators FUP that we proved to obey (UP), as well as a set of other properties commonly discussed in the literature. We then turned our attention to the application of this class of forgetting operators to forget input, output, and hidden atoms from modules, and related it with the operation of hiding. Despite showing that we can always forget atoms from modules under uniform persistence, we also showed that the important module theorem no longer holds in general, with negative consequences in the compositionality of stable models. Subsequently, after pinpointing the conditions under which the module theorem holds, we proceeded by investigating how the theorem could be recovered through a reconfiguration of the modules obtained by suitable decomposition and composition operations. Possible avenues for future work include investigating forgetting in other existing ways to view modular ASP, such

as (Dao-Tran et al. 2009; Harrison and Lierler 2016), and the precise relationship of (UP) and UP-Forgetting to the notion of relativized uniform equivalence (Eiter, Fink, and Woltran 2007), and obtaining syntactic operators for UP-Forgetting.

Acknowledgments Authors R. Gonc alves, M. Knorr, and J. Leite were partially supported by FCT project FORGET (PTDC/CCI-INF/32219/2017) and by FCT project NOVA LINCS (UID/CEC/04516/2013). T. Janhunen was partially supported by the Academy of Finland project 251170. R. Gonc alves was partially supported by FCT grant SFRH/BPD/100906/2014. S. Woltran was supported by the Austrian Science Fund (FWF): Y698, P25521.

Baral, C.; Dzifcak, J.; and Takahashi, H. 2006. Macros, macro calls and use of ensembles in modular answer set programming. In Etalle, S., and Truszczynski, M., eds., Procs. of ICLP, volume 4079 of LNCS, 376 390. Springer. Bledsoe, W. W., and Hines, L. M. 1980. Variable elimination and chaining in a resolution-based prover for inequalities. In Bibel, W., and Kowalski, R. A., eds., Procs. of CADE, volume 87 of LNCS, 70 87. Springer. Cabalar, P., and Ferraris, P. 2007. Propositional theories are strongly equivalent to logic programs. TPLP 7(6):745 759. Dao-Tran, M.; Eiter, T.; Fink, M.; and Krennwallner, T. 2009. Modular nonmonotonic logic programming revisited. In Hill, P. M., and Warren, D. S., eds., Procs. of ICLP, volume 5649 of LNCS, 145 159. Springer. Delgrande, J. P., and Wang, K. 2015. A syntax-independent approach to forgetting in disjunctive logic programs. In Bonet, B., and Koenig, S., eds., Procs. of AAAI, 1482 1488. AAAI Press. Eiter, T., and Fink, M. 2003. Uniform equivalence of logic programs under the stable model semantics. In Palamidessi, C., ed., Procs. of ICLP, volume 2916 of LNCS, 224 238. Springer. Eiter, T., and Wang, K. 2008. Semantic forgetting in answer set programming. Artif. Intell. 172(14):1644 1672. Eiter, T.; Fink, M.; and Woltran, S. 2007. Semantical characterizations and complexity of equivalences in answer set programming. ACM Trans. Comput. Log. 8(3). European Union. 2016. General Data Protection Regulation. Official Journal of the European Union L119:1 88. Gabbay, D. M.; Schmidt, R. A.; and Szalas, A. 2008. Second Order Quantifier Elimination: Foundations, Computational Aspects and Applications. College Publications. Gonc alves, R.; Knorr, M.; Leite, J.; and Woltran, S. 2017. When you must forget: Beyond strong persistence when forgetting in answer set programming. TPLP 17(5-6):837 854. Goncalves, R.; Knorr, M.; and Leite, J. 2016a. The ultimate guide to forgetting in answer set programming. In Baral, C.; Delgrande, J.; and Wolter, F., eds., Procs. of KR, 135 144. AAAI Press.

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 Fox, M. S., and Kaminka, G. A., eds., Procs. of ECAI, 957 965. IOS Press. Harrison, A., and Lierler, Y. 2016. First-order modular logic programs and their conservative extensions. TPLP 16(56):755 770. Janhunen, T.; Oikarinen, E.; Tompits, H.; and Woltran, S. 2009. Modularity aspects of disjunctive stable models. J. Artif. Intell. Res. (JAIR) 35:813 857. Knorr, M., and Alferes, J. J. 2014. Preserving strong equivalence while forgetting. In Ferm e, E., and Leite, J., eds., Procs. of JELIA, volume 8761 of LNCS, 412 425. Springer. Lang, J.; Liberatore, P.; and Marquis, P. 2003. Propositional independence: Formula-variable independence and forgetting. J. Artif. Intell. Res. (JAIR) 18:391 443. Lierler, Y., and Truszczynski, M. 2011. Transition systems for model generators - A unifying approach. TPLP 11(45):629 646. Lifschitz, V.; Pearce, D.; and Valverde, A. 2001. Strongly equivalent logic programs. ACM Trans. Comput. Log. 2(4):526 541. Middeldorp, A.; Okui, S.; and Ida, T. 1996. Lazy narrowing: Strong completeness and eager variable elimination. Theor. Comput. Sci. 167(1&2):95 130. Moinard, Y. 2007. Forgetting literals with varying propositional symbols. J. Log. Comput. 17(5):955 982. Oikarinen, E., and Janhunen, T. 2006. Modular equivalence for normal logic programs. In Brewka, G.; Coradeschi, S.; Perini, A.; and Traverso, P., eds., Procs. of ECAI, 412 416. Oikarinen, E., and Janhunen, T. 2008. Achieving compositionality of the stable model semantics for smodels programs. TPLP 8(5-6):717 761. Sagiv, Y. 1988. Optimizing datalog programs. In Minker, J., ed., Foundations of Deductive Databases and Logic Programming. Morgan Kaufmann. 659 698. Wang, Y.; Zhang, Y.; Zhou, Y.; and Zhang, M. 2014. Knowledge forgetting in answer set programming. J. Artif. Intell. Res. (JAIR) 50:31 70. Wang, Y.; Wang, K.; and Zhang, M. 2013. Forgetting for answer set programs revisited. In Rossi, F., ed., Procs. of IJCAI, 1162 1168. IJCAI/AAAI. Weber, A. 1986. Updating propositional formulas. In Expert Database Conf., 487 500. Wong, K.-S. 2009. Forgetting in Logic Programs. Ph.D. Dissertation, The University of New South Wales. Zhang, Y., and Foo, N. Y. 2006. Solving logic program conflict through strong and weak forgettings. Artif. Intell. 170(8-9):739 778.