# merging_in_the_horn_fragment__1f47ae8f.pdf

Merging in the Horn Fragment

Adrian Haret, Stefan R ummele, Stefan Woltran {haret, ruemmele, woltran}@dbai.tuwien.ac.at Institute of Information Systems Vienna University of Technology, Austria

Belief merging is a central operation within the ﬁeld of belief change and addresses the problem of combining multiple, possibly mutually inconsistent knowledge bases into a single, consistent one. A current research trend in belief change is concerned with tailored representation theorems for fragments of logic, in particular Horn logic. Hereby, the goal is to guarantee that the result of the change operations stays within the fragment under consideration. While several such results have been obtained for Horn revision and Horn contraction, merging of Horn theories has been neglected so far. In this paper, we provide a novel representation theorem for Horn merging by strengthening the standard merging postulates. Moreover, we present a concrete Horn merging operator satisfying all postulates.

1 Introduction

Belief merging uses a logical approach to study how information coming from multiple, possibly mutually inconsistent knowledge bases should be combined to form a single, consistent knowledge base. Merging shares a common methodology with other belief change operators, such as revision [Alchourr on et al., 1985; Katsuno and Mendelzon, 1992], contraction [Alchourr on et al., 1985] and update [Katsuno and Mendelzon, 1991]. Part of the methodology is the formulation of postulates, which any rational operator should satisfy. For merging, the IC-merging postulates [Konieczny and Pino P erez, 2002; 2011] are commonly used. In a further step, a representation result is usually derived: this shows that all (merging) operators satisfying the postulates can be characterized using rankings on the possible worlds described by the underlying language, which is typically taken to be full propositional logic. Recently, the restriction of belief change formalisms to different fragments of propositional logic has become a vivid research branch. There are pragmatic reasons for focusing on fragments, especially Horn logic. Firstly, Horn clauses are a natural way of formulating basic facts and rules, and thus

Supported by the Austrian Science Fund (FWF) under grants P25518 and P25521.

are useful to encode expert knowledge. Second, Horn logic affords very efﬁcient algorithms. Thus the computational cost of reasoning in this fragment is comparatively low. While revision [Delgrande and Peppas, 2015; Van De Putte, 2013; Zhuang et al., 2013] and contraction [Booth et al., 2011; Delgrande and Wassermann, 2013; Zhuang and Pagnucco, 2012] have received a lot of attention in this direction, belief merging has yet remained unexplored, with the notable exception of [Creignou et al., 2014]. We aim to ﬁll this gap and investigate the problem of merging in the Horn fragment of propositional logic. We ﬁnd that restricting the underlying language poses a series of non-trivial challenges, as representation results which work for full propositional logic break down in the Horn case. Firstly, we ﬁnd that we cannot rely on the same types of rankings as the ones used for merging in the case of full propositional logic. The reason is that such rankings lead to outputs that can not be expressed as Horn formulas. We ﬁx this problem by adding the restriction of Horn compliance: this narrows down the notion of ranking in a way that is coherent with the semantics of Horn formulas. Since standard merging operators are found not to be Horn compliant (hence useless for our needs), we also give a concrete operator that exhibits this property. This is remarkable, since previous research [Creignou et al., 2014] only resulted in Horn merging operators that do not satisfy all postulates. Secondly, Horn merging operators that satisfy the standard postulates turn out to represent more rankings than was expected, some of which are undesirable. We interpret this as an inadequacy of the standard postulates to capture the intended intuitive behaviour of a merging operator. Hence, we propose an alternative formulation of some key postulates, which allows us to derive an appealing representation result for the case of Horn merging. Our approach here is inspired by existing work on Horn revision [Delgrande and Peppas, 2015], though we go signiﬁcantly beyond it to tackle the problems posed by merging. The rest of the paper is organized as follows. In Section 2 we introduce the background to merging. In Section 3 we argue that standard model-based merging operators are inappropriate for Horn merging and introduce the property of Horn compliance. In Section 4 we argue that a subset of the IC-merging postulates should be replaced by a strengthened version, and introduce a representation result using the strengthened postulates. Finally, in Section 5 we describe a

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015)

concrete Horn merging operator satisfying all postulates. Due to lack of space, we do not include here the proofs of the claims found in the text. These can be found in the full version [Haret et al., 2015].

2 Preliminaries

Propositional logic. We work with the language L of propositional logic over a ﬁxed alphabet P = {p1, . . . , pn} of propositional atoms. We use standard connectives , , and the logical constants and . A literal is an atom or a negated atom. A clause is a disjunction of literals. A clause is called Horn if at most one of its literals is positive. The Horn fragment LH L is the set of all formulas in L that are conjunctions of Horn clauses. An interpretation is a set w P of atoms. The set of all interpretations is denoted by W. We will typically represent an interpretation by its corresponding bit-vector of length |P|. As an example, if |P| = 3, then 101 is the interpretation {p1, p3}. A pre-order on W is a reﬂexive, transitive binary relation on W. If w1, w2 W, then w1 < w2 denotes the strict part of , i.e., w1 w2 but w2 w1. We write w1 w2 to abbreviate w1 w2 and w2 w1. If M is a set of interpretations, then the set of minimal elements of M with respect to is deﬁned as min M = {w1 M | w2 M s.t. w2 < w1}. If interpretation w satisﬁes formula ϕ, we call w a model of ϕ. We denote the set of models of ϕ by [ϕ]. Given a set M of interpretations, we deﬁne Cl (M), the closure of M under intersection, as the smallest superset of M that is closed under , i.e., if w1, w2 Cl (M) then also w1 w2 Cl (M). We recall here a classic result concerning Horn formulas and their models (see e.g. [Schaefer, 1978]).

Proposition 1. A set of interpretations M is the set of models of a Horn formula ϕ if and only if M = Cl (M).

A formula is called complete if it has exactly one model. If wi is an interpretation, we sometimes write σwi or σi to denote the complete formula that has wi as a model. If σi and σj are complete formulas, then σi,j is a formula such that [σi,j] = {wi, wj}. If we are working in the Horn fragment, we take σi,j to be such that [σi,j] = Cl ({wi, wj}).

Belief Merging. A knowledge base is a ﬁnite set of propositional formulas. A proﬁle is a non-empty ﬁnite multi-set E = {K1, . . . , Kn} of consistent knowledge bases. Horn knowledge bases and Horn proﬁles contain only Horn formulas and Horn knowledge bases, respectively. The sets of all knowledge bases, Horn knowledge bases, proﬁles and Horn proﬁles are denoted by K, KH, E and EH, respectively. If E1 and E2 are proﬁles, then E1 E2 is the multi-set union of E1 and E2. Interpretation w is a model of knowledge base K if it is a model of every formula in K. Interpretation w is a model of proﬁle E if it is a model of every K E. We denote by [K] and [E] the set of models of K and E, respectively. We write V E for V K E V ϕ K ϕ. This reduces a proﬁle to a single propositional formula. Clearly, [V E] = [E]. Proﬁles E1 and E2 are equivalent, written E1 E2, if there exists a bijection f : E1 E2 such that for any K E1 we have [K] = [f(K)].

A merging operator is a function : E L K. It maps a proﬁle E and a formula µ, typically referred to as constraint, onto a knowledge base. We write µ(E) instead of (E, µ). As is common in the belief change literature, logical postulates are employed to set out properties which any merging operator should satisfy. An operator satisfying the following postulates is called IC-merging operator [Konieczny and Pino P erez, 2002; 2011]:

(IC0) µ(E) |= µ. (IC1) If µ is consistent, then µ(E) is consistent. (IC2) If V E is consistent with µ, then µ(E) V E µ. (IC3) If E1 E2 and µ1 µ2, then µ1(E1) µ2(E2). (IC4) If K1 |= µ and K2 |= µ, then µ({K1, K2}) K1 is consistent iff µ({K1, K2}) K2 is consistent. (IC5) µ(E1) µ(E2) |= µ(E1 E2). (IC6) If µ(E1) µ(E2) is consistent, then µ(E1 E2) |= µ(E1) µ(E2). (IC7) µ1(E) µ2 |= µ1 µ2(E). (IC8) If µ1(E) µ2 is consistent, then µ1 µ2(E) |= µ1(E) µ2.

It turns out that we can use a particular type of rankings on interpretations to compute the models of a merging operator. Deﬁnition 1. A syncretic assignment is a function mapping each E E to a pre-order E on W such that, for any E, E1, E2 E, K1, K2 K and w1, w2 W the following conditions hold:

(s1) If w1 [E] and w2 [E], then w1 E w2. (s2) If w1 [E] and w2 / [E], then w1 <E w2. (s3) If E1 E2, then E1= E2. (s4) If w1 [K1], then there is w2 [K2] such that w2 {K1,K2} w1. (s5) If w1 E1 w2 and w1 E2 w2, then w1 E1 E2 w2. (s6) If w1 E1 w2 and w1 <E2 w2, then w1 <E1 E2 w2.

We deﬁne syncretic assignments in a way that allows the pre-orders E to be partial, as we will make use of partial pre-orders in our own results on Horn operators (Theorems 3 and 4). In the context of full propositional logic, however, the classical result below characterizes all IC-merging operators in terms of syncretic assignments with total pre-orders. Theorem 1 ([Konieczny and Pino P erez, 2002; 2011]). A merging operator is an IC-merging operator if and only if there exists a syncretic assignment mapping each E E to a total pre-order E such that [ µ(E)] = min E[µ], for any µ L. When this equation holds we will say that the assignment represents the operator. It is useful to think of a proﬁle E = {K1, . . . , Kn} as a multi-set of agents, represented by their sets of beliefs Ki. Each agent is equipped with a pre-order Ki on W which can be thought of as the way in which the agent ranks possible worlds in terms of their plausibility. Merging is then the task of ﬁnding a common ranking that approximates, as best as

[K] Σ GMAX 00 2 2 (2) 01 1 1 (1) 10 1 1 (1) 11 0 0 (0)

Table 1: d H,Σ µ (E1) and d H,GMAX µ (E1) do not stay in the Horn fragment.

possible, the individual rankings. Proposition 1 tells us that if this process is done using syncretic assignments, we are in agreement with postulates IC0 IC8. Two parts need to be ﬁlled out to get a concrete merging operator: how to compute the individual rankings and how to aggregate them. For the ﬁrst part, the common approach in the literature is to use some notion of distance between interpretations, such as Hamming distance d H or the drastic distance d D. The minimal distance between interpretations and models of Ki is used to construct Ki. For the second part, common functions used to aggregate the distances are the sum Σ or GMAX , giving us operators d H,Σ, d H,GMAX , d D,Σ, d H,GMAX . The reader is referred to [Konieczny and Pino P erez, 2002; 2011] for more details.

3 Restricting assignments A Horn merging operator is a function : EH LH KH. Our aim is to characterize the class of such operators in the manner of Proposition 1 and to exhibit a concrete operator. The ﬁrst problem occurs when we apply standard merging operators to Horn proﬁles and formulas: their output cannot always be represented by a Horn formula. Examples 1 and 2 show how standard merging operators fail in the Horn fragment. In both cases we choose Horn proﬁles over the 2-letter alphabet and construct rankings using the Hamming distance and the drastic distance. We then aggregate the rankings with Σ and GMAX . The rankings and the result of their aggregation are shown in Tables 1 and 2. Each row displays one possible interpretation over {p1, p2} (denoted in the ﬁrst column). The second column displays the minimal distance of the interpretation to any model of K. The third and fourth column show the aggregation of the distances (in our case only one distance) according to the Σ as well as the GMAX function. The output of the merging operator is the set of those interpretations that are models of µ (marked grey) and have the smallest aggregated value. Example 1. Take K = {p1, p2}, E1 = {K} and µ = p1 p2 (all of them Horn). We compute d H,Σ µ (E1) and d H,GMAX µ (E1), keeping in mind that [K] = {11} and [µ] = {00, 10, 01}. Table 1 displays how the output of these two mergings is computed. We get [ d H,Σ µ (E1)] = min[µ] = {10, 01}, and the same result is obtained for d H,GMAX µ (E1). It holds, then, that d H,Σ µ (E1) and d H,GMAX µ (E1) cannot be expressed as Horn formulas. Example 2. Take K1 = {p1, p2}, K2 = { p1, p2}, E2 = {K1, K2} and µ = p1 p2: We get (see Table 2) [ d D,Σ µ (E2)] = min[µ] = {10, 01}, and the same

[K1] [K2] Σ GMAX 00 1 1 2 (1,1) 01 1 0 1 (1,0) 10 0 1 1 (1,0) 11 1 1 2 (1,1)

Table 2: d D,Σ µ (E2) and d D,GMAX µ (E2) do not stay in the Horn fragment.

result is obtained for d D,GMAX µ (E2). Again, d D,Σ µ (E2) and d D,GMAX µ (E2) cannot be represented by Horn formulas.

As we see in Examples 1 and 2, standard distance and aggregate functions are not adequate for the Horn fragment. Here we adopt a solution suggested by [Delgrande and Peppas, 2015], which is to impose an extra condition on the pre-orders.

Deﬁnition 2. A pre-order is Horn compliant if for any µ LH, min [µ] can be represented by a Horn formula.

Example 3. The computed pre-orders for E1 and E2 in Examples 1 and 2 are not Horn compliant, as we get that min[µ] = {01, 10} in both cases.

Adding Horn compliance makes it possible to deﬁne a merging operator for the Horn fragment, and this gives us one direction of a representation theorem.

Theorem 2. If there exists a syncretic assignment mapping every E EH to a Horn compliant total pre-order E, then we can deﬁne an operator : EH LH KH by taking [ µ(E)] = min E[µ], for any µ LH, and satisﬁes postulates IC0 IC8.

4 Strengthening the postulates

Conversely, we want to show that for any Horn merging operator there exists a syncretic assignment which represents it. This is true when the language is not restricted (see Proposition 1), but interesting problems arise as soon as we restrict ourselves to the Horn case. We know from existing work on Horn revision [Delgrande and Peppas, 2015] that we can ﬁnd non-syncretic assignments to represent a Horn operator . Such assignments are nonsyncretic in the sense that they contain non-transitive cycles between interpretations. Yet, we can still deﬁne an operator on top of these rankings, which satisﬁes postulates IC0 IC8. Furthermore, it can be shown that there are no non-cyclic pre-orders that represent the same operator . The solution proposed in [Delgrande and Peppas, 2015] is to add an extra postulate, called Acyc, speciﬁcally to eliminate cycles:

(Acyc) If for every n 1 and i {0, n 1}, µi µi+1(E) and µn µ0(E) are all consistent, then µ0 µn(E) is also consistent.

Acyc provably follows from postulates IC0 IC8 in full propositional logic, so it only makes a difference when we restrict the language to the Horn fragment. Here we employ the same strategy of adding an extra postulate to deal with non-transitive cycles, but we propose a postulate formulated in terms of complete formulas:

Figure 1: s4 does not hold.

(Acyc ) For any complete formulas σ0, . . . , σn, n 1 and i {0, n 1}, it holds that if σi σi,i+1(E) and σn σn,0(E) are all consistent, then σ0 σ0,n(E) is also consistent.

There is clearly a strong similarity between Acyc and Acyc , though we prefer the latter here for its intuitive appeal. Moreover, it can be shown that they are equivalent modulo the merging postulates.

Proposition 2. Given postulates IC0 IC8, Acyc and Acyc

are equivalent.

The intuition behind Acyc is that it prevents non-transitive cycles between chains of interpretations of arbitrary length. Suppose n = 2 and the antecedent of Acyc is true: then from the fact that σ0 σ0,1(E) is consistent we conclude that w0 [ σ0,1(E)], where [σi] = {wi}. This means that w0 is among the models of σ0,1 that are preferred , or considered more plausible, by . Thus, in the pre-order E that represents , it should hold that w0 E w1. By the same token, we get that w1 E w2 E w0 should hold. Since we want E to be transitive, it should also hold that w0 E w2, and this is exactly what Acyc requires at this point. Thus, we need the extra postulate Acyc (or something equivalent) to ensure that the pre-orders representing a given Horn merging operator preserve intuitive properties such as (in this case) transitivity. Introducing Acyc is not enough, as one can still ﬁnd assignments that represent a Horn merging operator without being syncretic, this time because they do not satisfy properties s4 s6. The following examples make this clearer.

Example 4. Consider Horn knowledge bases [K1] = {01}, [K2] = {10} and an assignment that works as in Figure 1 when restricted to K1 and K2. Figure 1 shows the rankings associated with K1 and K2 and the result of merging them into the new ranking {K1,K2}.1 Notice that s4 is not true: s4 requires that 01 {K1,K2} 10, whereas we have 01 <{K1,K2} 10. However, we can deﬁne a (Horn) merging operator on top of this assignment in the usual way, by taking [ µ(E)] = min E[µ], for any Horn formula µ, and will satisfy postulates IC0 IC8 + Acyc . This can be

1It is worth noting that K1, K2 and {K1,K2} are not generated using any familiar notion of distance the rankings were hand-picked.

010, 111, 100

010, 011, 001, 101, 100

Figure 2: s5 does not hold for 010 and 100.

veriﬁed by direct inspection; we focus here only on IC4. The problematic interpretations are the models 01 and 10 of K1 and K2, respectively. Notice that there is no Horn formula that represents exactly the set {01, 10}: the best we can do is take a Horn formula µ such that [µ] = [σ01,10] = {00, 01, 10}. Obviously, K1 |= µ and K2 |= µ, so we are in the range of application of IC4. We have that [ µ({K1, K2})] = {00}, and [ µ({K1, K2}) K1] = [ µ({K1, K2}) K2] = , so IC4 is satisﬁed for this particular µ. Example 4 is signiﬁcant because it shows that an assignment which does not satisfy s4 may still represent an operator obeying IC4. And given the standard formulation of IC4, this turns out to be unavoidable. Proposition 3. There is no syncretic assignment representing from Example 4 that assigns to {K1, K2} a pre-order {K1,K2} where 01 {K1,K2} 10.

Proof. Suppose 01 {K1,K2} 10. From Figure 1 we know that [ σ10,11({K1, K2})] = {11}, hence min {10, 11} = {11} and thus 11 < {K1,K2} 10. Similarly, we obtain 01 {K1,K2} 11, which implies 01 < {K1,K2} 10. This creates a contradiction.

The following example shows how s5 fails to be enforced by IC5 in the case of Horn logic. Example 5. Assume there exists an assignment which for two proﬁles E1 and E2 behaves as in Figure 2, and is otherwise Horn compliant and syncretic. Property s5 does not hold: 010 E1 100 and 010 E2 100, but 010 <E1 E2 100. However, as in Example 4, we can deﬁne a (Horn) merging operator on top of this assignment and will satisfy postulates IC0 IC8 + Acyc . Let us check that IC5 holds. The problematic interpretations here are 010 and 100 (for which s5 does not hold). In this case we have that σ010,100(E1) σ010,100(E2) is consistent, and

[ σ010,100(E1) σ010,100(E2)] = [ σ010,100(E1 E2)] = {000}. This shows that for the case we are interested in (µ = σ010,100) IC5 is true.

Similarly as for IC4, we can show that such a counterexample to s5 is unavoidable. It is perhaps surprising to see that IC5 can be satisﬁed in an assignment where s5 does not hold, but closer thought shows this is to be expected: since in the Horn fragment we cannot represent the set {100, 010} with a formula, it becomes harder to control the order in which 100 and 010 appear. Without any additional constraints on , one cannot prevent it from varying the order of 100 and 010 in ways that directly contradict s5. Similar counter-examples can be constructed for s6. Examples 4 and 5 show that a syncretic assignment with total pre-orders is not the most natural way to represent a Horn merging operator. Hence, we introduce the following notion.

Deﬁnition 3. A pre-order on W is Horn connected if

(h1) is Horn compliant,

(h2) any wi, wj W that are in the subset relation are in , and

(h3) for any wi, wj W such that wi wj and wj wi, it holds that if wi wj then:

(h3.1) wi min Cl ({wi, wj}), or (h3.2) for some n > 2, there exist pair-wise distinct interpretations w1, . . . , wn, such that w1 = wi, wn = wj and w1 wn.

A Horn connected pre-order E is not necessarily total. Example 6 illustrates this.

Example 6. Consider the following pre-orders on the 2-letter alphabet: (a) 11 <1 01 <1 10 <1 00, (b) 00 <2 01 <2 11 <2 10, (c) 00 <3 01 <3 11, 00 <3 10 <3 11, 01 3 10 10 3 01, (d) 00 <4 01 4 10 <4 11. It is immediately visible that all pre-orders are Horn compliant (h1) and that they satisfy h2. Let us focus on interpretations 01 and 10. In 1 we have 01 min Cl ({01, 10}). Thus h3.1 is satisﬁed, and 1 is Horn connected. In 2 we do not have 01 min Cl ({01, 10}), but there is interpretation 11 such that 01 < 11 < 10. Thus h3.2 is satisﬁed and 2 is Horn connected. Pre-order 3 is partial, as 01 and 10 are not in 3, and thus h3 is vacuously true. In 4 we have 01 10 though none of h3.1 and h3.2 holds, thus 4 is not Horn connected.

Next, for every Horn operator and Horn proﬁle E, we deﬁne a (partial) pre-order on complete formulas of LH.2

Deﬁnition 4. Given a Horn operator , then for any Horn proﬁle E and complete Horn formulas σi, σj, we say that σi E σj if there exist complete Horn formulas σ1, ..., σn such that σ1 = σi, σn = σj, and for i {1, n 1}, σi σi,i+1(E) are all consistent.

It is straightforward to check that E is reﬂexive and transitive, and thus a pre-order on complete Horn formulas. We write E for the strict part of E. It is also worth noting that E is total when the underlying language is full propositional

2The pre-order E is not to be confused with the pre-order E on interpretations, though it is meant to mirror it.

logic, since [σi,j] = {wi, wj} and we can take the sequence σ1, . . . , σn to be just σi, σj or σj, σi. This does not necessarily hold in the case of the Horn fragment, where E can be partial. We now reformulate IC4, IC5 and IC6 for K1, K2 KH, E1, E2 EH and complete Horn formulas σi, σj as follows:

(IC 4) For any σi |= K1, there exists σj |= K2 such that σj {K1,K2} σi.

(IC 5) If σi E1 σj and σi E2 σj, then σi E1 E2 σj.

(IC 6) If σi E1 σj and σi E2 σj, then σi E1 E2 σj.

These postulates make a difference only in the Horn fragment, while in full propositional logic they are redundant.

Proposition 4. In the case of full propositional logic, IC 4, IC 5 and IC 6 follow from the standard IC0 IC8 postulates.

With postulates IC 4, IC 5 and IC 6 we can derive a representation result for syncretic assignments with Horn connected pre-orders. The result is split across two theorems: Theorem 3 shows that Horn connected pre-orders can be used to construct a Horn merging operator satisfying our amended set of postulates. Its converse, Theorem 4, shows that any Horn merging operator satisfying the amended postulates is represented by a syncretic assignment with Horn connected pre-orders.

Theorem 3. If there exists a syncretic assignment mapping every E EH to a Horn connected total pre-order E, then we can deﬁne an operator : EH LH KH by taking [ µ(E)] = min E[µ], for any µ LH, and satisﬁes postulates IC0 IC3 + IC 4 + IC 5 + IC 6 + IC7 IC8 + Acyc .

Theorem 4. If a Horn operator : EH LH KH satisﬁes postulates IC0 IC3 + IC 4 + IC 5 + IC 6 + IC7 IC8 + Acyc , then there exists a syncretic assignment mapping every Horn proﬁle E to a Horn connected pre-order E, such that, for any Horn formula µ, it holds that [ µ(E)] = min E[µ].

In Theorem 4, the strengthened postulates IC 4, IC 5 and IC 6 rule out Horn merging operators represented by nonsyncretic assignments such as the ones in Examples 4 and 5, and thus justify their presence. Our focus on Horn connected pre-orders, on the other hand, should not be seen as a restriction: we can translate any Horn compliant pre-order E into a Horn connected one E such that the overall assignment (1) represents the same (Horn) merging operator and (2) remains syncretic. This can be done simply by uncoupling pairs wi and wj which are not in the subset relation and do not satisfy either of the properties h3.1 and h3.2. Since wi and wj do not appear together in any set of the type min E[µ], for µ LH, the Horn merging operators represented by E and E are the same. However, the reverse is not as straightforward: for any Horn connected pre-order there exist more than one Horn compliant pre-orders representing the same Horn merging operator: any interpretations wi and wj that are not in E can be related in several ways if we care about making E total (we could have wi < E wj, or wj < E wi, etc.), and some of the conﬁgurations give rise to non-syncretic assignments. Our point is that wi and wj do not need to be related as long as the represented merging operator stays the same. Indeed, the main motivation for

formulating the representation result with partial pre-orders is that if wi and wj do not satisfy h3.1 and h3.2 then a Horn merging operator does not give us any information on what the order between them should be. It makes sense, in this case, to not include wi and wj in the pre-order representing .

5 A concrete Horn merging operator

By Theorem 2, we can ﬁnd a Horn merging operator simply by exhibiting a Horn compliant, syncretic assignment. As in Examples 1 and 2, we can specify a pre-order K by assigning numbers to interpretations, relative to K, and in the rest of this section this is how we will be thinking of pre-orders. We write l K(w) to denote the number assigned to w with respect to some knowledge base K. If K has exactly one model w , we simply write lw (w). One difﬁculty here is that there is no obvious candidate for an off-the-shelf assignment that satisﬁes all the required properties: Horn compliance rules out standard approaches using familiar distances between interpretations. Therefore, we start by describing some general conditions sufﬁcient to guarantee that the resulting assignment satisﬁes s1 s6 and is Horn compliant. We take l K(w) 0, for any knowledge base K and any w W, with l K(w) = 0 if and only if w [K]. This guarantees the assignment satisﬁes s1 s3. We use the sum Σ to aggregate individual pre-orders, and this guarantees s5 s6. The next conditions spell out what is needed for an assignment to satisfy s4.

Deﬁnition 5. The distance between knowledge bases K1 and K2 is deﬁned as d(K1, K2) = min{l K1(w) | w [K2]}.

We are interested in knowledge bases that satisfy the following property.

Deﬁnition 6. Knowledge bases K1 and K2 are symmetric if d(K1, K2) = d(K2, K1).

Symmetry is important because it guarantees s4.

Proposition 5 ([Konieczny and Pino P erez, 2002]). If an assignment satisﬁes s1 s3, then it satisﬁes s4 iff any two knowledge bases are symmetric.

Interestingly, it turns out that if we ﬁx the pre-orders for every knowledge base K that has exactly one model, then pre-orders for knowledge bases K with more than one model are completely determined by this initial assignment (see Example 7). Thus, if symmetry is enforced, we can represent an assignment by just giving the pre-orders for single-model knowledge bases, as a 2n 2n matrix. We shall call this the initial matrix. The same symmetry condition forces the initial matrix to be symmetric. For s1 s3 to hold, the initial matrix needs to have positive entries and 0 on the main diagonal.3

Example 7. Table 3 shows the initial matrix for the 2 letter alphabet, plus an additional ranking obtained through symmetry. Each column represents a ranking: for instance the ﬁrst column represents the ranking for a knowledge base that has 00 as its sole model. The number assigned to 00 in this ranking is 0, the number assigned to 01 is 1, etc. The

3All this is treated rigorously in [Haret et al., 2015].

00 01 10 11 {10, 11} 00 0 1 2 3 2 01 1 0 3 5 3 10 2 3 0 8 0 11 3 5 8 0 0

Table 3: An initial assignment determines the remaining rankings by symmetry.

ranking for a knowledge base K that has {10, 11} as its set of models is computed from the initial assignment matrix with symmetry. For example, consider interpretation 00. By symmetry, we have that l K(00) = l00(K). Thus, we obtain l00(K) = min{l00(10), l00(11)} = min{2, 3} = 2. All that is left is Horn compliance, and here we propose the following notion. Deﬁnition 7. A pre-order is well-behaved if and only if for any interpretations w0, w1, w2 such that w1 w2, w2 w1 and w0 = w1 w2, it is the case that w0 w1 or w0 w2 and |min{l(w1), l(w2)} l(w0)| |max{l(w1), l(w2)} l(w0)|. Notice that a well-behaved pre-order is also Horn compliant. What makes well-behavedness suitable for our needs, however, is that it is transmitted through Σ-aggregation. Proposition 6. If 1 and 2 are well-behaved, then the preorder obtained by Σ-aggregating 1 and 2 is well-behaved. Using all this knowledge, we can now deﬁne a speciﬁc Horn compliant syncretic assignment, which we will call the summation assignment. We deﬁne this assignment for the general case of an alphabet of size n. As suggested by the previous discussion, we give the initial matrix and use symmetry to determine pre-orders K, when |[K]| > 1. Since the matrix for the initial assignment has to itself be symmetric and have 0 on the main diagonal, we will only deﬁne the entries in the matrix below the main diagonal, with the understanding that the entries above the main diagonal are ﬁxed by symmetry. Also, the order in which interpretations appear in the rows and columns is ﬁxed by the number of 1 s in the corresponding bit-vector. For instance, the matrix for the 3-letter alphabet has its rows and columns ordered as follows: 000, 001, 010, 100, 011, 101, 110, 111. The deﬁnition of the bottom half of the initial assignment matrix is recursive. First, put:

lw0(wi) = i, for i {0, . . . , 2n 1}.

Hence, the levels on the ﬁrst column are 0, 1, 2, . . . , 2n 1 (see Table 4). Second, for 1 i 2n 1, put:

lwi(wi+1) = lwi 1(wi) + lwi 1(wi+1).

Roughly, this means that the number in a particular cell under the main diagonal is the sum of its two neighbours to the left. In Table 4: if lwi 1(wi) = a, lwi 1(wi+1) = b, then lwi(wi+1) = a + b. This is simpler than it sounds, and Table 3 shows the matrix that we get for the 2-letter alphabet. The following proposition guarantees that the summation assignment is Horn compliant and stays Horn compliant through repeated Σ-aggregations.

w0 ... wi 1 wi wi+1 ... w0 0 ... i 1 i i + 1 ... . . . . . . ... . . . .. . . . . ... wi 1 i 1 ... 0 ... wi i ... a 0 ... wi+1 i + 1 ... b a + b 0 ... . . . . . . ... . . . .. . . . . ...

Table 4: The recursive relation for levels.

Proposition 7. The summation assignment is well-behaved.

This is the last piece of information needed. We can now assert the following theorem.

Theorem 5. The summation assignment represents a Horn merging operator.

6 Conclusion and future work

In this paper, we provided a novel representation theorem for Horn merging by strengthening the standard merging postulates. Belief change operators for the Horn fragment have attracted increasing attention over the last years, in particular revision and contraction, while merging in the Horn fragment remained rather unexplored so far. An exception is the work by Creignou et al. [2014], who proposed to adapt known merging operators by means of a certain post-processing and studied the limits of this approach in terms of satisfaction of the merging postulates. One of the main results of that paper is that in their framework it is not possible to keep all postulates satisﬁed. In our work, we have presented a novel concrete Horn merging operator satisfying all postulates. The moral of the present work is that, while going from syncretic assignments to Horn merging operators is relatively easy (Horn compliance is sufﬁcient, by Theorem 2), going from Horn merging operators to syncretic assignments requires considerably more machinery (in particular, stronger postulates). Thus, all the work in Section 4 is needed to obtain a full representation result. Even so, Section 5 highlights that the easiness of the ﬁrst direction is only relative, as ﬁnding concrete syncretic assignments that are also Horn compliant requires some conceptual work, and there is no obvious trivial operator that does the job. The main difﬁculty here lies in making sure that if two pre-orders 1 and 2 are Horn compliant, then the pre-order resulted from Σ-aggregating them is also Horn compliant. Our well-behavedness property guarantees this. Future work on merging in the Horn fragment would have to consider extending the family of Horn merging operators. This requires seeing how Horn compliance interacts, on the model side, with other aggregation functions (such as GMAX ) and exploring the range of conditions guaranteeing Horn compliance of an assignment. We may add to this the study of other merging postulates (e.g., majority and arbitration), considered in the merging literature [Konieczny and Pino P erez, 2002; 2011] but not touched upon here. Finally, we would like to extend our approach to other fragments of propositional logic (e.g., Krom or dual Horn), where similar problems arise and for which tailored notions of compliance and strengthened postulates are likely needed.

References [Alchourr on et al., 1985] Carlos E. Alchourr on, Peter G ardenfors, and David Makinson. On the logic of theory change: Partial meet contraction and revision functions. J. Symb. Log., 50(2):510 530, 1985. [Booth et al., 2011] Richard Booth, Thomas A. Meyer, Ivan J. Varzinczak, and Renata Wassermann. On the link between partial meet, kernel, and infra contraction and its application to Horn logic. J. Artif. Intell. Res. (JAIR), 42:31 53, 2011. [Creignou et al., 2014] Nadia Creignou, Odile Papini, Stefan R ummele, and Stefan Woltran. Belief merging within fragments of propositional logic. In Proc. ECAI 2014, volume 263 of Frontiers in Artiﬁcial Intelligence and Applications, pages 231 236. IOS Press, 2014. [Delgrande and Peppas, 2015] James P. Delgrande and Pavlos Peppas. Belief revision in Horn theories. Artif. Intell., 218:1 22, 2015. [Delgrande and Wassermann, 2013] James P. Delgrande and Renata Wassermann. Horn clause contraction functions. J. Artif. Intell. Res. (JAIR), 48:475 511, 2013. [Haret et al., 2015] Adrian Haret, Stefan R ummele, and Stefan Woltran. Merging in the Horn Fragment. Technical Report DBAI-TR-2015-91, Technische Universit at Wien, 2015. [Katsuno and Mendelzon, 1991] Hirofumi Katsuno and Alberto O. Mendelzon. On the difference between updating a knowledge base and revising it. In Proc. KR 1991, pages 387 394. Morgan Kaufmann, 1991. [Katsuno and Mendelzon, 1992] Hirofumi Katsuno and Alberto O. Mendelzon. Propositional knowledge base revision and minimal change. Artif. Intell., 52(3):263 294, 1992. [Konieczny and Pino P erez, 2002] S ebastien Konieczny and Ram on Pino P erez. Merging information under constraints: A logical framework. J. Log. Comput., 12(5):773 808, 2002. [Konieczny and Pino P erez, 2011] S ebastien Konieczny and Ram on Pino P erez. Logic based merging. J. Philosophical Logic, 40(2):239 270, 2011. [Schaefer, 1978] Thomas J. Schaefer. The complexity of satisﬁability problems. In Proc. STOC 1978, pages 216 226. ACM, 1978. [Van De Putte, 2013] Frederik Van De Putte. Prime implicates and relevant belief revision. J. Log. Comput., 23(1):109 119, 2013. [Zhuang and Pagnucco, 2012] Zhi Qiang Zhuang and Maurice Pagnucco. Model based horn contraction. In Proc. KR 2012. AAAI Press, 2012. [Zhuang et al., 2013] Zhi Qiang Zhuang, Maurice Pagnucco, and Yan Zhang. Deﬁnability of Horn revision from Horn contraction. In Proc. IJCAI 2013, 2013.