# belief_update_in_the_horn_fragment__f6281610.pdf

Belief Update in the Horn Fragment

Nadia Creignou1, Adrian Haret2, Odile Papini1, Stefan Woltran2

1 Aix Marseille Universit e, Universit e de Toulon, CNRS, LIS, Marseille, France 2 TU Wien, Institute of Logic and Computation 192-02, TU Wien, Vienna, Austria nadia.creignou@univ-amu.fr, haret@dbai.tuwien.ac.at, odile.papini@univ-amu.fr, woltran@dbai.tuwien.ac.at

In line with recent work on belief change in fragments of propositional logic, we study belief update in the Horn fragment. We start from the standard KM postulates used to axiomatize belief update operators; these postulates lend themselves to semantic characterizations in terms of partial (resp. total) preorders on possible worlds. Since the Horn fragment is not closed under disjunction, the standard postulates have to be adapted for the Horn fragment. Moreover, a restriction on the preorders (i.e., Horn compliance) and additional postulates are needed to obtain sensible characterizations for the Horn fragment, and this leads to our main contribution: a representation result which shows that the class of update operators captured by Horn compliant partial (resp. total) preorders over possible worlds is precisely that given by the adapted and augmented Horn update postulates. With these results at hand, we provide concrete Horn update operators and are able to shed light on Horn revision operators based on partial preorders.

1 Introduction The aim of an update operator is to incorporate new information into an agent s beliefs, reflecting a change in her environment. Originally developed for use with deductive databases [Fagin et al., 1983], links between update and other members of the belief change family soon emerged [Keller and Winslett, 1985]. Interest in distinctions between update and revision led to a unified treatment of both operations using logical postulates and representations using preorders on possible worlds [Katsuno and Mendelzon, 1992b]. Intuitively, revision is triggered by new information about a static environment, while update occurs in a changing environment. From a logical point of view, when the agent s beliefs are represented by a logical formula ψ, revision makes the models of ψ evolve as a whole towards the closest models of the new information µ. In contrast, update makes each model of ψ locally evolve towards the closest models of µ. Recently, concern about practical aspects related to belief change has prompted research on belief change in languages weaker than propositional logic, also known as fragments, a

particularly vivid topic of interest being the Horn fragment of propositional logic. Interest in the Horn fragment arises from the facts that (i) certain important reasoning tasks (e.g., deciding satisfiability of a Horn formula) are tractable in Horn logic, and (ii) it is a widely used restriction on the language, relevant for fields like logic programming, databases and description logics. Thus, an understanding of belief change in the Horn fragment could serve as a prototype for semantic approaches to change in these fields, a topic which has, as of late, met with increased attention [Kharlamov et al., 2013; Delgrande et al., 2013; Zhuang et al., 2016]. Research on belief change in the Horn fragment has looked at contraction [Booth et al., 2011; Delgrande and Wassermann, 2013; Zhuang and Pagnucco, 2014], revision [Delgrande and Peppas, 2015; Zhuang et al., 2017] and merging [Haret et al., 2017], often with an eye towards finding appropriate postulates and deriving representation results. There is a distinct lack, however, of foundational research on update in the Horn fragment. Our work is meant to fill this gap. Similarly to previous research, we find that existing results on update do not generalize in a straightforward way when the underlying language is restricted. Firstly, special care must be taken when stating postulates, as the limited expressibility of the Horn fragment makes formulation of familiar intuitions either cumbersome or impossible: since the Horn fragment is not closed under disjunction, certain key postulates must be weakened, but this then results in the possibility that Horn operators are represented by undesirable types of preorders on possible worlds. This difficulty is reminiscent of problems encountered when characterizing Horn revision using total preorders [Delgrande and Peppas, 2015]. However, since our aim is to capture Horn update operators characterizable with partial (as well as total) preorders, these problems are compounded and require new ideas. We handle this issue by adding new postulates whose effect is felt in the Horn fragment, but which follow from the standard postulates in propositional logic. Secondly, it is natural to expect that update operators working on Horn formulas should return a result that can also be represented by a Horn formula. This is a minimal requirement if, e.g., update is to be applied in an iterated way. However, it turns out that standard operators proposed in the literature (e.g., Forbus and Winslett s operators) do not meet it and a special restriction, called Horn compliance, must be placed

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18)

on any acceptable operator. Finally, we provide concrete Horn update operators that build on these results. In addition, we exploit insights gained in characterizing Horn update operators with partial preorders, and apply them to get representation results for Horn revision operators characterized with partial preorders. In summary, our main contributions are as follows:

we provide postulates for Horn update,

we study the relation between operators satisfying the postulates and operators given by total (respectively, partial) preorders on interpretations,

we find that additional postulates (UH A and UH A ) and a restriction on the preorders (Horn compliance) are needed in order to obtain a representation theorem,

we provide concrete Horn update operators, and

we obtain a representation result for Horn revision in terms of partial preorders.

2 Preliminaries

We use finite set P of propositional atoms, and L the set of propositional formulas formed over L using the usual propositional connectives. The set of all interpretations for formulas in L is W. An interpretation over P is represented by a set of atoms (corresponding to the variables set to true). For the sake of readability, e.g. the following set of interpretations, {{a, b}, {b, c}}, is written as {ab, bc}. If µ is a propositional formula, then [µ] is the set of models of µ. Given two formulas ψ and ϕ, ψ |= ϕ if [ψ] [ϕ]. A formula ψ is complete if for any formula ϕ we have ψ |= ϕ or ψ |= ϕ. Equivalently, a satisfiable formula ψ is complete if it has exactly one model. A literal is an atom or its negation. A clause is a disjunction of literals. A clause is called Horn if at most one of its literals is positive. A Horn formula is a conjunction of Horn clauses. We denote by LHorn the set of Horn formulas. Horn formulas have the property that their sets of models are closed under intersection, i.e., for any ϕ LHorn, if w1 and w2 are both models of ϕ, then so is w1 w2. Furtherome, this property characterizes the Horn fragment: given a set of interpretations M closed under intersection, i.e., such that for all w1 M and w2 M, also w1 w2 M, there exists a formula ϕ LHorn such that [ϕ] = M. Given M W we denote by Cl H(M) its closure under intersection. For any M W there exists a Horn formula ϕM such that [ϕM] = Cl H(M). A preorder on a set M is a reflexive and transitive binary relation on M. We write < for the strict part of . The minimal elements of M with respect to a preorder are min M = {x M | x M such that x < x}.

3 Belief Update

Formally, a propositional update operator is a function : L L L, mapping a propositional formula ψ (the initial agent s beliefs) and a propositional formula µ (new information) to a new propositional formula ψ µ (the updated agent s beliefs). For ψ, ψ1, ψ2, µ, µ1, µ2 L, we recall the KM postulates [Katsuno and Mendelzon, 1992a], intended to capture rational properties any update operator should satisfy:

(U1) ψ µ |= µ.

(U2) If ψ |= µ, then ψ µ ψ.

(U3) If ψ and µ are satisfiable, then ψ µ is satisfiable.

(U4) If ψ1 ψ2 and µ1 µ2, then ψ1 µ1 ψ2 µ2.

(U5) (ψ µ1) µ2 |= ψ (µ1 µ2).

(U6) If ψ µ1 |= µ2 and ψ µ2 |= µ1, then ψ µ1 ψ µ2 (U7) If ψ is complete, then (ψ µ1) (ψ µ2) |= ψ (µ1 µ2).

(U8) (ψ1 ψ2) µ (ψ1 µ) (ψ2 µ).

(U9) If ψ is complete and (ψ µ1) µ2 is satisfiable, then ψ (µ1 µ2) |= (ψ µ1) µ2.

Postulate U1 states that models of the updated beliefs have to be models of new information; U2 states that if µ was a consequence of ψ before update, then the agent s beliefs do not change after update, i.e., inertia is preferred to spontaneous evolution; U3 states that if the original beliefs and the new information are consistent, then update can always be performed; U4 enforces irrelevance of syntax; U5 expresses minimality of change. Postulate U6 says that if updating ψ by µ1 guarantees µ2 and updating ψ by µ2 guarantees µ1 then the two updates have the same effect. Postulate U7 says that when ψ is complete, a model of ψ updated by µ1 and of ψ updated by µ2 must be a model of ψ updated by µ1 µ2. Postulate U8 states that an update operator gives each model of the initial beliefs equal consideration. Finally, postulate U9 is the converse of U5, restricted to complete formulas ψ. Note, finally, that postulate U9 implies U6 7, and thus the set U1 9 can be said to be stronger than U1 8. A faithful assignment maps every formula ψ to a preorder ψ such that, for any w1, w2 W, it holds that:

(f1) If w1, w2 [ψ], then w1 ψ w2 and w2 ψ w1;

(f2) If w1 [ψ] and w2 / [ψ], then w1 <ψ w2;

(f3) If ψ1 ψ2, then ψ1= ψ2.

If ψ is a complete formula such that [ψ] = {w}, we abuse notation by writing w instead of ψ. Notice that in this case conditions f1 2 amount to simply saying that if w = w, then w <w w . For representing update operators we need assignments that give us only the preorders w, for w W, which we call pointwise faithful.1 The classical representation result presented below relates postulates U1 9 (respectively, U1 8) to total (respectively, partial) preorders over interpretations.

Theorem 1 ([Katsuno and Mendelzon, 1992a]). A propositional update operator satisfies postulates U1 9 iff there is a pointwise faithful assignment mapping each w W to a total preorder w such that [ψ µ] = S w [ψ] min w[µ]. A propositional update operator satisfies postulates U1 8 iff there is a pointwise faithful assignment mapping each w W to a partial preorder w such that [ψ µ] = S w [ψ] min w[µ].

As is apparent, Theorem 1 comes in two parts, one for each set of postulates. Several concrete update operators have been

1 The most general definition of a faithful assignment is used in the section on Horn revision.

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18)

acd b cd [µ] bd ac abd b acd ab

Table 1: Symmetric differences; on each column, cardinalityminimal elements are in bold and -minimal elements are marked with an asterisk.

proposed, and we recall here two known model-based update operators, i.e., Forbus and Winslett s operators. Closeness between models is measured by the symmetric difference between models, i.e., the set of propositional variables on which they differ: if ψ, µ L and w, w W, then w w is the symmetric difference between w and w and | |min w (µ) is the minimum number of variables in which w and a model of µ differ, defined as min{|w w | | w [µ]}. Forbus operator ( F ) [Forbus, 1989] was introduced in the context of qualitative physics, and is defined as: [ψ F µ] = S w [ψ]{w [µ] | |w w | = | |min w (µ)}. Winslett s operator ( W ), also called PMA (Possible Models Approach) [Winslett, 1990], was introduced for reasoning about actions and change. It interprets minimal change in terms of set inclusion instead of cardinality: min w (µ) denotes the minimal difference between w and a model of µ, defined as min ({w w | w [µ]}). Winslett s operator is now defined as: [ψ W µ] = S w [ψ]{w [µ] | w w min w (µ)}. Note that each model of ψ generates a preorder on the set W of interpretations according to the measure of closeness used: minimality with respect to set inclusion generates partial preorders, while minimality with respect to cardinality generates total preorders.

Example 1. Let ψ, µ L such that [ψ] = {abcd, a} and [µ] = {acd, bd, a}. Table 1 depicts the symmetric differences between each model of ψ and the models of µ. We have as results [ψ F µ] = {acd, b} and [ψ W µ] = {acd, bd, b}.

Proposition 2. Forbus operator F satisfies postulates U1 9 and Winslett s operator W satisfies postulates U1 8.

4 Horn Update: Postulates, Characterization

A Horn update operator is a function : LHorn LHorn LHorn. Our aim in this section is to understand and characterize the class of rational Horn update operators in terms of faithful assignments that represent them. Two outstanding problems occur on the way, one pertaining to the nature of the preorders used by the assignments, the other pertaining to the nature of the postulates for Horn update operators.

Horn compliance. With respect to the used preorders, the first observation to make is that Forbus and Winslett s operators (introduced in the previous section) do not work as Horn update operators, as they are not guaranteed to yield a result representable by a Horn formula.

ab [µ] a b b a

(a) Symmetric differences

Figure 1: Symmetric differences for [ψ] = {ab} and [µ] = { , a, b} and preorders generated by W and F , respectively

Example 2. Take formulas ψ = a b and µ = a b. We have that [ψ] = {ab} and [µ] = {a, b, }. Notice that both ψ and µ are Horn formulas, and are thus valid inputs to a Horn update operator. The operators give [ψ F µ] = [ψ W µ] = {a, b} (see Figure 1). Since Cl H({a, b}) = { , a, b} = {a, b}, there is no Horn formula ϕ such that [ϕ] = {a, b}.

Forbus and Winslett s operators generate assignments that represent no Horn update operator, as in Example 2, where interpretations a and b are selected in the final result, while their intersection is not. To mitigate this issue, the type of preorders w used to construct the update result must be restricted in such a way that no matter what update formula µ is used, the result ends up being representable by a Horn formula. Thus, we say that an assignment is Horn compliant if for any Horn formula ψ and Horn formula µ, it holds that S w [ψ] min w[µ] is representable by a Horn formula. It is immediately visible that a Horn compliant assignment is suitable to represent a Horn update operator, since its output is (by definition) representable by a Horn formula.

Postulates for Horn update. With respect to postulates for Horn update operators, the obvious choice is to use the propositional postulates and restrict them to Horn formulas, as done, e.g., for Horn revision [Delgrande and Peppas, 2015]. However, this is not as straightforward for update as it is for revision: since postulates U7 8 make use of disjunction, which is not unrestrictedly expressible in the Horn fragment, special care must be taken when applying these postulates to Horn formulas. In the present paper we have opted for applying these postulates only to those Horn formulas whose disjunction is also representable in the Horn fragment. Thus, for any Horn formulas ψ, ψ1, ψ2, µ, µ1 and µ2, we propose the following postulates:

(UH 1 ) ψ µ |= µ.

(UH 2 ) If ψ |= µ, then ψ µ ψ.

(UH 3 ) If ψ and µ are satisfiable, then ψ µ is satisfiable.

(UH 4 ) If ψ1 ψ2 and µ1 µ2, then ψ1 µ1 ψ2 µ2.

(UH 5 ) (ψ µ1) µ2 |= ψ (µ1 µ2).

(UH 6 ) If ψ µ1 |= µ2 and ψ µ2 |= µ1, then ψ µ1 ψ µ2 (UH 7 ) If ψ is complete and µ1, µ2 are such that µ µ1 µ2, then (ψ µ1) (ψ µ2) |= ψ µ.

(UH 8 ) If ψ1 and ψ2 are such that ψ ψ1 ψ2, then ψ µ (ψ1 µ) (ψ2 µ).

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18)

Figure 2: Relation on interpretations with non-transitive cycle that goes undetected by UH 5 and UH 9: an arrow from x to y means that x <abc y, and separating x and y by a comma means that x abc y

(UH 9 ) If ψ is complete and (ψ µ1) µ2 is satisfiable, then ψ (µ1 µ2) |= (ψ µ1) µ2.

Restricting postulates UH 7 8 to formulas whose disjunction is also a Horn formula makes these postulates weaker in the Horn fragment than they are in propositional logic.

Example 3. If µ1 and µ2 are Horn formulas such that [µ1] = {ab, bc, b}, [µ2] = {bc, ac, c}, there is no Horn formula µ such that [µ] = [µ1 µ2] = {ab, ac, bc, b, c}. Thus, there is no Horn formula µ such that UH 7 applies to µ, µ1 and µ2.

Total preorders. The main issue raised by working in a less expressive language (as the Horn fragment is to propositional logic) is that the standard postulates turn out to characterize relations on interpretations one would like to avoid. In other words, due to the limited expressiveness of the Horn fragment, it suddenly becomes possible to generate reasonably looking Horn update operators from undesirable types of assignments.

Example 4. Take the total reflexive relation abc in Figure 2, transitive everywhere except for ab, bc and ac, which form a non-transitive cycle. Let ψ be a Horn formula such that [ψ] = {abc}. It is easy to see that for any Horn formula µ, min abc[µ] is representable by a Horn formula. Thus, abc can be used to represent a Horn update operator , i.e. an operator which is defined in this particular case by ψ µ = min abc[µ], and it can be checked that postulates UH 1 9 are satisfied. Moreover, there is no total preorder abc which represents the same operator, since such a preorder would have to yield {ab} as a result of updating ψ by [µ0] = {ab, ac, a}, {ac} as a result of updating ψ by [µ1] = {ac, bc, c} and {bc} as a result of updating ψ by [µ2] = {ab, bc, b}, and the cycle would appear again in abc. The non-transitive cycle could be rendered illegal if it were possible to apply postulates UH 5 and UH 9 to a Horn formula whose set of models is {ab, ac, bc}, but no such formula exists in the Horn fragment.

The problem highlighted in Example 4 occurs in an entirely similar way as for Horn revision and Horn merging, where it is handled by employing a special postulate [Delgrande and Peppas, 2015; Haret et al., 2017]. This postulate follows from the regular postulates in propositional logic, but makes a distinct contribution in the Horn fragment, where it rules out exactly the kind of non-transitive cycles illustrated in Example 4. We follow previous usage in formulating such a postulate in terms of complete formulas [Haret et al., 2017]. To write the postulate, we need to introduce some additional notation. If χ1 and χ2 are complete Horn formulas such that χ1 χ2, i.e., [χ1] = {w1} and [χ2] = {w2} with w1 = w2, then χ1,2 denotes a Horn formula such that

[χ1,2] = Cl H({w1, w2}). Using this notation, we define the following postulate:2

(UH A) For any n 1, if ψ is a complete formula and χ1,. .. , χn are complete formulas such that (ψ χ1,2) χ1, . .. , (ψ χn 1,n) χn 1 and (ψ χn,1) χn are all consistent, then (ψ χn,1) χ1 is also consistent.

Example 5. Take the preorder abc in Example 4 and complete Horn formulas χ1, χ2 and χ3 such that [χ1] = {ab}, [χ2] = {ac} and [χ3] = {bc}. Then [χ1,2] = {a, ab, ac}, [ψ χ1,2] = min abc[χ1,2] = {ab} and thus (ψ χ1,2) χ1 is consistent. Similarly, we get that (ψ χ2,3) χ2 and (ψ χ3,1) χ3 are consistent, but (ψ χ3,1) χ1 is inconsistent, which means that UH A is not satisfied by this example.

The motivation for UH A is that it enforces a coherent behavior on the preorders w induced by . Example 4 shows that postulates UH 1 9 are not strong enough to guarantee the following property of a reflexive relation w:

(fa) If w1 w w wn w w1, then w1 w wn.

Notice that fa follows if w is transitive, but postulates UH 1 9 do not enforce transitivity of w. Postulate UH A delivers property fa. Though fa is weaker than transitivity, its presence ensures that w can be extended to a transitive preorder.

Partial preorders. Moving to partial preorders, problems are compounded by the fact that (i) previous issues crop up here as well (i.e., nontransitive cycles still have to be ruled out), and (ii) postulate UH A is not the right choice, as illustrated by Example 6.

Example 6. Take complete Horn formulas χ1, χ2 and χ3 such that [χ1] = {ab}, [χ2] = {abc}, [χ3] = {ac} and a pointwise faithful assignment where is the transitive partial preorder in Figure 3-(a). If ψ is a Horn formula such that [ψ] = { }, we get that [ψ χ1,2] = {ab, abc}, [ψ χ2,3] = {ac, abc} and [ψ χ3,1] = {a, ac}. A quick check reveals that UH A is not satisfied, even though is a valid partial preorder. Take, then, complete Horn formulas χ1, χ2 and χ3 such that [χ1] = {a}, [χ2] = {b}, [χ3] = {c}, and a pointwise faithful assignment where is the partial preorder in Figure 3-(b) (a and c are incomparable). It is straightforward to check that in this case UH A is satisfied, even though this is a relation we would like to rule out, since a < b < c should imply that a < c, or at the very least that a and c are not both selected when the choice set is Cl H({a, c}).

The moral of Example 6 is that when working with partial preorders in the Horn fragment, postulate UH A applies to the wrong type of cases, which means we need a different postulate. To be clear, the semantic property we want to axiomatize in the case of partial preorders is the following:

(fa ) If w1<w <wwn, then wn / min w Cl H({w1, wn}).

Property fa is captured in the following way:

(UH A ) For any n 1, if ψ is a complete formula and χ1,. .. ,χn are complete formulas such that for all i {1, . . . , n

2Postulate UH A is, more precisely, a family of postulates.

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18)

[χ1,2] [χ2,3]

(a) UH A is not satisfied, wrongly

(b) UH A is satisfied, wrongly

Figure 3: Postulate UH A captures the wrong cases when working with partial preorders

1} it holds that (ψ χi,i+1) χi is consistent and (ψ χi,i+1) χi+1 is inconsistent, then (ψ χ1,n) χn is inconsistent. Example 7. For from Example 6-(a), we get that the conditions in UH A are not satisfied since (ψ χ1,2) χ2, for instance, is not inconsistent. Thus, UH A cannot rule out this partial preorder, which is what we wanted to achieve. At the same time, the relation ψ from Example 6-(b) is ruled out by UH A , since [(ψ χ1,3) χ3] = {c}. An important thing to note here is that in propositional logic the new postulates we have introduced are redundant, in the sense that they are implied by the standard postulates. Proposition 3. In propositional logic postulate UA follows from postulates U1 9 and postulate UA follows from U1 8.

Proof. We use induction on n: for n = 1 and n = 2, the claim is immediate in both cases. In the inductive step, we assume complete formulas χ1, . . ., χn+1 and, for UH A, show that (ψ χ1,3) χ1 is consistent; for UH A we show, in addition to this, that (ψ χ1,3) χ3 is inconsistent. We then apply the inductive hypothesis to χ1, χ3, ... , χn+1.

Representation result. Augmenting the standard set of update postulates with UH A (respectively, UH A ) allows us to capture Horn update operators represented by Horn compliant pointwise faithful assignments with total (respectively, partial) preorders. Theorem 4. A Horn update operator satisfies postulates UH 1 9, A iff there exists a Horn compliant pointwise faithful assignment that maps each interpretation w to a total preorder w such that [ψ µ] = S w [ψ] min w[µ]. A Horn update operator satisfies postulates UH 1 8, A iff there exists a Horn compliant pointwise faithful assignment that maps each interpretation w to a partial preorder such that [ψ µ] = S w [ψ] min w[µ].

Theorem 4 comes in two parts, one for each set of postulates. We make use of the remaining part of the section to highlight the main ideas used in the proof of Theorem 4. For one direction, where we are given a Horn compliant assignment with total (respectively, partial) preorders, note first that a Horn operator representing it is well defined. Then, since a Horn compliant pointwise faithful assignment is just a special case of a general pointwise faithful assignment, such an operator also satisfies postulates UH 1 9 (respectively, UH 1 8) and, by Proposition 3, postulate UH A (respectively, UH A ) as well.

Conversely, given a Horn operator satisfying the postulates, we have to construct the assignment representing it: we do this differently depending on the postulates used. If w1, w2 W, we write ϕ1,2 for a Horn formula such that [ϕ1,2] = Cl H({w1, w2}). For a Horn operator satisfying postulates UH 1 9 and UH A, and a Horn formula ψ such that [ψ] = {w}, define the the non-strict revealed plausibility relation w as: w1 w w2 iff w1 [ψ ϕ1,2]. Relation w is partial, and we use the two-step construction in [Delgrande and Peppas, 2015] to extend w to a Horn compliant total preorder w. We then show, using postulate UH A, that w satisfies property fa and that, for any Horn formulas µ and ψw such that [ψw] = {w}, we have [ψw µ] = min w[µ]. Finally, we use postulate UH 8 to show that, for any Horn formulas ψ and µ, [ψ µ] = S w [ψ] min w[µ]. For a Horn operator satisfying postulates UH 1 8 and UH A , and w, w1, w2 W such that w1 = w2, define the strict revealed plausibility relation w as: w1 w w2 iff w1 [ψ ϕ1,2] and w2 / [ψ ϕ1,2]. From postulates UH 5 7, it follows that w1 [ψ ϕ1,2] iff w1 min w Cl H({w1, w2}). Take, then, w to be the reflexive and transitive closure of w. Two details are now crucial. One follows from UH A , and it is that w satisfies property fa . The other is a feature of the Horn fragment, namely that if µ is a Horn formula and w1 [µ], then µ W ϕ1,i, for any wi [µ] such that w1 = wi. Given this, it follows that [ψw µ] = min w[µ], for any Horn formulas µ and ψw such that [ψw] = {w}. Finally, with postulate UH 8 , we infer that [ψ µ] = S w [ψ] min w[µ].

5 Concrete Horn Update Operators

We briefly present two concrete Horn operators, defined for any Horn formulas ψ and µ as follows. First, the trivial Horn update operator T is obtained by taking [ψ T µ] = S w [ψ] min T w [µ], where for any w, w W, w <T w w if w = w. Second, similarly as with Forbus, we define an operator that prioritizes models of small cardinality. Thus, the basic Horn update operator B is obtained by [ψ B µ] = S w [ψ] min B w [µ], where for any w, w W, w <B w w if w = w and w B w w if w , w = w and |w | |w |. The function that assigns to each interpretation w the partial Horn ranking T w (resp. the total Horn ranking B w) is a Horn compliant pointwise faithful assignment. Therefore, according to Theorem 4, the trivial Horn update operator (resp. the basic Horn update operator) T (resp. B) satisfies UH 1 8 and UH A (resp. UH 1 9 and UH A).

6 Revision With Partial Preorders

The insights gained in Theorem 4 can be used to obtain a representation result for Horn revision with partial preorders. Like Horn update, a Horn revision operator is a function : LHorn LHorn LHorn. The main difference between revision and update stems from the type of change scenario envisioned, and is embodied in the different postulates used. Thus, for ψ, µ, µ1, µ2 LHorn, consider the following Horn revision postulates:

(RH 1 ) ψ µ |= µ.

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18)

(RH 2 ) If ψ µ is consistent, then ψ µ ψ µ. (RH 3 ) If µ is consistent, then ψ µ is consistent. (RH 4 ) If ψ1 ψ2 and µ1 µ2, then ψ1 µ1 ψ2 µ2. (RH 5 ) (ψ µ1) µ2 |= ψ (µ1 µ2). (RH 6 ) If ψ µ1 |= µ2 and ψ µ2 |= µ1, then ψ µ1 ψ µ2 (RH 7 ) If µ1, µ2 are such that µ µ1 µ2, then (ψ µ1) (ψ µ2) |= ψ µ. (RH 8 ) If (ψ µ1) µ2 is satisfiable, then ψ (µ1 µ2) |= (ψ µ1) µ2. (RH A) For any n 1, if χ1,. .. , χn are complete formulas such that (ψ χ1,2) χ1, .. . , (ψ χn 1,n) χn 1 and (ψ χn,1) χn are consistent, then (ψ χn,1) χ1 is consistent. (RH A ) For any n 1, if χ1,. .. ,χn are complete formulas such that for all i {1, . . . , n 1} it holds that (ψ χi,i+1) χi is consistent and (ψ χi,i+1) χi+1 is inconsistent, then (ψ χ1,n) χn is inconsistent. We follow the precedent set by existing work on Horn revision [Delgrande and Peppas, 2015] and by this paper (see section on postulates for Horn update) in adapting existing postulates for propositional revision to the Horn fragment, and adding postulates RH A, A which make a difference only in the Horn fragment. As for update, the set of postulates RH 1 8 is stronger than RH 1 7, since RH 8 implies RH 6 7. Notice, also, that there is a strong similarity between revision postulates RH 1 8 and update postulates UH 1 7, 9:3 the similarity is inherited from the propositional case [Katsuno and Mendelzon, 1992a], and it is what drives our representation result. Theorem 5. A Horn revision operator satisfies postulates RH 1 7, A iff there exists a Horn compliant faithful assignment mapping each formula ψ to a partial preorder ψ such that [ψ µ] = min ψ[µ].

Proof. We apply the argument in Theorem 4 for update operators represented with partial preorders to prove that a revision operator satisfying all postulates except RH 2 coincide with operators represented by Horn compliant faithful assignments. Finally, it is straightforward to check that properties f1 2 are satisfied iff postulate RH 2 is satisfied.

Using the stronger postulates RH 1 8, A yields Horn revision operators characterizable with total preorders, a result which has been already obtained in [Delgrande and Peppas, 2015]. Compared to revision with total preorders, revision with partial preorders has received less attention, and we are not aware of any results concerning the Horn fragment. In the propositional logic setting, the problem was first addressed in [Katsuno and Mendelzon, 1992a] and revisited in [Benferhat et al., 2005], where the definition of a faithful assignment is weakened, thus obtaining a larger class of partial preorders, which correspond to a weaker version of postulate R2. Other works include [Ma et al., 2012; Touazi et al., 2015; Tur an and Yaggie, 2015; Yaggie and Tur an, 2016].

3The most notable differences are dropping the condition that ψ is a complete formula and the fact that postulate RH 2 is stronger than UH 2, though they are equivalent when ψ is complete.

total preorders partial preorders

update U1 9 U1 8 pointwise faithful [1] pointwise faithful [1]

Horn update UH 1 9, A UH 1 8, A pointwise faithful pointwise faithful Horn compliant Horn compliant

revision R1 8 R1 7 faithful [2] faithful [2]

Horn revision RH 1 8, A RH 1 7, A faithful faithful Horn compliant [3] Horn compliant

Table 2: A snapshot of the different types of representation results, with postulates and types of assignments on interpretations used for every type of operator; results marked with [1], [2] and [3] are obtained in [Katsuno and Mendelzon, 1992a; Katsuno and Mendelzon, 1992b; Delgrande and Peppas, 2015], respectively; results highlighted in grey are obtained in this paper.

7 Conclusion By studying Horn update, we have contributed to a better understanding of belief change in the Horn fragment. We have shown that KM belief update does not immediately generalize to the Horn fragment, and that specific difficulties arise in addition to the ones encountered for revision. To overcome them we (i) weakened the KM postulates to make them fit into the Horn fragment, and (ii) introduced additional postulates (UH A, A ) to enforce rational behavior of the operators. We provided new representation theorems for Horn update, relating the postulates to partial (respectively, total) preorders on interpretations, and provided concrete Horn update operators. We also extended work on Horn revision [Delgrande and Peppas, 2015] by considering an alternative (weaker) set of postulates, which we characterized using partial preorders. Our representation results are summarized, in the context of existing work, in Table 2. For future work, an initial task is to build on our representation result and provide more Horn update operators, followed by the study of iterated update within the Horn fragment. Moreover, we want to extend our investigation of belief change operators within the Horn fragment to other prominent operators, e.g., erasure, which is to update what contraction is to belief revision [Katsuno and Mendelzon, 1992a]. Finally, careful reading of the proofs of our representation theorems shows that they depend on certain structural properties of the underlying language, which may be shared by other fragments. Thus, a natural further line of inquiry is to extend our results to other fragments, e.g., Krom and, more generally, any fragment characterized by a closure property.

Acknowledgments This work has been supported by projects FWF P30168-N31, P25521, W1255-N23, and a Marietta Blau grant (Oe ADGmb H).

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18)

References [Benferhat et al., 2005] Salem Benferhat, Sylvain Lagrue, and Odile Papini. Revision of partially ordered information: Axiomatization, semantics and iteration. In IJCAI05, Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, Edinburgh, Scotland, UK, July 30 - August 5, 2005, pages 376 381, 2005. [Booth et al., 2011] Richard Booth, Thomas Andreas Meyer, Ivan Jos e 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. [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:457 511, 2013. [Delgrande et al., 2013] James P. Delgrande, Torsten Schaub, Hans Tompits, and Stefan Woltran. A Model Theoretic Approach to Belief Change in Answer Set Programming. ACM Trans. Comput. Log., 14(2):14:1 14:46, 2013. [Fagin et al., 1983] Ronald Fagin, Jeffrey D. Ullman, and Moshe Y. Vardi. On the semantics of updates in databases. In Proc. ACM SIGACT SIGMOD, pages 352 365, 1983. [Forbus, 1989] Kenneth D. Forbus. Introducing actions into qualitative simulation. In Proc. of IJCAI 1989, pages 1273 1278, 1989. [Haret et al., 2017] Adrian Haret, Stefan R ummele, and Stefan Woltran. Merging in the Horn fragment. ACM Trans. Comput. Log., 18(1):6:1 6:32, 2017. [Katsuno and Mendelzon, 1992a] Hirofumi Katsuno and Alberto O. Mendelzon. On the difference between updating a knowledge base and revising it. In Peter G ardenfors, editor, Belief Revision, pages 183 203. Cambridge University Press, 1992. [Katsuno and Mendelzon, 1992b] Hirofumi Katsuno and Alberto O. Mendelzon. Propositional knowledge base revision and minimal change. Artif. Intell., 52(3):263 294, 1992. [Keller and Winslett, 1985] Arthur M. Keller and Marianne Winslett. On the use of an extended relational model to handle changing incomplete information. IEEE Trans. Software Eng., 11(7):620 633, 1985. [Kharlamov et al., 2013] Evgeny Kharlamov, Dmitriy Zheleznyakov, and Diego Calvanese. Capturing modelbased ontology evolution at the instance level: The case of DL-Lite. J. Comput. Syst. Sci., 79(6):835 872, 2013. [Ma et al., 2012] Jianbing Ma, Salem Benferhat, and Weiru Liu. Revising partial pre-orders with partial pre-orders: A unit-based revision framework. In Principles of Knowledge Representation and Reasoning: Proceedings of the Thirteenth International Conference, KR 2012, Rome, Italy, June 10-14, 2012, pages 633 637, 2012.

[Touazi et al., 2015] Fayc al Touazi, Claudette Cayrol, and Didier Dubois. Possibilistic reasoning with partially ordered beliefs. J. Applied Logic, 13(4):770 798, 2015. [Tur an and Yaggie, 2015] Gy orgy Tur an and Jon Yaggie. Characterizability in belief revision. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015, pages 3236 3242, 2015. [Winslett, 1990] Marianne Winslett. Updating Logical Databases. Cambridge University Press, 1990. [Yaggie and Tur an, 2016] Jon Yaggie and Gy orgy Tur an. Characterizability in Horn belief revision. In Logics in Artificial Intelligence - 15th European Conference, JELIA 2016, Larnaca, Cyprus, November 9-11, 2016, Proceedings, pages 497 511, 2016. [Zhuang and Pagnucco, 2014] Zhiqiang Zhuang and Maurice Pagnucco. Entrenchment-based Horn contraction. J. Artif. Intell. Res. (JAIR), 51:227 254, 2014. [Zhuang et al., 2016] Zhiqiang Zhuang, Zhe Wang, Kewen Wang, and Guilin Qi. DL-Lite Contraction and Revision. J. Artif. Intell. Res., 56:329 378, 2016. [Zhuang et al., 2017] Zhiqiang Zhuang, Maurice Pagnucco, and Yan Zhang. Inter-definability of Horn contraction and Horn revision. J. Philosophical Logic, 46(3):299 332, 2017.

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18)