Revising Horn Theories

1 Introduction

The area of belief change studies how an agent may modify its beliefs given new information about its environment. The best-known approach in this area is the AGM paradigm [Alchourr´on et al., 1985; G¨ardenfors, 1988], named after the original developers. This work focussed on belief revision, in which new information is incorporated into an agent's belief corpus, as well as belief contraction, in which an agent may reduce its set of beliefs. The AGM approach addresses belief change at an abstract level, in which an agent's beliefs are characterised by belief sets or deductively closed sets of sentences, and where the underlying logic includes classical propositional logic. In the basic approach to revision, a set of rationality postulates is given which arguably any revision function should satisfy. As well, a semantic construction of

Pavlos Peppas

Dept of Business Administration University of Patras Patras 265 00 Greece pavlos@upatras.gr

revision functions has been given, in terms of a total preorder over possible worlds, called a faithful ranking. These syntactic and semantic approaches are then shown to capture the same set of revision functions.

In this paper we consider AGM-style belief revision in the language of Horn clauses, where a Horn clause can be expressed as a rule of the form a1∧a2∧· · ·∧an → a for n ≥ 0, and where a, ai (1 ≤ i ≤ n) are atoms. (Thus, expressed in conjunctive normal form, a Horn clause will have at most one positive literal.) In our approach an agent's beliefs are represented by a Horn clause knowledge base, and the input is a Horn formula, consisting of a conjunction of Horn clauses. It proves to be the case that AGM-style belief revision doesn't transfer directly to Horn knowledge bases. On the one hand, in the Horn case the AGM postulate set is unsound with respect to a faithful ranking over possible worlds. On the other hand, given a Horn revision function that satisfies the AGM postulates, there may be no corresponding faithful ranking that captures the revision function or, alternately, there may be several faithful rankings that capture the function.

Nonetheless, we show that the AGM approach may be extended to the Horn case naturally and satisfactorily. On the semantic side, we impose a "well-behaved" condition on faithful rankings, expressing that a ranking must be coherent with respect to Horn revision. (In propositional logic, the corresponding condition proves to be trivial.) On the syntactic, postulational, side, we add a postulate to the standard suite of AGMpostulates. Interestingly, in the AGMapproach this additional postulate is redundant, in that it follows as a theorem from the other AGM postulates. In the Horn case, in which inference is weaker than in the classical case, this postulate is independent of the others. Given these adjustments to the AGM approach, we then prove a representation result, showing that the class of Horn revision functions conforming to the extended postulate set is the same as those capturable by "well-behaved" faithful rankings.

This topic is interesting for several reasons. It sheds light on the theory of belief change, in that it weakens the assumption that the underlying logic contains propositional logic. In so doing, it shows that the AGM approach is more generally applicable than perhaps originally believed. That is, our results provide a broadening of the AGM approach to include Horn reasoning, and not just a modification of the AGM approach to accommodate Horn reasoning. Horn clauses are a very useful restriction of classical logic, and have found widespread application in artificial intelligence and database theory. As well, results here may also be relevant to belief change in description logics, a topic that has also received recent attention.

The next section introduces belief change, Horn clause reasoning, and work that has been carried out in the intersection of these areas. This is followed by a discussion of issues that arise in Horn clause belief revision (Sections 4 and 5). The following section develops the approach, and in particular presents the representation result for Horn formula revision. The paper concludes with a discussion of future work and a brief conclusion. Proofs are omitted due to space considerations, but are available in the full paper.

2 Formal Preliminaries

We introduce here the terminology that we will use in the rest of the paper. P = {a, b, c, . . . } is a finite set of propositional variables. LH denotes the Horn formula language over P ∪ {⊥}. That is, LH is the least set given by:

1. a1 ∧ a2 ∧ · · · ∧ an → a is a Horn clause, where n ≥ 0 and a, ai ∈ P ∪ {⊥} for 1 ≤ i ≤ n.

If n = 0 then → a is also written a, and is a fact.

1. Every Horn clause is a Horn formula.
2. If φ and ψ are Horn formulas then so is φ ∧ψ.

In our approach, we deal exclusively with Horn formulas, and so formula will refer to a Horn formula; the only exception is when we discuss background work, in which case the context is clear. Formulas are denoted by lower case Greek letters; sets of formulas are denoted by upper case Greek letters.

An interpretation m is a subset of P, where a ∈ m is true and a ̸∈ m is false. Occasionally we will explicitly list negated atoms in an interpretation; for example for P = {p, q} the interpretation {p} will sometimes be written {p, ¬q} or more briefly pq. The symbol ⊥ is always assigned false. M is the set of interpretations or (possible) worlds. Sentences of LH are true or false in an interpretation according to the standard rules in propositional logic. Truth of φ in m is denoted m |= φ. As well, for W ⊆ M, W |= φ iff for every m ∈ W, m |= φ. For formula φ, |φ| is the set of models of φ. For set of worlds W, tH(W) denotes the set of formulas satisfied by all worlds in W, i.e. tH(W) = {φ ∈ LH | m |= φ for every m ∈ W}. Note that this means that tH(∅) = LH.

Γ ⊢ φ iff φ is derivable from set of formulas Γ [Delgrande, 2008] (again, members of Γ and φ are Horn, and ⊢ is defined in terms of Horn formulas). ψ ⊢ φ is an abbreviation for {ψ} ⊢ φ, and ψ ≡ φ is logical equivalence, i.e. ψ ⊢ φ and φ ⊢ ψ. This extends in the obvious fashion to sets of formulas. For a set of formulas Γ, the closure of Γ under Horn derivability is denoted CnH(Γ). A (Horn) theory H is a set of formulas such that H = CnH(H), also referred to as a belief set. H is the set of Horn theories. For theory H and formula φ, H + φ = CnH(H ∪ {φ}) is the expansion of H. H⊥ = LH is the inconsistent belief set.

Models of Horn formulas are distinguished by the fact that they are closed under intersection of positive atoms in an interpretation. That is:

We note that the converse is also true; i.e., if a set of models W is closed under intersection of positive atoms in an interpretation, then there is a Horn formula φ such that |φ| =W.

Cl∩(W) is the intersection closure of a set of interpretations W, i.e. Cl∩(W) is the least set such that W ⊆ Cl∩(W) and m1, m2 ∈ Cl∩(W) implies that m1 ∩m2 ∈ Cl∩(W).

A (partial) preorder ⪯ is a reflexive, transitive binary relation. A total preorder is a partial preorder such that either m1 ⪯ m2 or m2 ⪯ m1 for every m1, m2. The strict part of preorder ⪯ is denoted by ≺, that is, m1 ≺ m2 just if m1 ⪯ m2 and m2 ̸⪯ m1. As usual, m1 ≈ m2 abbreviates m1 ⪯ m2 and m2 ⪯ m1. Finally, for a set of interpretations W ⊆ M, by min(W, ⪯) we denote the set min(W, ⪯) = {m1 ∈W: for all m2 ∈W, if m2 ⪯m1 then m1 ⪯m2}.

3 Background

3.1 Belief Revision

In the AGM approach to belief change, beliefs of an agent are modelled by a deductively closed set of formulas, or belief set. Thus a belief set is a set of formulas K such that K = Cn(K). 1 It is assumed that the underlying logic subsumes classical propositional logic. Belief revision is modeled as a function from a belief set K and a formula φ to a belief set K′ such that φ is believed in K′ , i.e. φ ∈ K′ . Since φ may be inconsistent with K, and since it is desirable to maintain consistency whenever possible (i.e. whenever φ is consistent) then some formulas may need to dropped from K before φ can be consistently added. Formally, a revision operator ∗ maps a belief set K and formula φ to a revised belief set K ∗ φ. The AGM postulates for revision can be formulated as follows, where ≡PC and +PC stand for logical equivalence and expansion, respectively, in classical propositional logic.

• (K*1) K ∗ φ = Cn(K ∗ φ)
• (K*2) φ ∈ K ∗ φ
• (K*3) K ∗ φ ⊆ K +PC φ
• (K*4) If ¬φ /∈ K then K +PC φ ⊆K ∗ φ
• (K*5) K ∗ φ is inconsistent only if φ is inconsistent
• (K*6) If φ ≡PC ψ then K ∗ φ =K ∗ ψ
• (K*7) K ∗ (φ ∧ ψ) ⊆ K ∗ φ +PC ψ

Thus, the result of revising K by φ yields a belief set in which φ is believed ((K*1), (K*2)); whenever the result is consistent, the revised belief set consists of the expansion of K by φ ((K*3), (K*4)); the only time that K is inconsistent is when φ is inconsistent ((K*5)); and revision is independent of the syntactic form of the formula for revision ((K*6)). The last two postulates deal with the relation between revising by a conjunction and expansion: whenever consistent, revision by a conjunction corresponds to revision by one conjunct and expansion by the other. Motivation for these postulates can be found in [G¨ardenfors, 1988; Peppas, 2008]. The intent of these postulates is that they should hold for any rational belief revision function.

1 Cn(K) denotes the closure of K under classical logical implication.

Katsuno and Mendelzon [1991] have shown that a necessary and sufficient condition for constructing an AGM revision operator is that there is a function that associates a total preorder on the set of possible worlds with any belief set K, as follows: 2

Definition 1 A faithful assignment is a function that maps each belief set K to a total preorder ⪯K on M such that for any possible worlds w1, w2:

The resulting preorder is referred to as the faithful ranking associated with K. Intuitively, w1 ⪯K w2 if w1 is at least as plausible as w2. Katsuno and Mendelzon then provide the following representation result, where t(W) is the set of formulas of classical logic true inW:

Theorem 1 ([Katsuno andMendelzon, 1991]) A revision operator * satisfies postulates (K*1)-(K*8) iff there exists a faithful assignment that maps each belief set K to a total preorder ⪯K such that

Thus the revision of K by φ is characterised by those models of φ that are most plausible according to the agent. Given that we are working with a finite language, this construction is in fact equivalent to the earlier systems of spheres approach of [Grove, 1988]. It is easier to present our results in terms of faithful assignments, and so we do so here.

Another form of belief change in the AGM approach is belief contraction, in which an agent's beliefs strictly decrease. Thus in the contraction K - φ, one has φ ̸∈ K - φ ⊆ K, while ¬φ is not necessarily believed. There are two primary means of constructing contraction functions. Using remainder sets, a contraction K - φ is defined in terms of maximal subsets of K that fail to imply φ. Via epistemic entrenchment, an ordering is defined on sentences of K, and a contraction K-φ is (roughly) defined in terms of the most entrenched set of sentences that does not imply φ. Of interest, and pertinent to the approach at hand, these various constructions are all in a certain sense interdefinable, as are revision and contraction functions. Hence, given a contraction function -, one may define a revision function by the so-called Levi identity:

See [G¨ardenfors, 1988; Peppas, 2008] for details.

2 In fact, Katsuno and Mendelzon deal with formulas instead of belief sets. Since we deal with finite languages only, the difference is immaterial. We use belief sets in order to adhere more closely to the original AGM approach.

3.2 RelatedWork

Earlier work on belief change involving Horn formulas dealt with the Horn fragment of a propositional theory, rather than Horn clause belief change as a distinct phenomenon. For example, the complexity of specific approaches to revising knowledge bases is addressed in [Eiter and Gottlob, 1992], including the case where the knowledge base and formula for revision are Horn formulas. [Liberatore, 2000] considers the problem of compact representation for revision in the Horn case. Given a knowledge base K and formula φ, both Horn, the main problem considered is whether a revised knowledge base can be expressed by a propositional formula whose size is polynomial with respect to the sizes of K and φ.

[Langlois et al., 2008] approaches the study of revising Horn formulas by characterising the existence of a complement of a Horn consequence; such a complement corresponds to the result of a contraction operator. This work may be seen as a specific instance of a general framework developed in [Flouris et al., 2004].

The main difference between our work and the above approaches to Horn revision, is that in our approach revision functions always produce Horn theories (they are postulated to do so). This of course adds an extra burden to the revision process since it now needs to comply with both the principle of minimal change (see [G¨ardenfors, 1988; Peppas, 2008]), and the requirement to produce Horn theories (which in this context can be seen as an instance of the principle of categorical matching). Our results show that, with some adjustments to the original AGM framework, this double objective can indeed be achieved.

Similar results have already been acheived for Horn contraction. [Delgrande, 2008] addresses maxichoice belief contraction in Horn clause theories, where contraction is defined in terms of remainder sets. Further developments in Horn contraction can be found in [Booth et al., 2009], [Delgrande and Wassermann, 2010], and [Zhuang and Pagnucco, 2010].

4 Horn Revision: Preliminary Considerations

The postulates and semantic construction of Section 3.1 are easily adapted to Horn theories. For the postulates, we have the following, expressed in terms of Horn theories.

An AGM (Horn) revision function ∗ is a function from H× LH to H satisfying the following postulates.

As well, faithful assignments can be defined for the Horn case, basically by changing notation:

Definition 2 A faithful assignment is a function that maps each Horn theory H to a total preorder ⪯H on M such that for any possible worlds m1, m2:

1. If m1, m2 ∈ |H| then m1 ≈H m2
2. If m1 ∈ |H| and m2 ̸∈ |H|, then m1 ≺H m2.

The resulting preorder is referred to as the faithful ranking associated with H. Finally, one can define a function ∗ in terms of a faithful ranking by:

The use of ∗ in (2) is suggestive; ideally one would next establish a correspondence between functions that satisfy the postulates and those that can be defined via Definition 2. However, there are significant difficulties in immediately establishing such a representation result. We review these problems next, and then present our solution in the following section.

5 Problems with Na¨ıve AGMHorn revision

1. Interdefinability results do not hold in Horn belief change. Asmentioned in Section 3.1, in theAGMapproach revision may be defined in terms of contraction via the Levi Identity (1). However, previous work [Delgrande and Wassermann, 2010] suggests that Horn contraction is unsuitable for specifying a revision operator. As well, if one considers the Levi Identity, revision by a Horn formula φ is defined in terms of the contraction by ¬φ. Since φ is a conjunction of Horn clauses, ¬φ in general will not be Horn, and so the Levi identity would seem to be inapplicable for Horn theories.

These points are not definitive (there is, after all, no formal result stating an impossibility of interdefinability of Horn contraction and revision), but they do suggest the overall difficulty in obtaining such a result. Consequently, we focus on a direct definition of Horn revision, in terms of ranking functions in the next section. Having developed such an approach, we then suggest that the relation between Horn contraction and revision is a suitable and interesting topic for future research.

1. Distinct rankings may yield the same revision function. Consider the Horn language defined by P = {p, q}, and the following three total preorders:

It can be verified that if one defines revision via Definition 2, the three total preorders yield the same revision function. In particular, there is no way in which the relative ranking of worlds given by pq and pq can be distinguished.

The difficulty is that, in AGM revision, given a revision function that satisfies the AGM revision postulates, for interpretations m1 and m2 one can define m1 ⪯K m2 just if there is φ such that m1 ∈ |K ∗ φ| and m2 ∈ |φ|. The problem in the example is that for m1 = {pq} and m2 = {pq}, then for any φ with m1,m2 ∈ |φ|, one also has m3 = pq ∈ |φ|.

In the example, for H = CnH(p ∧ q) and φ = p ∧ q → ⊥, H ∗ φ = CnH(¬p ∧ ¬q). Consequently the relative ranking of m1 and m2 cannot be specified.

3. Postulates may not be satisfied in a faithful ranking. Consider the Horn language with atoms P = {p, q, r} and the ranking:

The agent's belief set H is given by CnH(p ∧ q ∧ r). Let μ be p∧q → ⊥ and φ be ¬p∧¬q. Defining ∗ as in Definition 2, it can be verified that:

Thus (H ∗ μ) + φ and H ∗ (μ ∧ φ) are not equivalent and violate both (H*7) and (H*8).

Informally, the culprit is the set of worlds {pqr, pqr}. This set (as with the previous problem) is not expressible by a Horn formula, since it is not closed under intersection of (positive) atoms. It can be observed that the "missing" interpretation is given by pqr, where in addition we have pqr ≈ pqr ≺ pqr. The problem arises then because one may revise by a Horn formula (viz. μ = p ∧ q → ⊥) that yields the set of minimal models {pqr, pqr}, but in producing the corresponding Horn theory tH({pqr, pqr}) = CnH((p ∧ q →⊥) ∧¬r)), a new non-minimal model pqr creeps in. 3

1. There is a Horn AGM revision function satisfying (H*1)-(H*8) that cannot be modelled by a preorder on worlds. Consider the following pseudo-preorder onworlds:

That is, the most preferred world is pqr, followed by pqr, followed by pqr, pqr, pqr which form a cycle (i.e. pqr ≺ pqr ≺ pqr ≺ pqr). Finally comes the sequence of worlds pqr ≺ pqr ≺ pqr.

Based on the pseudo-preorder ⪯ of Figure 1, we can define a Horn revision function according to Definition 2. The only time this revision function can run into trouble (i.e. produce an inconsistent result for a consistent φ) is if φ is inconsistent with the first two worlds pqr, pqr and consistent with all three world in the cycle; i.e. {pqr, pqr} ∩ |φ| = ∅ and {pqr, pqr, pqr} ⊆ |φ|. However, no such Horn formula φ

3 As a sublety, this doesn't imply that a maximum set of equivalently-ranked worlds must be definable by a Horn formula. For example (5) contains a set of worlds that isn't definable by a Horn formula. However, in our approach this ranking will prove to be an acceptable ordering on worlds.

exists. To see this notice that any Horn formula μ such that {pqr, pqr, pqr} ⊆ [μ], has pqr as a model (since the models of Horn formulas are closed under intersections of the positive atoms in an interpretation).

It proves to be the case that * as defined in Figure 1 satisfies all AGM postulates for Horn revision. However, it can also be shown that no (partial or total) preorder on worlds can model *. The details are omitted due to space constraints but are included in the full paper.

6 Horn Revision: The Approach

As is clear from the previous discussion, there are substantial differences between classical AGM revision and Horn revision. Since the AGM postulates and the Katsuno-Mendelzon construction are essentially the same for Horn theories, these differences come about from the weakened expressibility of Horn clause theories.

Consider again the issues discussed in the previous section. The first issue isn't a problem per se. Rather, it suggests that, when we look at Horn theories, belief change operators are not interdefinable, or at best are not readily interdefinable.

The second issue also isn't a problem as such. Instead, it indicates that a ranking may be underconstrained by a revision function. In our approach, we address this indirectly by defining a canonical ranking, in which if there is no reason to distinguish the rank of worlds then they are assigned the same rank.

The third issue, that a ranking may violate the postulates (H*7) and (H*8), is indeed a problem. As discussed, the difficulty essentially is that some orderings are unsuitable with respect to Horn revision. The solution then is to add a constraint to faithful orderings such that these "unsuitable orderings" are ruled out. This is covered by the notion of Horn compliance, defined below.

As the fourth problem demonstrates, the Horn AGM postulates may fail to rule out undesirable relations on sets of worlds, which is to say, the postulate set is too weak to eliminate certain undesirable non-preorders. This then requires adding to the postulate set to (semantically) further constrain the set of allowable orderings.

6.1 ARepresentation Result

In accordance with the previous discussion, on the one hand we add a condition to restrict rankings on worlds; on the other we add a postulate to the set of Horn AGM postulates.

On the semantic side, we restrict rankings to those that yield coherent results with respect to Horn revision. That is, we want to allow only those orderings where revision by a Horn formula will yield a set of worlds corresponding to a Horn formula.

Call a set of worlds W Horn elementary iff it is definable via a Horn formula, i.e. if there is a Horn formula φ such that W = |φ|. So W is Horn elementary iff W = Cl∩(W). A preorder ⪯H is Horn compliant iff for every formula φ ∈ LH, min(|φ|, ⪯H) is Horn elementary.

For example, the preorder in (5) is Horn compliant. Note that, while the set {pq, pq} is not Horn elementary, there is no Horn formula φ over P = {p, q} such that min(|φ|,⪯H) = {pq, pq}. On the other hand, the ordering in (6) is not Horn compliant since min(|p ∧ q → ⊥|, ⪯H) = {pqr, pqr}, and {pqr, pqr} is not Horn elementary.

With respect to postulates, we introduce the following schema:

We note the following minor results:

Proposition 1 (Acyc) is a logical consequence of the AGM postulates (i.e. where the underlying logic contains classical propositional logic).

Proposition 2 (Acyc) is independent of the Horn AGM postulates.

Figure 1 suffices to show the independence of (Acyc) from the Horn AGM postulates: defining revision according to Definition 2 yields a revision function that satisfies the AGM postulates for Horn revision; however it can be verified that it violates (Acyc).

Informally, (Acyc) rules out cycles (of any length n) as found for example in Figure 1. To see this, consider the instance of (Acyc) for n = 2:

If revision is defined as in Definition 2, then (H∗μ1)+μ0 ̸⊢ ⊥ iff min(|μ1|,⪯H) ∩ |μ0| ̸= ∅. This last relation implies that, for w1 ∈ min(|μ1|, ⪯H) and w0 ∈ min(|μ0|, ⪯H) it must be that w0 ⪯H w1. Consequently, the postulate can then be read as requiring that if w0 ⪯H w1 ⪯H w2 ⪯H w0 then w0 ⪯H w2, and with some further deliberation, w0 ≈H w1 ≈H w2 (thus ruling out the pseudo-preorder of Figure 1).

The notion of Horn compliance on the one hand, and the postulate (Acyc) on the other, prove to be sufficient to extend the AGM approach to capture revision in Horn theories. We obtain the following results:

Theorem 2 Let H be a Horn belief set and ⪯H a Horn compliant faithful ranking associated with H. Define an operator ∗ : H× LH ↦→ H by H ∗ φ = tH(min(|φ|,⪯H)). Then ∗ satisfies postulates (H*1)-(H*8) and (Acyc).

Proof Summary: The proof is much the same as for classical AGM revision. Horn compliance is required to show that (H*7) and (H*8) hold. (Acyc) basically follows the informal rationale of the postulate given above. ✷

Theorem 3 Let ∗ : H× LH ↦→ H be a function satisfying postulates (H*1)-(H*8) and (Acyc). Then for fixed theory H, there is a faithful ranking ⪯H on M such that ⪯H is Horn compliant and H ∗ φ = tH(min(|φ|, ⪯H)).

Proof Summary: For interpretations m1, m2, define f(m1,m2) to be the logically strongest Horn formula with models m1, m2. It may be that {m1,m2} ⊂ |f(m1,m2)|. Nonetheless we can define m1 ⪯◦H m2 iff m1 ∈ |H ∗ f(m1,m2)|. The relation ⪯◦H is not transitive, but (Acyc) guarantees that ⪯◦H can be extended safely to a total preorder ⪯H that is shown to be Horn compliant and that exactly captures the original revision function. ✷

We conclude this section with some comments on Horn compliance. Firstly notice that, in certain cases, Horn compliance excludes some popular preorders like, for example, those proposed in [Dalal, 1988]. To see this, assume that P = {p, q}, and H = CnH({p, q}). Then according to Dalal, pq ≺H pq ≈H pq ≺H pq, which however is not a Horn compliant preorder.

This raises the question of whether Horn compliant preorders are at all possible. Luckily the answer is affirmative. For any Horn theory H, one can construct a Horn compliant preorder ⪯H as follows: start with the H-worlds, and then attach any linear order on the non-H-worlds. The resulting preorder can be easily shown to be Horn-compliant (of course there are also other ways to build Horn-compliant preorders - see the full paper for more details).

7 Discussion

It can be noted that while the above results are expressed in terms of Horn theories, they represent an extension rather than a modification of the AGM approach. That is, we could redefine (AGM-style) revision in the context of a logic that contains Horn derivability. Postulates would consist of (H*1)- (H*8) and (Acyc) as before, while the construction would be in terms of Horn compliant faithful rankings. This would subsume classical AGM revision: classical propositional logic obviously is stronger than Horn logic. In classical propositional logic the notion corresponding to Horn compliance is trivial, since (over a finite alphabet) for any formula φ of propositional logic, min(|φ|,⪯) is definable via a formula of propositional logic. On the postulational side, as indicated, (Acyc) is derivable from the other postulates if one has classical propositional logic.

These results also suggest several (in our opinion) very interesting directions for future work. First, we argued that AGM revision can be extended by weakening the underlying logic to that of Horn logic. This raises the issue of whether the overall framework can be broadened to subsume other weakened inference relations, while maintaining the overall AGM character, as reflected in the standard AGM postulates.

The area of belief change in Horn theories is in the process of being mapped out. Other research has characterised Horn contraction, while the present paper has addressed revision. However, there has been no work that we are aware of in linking the areas of Horn contraction and revision. Moreover, the constructions in Horn contraction have focussed on the standard contraction constructions of remainder sets and epistemic entrenchment, while the present work has used the standard revision construction of a faithful ranking. Hence there is also a disconnect in the underlying formal characterisations. Consequently, research on linking Horn contraction and revision would help shed further light on the foundations of belief change.

Last, there is burgeoning interest in addressing belief change in description logics (see [Qi and Yang, 2008] for instance) or in analogous areas such as ontology evolution. Given that a Horn clause may also find interpretation as a subsumption, by mapping a rule p ∧ q → r to a subsumption of the form P ⊓ Q ⊑ R, the present approach may also shed light on approaches to revision in description logics.