# distributing_knowledge_into_simple_bases__2936144a.pdf

Distributing Knowledge into Simple Bases

Adrian Haret and Jean-Guy Mailly and Stefan Woltran

Institute of Information Systems

TU Wien, Austria {haret,jmailly,woltran}@dbai.tuwien.ac.at

Understanding the behavior of belief change operators for fragments of classical logic has received increasing interest over the last years. Results in this direction are mainly concerned with adapting representation theorems. However, fragment-driven belief change also leads to novel research questions. In this paper we propose the concept of belief distribution, which can be understood as the reverse task of merging. More speciﬁcally, we are interested in the following question: given an arbitrary knowledge base K and some merging operator , can we ﬁnd a proﬁle E and a constraint µ, both from a given fragment of classical logic, such that µ(E) yields a result equivalent to K? In other words, we are interested in seeing if K can be distributed into knowledge bases of simpler structure, such that the task of merging allows for a reconstruction of the original knowledge. Our initial results show that merging based on drastic distance allows for an easy distribution of knowledge, while the power of distribution for operators based on Hamming distance relies heavily on the fragment of choice.

1 Introduction Belief change and belief merging have been topics of interest in Artiﬁcial Intelligence for three decades [Alchourr on et al., 1985; Katsuno and Mendelzon, 1991; Konieczny and Pino P erez, 2002]. However, the restriction of such operators to speciﬁc fragments of propositional logic has received increasing attention only in the last years [Delgrande et al., 2013; Creignou et al., 2014a; 2014b; Zhuang and Pagnucco, 2012; Zhuang et al., 2013; Zhuang and Pagnucco, 2014; Delgrande and Peppas, 2015; Haret et al., 2015]. Mostly, the question tackled in these works is How should rationality postulates and change operators be adapted to ensure that the result of belief change belongs to a given fragment? . Surprisingly, the question concerning the extent to which the result of a belief change operation can deviate from the fragment under consideration has been neglected so far. In order to tackle this question, we focus here on a certain form of reverse merging. The question is, given an arbitrary knowledge base K and

some IC-merging (i.e. merging with integrity constraint, see [Konieczny and Pino P erez, 2002]) operator , can we ﬁnd a proﬁle E, i.e. a tuple of knowledge bases, and a constraint µ, both from a given fragment of classical logic, such that µ(E) yields a result equivalent to K? In other words, we are interested in seeing if K can be distributed into knowledge bases of simpler structure, such that the task of merging allows for a reconstruction of the original knowledge. We call this operation knowledge distribution.

Studying the concept of knowledge distribution can be motivated from different points of view. First, consider a scenario where the storage devices have limited expressibility, for instance, databases or logic programs. Our analysis will show which merging operators are required to reconstruct arbitrary knowledge stored in such a set of limited devices. Second, distribution can also be understood as a tool to hide information; only users who know the used merging operator (which thus acts as an encryption key) are able to faithfully retrieve the distributed knowledge. Given the high complexity of belief change (even for revision in simple fragments like Horn and 2CNF [Eiter and Gottlob, 1992; Liberatore and Schaerf, 2001; Creignou et al., 2013]), bruteforce attack to guess the merging operator is unthinkable. Finally, from the theoretical perspective our results shed light on the power of different merging operators when applied to proﬁles from certain fragments. In particular, our results show that merging 1CNF formulas via the Hammingdistance based operator H, does not need additional care, since the result is guaranteed to stay in the fragment.

Related Work. Previous work on merging in fragments of propositional logic proposed an adaptation of existing belief merging operators to ensure that the result of merging belongs to a given fragment [Creignou et al., 2014b], or modiﬁed the rationality postulates in order to function in the Horn fragment [Haret et al., 2015]. Our approach is different, since we do not require that the result of merging stays in a given fragment. On the contrary, we want to decompose arbitrary bases into a fragment-proﬁle. Recent work by Liberatore has also addressed a form of meta-reasoning over belief change operators. In [Liberatore, 2015a], the input is a proﬁle of knowledge bases with the expected result of merging R, and the aim is to determine the reliability of the bases (for instance, represented by weights) which allow the obtaining of R. In

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI-16)

another paper, Liberatore [2015b] identiﬁes, given a sequence of belief revisions and their results, the initial pre-order which characterizes the revision operator. Finally, even if our approach may seem related to Knowledge Compilation (KC) [Darwiche and Marquis, 2002; Fargier and Marquis, 2014; Marquis, 2015], both methods are in fact conceptually different. KC aims at modifying a knowledge base K into a knowledge base K0 such that the most important queries for a given application (consistency checking, clausal entailment, model counting, . . . ) are simpler to solve with K0. Here, we are interested in the extent to which it is possible to equivalently represent an arbitrary knowledge base by simpler fragments when using merging as a recovery operation.

Main Contributions. We formally introduce the concept of knowledge distributability, as well as a restricted version of it where the proﬁle is limited to a single knowledge base (simpliﬁability). We show that for drastic distance arbitrary knowledge can be distributed into bases restricted to mostly any kind of fragment, while simpliﬁability is limited to trivial cases. On the other hand, for Hamming-distance based merging the picture is more opaque. We show that for 1CNF, distributability w.r.t. H, is limited to trivial cases, while slightly more can be done with H,GMin and H,GMax. For 2CNF we show that arbitrary knowledge can be distributed and even be simpliﬁed. Finally, we discuss the Horn fragment for which the results for H, , H,GMin and H,GMax are situated in between the two former fragments.

2 Background

Fragments of Propositional Logic. We consider L as the language of propositional logic over some ﬁxed alphabet U of propositional atoms. We use standard connectives _, , , and constants >, ?. A clause is a disjunction of literals. A clause is called Horn if at most one of its literals is positive. An interpretation is a set of atoms (those set to true). The set of all interpretations is 2U. Models of a formula ' are denoted by Mod('). A knowledge base (KB) is a ﬁnite set of formulas and we identify models of a KB K via Mod(K) = T

'2K Mod('). A proﬁle is a ﬁnite non-empty tuple of KBs. Two formulae '1, '2 (resp. KBs K1, K2) are equivalent, denoted '1 '2 (resp. K1 K2), when they have the same set of models.

We use a rather general and abstract notion of fragments.

Deﬁnition 1. A mapping Cl : 22U ! 22U is called closureoperator if it satisﬁes the following for any M, N 2U:

If M N, then Cl(M) Cl(N)

If |M| = 1, then Cl(M) = M

Deﬁnition 2. L0 L is called a fragment if it is closed under conjunction (i.e., ' 2 L0 for any ', 2 L0), and there exists an associated closure-operator Cl such that (1) for all 2 L0, Mod( ) = Cl(Mod( )) and (2) for all M 2U there is a 2 L0 with Mod( ) = Cl(M). We often denote the closure-operator Cl associated to a fragment L0 as Cl L0.

Deﬁnition 3. For a fragment L0, we call a ﬁnite set K L0 an L0-knowledge base. An L0-proﬁle is a proﬁle over L0knowledge bases. A KB K L is called L0-expressible if there exists an L0-KB K0, such that K K0.

Many well known fragments of propositional logic are indeed captured by our notion. For the Horn-fragment LHorn, i.e. the set of all conjunctions of Horn clauses over U, take the operator Cl LHorn deﬁned as the ﬁxed point of the function

LHorn(M) = {!1 \ !2 | !1, !2 2 M}.

The fragment L2CNF which is restricted to formulas over clauses of length at most 2 is linked to the operator Cl L2CNF deﬁned as the ﬁxed point of the function Cl1

L2CNF given by

L2CNF (M) = {maj3(!1, !2, !3) | !1, !2, !3 2 M}.

Here, we use the ternary majority function maj3(!1, !2, !3) which yields an interpretation containing those atoms which are true in at least two out of !1, !2, !3. Finally, we are also interested in the L1CNF fragment which is just composed of conjunctions of literals; its associated operator Cl L1CNF is deﬁned as the ﬁxed point of the function

L1CNF (M) = {!1 \ !2, !1 [ !2 | !1, !2 2 M} [ {!3 | !1 !3 !2; !1, !2 2 M}.

Note that full classical logic is given via the identity closure operator Cl L(M) = M.

Merging Operators. We focus on IC-merging, where a proﬁle is mapped into a KB, such that the result satisﬁes some integrity constraint. Postulates for IC-merging have been stated in [Konieczny and Pino P erez, 2002]. We recall a speciﬁc family of IC-merging operators, based on distances between interpretations, see also [Konieczny et al., 2004].

Deﬁnition 4. A distance between interpretations is a mapping d from two interpretations to a non-negative real number, such that for all !1, !2, !3 U, (1) d(!1, !2) = 0 iff !1 = !2; (2) d(!1, !2) = d(!2, !1); and (3) d(!1, !2) + d(!2, !3) d(!1, !3). We will use two speciﬁc distances:

drastic distance D(!1, !2) = 1 if !1 = !2, 0 otherwise;

Hamming distance H(!1, !2) = |(!1 \ !2) [ (!2 \ !1)|.

We overload the previous notations to deﬁne the distance between an interpretation ! and a KB K: if d is a distance between interpretations, then d(!, K) = min!02Mod(K) d(!, !0). Next, an aggregation function must be used to evaluate the distance between an interpretation and a proﬁle.

Deﬁnition 5. An aggregation function associates a nonnegative number to every ﬁnite tuple of non-negative numbers, such that (1) if x y, then (x1, . . . , x, . . . , xn) (x1, . . . , y, . . . , xn); (2) (x1, . . . , xn) = 0 iff x1 = = xn = 0; (3) for every non-negative number x, (x) = x. As aggregation functions, we will consider the

sum , GMax and GMin1, deﬁned as follows. Given a proﬁle (K1, . . . , Kn), let V! = (d!

1 , . . . , d!

n) be the vector of distances such that d!

i = d(!, Ki). GMax(d!

1 , . . . , d!

n) (resp. GMin(d!

1 , . . . , d!

n)) is deﬁned by ordering V! in decreasing (resp. increasing) order. Given two interpretations !1, !2, GMax(d!1

1 , . . . , d!1 n ) GMax(d!2

1 , . . . , d!2 n ) (resp. GMin(d!1

1 , . . . , d!1 n ) GMin(d!2

1 , . . . , d!2 n )) is deﬁned by comparing them w.r.t. the lexicographic ordering.

Finally, let d be a distance, ! an interpretation and E = (K1, . . . , Kn) a proﬁle. Then, d (!, E) = (d(!, K1), . . . , d(!, Kn)). If there is no ambiguity about the function , we write d(!, E) for d (!, E). Deﬁnition 6. For any distance d between interpretations, and any aggregation function , the merging operator d, is a mapping from a proﬁle E and a formula µ to a KB, such that Mod( d,

µ (E)) = min(Mod(µ), d,

E ), with !1 d,

E !2 iff d (!1, E) d (!2, E).

When we consider a proﬁle containing a single knowledge base K, all aggregation functions are equivalent; we write d

µ(K) instead of d,

µ ((K)) for readability. For drastic distance, GMin, GMax, and are equivalent for arbitrary proﬁles. Thus, whenever we show results for D, , these carry over to D,GMin and D,GMax.

3 Main Concepts and General Results We now give the central deﬁnition for a knowledge base being distributable into a proﬁle from a certain fragment with respect to a given merging operator. Deﬁnition 7. Let be a merging operator, K L be an arbitrary KB, and L0 be a fragment. K is called L0-distributable w.r.t. if there exists an L0-proﬁle E and a formula µ 2 L0, such that µ(E) K. Example 1. Let U = {a, b} and consider K = {a _ b} which we want to check for LHorn-distributability w.r.t. operator H, . We have Mod(K) = {{a}, {b}, {a, b}}, thus K is not LHorn-expressible (note that Cl LHorn(Mod(K)) = {;, {a}, {b}, {a, b}} 6= Mod(K)), otherwise K would be distributable in a simple way (see Proposition 1 below).

Take the LHorn-proﬁle E = (K1, K2) with K1 = {a b}, K2 = { a _ b}, together with the empty constraint µ = >. We have Mod(K1) = {{a, b}}, Mod(K2) = {{a}, {b}, ;}. In the following matrix, each line corresponds to the distance between a model of µ and a KB from the proﬁle E, or between a model of µ and the proﬁle using the -aggregation over the distances to the single KBs.

K1 K2 {a, b} 0 1 1 {a} 1 0 1 {b} 1 0 1 ; 2 0 2

1GMax and GMin are known as leximax and leximin respectively. These functions return a vector of numbers, not a single number. However, GMax (resp. GMin) can be associated with an aggregation function as deﬁned in Def. 5 which yields the same vector ordering than GMax (resp. GMin). We do a slight abuse by using GMax and GMin as the names of aggregation functions. See [Konieczny et al., 2002].

We observe that Mod( H,

µ (E)) = {{a}, {b}, {a, b}}, thus H,

µ (E) K as desired. It is easily checked that also other aggregations work: H,GMax

µ (E) H,GMin

Next, we recall that IC-merging of a single KB yields revision. Thus, the concept we introduce next is also of interest, as it represents a certain form of reverse revision. Deﬁnition 8. Let be a merging operator, K L an arbitrary KB, and L0 a fragment. K is called L0-simpliﬁable w.r.t. if there exists an L0-KB K0 and µ 2 L0, such that µ(K0) K.

As we will see later, the KB K from Example 1 cannot be LHorn-simpliﬁed w.r.t. H; in other words, we need here at least two KBs to express K. However, it is rather straightforward that any L0-expressible KB can be L0-simpliﬁed. Proposition 1. For every fragment L0 and every KB K, it holds that K is L0-simpliﬁable (and thus also L0distributable) w.r.t. , whenever K is L0-expressible.

Proof. Let K0 be an L0-KB equivalent to K, and let µ = (V

'2K0 '). Thus, µ 2 L0 by deﬁnition of fragments and it is easily veriﬁed that µ(K0) K.

Next, we show that in order to determine whether a KB K is L0-distributable, it is sufﬁcient to consider constraints µ such that Mod(µ) = Cl L0(Mod(K)). Proposition 2. Let K 2 L be a KB, L0 be a fragment, E an L0-proﬁle and µ 2 L0. Then µ(E) K implies µ0(E) K for any µ0 such that Mod(µ0) = Cl L0(Mod(K)).

Proof. Let = d, . By Deﬁnition 6, Mod(K) = min(Mod(µ), d,

E ), hence Mod(K) Mod(µ). Moreover, µ is L0-closed, so Cl L0(Mod(K)) = Mod(µ0) Mod(µ). We get Mod(K) Mod(µ0) Mod(µ). Thus, Mod(K) = min(Mod(µ0), d,

E ), i.e. µ0(E) K.

Next, we give two positive results for distributing knowledge in any fragment. The key idea is to use KBs in the proﬁle which have exactly one model (our notion of fragment guarantees existence of such KBs). The ﬁrst result is independent of the distance notion but requires GMin as the aggregation function. The second result is for drastic distance and thus works for any of the aggregation functions we consider. Theorem 3. Let d be a distance and L0 be a fragment. Then for every KB K, such that for all distinct !1, !2 2 Mod(K), d(!1, !2) = e for some e > 0, it holds that K is L0distributable w.r.t. d,GMin.

Proof. Build the L0-proﬁle E such that for each ! 2 Mod(K), there is a KB with ! as its only model. Thus all models of K get a GMin-vector (0, e, e, e, e, . . .). All interpretations from Cl L0(Mod(K)) \ Mod(K) get a vector (f, g, . . .) with f > 0. Hence, we have min(Mod(µ), d,GMin

E ) = Mod(K) using µ 2 L0 with Mod(µ) = Cl L0(Mod(K)).

Theorem 4. For every fragment L0 and every knowledge base K, it holds that K is L0-distributable w.r.t. D, , for 2 { , GMin, GMax}.

The proof is similar to the one of Theorem 3 and thus omitted. For simpliﬁability w.r.t. drastic distance based operators, Proposition 1 cannot be improved, as we show next.

Theorem 5. For every fragment L0 and every KB K, K is L0-simpliﬁable w.r.t. D iff K is L0-expressible.

Proof. The if-direction is by Proposition 1. For the other direction, suppose K is not L0-expressible. We show that for any L0-KB K0, D

µ (K0) 6 K with µ = Cl L0(K). By Proposition 2 the result then follows. Now suppose there exists an L0-KB K0 such that D

µ (K0) K. First observe that since K is not L0-expressible, Mod(µ) Mod(K). Since we are working with drastic distance, in order to promote models of K, we also need them in K0, hence Mod(K0) Mod(K) and since K0 is from L0 we have Mod(K0) Cl L0(K) = Mod(µ). Thus there exists ! 2 Cl L0(Mod(K)) \ Mod(K) having distance 0 to K0, and thus ! 2 D

µ (K0). Since ! /2 Mod(K), this yields a contradiction to D

4 Hamming Distance and Speciﬁc Fragments

We ﬁrst consider the simplest fragment under consideration, namely conjunction of literals. As it turns out, (non-trivial) distributability for this fragment w.r.t. H, is not achievable. We then see that more general fragments allow for nontrivial distributions. In particular, we show that every KB is distributable (and even simpliﬁable) in the 2CNF case, and we ﬁnally give a few observations for LHorn.

4.1 The 1CNF Fragment The following technical result is important to prove the main result in this section.

Lemma 6. For any L1CNF-proﬁle E = (K1, . . . , Kn) and interpretations !1, !2, it holds that:

H(!1, E) + H(!2, E) = H(!1 \ !2, E) + H(!1 [ !2, E).

Proof. It sufﬁces to show that for each Ki in proﬁle E, H(!1, Ki)+H(!2, Ki) = H(!1\!2, Ki)+H(!1[!2, Ki). Indeed, summing up these equalities over all Ki 2 E, we get

Ki2EH(!1, Ki) + Ki2EH(!2, Ki) = Ki2EH(!1 \ !2, Ki) + Ki2EH(!1 [ !2, Ki).

Since H(!, E) = Ki2EH(!, Ki), for any interpretation !, our conclusion then follows immediately.

Thus, take !0

2 to be two interpretations that are closest to !1 and !2, respectively, among the models of Mod(Ki). In other words, H(!1, !0

1) = min!2Mod(Ki) H(!1, !) and H(!2, !0

2) = min!2Mod(Ki) H(!2, !). By induction on the number of propositional atoms in L, we can show that !0

2 are closest in Mod(Ki) to !1 \ !2 and !1 [ !2, respectively. Thus, we have that H(!1, Ki) = H(!1, !0

1), H(!2, Ki) = H(!2, !0

2), H(!1\!2, Ki) = H(!1\!2, !0

2), H(!1 [ !2, Ki) = H(!1 [ !2, !0

2), and our problem reduces to showing that H(!1, !0

1) + H(!2, !0

2) = H(!1 \!2, !0

2)+H(!1 [!2, !0

2). By using induction on the number of propositional atoms in L again, we can show that this equality holds. The argument runs as follows:

in the base case, when the alphabet consists of just one propositional atom, the equality is shown to be true by checking all the cases. For the inductive step we assume the claim holds for an alphabet of size n and show that it also holds for an alphabet of size n+1. Concretely, we analyze the way in which the Hamming distances between interpretations change when we add a propositional atom to the alphabet. An analysis of all the possible cases shows that the equality holds.

Next we observe certain patterns of interpretations that indicate whether a KB is L1CNF-expressible or not.

Deﬁnition 9. If K is a knowledge base, then a pair of interpretations !1 and !2 are called critical with respect to K if !1 * !2 and !2 * !1, and one of the following cases holds:

1. !1, !2 2 Mod(K) and !1 \ !2, !1 [ !2 /2 Mod(K),

2. !1, !2, !1 \ !2 2 Mod(K) and !1 [ !2 /2 Mod(K),

3. !1, !2, !1 [ !2 2 Mod(K) and !1 \ !2 /2 Mod(K),

4. !1 \ !2, !1 [ !2 2 Mod(K) and !1, !2 /2 Mod(K), or

5. !1, !1 \ !2, !1 [ !2 2 Mod(K) and !2 /2 Mod(K).

Lemma 7. If a KB K is not L1CNF-expressible, then there exist !1, !2 2 Cl L1CNF (K) being critical with respect to K.

Proof. The fact that K is not L1CNF-expressible implies that either: (i) K is not closed under intersection or union, or (ii) there are w1, w2, w3 2 Cl L1CNF (K) such that w1 w3 w2, and w1, w2 2 Mod(K), w3 /2 Mod(K). Case (i) implies that there exist w1, w2 2 Mod(K) such that one of Cases 1-3 from Deﬁnition 9 holds. If we are in Case (ii), then consider the interpretation w4 = (w2\w3) [ w1. Clearly, w1 w4 w2, hence w4 2 Cl L1CNF (K). Also, w3 \ w4 = w1 and w3 [ w4 = w2. There are two sub-cases to consider here. If w4 /2 Mod(K), then we are in Case 4 of Deﬁnition 9. If w4 2 Mod(K), then we are in Case 5 of Deﬁnition 9.

We can now state the central result of this section.

Theorem 8. A KB K is L1CNF-distributable with respect to H, if and only if K is L1CNF-expressible.

Proof. If part is by Proposition 1. Only if part: let K be a KB that is not L1CNF-expressible. We will show that it is not L1CNF-distributable w.r.t. H, . Suppose, on the contrary, that K is L1CNF-distributable. Then there exists an L1CNF proﬁle E = (K1, . . . , Kn) such that H,

µ (E) K, where Mod(µ) = Cl L1CNF (Mod(K)) (cf. Proposition 2).

By Lemma 7, there exist interpretations !1, !2 2 Mod(µ) that are critical with respect to K. By Lemma 6, we have

H(!1, E)+H(!2, E)=H(!1\!2, E)+H(!1[!2, E). (1)

Let us now do a case analysis depending on the type of critical pair we are dealing with. If we are in Case 1 of Deﬁnition 9, then it needs to be the case that H(!1, E) = H(!2, E) = m, H(!1 \ !2, E) = m + k1 and H(!1 [ !2, E) = m + k2, for some integers m 0 and k1, k2 > 0. Plugging these numbers into Equality (1), we get that 2m = 2m + k1 + k2 and k1 + k2 = 0. Since k1, k2 > 0, we have arrived at a contradiction. If we are in Case 2, then it needs to be the case that H(!1 \ !2, E) = H(!1 [ !2, E) = m, H(!1, E) =

m+k1 and H(!2, E) = m+k2, for some integers m 0 and k1, k2 > 0. Plugging these numbers into Equality (1) again, we get a contradiction along the same lines as in Case 1. If we are in Case 3, then it needs to hold that H(!1, E) = H(!1 \ !2, E) = H(!1 [ !2, E) = m, H(!2, E) = m + k, for some integers m 0 and k > 0. Plugging these numbers into Equality (1) gives us 2m + k = 2m and hence k = 0. Since k > 0, we have arrived at a contradiction. Cases 4 and 5 are entirely similar.

In other words, for any L1CNF-proﬁle and µ 2 1CNF, H,

µ is guaranteed to be L1CNF-expressible as well. As we have already shown in Theorem 3, this is not necessarily the case if we replace by GMin. The following example shows how to obtain a similar behavior for GMax; we then generalize this idea below.

Example 2. Let U = {a, b} and K = {a _ b, a _ b}. We have Mod(K) = {{a}, {b}}. K is not L1CNF-expressible, since Cl L1CNF (Mod(K)) = 2U. Let KS be the L1CNFKB with a single model S for any S U and let us have a look at the following distance matrix for µ with Mod(µ) = Cl L1CNF (Mod(K)), E = (K{a}, K{b}), and E0 = (K;, K{a,b}).

K; K{a} K{b} K{a,b} HGMin(E) HGMax(E0) ; 0 1 1 2 (1, 1) (2, 0) {a} 1 0 2 1 (0, 2) (1, 1) {b} 1 2 0 1 (0, 2) (1, 1) {a, b} 2 1 1 0 (1, 1) (2, 0)

The lexicographic order of the involved vectors is (0, 2) < (1, 1) < (2, 0). We thus get that H,GMin

µ (E) K (see also Theorem 3), and on the other hand, H,GMax

Theorem 9. Any KB K such that Mod(K) = {!, !0} is L1CNF-distributable with respect to H,GMax.

Proof. If K is L1CNF-expressible, then the conclusion follows from Proposition 1. If K is not L1CNF-expressible, then consider the set Cl L1CNF (Mod(K))\Mod(K) = {!1, . . . , !n}. We deﬁne the proﬁle E = (K1, . . . , Kn), where Mod(Ki) = {U\!i}, for i 2 {1, . . . , n}. We show that H,GMax

µ (E) K, where Mod(µ) = Cl L1CNF (Mod(K)). First, we have that H(!i, U\!i) = |U|, which implies that HGMax(!i, E) = GMax(|U|, . . . ), for any i 2 {1, . . . , n}. Furthermore, since H(!, U\!i) < |U| and H(!0, U\!i) < |U|, for any i 2 {1, . . . , n}, it follows that ! <H,GMax

E !i and !0 <H,GMax

E !i. Next, we show that HGMax(!, E) = HGMax(!0, E). Consider the vectors V = (H(!, !1), . . . , H(!, !n)) and V 0 = (H(!0, !1), . . . , H(!0, !n)). Our claim is that GMax(V ) = GMax(V 0). To see why, notice that the elements in Cl L1CNF (Mod(K)) form a complete subset lattice with ![!0 and ! \ !0 as the top and bottom elements, respectively. Let us write H(!, !0) = m. This lattice has 2m elements, and the maximum distance of two elements in it is m. Thus, the vector V is the vector of distances between ! and every other element in this lattice, except itself and !0. A similar consideration holds for V 0. Hence V and V 0 are vectors of length

2m 2 whose elements are m 1, m 2, . . . , 1. We can actually count how many times each number appears in V and V 0. The number of interpretations in the lattice that are at distance of 1 from ! (and !0) is

: thus, m 1 appears

times in V (and V 0). The number of interpretations that are at distance 2 from ! (and !0) is

, thus m 2 appears

times in V and V 0. We iterate this argument for every distance, up to 1. It is then easy to see that, based on these considerations, V and V 0 are equal when sorted in descending order. Our conclusion follows from this.

4.2 The 2CNF Fragment We show that every knowledge base K can be distributed in the fragment L2CNF. Even a single L2CNF knowledge base is enough to represent K. Before giving the general result, we sketch the idea via an example. Example 3. Let K be a KB with Mod(K) = {{a, b}, {b, c, e}, {a, c, d}}. We observe that K is not L2CNF-expressible since Cl L2CNF (Mod(K)) = Mod(K) [ {a, b, c}. However, we can give an L2CNF-KB K0 using three new atoms x, y, z to penalize the undesired interpretation {a, b, c} such that H

µ (K0) K, with µ 2 L2CNF of the form Mod(µ) = Cl L2CNF (Mod(K)). To this end, assume K0 with Mod(K0) = {!1, !2, !3, !4} of the form

!1 = {a, b, x, y}, !2 = {b, c, e, x, z}, !3 = {a, c, d, y, z}, !4 = {a, b, c, x, y, z}.

One can verify that Cl L2CNF (Mod(K0)) = Mod(K0). Thus, K0 can be picked from L2CNF. We use µ such that Mod(µ) = Cl L2CNF (Mod(K)) and get distances

!1 !2 !3 !4 min {a, b} 2 5 5 4 2 {b, c, e} 4 2 6 4 2 {a, c, d} 4 6 2 4 2 {a, b, c} 3 4 4 3 3

Here, each line gives the distance between a model of µ and a model of K0 (!i columns), or between a model of µ and K0 (min column). The key observation is that pairs from x, y, z as used in !1, !2, !3 give minimal distances 2 while the remaining interpretation !4, which corresponds to the closure of K, contains all three new atoms (since maj3({x, y}, {x, z}, {y, z}) = {x, y, z}).

Theorem 10. Any KB K is L2CNF-simpliﬁable w.r.t. H

Proof. We have to show that for any KB K, there exists an L2CNF-KB K0 and a formula µ 2 L2CNF such that H

µ (K0) K. If K is L2CNF-expressible, the result is due to Proposition 1. So suppose that K is not L2CNFexpressible and let Mod(K) = {!1, . . . , !n}. Consider a set of new atoms A = {a1, . . . , an}, and for each !i 2 Mod(K), let !0

i = !i [ A \ {ai}. We deﬁne the L2CNF-KB K0 and µ 2 L2CNF such that Mod(K0) = Cl L2CNF ({!0

i | !i 2 Mod(K)}) and Mod(µ) = Cl L2CNF (Mod(K)). Let 0 = {!0

i | !i 2 Mod(K)}. We ﬁrst show that for each ! 2 Mod(K0) \ 0, A !. Indeed, for any triple !j, !k, !l 2 Mod(K), such that !jkl = maj3(!j, !k, !l) /2 Mod(K), we

observe that maj3(!0

l) = !jkl [ maj3(A \ {aj}, A \ {ak}, A\{al}) = !jkl[A. Thus, for each ! 2 Cl1

L2CNF ( 0)\ 0, A !. Recall that Mod(K0) = Cl L2CNF ( 0). It follows quite easily that each further interpretation ! 2 Cl L2CNF ( 0) \ (Cl1

L2CNF ( 0) [ 0), also satisﬁes A !. This shows that each model of K0 contains at least n 1 atoms from A. Thus, for every model !i 2 K, H(!i, K0) = H(!i, !0

i) = n 1. It remains to show that for each ! 2 Mod(µ) \ Mod(K), H(!, K0) n. First, let !0 2 0. Since ! /2 Mod(K), !0 \ A 6= ! and since !0 contains n 1 elements from A, we have H(!, !0) n. As shown above all other interpretations !00 2 Mod(K0) \ 0 contain all n atoms from A, thus H(!, !00) n, too.

As an immediate consequence, we obtain that any KB K is L2CNF-distributable w.r.t. H, for any aggregation function . Note that this result is in strong contrast to the L1CNF fragment, where only L1CNF-expressible KBs are L1CNFdistributable w.r.t. H, .

4.3 The Horn-Fragment

We now turn our attention to the LHorn fragment. Recall Example 1 where we have shown how to distribute some non LHorn-expressible KB using a proﬁle over two LHorn-KBs. Our ﬁrst result shows that in this example case we cannot reduce to proﬁles of a single KB, i.e. that there are KBs which are LHorn-distributable but not LHorn-simpliﬁable.

Proposition 11. A KB K with Mod(K) = {!1, !2, !3}, where !3 = !1 [ !2, H(!1, !2) = 2 and !1, !2 are incomparable, is not LHorn-simpliﬁable w.r.t. H.

Proof. The situation described in the proposition corresponds to a KB K = {! [ {a}, ! [ {b}, ! [ {a, b}} with ! some interpretation which does not contain a or b. We need Mod(µ) = {!, ! [ {a}, ! [ {b}, ! [ {a, b}}, as required by Proposition 2. We want to identify a LHorn-KB K0 such that H

µ (K0) K. This means that ! is the single model of µ which is not minimal w.r.t. the Hamming distance. Let !0

1 be the model in K0 closest to !1 = ! [ {a} and !0

2 the one closest to !2 = ! [ {b}. We need a 2 !0

1 and b 2 !0

2; otherwise H(!, !0

1) < H(!1, !0

1) or H(!, !0

2) < H(!2, !0

2); further we need b /2 !0

1 and a /2 !0

2; otherwise H(!3, !0

1) < H(!1, !0

1) or H(!3, !0

2) < H(!2, !0

2). Hence !0

2 are incomparable thus also !0

2 2 Mod(K0), since K0 is a Horn KB. But then H(!, !0

2) H(!1, !0

Our last result shows that H nonetheless increases the range of LHorn-simpliﬁable KBs compared to D.

Proposition 12. Any knowledge base K with Mod(K) = {!1, !2} is LHorn-simpliﬁable w.r.t. H.

Proof. If !1, !2 are comparable, we can apply Proposition 1. Thus, assume !1, !2 are incomparable and let d1 = |!1 \ !2| and d2 = |!2 \ !1|. W.l.o.g. assume d1 d2. Also note that d1 > 0. We use K0 with Mod(K0) = {!+

1 , !1 [ !2} where !+

1 adds d1 elements from !2 \ !1 to !1. Thus, !+

1 !1[!2 and we can choose K0 from LHorn. Moreover, let µ 2

1CNF 2CNF Horn simpliﬁable w.r.t. D simpliﬁable w.r.t. H X distributable w.r.t. D, X X X distributable w.r.t. H, X distributable w.r.t. H,GMax X distributable w.r.t. H,GMin X

Table 1: Summary of Results

LHorn such that Mod(µ) = {!1, !2, !1 \ !2}. We have the following distances (note that d(!2, !+

1 ) = d1 + (d2 d1)).

1 !1 [ !2 K0

!1 d1 d2 d1 !2 d2 d1 d1 !1 \ !2 2d1 d1 + d2 > d1

µ (K0) K as desired.

5 Conclusion

In this paper we have proposed the notion of distributability and we have studied the properties of several merging operators with respect to different fragments of propositional logic. Our results are summarized in Table 1.

Symbol means that only trivial KBs (belonging to the considered fragment) can be distributed with the corresponding operator. Alternately, X means that any KB can be distributed. Symbol means we know that some non-trivial KBs can be distributed, and ﬁnally means that some, but not all, non-trivial KBs can be simpliﬁed. Interestingly, the picture emerging from Table 1 is that merging operators behave quite differently depending on the distance and aggregation function employed, in a way that does not lend itself to simple categorization. For instance, our results on simpliﬁability imply that using Dalal revision to L1CNF KBs never takes us outside the 1CNF fragment; applying the same revision operator to L2CNF KBs can produce any KB in L; and applying it to LHorn KBs can produce some, though not all possible KBs.

Several questions are still open for future work. We plan to study the exact characterization of what can (and cannot) be distributed, in order to replace the symbols and in the Table 1. Other merging operators can also be integrated to our study. Some of our results on distributability require the addition of new atoms to the interpretations. We want to determine whether similar results can be obtained without modifying the set of propositional variables. We are also interested in the number of KBs needed to distribute knowledge: given an integer n, a KB K and a merging operator , is it possible to distribute K w.r.t. such that the resulting proﬁle contains at most n KBs? This paper was a ﬁrst step to understand the limits of distributability; the actual construction of the proﬁle and complexity of this process are important questions that will be tackled in future research. Finally, we also consider applying the concept of distributability to non-classical formalisms, in particular in connection with merging operators proposed for logic programs [Delgrande et al., 2013].

Acknowledgments

This work was supported by the Austrian Science Fund (FWF) under grant P25521.

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. Journal of Symbolic Logic, 50:510 530, 1985. [Creignou et al., 2013] Nadia Creignou, Reinhard Pichler,

and Stefan Woltran. Do hard SAT-related reasoning tasks become easier in the Krom fragment? In Proceedings of the Twenty-Third International Joint Conference on Artiﬁcial Intelligence (IJCAI 13), pages 824 831, 2013. [Creignou et al., 2014a] Nadia Creignou, Odile Papini, Reinhard Pichler, and Stefan Woltran. Belief revision within fragments of propositional logic. Journal of Computer and System Sciences, 80(2):427 449, 2014. [Creignou et al., 2014b] Nadia Creignou, Odile Papini, Ste-

fan R ummele, and Stefan Woltran. Belief merging within fragments of propositional logic. In Proceedings of the Twenty-First European Conference on Artiﬁcial Intelligence (ECAI 14), pages 231 236, 2014. [Darwiche and Marquis, 2002] Adnan Darwiche and Pierre

Marquis. A knowledge compilation map. Journal of Artiﬁcial Intelligence Research (JAIR), 17:229 264, 2002. [Delgrande and Peppas, 2015] James P. Delgrande and Pav-

los Peppas. Belief revision in Horn theories. Artiﬁcial Intelligence, 218:1 22, 2015. [Delgrande et al., 2013] James P. Delgrande, Torsten Schaub, Hans Tompits, and Stefan Woltran. A modeltheoretic approach to belief change in answer set programming. ACM Transactions on Computational Logic, 14(2), 2013. [Eiter and Gottlob, 1992] Thomas Eiter and Georg Gottlob.

On the complexity of propositional knowledge base revision, updates, and counterfactuals. Artiﬁcial Intelligence, 57(2-3):227 270, 1992. [Fargier and Marquis, 2014] H el ene Fargier and Pierre Mar-

quis. Disjunctive closures for knowledge compilation. Artiﬁcial Intelligence, 216:129 162, 2014. [Haret et al., 2015] Adrian Haret, Stefan R ummele, and Ste-

fan Woltran. Merging in the Horn fragment. In Proceedings of the Twenty-Fourth International Joint Conference on Artiﬁcial Intelligence (IJCAI 15), pages 3041 3047, 2015. [Katsuno and Mendelzon, 1991] Hirofumi Katsuno and Al-

berto O. Mendelzon. Propositional knowledge base revision and minimal change. Artiﬁcial Intelligence, 52:263 294, 1991. [Konieczny and Pino P erez, 2002] S ebastien Konieczny and

Ram on Pino P erez. Merging information under constraints: a logical framework. Journal of Logic and Computation, 12(5):773 808, 2002.

[Konieczny et al., 2002] S ebastien Konieczny, J erˆome Lang,

and Pierre Marquis. Distance-based merging: a general framework and some complexity results. In Proceedings of the Eighth International Conference on Principles of Knowledge Representation and Reasoning (KR 02), pages 97 108, 2002. [Konieczny et al., 2004] S ebastien Konieczny, J erˆome Lang,

and Pierre Marquis. DA2 merging operators. Artiﬁcial Intelligence, 157(1-2):49 79, 2004. [Liberatore and Schaerf, 2001] Paolo Liberatore and Marco

Schaerf. Belief revision and update: Complexity of model checking. Journal of Computer and System Sciences, 62(1):43 72, 2001. [Liberatore, 2015a] Paolo Liberatore. Belief merging by examples. ACM Transactions on Computational Logic, 17(2), 2015. [Liberatore, 2015b] Paolo Liberatore. Revision by history.

Journal of Artiﬁcial Intelligence Research (JAIR), 52:287 329, 2015. [Marquis, 2015] Pierre Marquis. Compile! In Proceedings

of the Twenty-Ninth AAAI Conference on Artiﬁcial Intelligence, pages 4112 4118, 2015. [Zhuang and Pagnucco, 2012] Zhi Qiang Zhuang and Mau-

rice Pagnucco. Model based horn contraction. In Proceedings of the Thirteenth International Conference on Principles of Knowledge Representation and Reasoning (KR 12), pages 169 178, 2012. [Zhuang and Pagnucco, 2014] Zhiqiang Zhuang and Mau-

rice Pagnucco. Entrenchment-based horn contraction. Journal of Artiﬁcial Intelligence Research (JAIR), 51:227 254, 2014. [Zhuang et al., 2013] Zhi Qiang Zhuang, Maurice Pagnucco,

and Yan Zhang. Deﬁnability of horn revision from horn contraction. In Proceedings of the Twenty-Third International Joint Conference on Artiﬁcial Intelligence (IJCAI 13), pages 1205 1211, 2013.