{'fraction_non_alphanumeric': 0.040617860141771954, 'fraction_numerical': 0.007576793141830538, 'mean_word_length': 4.262562943171308, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On the Link between Partial Meet, Kernel, and Infra Contraction and its Application to Horn Logic

Standard belief change assumes an underlying logic containing full classical propositional logic. However, there are good reasons for considering belief change in less expressive logics as well. In this paper we build on recent investigations by Delgrande on contraction for Horn logic. We show that the standard basic form of contraction, partial meet, is too strong in the Horn case. This result stands in contrast to Delgrande's conjecture that orderly maxichoice is the appropriate form of contraction for Horn logic. We then define a more appropriate notion of basic contraction for the Horn case, influenced by the convexity property holding for full propositional logic and which we refer to as infra contraction. The main contribution of this work is a result which shows that the construction method for Horn contraction for belief sets based on our infra remainder sets corresponds exactly to Hansson's classical kernel contraction for belief sets, when restricted to Horn logic. This result is obtained via a detour through contraction for belief bases. We prove that kernel contraction for belief bases produces precisely the same results as the belief base version of infra contraction. The use of belief bases to obtain this result provides evidence for the conjecture that Horn belief change is best viewed as a hybrid version of belief set change and belief base change. One of the consequences of the link with base contraction is the provision of a representation result for Horn contraction for belief sets in which a version of the Core-retainment postulate features.


Introduction
In his seminal paper, Delgrande (2008) has shed some light on the theoretical underpinnings of belief change by weakening a usual assumption in the belief change community, namely that the underlying logical formalism should be at least as strong as (full) classical propositional logic (Gärdenfors, 1988). Delgrande investigated contraction functions for belief sets (sets of sentences that are closed under logical consequence) restricted to Horn formu-las (1951). Delgrande's main contributions were essentially threefold. Firstly, he showed that the move to Horn logic leads to two different types of contraction functions, referred to as entailment-based contraction (e-contraction) and inconsistency-based contraction (icontraction), which coincide in the full propositional case. Secondly, he showed that Horn contraction for belief sets does not satisfy the controversial Recovery postulate, but exhibits some characteristics that are usually associated with the contraction of belief bases (arbitrary sets of sentences). And finally, Delgrande made a tentative conjecture that a version of Horn contraction usually referred to as orderly maxichoice contraction is the appropriate method for contraction in Horn theories.
While Delgrande's partial meet constructions are appropriate choices for contraction in Horn logic, we show that they do not constitute all the appropriate forms of Horn contraction. Moreover, as referred to above, although Horn contraction is defined for Horn belief sets, it is related in some ways to contraction for belief bases, an aspect which has not yet been explored properly in the literature.
In this paper we continue the investigation into contraction for Horn logic, and address both the issues mentioned above, as well as others. Focusing on Delgrande's entailmentbased contraction, we start by providing a more fine-grained construction for belief set contraction which we refer to in this paper as infra contraction. We then bring into the picture a construction method for contraction first introduced by Hansson (1994), known as kernel contraction. Although kernel contraction is usually associated with belief base contraction, it can be applied to belief sets as well. Our main contribution is a result which shows that infra contraction corresponds exactly to Hansson's kernel contraction for belief sets, when restricted to Horn logic. In order to prove this, we first take a close look at contraction for belief bases, defining a base version of infra contraction and proving that this construction is equivalent to kernel contraction for Horn belief bases. Since Horn belief sets are not closed under classical logical consequence, they can be seen as a 'hybrid' between belief sets and belief bases. This justifies the use of belief bases to obtain results for belief set Horn contraction.
Horn logic has found extensive use in Artificial Intelligence, in particular in logic programming, truth maintenance systems, and deductive databases. This explains, in part, our interest in belief change for Horn logic. (Despite our interest in Horn formulas, it is worth noting that in this work we do not consider logic programming explicitly and we do not use negation as failure at all.) Another reason for focusing on this topic is because of its application to debugging and repairing ontologies in description logics (Baader, Calvanese, McGuinness, Nardi, & Patel-Schneider, 2007). In particular, Horn logic can be seen as the backbone of the EL family of description logics (Baader, Brandt, & Lutz, 2005), and therefore a proper understanding of belief change for Horn logic is important for finding solutions to similar problems expressible in the EL family.
The remainder of the present paper is organized as follows: After some logical preliminaries (Section 2), we give the background on belief set contraction (Section 3) and on belief base contraction (Section 4) that is necessary for the core section of the paper (Section 5). There we prove that kernel contraction and infra contraction are equivalent on the level of belief bases. This enables us to prove that kernel contraction and infra contraction are equivalent on the Horn belief set level as well. From this we are led to provide a characterization of infra contraction for Horn belief sets in which a version of the Core-retainment postulate (Hansson, 1994) for bases features. This provides even more evidence for the 'hybrid' aspect of Horn belief change. All these results are stated for entailment-based contraction (e-contraction). In Section 6, where we discuss related work, we also mention similar results for Delgrande's i-contraction and another relevant type of Horn contraction, namely Booth et al's (2009) package contraction. We conclude with a summary of our contributions as well as a discussion on future directions of investigation. Proofs of all new results can be found in Appendix A.

Preliminaries
We work in a finitely generated propositional language over a set of propositional atoms P, together with the distinguished atom (true), and with the standard model-theoretic semantics. Atoms are denoted by p, q, . . ., possibly with subscripts. The formulas of our language are denoted by ϕ, ψ, . . . Those are recursively defined as follows: All the other connectives (∨, →, ↔, . . . ) and the special atom ⊥ (false) are defined in terms of ¬ and ∧ in the usual way. With L P we denote the set of all formulas of the language.
Classical logical consequence and logical equivalence are denoted by |= and ≡ respectively. For X ⊆ L P , the set of sentences logically entailed by X is denoted by Cn(X). A belief set is a logically closed set, i.e., for a belief set K, K = Cn(K). We usually denote belief sets by K, possibly decorated by primes. P(X) denotes the power set (set of all subsets) of X. When displaying belief sets we sometimes follow the convention of displaying one representative of each equivalence class modulo logical equivalence, and dropping the representative for the tautologies. As an example, for L P generated by the two atoms p and q, the set Cn({p}) can be represented as {p, p ∨ q, p ∨ ¬q}.
A Horn clause is a sentence of the form p 1 ∧ p 2 ∧ . . . ∧ p n → q where n ≥ 0, p i , q ∈ P for 1 ≤ i ≤ n (recall that the p i s and q may be one of ⊥ or as well). If n = 0 we write q instead of → q. A Horn formula is a conjunction of Horn clauses. A Horn set is a set of Horn formulas.
Given a propositional language L P , the Horn language L H generated from L P is simply the set of Horn formulas occurring in L P . The Horn logic obtained from L H has the same semantics as the propositional logic obtained from L P , but just restricted to Horn formulas. Hence, we have that |=, ≡, and all other related notions are defined relative to the logic we are working in. We use |= PL and Cn PL (.) to denote classical entailment and consequence for propositional logic. For Horn logic, we define Cn HL (.) as follows: Cn HL (X) = def Cn PL (X) ∩ L H for X ⊆ L H . And we define |= HL as follows: For X ⊆ L H and ϕ ∈ L H , X |= HL ϕ if and only if X |= PL ϕ.
The consequence operator Cn HL (.) is a Tarskian consequence operator in the sense that it satisfies the following properties for all Horn sets X, X : • Cn HL (X) = Cn HL (Cn HL (X)) (Idempotency) • If X ⊆ X , then Cn HL (X) ⊆ Cn HL (X ) A Horn belief set, usually denoted by H (possibly with primes), is a Horn set closed under the operator Cn HL (.), i.e., H = Cn HL (H). We shall dispense with such subscripts whenever the context makes it clear which logic we are dealing with.
In the AI tradition, a given set of formulas of the underlying logical language is called a knowledge base, or simply a set of beliefs. Belief change deals with situations in which an agent has to modify its beliefs about the world, usually due to new or previously unknown incoming information, also represented as formulas of the language. Common operations of interest in belief change are the expansion (Gärdenfors, 1988) of an agent's current beliefs X by a given formula ϕ (usually denoted as X + ϕ), where the basic idea is to add ϕ regardless of the consequences, and the revision (Gärdenfors, 1988) of its current beliefs by ϕ (denoted as X ϕ), where the intuition is to incorporate ϕ into the current beliefs in some way while ensuring consistency of the resulting theory at the same time. Perhaps the most basic operation in belief change is that of contraction (Alchourrón, Gärdenfors, & Makinson, 1985;Gärdenfors, 1988), which is intended to represent situations in which an agent has to give up ϕ from its current stock of beliefs (denoted as X − ϕ). Indeed the revision operation can be defined in terms of contraction and simple expansion via the Levi identity (Levi, 1977). Therefore, contraction is the focus of the present paper and in what follows we shall investigate it in detail. Throughout Sections 3 and 4 we assume we work in the language of full propositional logic L P .

Belief Set Contraction
We commence with a discussion on belief set contraction, where the aim is to describe contraction on the knowledge level (Gärdenfors, 1988), i.e., independently of how beliefs are represented syntactically. Thus, contraction is defined only for belief sets.
Definition 1 (Belief Set Contraction) A belief set contraction − for a belief set K is a function from L P to P(L P ).
By the principle of categorical matching (Gärdenfors & Rott, 1995) the contraction of a belief set by a sentence is expected to yield a new belief set.
One of the standard approaches for constructing belief contraction operators is based on the notion of a remainder set of a set K with respect to a formula ϕ: a maximal subset of K not entailing ϕ . Here we define this for belief sets, but it has been known in the literature that its basic principle can be applied to belief bases as well (we shall recall this in Section 4).
Definition 2 (Remainder Sets) Given a belief set K and a formula ϕ ∈ L P , X ∈ K⊥ϕ if and only if • For every X such that X ⊂ X ⊆ K, X |= ϕ.
We call the elements of K⊥ϕ the remainder sets of K with respect to ϕ.
Since there is no unique method for choosing between possibly different remainder sets, there is a presupposition of the existence of a suitable selection function for doing so: Definition 3 (Selection Functions) A selection function γ for a set K is a (partial) function from P(P(L P )) to P(P(L P )) such that Selection functions provide a mechanism for identifying the remainder sets judged to be most appropriate. The resulting contraction is obtained by taking the intersection of the chosen remainder sets.
Definition 4 (Partial Meet Contraction) For a selection function γ, the belief set contraction operator − γ generated by γ and defined as K − γ ϕ = def γ(K⊥ϕ) is a partial meet contraction.
Two subclasses of belief set partial meet deserve special mention: It is worth mentioning that belief set full meet contraction is unique, while belief set maxichoice contraction usually is not.
Kernel contraction was introduced by Hansson (1994) as a generalization of safe contraction . Instead of looking at maximal subsets not implying a given formula, kernel operations are based on minimal subsets that do imply it.
Definition 6 (Kernel) For a belief set K, X ∈ K ⊥ ⊥ ϕ if and only if • For every X such that X ⊂ X, X |= ϕ.
K ⊥ ⊥ ϕ is called the kernel set of K with respect to ϕ and the elements of K ⊥ ⊥ ϕ are called the ϕ-kernels of the belief set K.
The result of a kernel contraction is obtained by removing at least one element from every (non-empty) ϕ-kernel of K, using an incision function.
Definition 7 (Incision Functions) An incision function σ for a set K is a function from the set of kernel sets of K to P(L P ) such that Given a belief set K and an incision function σ for K, ideally we would want the kernel contraction − σ for K generated by σ be defined as: It turns out that for a belief set K, the contraction operator in (1) does not respect the principle of categorical matching. That is because, for a belief set as input, the kernel contraction − σ from (1) above does not necessarily produce a belief set as a result: K − σ ϕ is not in general closed under logical consequence, as shown by the following example.
Example 1 Let K = Cn({p → q, q → r}) and assume that we want to contract p → r from K. We have K ⊥ ⊥ (p → r) = {{p → r}, {p → q, q → r}, {p → q, p ∧ q → r}}. For the incision function σ defined such that σ(K ⊥ ⊥ (p → r)) = {p → r, p → q, p ∧ q → r}, we have that applying the operator in (1) gives us K such that K |= p ∧ q → r, but obviously Of course, it is possible to ensure that one obtains a belief set by closing the result obtained from the operator above under logical consequence.
Definition 8 (Belief Set Kernel Contraction) Given a belief set K and an incision function σ for K, the belief set contraction operator ≈ σ for K generated by σ and defined as K ≈ σ ϕ = def Cn(K − σ ϕ) is a belief set kernel contraction.
We shall see in Section 4 that belief set kernel contraction is closely related to a version of belief base contraction referred to as saturated base kernel contraction (Hansson, 1999).
Belief set contraction defined in terms of partial meet contraction corresponds exactly to what is perhaps the best-known approach to belief change: the so-called AGM approach . AGM requires that (basic) belief set contraction be characterized by the following set of postulates: Full AGM contraction involves two extended postulates in addition to the basic postulates given above. We shall not elaborate in detail on the intuition of these postulates. For that we refer the reader to the book by Gärdenfors (1988) or the handbook by Hansson (1999).  have shown that these postulates characterize belief set partial meet contraction exactly, as shown by the following result: Theorem 1  Every belief set partial meet contraction satisfies Postulates (K − 1)-(K − 6). Conversely, every belief set contraction which satisfies Postulates (K − 1)-(K − 6) is a belief set partial meet contraction. Hansson (1994) has shown that Postulates (K − 1)-(K − 6) also characterize kernel contraction for belief sets: Theorem 2 (Hansson, 1994) Every belief set kernel contraction satisfies the Postulates (K −1)-(K −6). Conversely, every belief set contraction which satisfies Postulates (K −1)-(K − 6) is a belief set kernel contraction.
We conclude this section with an important new observation whose usefulness will become apparent in Section 5.
Theorem 3 (Convexity) Let K be a belief set, let − mc be a (belief set) maxichoice contraction, and let − fm denote (belief set) full meet contraction. For every ϕ ∈ L P and every belief set This result shows that every belief set between the results obtained from full meet contraction and some maxichoice contraction can also be obtained from some partial meet contraction. So, it is possible to define a version of belief set contraction based on such sets.
Definition 9 (Infra Remainder Sets) Given a formula ϕ ∈ L P , and belief sets K and K , K ∈ K ↓ ϕ if and only if there is some K ∈ K⊥ϕ such that ( K⊥ϕ) ⊆ K ⊆ K . We refer to the elements of K ↓ ϕ as the infra remainder sets of K with respect to ϕ.
It is easy to see that K ↓ ϕ = ∅ if and only if |= ϕ. Note that by definition the set of infra remainder sets of a belief set K are required to be belief sets themselves.
All remainder sets with respect to a formula ϕ are also infra remainder sets with respect to ϕ, and so is the intersection of any set of remainder sets with respect to ϕ. Indeed, the intersection of any set of infra remainder sets with respect to ϕ is also an infra remainder set with respect to ϕ. So the set of infra remainder sets with respect to ϕ contains all belief sets between some remainder set with respect to ϕ and the intersection of all remainder sets with respect to ϕ. This explains why infra contraction below is not defined as the intersection of infra remainder sets (cf. Definition 4).
Definition 10 (Infra Contraction) Let K be a belief set. An infra selection function τ for K is a (partial) function from P(P(L P )) to P(L P ) such that τ (K ↓ ϕ) = K whenever K ↓ ϕ = ∅, and τ (K ↓ ϕ) ∈ K ↓ ϕ otherwise. A belief set contraction operator − τ is a belief set infra contraction if and only if K − τ ϕ = τ (K ↓ ϕ).
In a sense, then, infra contraction is closer to maxichoice contraction than to partial meet contraction, since it chooses just a single element from the set of infra remainder sets, much like maxichoice contraction chooses just a single element from the set of remainder sets.
One immediate consequence of Theorem 3 and Definition 10 is the following: Corollary 1 Infra contraction and partial meet contraction coincide for belief sets.

Belief Base Contraction
Now we turn our attention to belief base contraction, where an agent's beliefs are represented as a (usually finite) set of sentences not necessarily closed under logical consequence, also known as a base. We usually denote bases by B, possibly decorated with primes.
Definition 11 (Belief Base Contraction) A base contraction − for a base B is a function from L P to P(L P ).
Intuitively the idea is that, for a fixed belief base B, contraction of a formula ϕ from B produces a new base B − ϕ.
Given the construction methods for belief set contraction already discussed in Section 3, two obvious ways to define belief base contraction are to consider both partial meet contraction and kernel contraction for bases. Below we present both cases.
All definitions required for partial meet in the base case are analogous to those given in the belief set case in Section 3. For the reader's convenience, we state them explicitly here: Definition 12 (Base Remainder Sets) Given a base B and a formula ϕ, X ∈ B⊥ϕ if and only if We call the elements of B⊥ϕ the base remainder sets of B with respect to ϕ.
Similarly to the belief set case, it is easy to verify that B⊥ϕ = ∅ if and only if |= ϕ.
Definition 13 (Selection Functions) A selection function γ for a base B is a (partial) function from P(P(L P )) to P(P(L P )) such that Definition 14 (Base Partial Meet Contraction) For a selection function γ, the belief base contraction operator − γ generated by γ and defined as B − γ ϕ = def γ(B⊥ϕ) is a base partial meet contraction.
Definition 15 (Base Maxichoice and Full Meet) Given a selection function γ, − γ is a base maxichoice contraction if and only if γ(B⊥ϕ) is always a singleton set. It is a base full meet contraction if and only if γ(B⊥ϕ) = B⊥ϕ whenever B⊥ϕ = ∅.
As in the belief set case, it can be checked that belief base full meet contraction is unique, while base maxichoice contraction usually is not. Hansson (1992) showed that belief base partial meet contraction can be characterized by the following postulates: Again, we shall not elaborate in detail on the intuition of these postulates. For that we refer the reader to the handbook by Hansson (1999).
Theorem 4 (Hansson, 1992) Every base partial meet contraction operator satisfies Pos- is a base partial meet contraction.
One question that arises is whether the following belief base version of the convexity principle from Theorem 3 holds: (Base Convexity) For a belief base B, let − mc be a base maxichoice contraction, and let − fm denote base full meet contraction. For every set X and ϕ such that B − fm ϕ ⊆ X ⊆ B − mc ϕ, there is a base partial meet contraction − pm such that B − pm ϕ = X.
As in the belief set case, this principle simply states that every set between the results obtained from base full meet contraction and some base maxichoice contraction can be obtained from some belief base partial meet contraction. The following example shows that it does not hold.
Therefore the only other result obtained from base partial meet contraction is that which is provided by base full meet contraction: We shall come back to this issue at the end of the section.
Below we give the definitions for kernel contraction in the belief base case. Again, they are analogous to those given in the belief set case in the previous section, but for the reader's convenience we state them explicitly here.
Definition 16 (Base Kernels) For a belief base B and a formula ϕ, X ∈ B ⊥ ⊥ ϕ if and only if B ⊥ ⊥ ϕ is called the kernel set of B with respect to ϕ, and the elements of B ⊥ ⊥ ϕ are called the ϕ-kernels of B.
The result of a base kernel contraction is obtained by removing at least one element from every (non-empty) ϕ-kernel of B, using an incision function.
Definition 17 (Incision Functions for Bases) An incision function σ for a base B is a function from the set of kernel sets of B to P(L P ) such that We refer to an incision function σ as minimal if and only if for every ϕ, and every incision It is worthy of mention that minimal incision functions always exist.
Definition 18 (Base Kernel Contraction) Given an incision function σ for a base B, the base kernel contraction − σ for B generated by σ is defined as: Base kernel contraction can be characterized by the same postulates as base partial meet contraction, except that Relevance is replaced by the Core-retainment postulate below: Theorem 5 (Hansson, 1994 Clearly, Core-retainment is slightly weaker than Relevance. And indeed, it thus follows that all base partial meet contractions are base kernel contractions, but as the following example from Hansson (1999) shows, some base kernel contractions are not base partial meet contractions. As we briefly pointed out after Definition 8, our definition of kernel contraction for belief sets is closely related to a version of belief base contraction that Hansson (1999) refers to as saturated base kernel contraction: Definition 19 (Saturated Base Kernel Contraction) Given a belief base B and an incision function σ for B, the base contraction ≈ σ for B generated by σ and defined as It is easily shown (Hansson, 1994) that when the set B in the definition for saturated base kernel contraction is a belief set, the two notions coincide.
Observation 1 For a belief set K and an incision function σ for K, the saturated base kernel contraction for σ and the belief set kernel contraction for σ are identical.
While saturated base kernel contractions are not in general base partial meet contractions (Hansson, 1999, p. 91), this distinction disappears when considering belief sets only: Theorem 6 (Hansson, 1994) Let K be a belief set. A belief set contraction − is a saturated base kernel contraction if and only if it is a belief set partial meet contraction.
And as a result of Observation 1 and Theorem 6 we immediately have the following corollary: Corollary 2 Let K be a belief set. A belief set contraction − is a belief set kernel contraction if and only if it is a belief set partial meet contraction.
Thanks to Theorem 3 (Convexity) we can extend Corollary 2 to show that kernel contraction, partial meet contraction, and infra contraction all coincide for belief sets.
Corollary 3 Let K be a belief set. A belief set contraction − is a belief set kernel contraction if and only if it is a belief set partial meet contraction if and only if it is a belief set infra contraction.
So far we have considered remainder sets for bases and kernel sets for bases, but not infra remainder sets for bases (cf. end of Section 3). We conclude this section with a discussion on this commencing with the definition of base infra remainder sets.
Definition 20 (Base Infra Remainder Sets) Given a formula ϕ, and bases B and B , B ∈ B ↓ ϕ if and only if there is some B ∈ B⊥ϕ such that ( B⊥ϕ) ⊆ B ⊆ B . We refer to the elements of B ↓ ϕ as the base infra remainder sets of B with respect to ϕ.
Observe that the definition of base infra remainder sets is the same as for infra remainder sets, differing only in that it deals with belief bases and not belief sets. Note in particular that the elements are not required to be belief sets themselves. Base infra remainder sets can be used to define a form of base contraction in a way that is similar to the definition of (belief set) infra contraction (cf. Definition 10).
A natural question to ask is how base infra contraction compares with base partial meet contraction and base kernel contraction. The following result, which plays a central role in this paper, shows that base infra contraction corresponds exactly to base kernel contraction.

Theorem 7 A base contraction for a belief base B is a belief base kernel contraction for B if and only if it is a base infra contraction for B.
From Example 3 we know that base kernel contraction is more general than base partial meet contraction: every base partial meet contraction is also a base kernel contraction, but the converse does not hold. From Theorem 7 the following result thus follows.
Observation 2 Base infra contraction is more general than base partial meet contraction.
Theorem 7 has a number of other interesting consequences as well. On a philosophical note, it provides evidence for the contention that the kernel contraction approach is more appropriate than the partial meet approach. As mentioned earlier, it is well-known that kernel contraction and partial meet contraction coincide for belief sets, but differ for belief bases (kernel contraction being more general than partial meet contraction in this case). The importance of Theorem 7 is that it shows a new and seemingly different approach to contraction (infra contraction) to be identical to kernel contraction for both belief sets and belief bases, but different from partial meet contraction for belief bases, thereby tilting the scales of evidence towards kernel contraction. As we shall see in the next section, Theorem 7 is also instrumental in "lifting" this result to the level of Horn belief sets.

Horn Belief Set Contraction
In the previous sections we recalled several results from the belief change literature and stated new ones, connecting different constructions to sets of rationality postulates. It is important to note that although most of the examples in the literature assume that the underlying logic contains classical propositional logic, the results are usually valid for a broader set of languages. This has been discussed in different contexts by Hansson and Wassermann (2002), Flouris et al. (2006), Ribeiro and Wassermann (2009a, 2009b, Varzinczak (2008Varzinczak ( , 2010, and Wassermann (2011), among others. For belief bases, it was shown by Hansson and Wassermann (2002) that in order to keep the representation theorems for partial meet and kernel contraction, the logic only needs to be compact and monotonic. This means that the results transfer directly to Horn logics. However, for belief sets the representation theorems demand more restrictions of the logic. As shown by Flouris et al. (2006), a contraction operation satisfying the basic AGM postulates exists only if the logic is decomposable.
Definition 22 (Flouris et al., 2006) A logic is called decomposable if and only if for all sets of formulas X, X , such that Cn(∅) ⊂ Cn(X ) ⊂ Cn(X), there exists a set of formulas X such that Cn(X ) ⊂ Cn(X) and Cn(X) = Cn(X ∪ X ).
It was shown by Ribeiro (2010) that Horn logic is not decomposable. Therefore, new constructions and sets of postulates are needed to deal with contraction of Horn belief sets. Delgrande (2008) investigated two distinct classes of contraction functions for Horn belief sets: entailment-based contraction (e-contraction), for removing an unwanted consequence; and inconsistency-based contraction (i-contraction), for removing formulas leading to inconsistency; while Booth et al. (2009) subsequently extended the work of Delgrande by providing more fine-grained versions of his constructions. Our focus in this paper is on e-contraction, although Delgrande, as well as Booth et al., also consider i-contraction.
Recall that we use H, sometimes decorated with primes, to denote a Horn belief set.
Definition 23 (e-Contraction) An e-contraction − for a Horn belief set H is a function from L H to P(L H ).
Delgrande's method of construction for e-contraction is in terms of partial meet contraction. The definitions of remainder sets (Definition 2), selection functions (Definition 3), partial meet contraction (Definition 4), as well as maxichoice and full meet contraction (Definition 5) all carry over for e-contraction, with the set K in each case being replaced by a Horn belief set H, and we refer to these as e-remainder sets (denoted by H⊥ e ϕ), e-selection functions, partial meet e-contraction, maxichoice e-contraction and full meet e-contraction respectively (we leave out the reference to the term "Horn", since there is no room for ambiguity here). As in the full propositional case, it is easy to verify that all e-remainder sets are also Horn belief sets, and that all partial meet e-contractions (and therefore the maxichoice e-contractions, as well as full meet e-contraction) produce Horn belief sets.
Although Delgrande defines and discusses partial meet e-contraction, he argues that maxichoice e-contraction is the appropriate approach for e-contraction. To be more precise, the version of maxichoice e-contraction that Delgrande advocates is actually a restricted version of maxichoice e-contraction that we refer to as orderly maxichoice e-contraction. (This is just the Horn case of the maxichoice contraction operators satisfying all the AGM postulates, including the supplementary ones). Whereas (ordinary) maxichoice e-contraction is constructed by setting, for every ϕ ∈ L H , H − ϕ equal to any element of H⊥ϕ, orderly maxichoice e-contraction is more systematic in nature. Associated with every orderly maxichoice e-contraction is a linear order ≤ on ϕ∈L H (H⊥ϕ), the union of all e-remainder sets of H with respect to all sentences ϕ ∈ L H . Intuitively, the higher up in the linear order, the more plausible an element of ϕ∈L H (H⊥ϕ) is intended to be. The orderly maxichoice e-contraction generated from ≤ is then obtained as follows: for every ϕ ∈ L H , K − ϕ is selected to be the most plausible e-remainder set of H with respect to ϕ (the one that is the highest up in the order ≤).
Here we argue that although all partial meet e-contractions are appropriate choices for e-contraction, they do not make up the set of all appropriate e-contractions. In other words, Delgrande's approach is not 'complete'. The argument for appropriate e-contractions other than partial meet e-contraction is based on the observation that the convexity result for full propositional logic in Theorem 3 does not hold for Horn logic. In order to rectify this situation, we propose that e-contraction should be extended to include cases such as H above. The argument is as follows: Since full meet e-contraction is deemed to be appropriate, it stands to reason that any belief set H bigger than it should also be seen as appropriate, provided that H does not contain any irrelevant additions. But since H is contained in some maxichoice e-contraction, H cannot contain any irrelevant additions. After all, the maxichoice Horn e-contraction contains only relevant additions, since it is an appropriate form of contraction. Hence H is also an appropriate result of e-contraction.

Example 4 Let
In summary, every Horn belief set between full meet and some maxichoice e-contraction ought to be seen as an appropriate candidate for e-contraction. This is captured by the definition below.
Definition 24 (Infra e-Remainder Sets) For Horn belief sets H and H , H ∈ H ↓ e ϕ if and only if there is some H ∈ H⊥ e ϕ such that ( H⊥ e ϕ) ⊆ H ⊆ H . We refer to the elements of H ↓ e ϕ as the infra e-remainder sets of H with respect to ϕ.
As with the case for full propositional logic (cf. Definition 9), e-remainder sets are also infra e-remainder sets, and so is the intersection of any set of e-remainder sets. Similarly, the intersection of any set of infra e-remainder sets is also an infra e-remainder set, and the set of infra e-remainder sets contains all Horn belief sets between some e-remainder set and the intersection of all e-remainder sets. As in the full propositional case, this explains why e-contraction is not defined as the intersection of infra e-remainder sets (cf. Definition 4).
Definition 25 (Horn e-Contraction) Let H be a Horn belief set and ϕ ∈ L H be a Horn formula. An infra e-selection function τ is a (partial) function from P(P(L H )) to P(L H ) such that The results on how kernel contraction, partial meet contraction and infra contraction compare for the base case (kernel contraction and infra contraction are identical, while both are more general than partial meet contraction) invite the question whether similar results hold for Horn belief sets. Before we provide an answer to this, we need a suitable version of kernel contraction for Horn belief sets.
Definition 26 (Horn kernel e-contraction) Given a Horn belief set H and an incision function σ for H, the Horn kernel e-contraction for H, abbreviated as the kernel econtraction for H, is defined as H ≈ e σ ϕ = def Cn HL (H − σ ϕ), where − σ is the belief base kernel contraction for ϕ obtained from σ.
It turns out that infra e-contraction and kernel e-contraction coincide, as the following result shows.
Theorem 8 An e-contraction for a Horn belief set H is an infra e-contraction for H if and only if it is a kernel e-contraction for H.
From Theorem 8 and Example 4 it follows that partial meet e-contraction is more restrictive than kernel e-contraction. When it comes to Horn belief sets, we therefore have exactly the same pattern as we have for belief bases: kernel contraction and infra contraction coincide, while both are strictly more permissive than partial meet contraction. Contrast this with the case for belief sets for full propositional logic where infra contraction, partial meet contraction and kernel contraction all coincide.
One conclusion to be drawn from this is that the restriction to the Horn case produces a curious hybrid between belief sets and belief bases for full propositional logic. On the one hand, Horn contraction deals with sets that are logically closed. But on the other hand, the results for Horn logic obtained in terms of construction methods are close to those obtained for belief base contraction.
Either way, the new results on belief base contraction prove to be quite useful in the investigation of contraction for Horn belief sets. We conclude this section by providing a representation result for Horn contraction inspired by the new results on belief base contraction in this paper.
This result was inspired by Theorem 7 which shows that base kernel and base infra contraction coincide. Given that Core-retainment is used in characterizing base kernel contraction, Theorem 7 shows that there is a link between Core-retainment and base infra contraction, and raises the question of whether there is a link between Core-retainment and infra e-contraction. The answer, as we have seen in Theorem 9, is yes. This result provides more evidence for the hybrid nature of contraction for Horn belief sets. In this case the connection with base contraction is strengthened.

Related Work
To our knowledge, the first formal proposal of taking non-maximal remainder sets for a contraction following the AGM principles was made by Restall and Slaney (1995). The construction appears in a context very different from ours: they use a four-valued logic and show that by dropping the Recovery postulate, they obtain a representation result for partial-meet with non-maximal remainders. Note that there is no restriction as to the remainder sets containing a minimal core, as was made for infra remainders, and as a result there is no postulate associated with any kind of minimal change.
While there has been some work on revision for Horn formulas (Eiter & Gottlob, 1992;Liberatore, 2000;Langlois, Sloan, Szörényi, & Turán, 2008), it is only recently that attention has been paid to contraction for Horn logic. Apart from the work of Delgrande (2008) which has been discussed, there is some recent work on obtaining a semantic characterisation of Horn contraction using the system of spheres by Fotinopoulos and Papadopoulos (2009), and via epistemic entrenchment by Zhuang and Pagnucco (2010). Billington et al. (1999) considered revision and contraction for defeasible logic which is quite different from Horn logic in many respects, but nevertheless has a rule-like flavour to it which has some similarity to Horn logic.
The present paper is an extension of the work by Booth et al. (2009) in which they show that infra e-contraction is captured precisely by the six AGM postulates for belief set contraction, except that Recovery is replaced by the following ( Postulate (H − e 6) bears some resemblance to the Relevance postulate for base contraction in that it states that all sentences removed from H during a ϕ-contraction must have been removed for a reason: adding them again brings back ϕ. Postulate (H − e 7) simply states that contracting with a tautology leaves the initial belief set unchanged.
It is worth noting that (H − e 6) is a somewhat unusual postulate in that it refers directly to the construction method it is intended to characterize, i.e., to e-remainder sets.
Here we have provided a more elegant characterization of infra e-contraction by taking a detour through base contraction. Firstly, we replaced (H − e 6) with the Core-retainment postulate that is used in the characterization of base kernel contraction. Then it turns out that the Vacuity postulate (K − 3) and the Failure postulate (H − e 7) both follow from Core-retainment and the Inclusion postulate (K − 2), from which we then obtained our characterization of infra e-contraction.
In addition to e-contraction, Delgrande also investigated a version of Horn contraction he refers to as inconsistency-based contraction (or i-contraction) where the purpose is to modify an agent's Horn belief set in such a way as to avoid inconsistency when a sentence ϕ is provided as input. That is, an i-contraction − i should be such that (H − i ϕ) ∪ {ϕ} |= HL ⊥.
In addition to both e-and i-contraction, Booth et al. (2009) considered package contraction (or p-contraction), a version of contraction studied by Fuhrmann and Hansson (1994) for the classical case (i.e., for logics containing full propositional logic). Given a set of formulas X, the goal is to make sure that none of the sentences in X is in the result obtained from p-contraction. For full propositional logic this is similar to contracting with the disjunction of the sentences in X. For Horn logic, which does not have full disjunction, package contraction is more interesting. Although it seems that the new results presented in this paper can be applied to both i-contraction and p-contraction, this still has to be verified in detail. Delgrande and Wassermann (2010) draws inspiration from the semantic representation of remainder sets. In the classical AGM approach, a remainder set can be obtained semantically by adding to the models of a belief set H a counter-model of the formula ϕ for contraction. With Horn clauses, this construction will not necessarily lead to sets that correspond to remainder sets. This is because, as is known in Horn logic, given any two models of m 1 , m 2 of a Horn belief set H, the model m 1 m 2 is also a model of H, where m 1 m 2 denotes that model in which the atoms true in it are precisely the atoms which are true in both m 1 and m 2 . To illustrate this, consider the following example:
In Example 5, the unique model of the set {p, ¬q, r} is a countermodel of p ∧ q. If we add it to the models of H and close them under so that the result represents a Horn belief set, we obtain the set of models of the formula p, which cannot be an e-remainder set, as there is an e-remainder set (Cn HL (p ∧ (r → q))) containing it. This means that in an approach based on e-remainder sets we cannot have contraction operators with the same behaviour as the classical ones.
Delgrande and Wassermann propose to mimic the semantic construction of classical remainders: a weak-remainder of H and ϕ is formed by intersecting H with a maximal consistent Horn theory not containing ϕ. Equivalently, the weak-remainders can be semantically characterized by taking the closure under intersection of the models of H together with a single counter-model of ϕ. Representation results for contraction based on weakremainders are then provided.
Concerning the connection between partial meet contraction and kernel contraction for bases, Falappa et al. (2006) have shown how to construct a partial meet contraction from a kernel contraction, which is always possible, and how to construct a kernel contraction from a partial meet contraction, when this is possible. These results can be generalized so that they apply to base infra contraction and base kernel contraction. That is, it should be possible to construct a base infra contraction from every base kernel contraction, as well as a base kernel contraction from every base infra contraction.

Concluding Remarks
In bringing Hansson's kernel contraction into the picture, we have made meaningful contributions to the investigation into contraction for Horn logic. The main contributions of the present paper are as follows: (i) A result which shows that infra contraction and kernel contraction for the belief base case coincide; and (ii) Lifting the previous results to Horn belief sets to show that infra contraction and kernel contraction for Horn belief sets coincide.
The investigation into base contraction also allowed us to improve on the rather unsatisfactory representation result proved by Booth et al. for infra contraction, which relies on a postulate referring directly to the construction method it is intended to characterize. We obtained a more elegant representation result by replacing the postulate introduced by Booth et al. with the well-known Core-retainment postulate, which is usually associated with base contraction. The presence of Core-retainment here further enforces the hybrid nature of Horn belief change, lying somewhere between belief set change and base change.
We have seen that kernel e-contraction and infra e-contraction are more general than partial meet e-contraction. But there is also evidence that even these forms of Horn contraction may not be sufficient to obtain all meaningful answers. Consider, for example, our Horn belief set example Cn HL ({p → q, q → r}) encountered in Example 4. If we view basic Horn clauses (clauses with exactly one atom in the head and the body) as representative of arcs in a graph, in the style of the old inheritance networks, there is a case to be made for regarding the three "arcs" p → q, q → r, and p → r, as the basic information used to generate the belief set. Then one possible desirable outcome of a contraction by p → r is Cn HL (q → r). However, as we have seen in Example 4, this is not an outcome supported by infra e-contraction (and therefore not by kernel e-contraction either). Ideally, a truly comprehensive e-contraction approach for Horn logic would be able to account for such cases as well.
Here we focus only on basic Horn contraction. For future work we plan to investigate Horn contraction for full AGM contraction, obtained by adding the extended postulates. Another interesting question for further investigation is whether Theorem 9 can be generalized to other logics, notably extensions of (full) propositional logic.
Finally, as mentioned earlier, one of the reasons for focusing on this topic is because of its application to debugging and repairing ontologies in description logics. In particular, Horn logic can be seen as the backbone of the EL family of description logics (Baader et al., 2005), and therefore a proper understanding of belief change for Horn logic is important for finding solutions to similar problems expressible in the EL family. We are currently investigating these possibilities.
valuations which satisfy ϕ. For a set of sentences X, we denote by [X] the set of models of X, i.e., the set of valuations which satisfy all sentences in X. For any V ⊆ W, we let The results in Lemma A.1 below are well-known model-theoretic descriptions of full meet, partial meet, and maxichoice contraction, first presented by Katsuno & Mendelzon (1991). The results, as stated below, are not stated directly by Katsuno & Mendelzon, but follow as easy consequences of their Theorem 3.3.
1. Let − fm be the (belief set) full meet contraction. For every ϕ ∈ L P , K − fm ϕ = There is a (belief set) partial meet contraction − pm such that for every ϕ ∈ L P , Theorem 3 (Convexity) Let K be a belief set, let − mc be a (belief set) maxichoice contraction, and let − fm denote (belief set) full meet contraction. For every ϕ ∈ L P , let X ϕ be a belief set such that There is a (belief set) partial meet contraction − pm such that for every ϕ ∈ L P , K − pm ϕ = X ϕ .

Proof:
The cases where |= ϕ and ϕ / ∈ K hold easily, so we suppose that |= ϕ and ϕ ∈ K. Now, pick any belief set X ϕ such that K − fm ϕ ⊆ X ϕ ⊆ K − mc ϕ. By Points (1) and (2) (3) of Lemma A.1 it then follows that there is a partial meet contraction − pm such that, for every ϕ ∈ L P , K − pm ϕ = X ϕ = T h([K] ∪ V ϕ ). [qed] Lemma A.2 (Falappa et al., 2006) Every base kernel contraction defined by a minimal incision function is a base maxichoice contraction.
Lemma A.3 The base kernel contraction defined by the maximal incision function is the full meet base contraction.

Proof:
We need to prove that B \ (B ⊥ ⊥ ϕ) = (B⊥ϕ). If |= ϕ or B |= ϕ the result follows immediately. So we suppose that |= ϕ and B |= ϕ. For the left-to-right direction, suppose that ψ ∈ B and ψ / ∈ (B ⊥ ⊥ ϕ), and assume there is some base remainder set of B with respect to ϕ, say X, such that ψ / ∈ X. Then it must be the case that ψ is contained in some ϕ-kernel of B. But then ψ ∈ (B ⊥ ⊥ ϕ): a contradiction. For the right-to-left direction, suppose ψ is in every base remainder set of B with respect to ϕ, and assume that ψ / ∈ B \ (B ⊥ ⊥ ϕ). Since ψ ∈ B it follows that ψ ∈ (B ⊥ ⊥ ϕ). That is, ψ is in some ϕ-kernel of B. So there is at least one minimal incision function σ such that ψ ∈ σ(B ⊥ ⊥ ϕ). Now, from Lemma A.2 it follows that there is a base remainder set of B with respect to ϕ, say Y , such that Y = B \ σ(B ⊥ ⊥ ϕ). So ψ / ∈ Y , which contradicts the supposition that ψ is in every base remainder set of B with respect to ϕ. [qed] Theorem 7 A base contraction for a belief base B is a belief base kernel contraction for B if and only if it is a base infra contraction for B.

Proof:
For the "only if" part, let − be a base kernel contraction for B, let σ be the incision function for B which generates −, and pick a ϕ ∈ L P . If |= ϕ or B |= ϕ the result holds easily, so we suppose that |= ϕ and B |= ϕ. It remains to be shown that ( For the "if" part, let − be a base infra contraction for B. We construct an incision function σ such that the base kernel contraction it generates is exactly −. Pick a ϕ ∈ L P and suppose that |= ϕ and B |= ϕ (for the remaining cases the result easily holds). Let σ(B ⊥ ⊥ ϕ) = B \(B −ϕ). Since B −ϕ ⊆ B we have that B −ϕ = B \σ(B ⊥ ⊥ ϕ). First we need to show that σ(B ⊥ ⊥ ϕ) ⊆ (B ⊥ ⊥ ϕ). To do so, observe that since B − ϕ ∈ B ↓ ϕ, it follows that (B⊥ϕ) ⊆ B − ϕ. Therefore B \ (B − ϕ) ⊆ B \ (B⊥ϕ). By Lemma A.3 and the construction of σ we then have that σ(B ⊥ ⊥ ϕ) = B \ (B − ϕ) ⊆ B \ (B⊥ϕ) = (B ⊥ ⊥ ϕ).
It remains to be shown that for every Y such that ∅ ⊂ Y ∈ B ⊥ ⊥ ϕ, Y ∩ σ(B ⊥ ⊥ ϕ) = ∅. Pick a Y such that ∅ ⊂ Y ∈ B ⊥ ⊥ ϕ, and assume that Y ∩ σ(B ⊥ ⊥ ϕ) = ∅. Then it must be the case that Y ⊆ B − ϕ. But Y |= φ and therefore B − ϕ |= ϕ, a contradiction. [qed] Theorem 8 An e-contraction for a Horn belief set H is an infra e-contraction for H if and only if it is a kernel e-contraction for H.

Proof:
Consider a belief base B and a formula ϕ. From Theorem 7 it follows that the set of base infra remainder sets of B with respect to ϕ (i.e., the set B ↓ ϕ) is equal to the set of results obtained from the base kernel contraction of B by ϕ, call it KC B ϕ . Now let B be such that it is a set of Horn formulas closed under Horn consequence (a Horn belief set) and ϕ a Horn formula. The elements of KC B ϕ are not necessarily closed under Horn consequence, but if we do close them, we obtain exactly the set of results obtained from kernel e-contraction when contracting B by ϕ (by the definition of kernel e-contraction). Let us refer to this latter set as Cn HL (KC B ϕ ), i.e., Cn HL (KC B ϕ ) = {Cn HL (X) | X ∈ KC B ϕ }. Also, the elements of B ↓ ϕ are not closed under Horn consequence, but if we do close them the resulting set (refer to this set as Cn HL (B ↓ ϕ)) contains exactly the infra e-remainder sets of B with respect to ϕ, i.e., Cn HL (B ↓ ϕ) = B ↓ e ϕ. To see why, observe that since B is closed under Horn consequence, the (base) remainder sets of B with respect to ϕ (i.e., the elements of B⊥ϕ) are also closed under Horn consequence. So the elements of B ↓ ϕ are all the sets (not necessarily closed under Horn consequence) between (B⊥ϕ) and some element of B⊥ϕ. Therefore the elements of Cn HL (B ↓ ϕ) are all those elements of B ↓ ϕ that are closed under Horn consequence, i.e., Cn HL (B ↓ ϕ) = B ↓ e ϕ as was claimed. But since B ↓ ϕ = KC B ϕ , it is also the case that Cn HL (B ↓ ϕ) = Cn HL (KC B ϕ ), and therefore Cn HL (KC B ϕ ) = B ↓ e ϕ. [qed]