Rule Based Updates on Simple Knowledge Bases

Chitta Baral

Department of Computer Science University of Texas at El Paso El Paso, Texas 79968, U.S.A.

chitta@cs.ep.utexas.edu

Abstract

In this paper we consider updates that are specified as rules and consider simple knowledge bases consisting of ground atoms. We present a translation of the rule based update specifications to extended logic programs using situation calculus notation so as to compute the updated knowledge base. We show that the updated knowledge base that we compute satisfies the update specifications and yet is minimally different from the original database. We then expand our approach to incomplete knowledge bases. We relate our approach to the standard revision and update operators, the formalization of actions and its effects using situation calculus and the formalization of database evolution using situation calculus.

Introduction

Most work on belief revision in the literature focus on updating theories by sentences in the theory itself. Several different “update” operators (update, revision, contraction, erasure, forget etc) (KM89; GM88) and the relation between them have been studied (KM92) and postulates have been suggested for some of these operators (GM88; KM92).

In this paper^{1} we consider updates that are specified as rules (MT94b) (similar to rules in a logic program) and present methods to compute updated knowledge bases when knowledge bases consist of a set of ground atoms.

The following example illustrates the kind of updates that we consider.

Consider a knowledge base consisting of three employees: John, Peter and Carl; which represent a certain department D in an organisation. During an oraganisational shake up the department has to be updated based on the new knowledge that “If John remains in the department D then Peter has to leave the department D and if Carl remains in the department then John has to stay in the department”.

It should be noted that the intended meaning (MT94a) of the first statement is different from the statement “either John leaves the department or Peter leaves the department”. If the new knowledge is specified in propositional theory or in first order logic they would be equivalent. The “if” and “then” in the statement “If John remains in the department D then Peter has to leave the department D” are treated differently from the first order implication. Our intent is to give a higher priority to “John than to Peter”. This is necessary because we might like to have the language that specifies updates to have properties (say like ‘monotonicity’) which are different from the ones held by the language of the database.

To specify such rules Marek and Truszczynski (MT94a) introduce the notion of revision programs. They define P-justified revision of simple knowledge bases by a revision program. In this paper we show how to compute P-justified revisions of knowledge bases using extended logic programs and situation calculus. Marek and Truszczynski ’s definition of P-justified revision is only limited to the case when the CWA is assumed about the initial knowledge base. We extend the idea of P-justified revision to knowledge bases that could be incomplete and present an extended logic program that computes the revised knowledge base when the initial knowledge base may be incomplete.

We then consider update rules that explicitly relates the initial knowledge base to the revised knowledge base and show how revisions can be computed for such updates. Such rules are beyond the scope of Marek and Truszczynski ’s revision programs.

Our approach of computing the revised knowledge base is similar to the formalization of database evolution (Rei92) but uses extended logic programs (GL91) instead of first order logic. In its use of situation calculus and extended logic programs our approach treats revision specifications as “actions” and a knowledge base as a “situation” and has similarity to the formalization of actions and their effects in (GL92). Our approach is different than the event calculus approach in (Ko92) and considers more complex revisions than discussed in it.

1Supported by the grants NSF-IRI-92-11-662 and NSF-CDA 90-15-006.

Revision Specifications

In this section we review the concept of revision specifications^{2} and P-justified revision as defined in (MT94b).

Let U be a denumerable set. Its elements are referred to as atoms. A knowledge base is any subset of U. By ¬U we mean the set {¬a : a ∈ U}. Elements of U ∪ ¬U are called literals.

A revision specification uses a syntax similar to logic programs except that it has two special operators “in” and “out”. For any atom a the intuitive meaning in(a) is that the atom a is present in the revised knowledge base. Similarly the meaning of out(a) is that the atom a is absent in the revised knowledge base. For any atom p in U, in(p) an out(p) are referred to as r-literals of U.

The statement “If John remains in the department D then Peter has to leave the department D” is written as the revision rule:

out(peter) ← in(john)

We now formally define the revision specifications and P-justified revision. Definition 1 (MT94b) A revision rule can be of the following two forms

in(p) ← in(q_{1}), …, in(q_{m}), out(s_{1}), …, out(s_{n}) (1)

out(p) ← in(q_{1}), …, in(q_{m}), out(s_{1}), …, out(s_{n}) (2)

where p, q_{i}’s and s_{j}’s are atoms.

A collection of revision rules is called a revision specification. □

A knowledge base B is a r-model of (satisfies) an r-literal in(p) (out(p) respectively) if p ∈ B (p ∉ B, respectively). B is a r-model of the body of a rule if it satisfies each r-literal of the body. B is a r-model of a rule C if the following conditions hold: whenever B satisfies the body of C, then B satisfies the head of C. B is a r-model of a revision specification P if B satisfies each rule in P. Definition 2 (MT94b) Let P be a revision specification. By norm(P) we denote the definite program obtained from P by replacing each occurance of in(a) by a and each occurance of out(b) by b′. The necessary change for P is the pair (I, O) where I = {a : a ∈ least model of norm(P)} and O = {b : b′ ∈ least model of norm(P)}. P with necessary change (I, O) is said to be coherent if I ∩ O = ∅. □

Definition 3 (MT94b) Let P be a revision specification and D_{I} and D_{R} be two knowledge bases.

P_{D_{R}} is the revision program obtained from P by eliminating from P every rule of the type 1 or 2 such that q_{i} ∉ D_{R} or s_{j} ∈ D_{R}.

P_{D_{R}}|D_{I} is the revision program obtained from P_{D_{R}} by eliminating from the body of each rule in P_{D_{R}} in(a) if a ∈ D_{I} and out(a) if a ∉ D_{I}.

If P_{D_{R}}|D_{I} with necessary change (I, O) is coherent and D_{R} = D_{I} ∪ I \ O then D_{R} is called P-justified revision of D_{I}, and we write D_{I} ⟶^{P} D_{R}. □

Intuitively, P_{D_{R}} is the set of rules obtained from P by removing all rules in P whose body is not satisfied by D_{R}; and P_{D_{R}}|D_{I} is the set of rules obtained from P_{D_{R}} by removing all r-literals that satisfy D_{I} from the bodies of rules in P_{D_{R}}.

Example 1 Let D_{I} = {a, b} and P_{1} be the revision specification

out(b) ← in(a) } P_{1}

Let D_{R} be {a}. P_{1}_{D_{R}} is same as P_{1} and P_{1}_{D_{R}}|D_{I} = {out(b)} and hence is coherent with the necessary change (∅, {b})

and D_{R} = D_{I} ∪ ∅ \ {b}. Hence, D_{I} ⟶^{P} D_{R}.

Let P_{2} be

\begin{matrix}out(b) ← in(a) \\ out(a) ← in(b) \end{matrix} \} P_{2}

It is easy to see that P_{2}-justified revisions of D_{I} are {a} and {b}.

Let P_{3} be

\begin{matrix}out(b) ← in(a) \\ out(a) \end{matrix} \} P_{3}

It is easy to see that P_{3}-justified revisions of D_{I} is {b}. Intuitively we can consider P_{1} as the logic program {out b ← not out_{a}} and P_{3} as the logic program

out b ← not out a

out a ←

Let P_{4} be

\begin{matrix}in(a) ← in(a) \\ in(c) ← in(c) \end{matrix} \} P_{4}

It is easy to see that P_{4}-justified revisions of D_{I} is {a, b}. □

Proposition 1 (MT94b) If a knowledge base D satisfies a revision specification P then D is a unique Pjustified revision of D. □

Proposition 2 (MT94b) Let P be a revision specification and D_{I} be a knowledge base. If a knowledge base D_{R} is a P -justified revision of D_{I}, then D_{R} is a r-model of P. □

2Marek and Truszczynski used the term revision programs instead of revision specifications. We believe it to be more of a specification language (similar to the language A (GL92) for specifying effects of actions) that can be implemented in a logical language of choice, rather than a programming language.

Proposition 3 (MT94b) Let P be a revision specification and D_{I} be a knowledge base. If D_{R} is a P -justified revision of D_{I}, then D_{R} ÷ D_{I} is minimal in the family {D ÷ D_{I} : D is a r-model of P }, where ÷ denotes the symmetric difference. i.e. A ÷ B = (A \ B) ∪ (B \ A). □

It should be noted that the above proposition just says P-justified revisions are r-models of the revision specification that are minimally different from the original database. It does not say that r-models of the revision specification that are minimally different from the original database are P-justified revisions. In Example 1 both {a} and {b} are r-models of P_{1} minimally different from D_{I} but only {a} is a P_{1}-justified revision. This is similar to the logic program a ← not b which has two minimal models {a} and {b}, but has the only stable model {a}.

Translating Revision specifications to Extended Logic Programs

In this section we translate revision specifications to extended logic programs and show that the answer sets of the translated program correspond to the Previsions.

The extended logic program Π(P ∪ D_{I}) where P is the revision specification and D_{I} is the initial knowledge base, uses variables of three sorts: situation variables s, s′, …, fluent variables f, f′, …, and revision^{3} variables r, r′, . . ..

The program Π(P ∪ D_{I}) consists of the translations of the individual revision rules and the initial knowledge base in P and certain other rules. We now present the translation Π(P ∪ D_{I}) where s is the situation corresponding to the initial knowledge base D_{I}, r correspond to the revision dictated by the revision specification P and res(r, s) is the situation corresponding to the knowledge base obtained by revising the initial knowledge base with the revision specification P.

Algorithm 1 [Translating Revision Specifications – with CWA about the initial database]

1. Initial Database If p is proposition in the initial database then Π(P ∪D_{I}) contains

(1.1) holds(p, s)

and the rule

(1.2) ¬holds(F, s) ← not holds(F, s) which encodes the CWA about the initial database.

2. Inertia Rule

(2.1) holds(F, res(r, s)) ← holds(F, s), not ab(F, r, s)

This rule is motivated by the minimality consideration that only changes that happens to the initial knowledge base are the ones dictated by the revision specification.

3. Translating the revision rules

(a) Each revision rule of the type (1)

is translated to the rule

(3.a.1) holds(p, res(r, s)) ← holds(q_{1}, res(r, s)), …, holds(q_{m}, res(r, s)), ¬holds(s_{1}, res(r, s)), …, ¬holds(s_{n}, res(r, s))

(b) Each revision rule of the type (2)

out(p) ← in(q_{1}), …, in(q_{m}), out(s_{1}), …, out(s_{n})

is translated to the rules:

(3.b.1) ¬holds(p, res(r, s)) ←

holds(q_{1}, res(r, s)), …, holds(q_{m}, res(r, s)),
¬holds(s_{1}, res(r, s)), …, ¬holds(s_{n}, res(r, s))

(3.b.2) ab(p, a, s) ←

holds(q_{1}, res(r, s)), …, holds(q_{m}, res(r, s)),
¬holds(s_{1}, res(r, s)), …, ¬holds(s_{n}, res(r, s))

Since the inertia rule (2.1) is only for the positive facts we do not need a rule defining abnormality corresponding to (3.a.1), but we do need such a rule corresponding to (3.b.1) to block the inertia rule and avoid inconsistency.

4. Completing the revised database

To encode the CWA w.r.t. the revised database Π(P ∪ D_{I}) contains the rule

(4.1) ¬holds(F, res(r, s)) ← not holds(F, res(r, s)) □ Example 2 Consider D_{I} and P_{2} from Example 1. the translation Π(P_{2} ∪ D_{I}) consists of the following rules:

\begin{matrix}holds(a, s) \\ holds(b, s) \\ ¬holds(b, res(r_{1}, s)) ← holds(a, res(r_{1}, s)) \\ ab(b, r_{1}, s) ← holds(a, res(r_{1}, s)) \\ ¬holds(a, res(r_{1}, s)) ← holds(b, res(r_{1}, s)) \\ ab(a, r_{1}, s) ← holds(b, res(r_{1}, s) \\ 1.2 \\ 2.1 \\ 4.1 \end{matrix} \} Π(P_{2}∪D_{I})

□

Theorem 1 Let P be a revision specification corresponding to a revision operator r and D_{I} be an initial database. Let Π(P ∪D_{I}) be the translation to extended logic programs.

(i) D_{I} ⟶^{P} D_{R} implies there exists a consistent answer set A of Π(P ∪ D_{I}) such that

(a) f ∈ D_{R} iff holds(f, res(r, s)) ∈ A.

(b) f ∉ D_{R} iff ¬holds(f, res(r, s)) ∈ A.

(ii) If A is a consistent answer set of Π(P ∪ D_{I}) then

D_{I} ⟶^{P} D_{R} , where D_{R} = {f : holds(f, res(r, s)) ∈

A} Proof:(sketch)

3The revision variables correspond to the action variables in situation calculus and in the translation of the language A to extended logic programs in (GL92)

(i) Let A = A_{1} ∪ A_{2} ∪ A_{3} ∪ A_{4} ∪ A_{5} ∪ A_{6} where,

A_{1} = {holds(f, res(r, s)) : f ∈ D_{I} \ O}

A_{2} = {holds(f, res(r, s)) : f ∈ I}

A_{3} = {¬holds(f, res(r, s)) : f ∉ D_{R}}

A_{4} = {holds(f, s) : f ∈ D_{I}}

A_{5} = {¬holds(f, s) : f ∉ D_{I}}∪

A_{6} = {ab(f, r, s) : f ∈ O}

It is easy to see that A is consistent. To show A as an answer set of Π(P ∪D_{I}) we observe that A_{1}, A_{3}, A_{4}, A_{5} come from application of the rules (2.1), (4.1), (1.1) and (1.2) respectively and A_{2} and A_{6} come from combined application of the rules (3.a.1), (3.b.1) and (3.b.2).

Moreover, there is a one to one correspondence between P_{D_{R}} and R^{A} where R consists of the rules from (3.a.1) and (3.b.1). □ Example 3 The answer sets of Π(P_{2} ∪ D_{I}) are

{holds(a, s), holds(b, s), holds(a, res(r_{1}, s)), ¬holds(b, res(r_{1}, s))ab(b, r_{1}, s)} and

{holds(a, s), holds(b, s), holds(b, res(r_{1}, s)), ¬holds(a, res(r_{1}, s))ab(a, r_{1}, s)} □

Rule based Revision of Incomplete

Knowledge Bases

The approach in the last section and in (MT94b) assumes that the initial knowledge base is complete. i.e. there is CWA about the initial knowledge base. In this section we define P-justified revision of possibly incomplete knowledge bases with respect to revision specifications. We believe that it is more intuitive and understandable to define the P-justified revision through a translation to an extended logic program than directly in the style given in the previous section and hence do the former in this section.

Unless otherwise specified from now on by a knowledge base we mean a possibly incomplete knowledge base which is a subset of U ∪ ¬U. As in the last section we translate the initial knowledge base and the revision specification to an extended logic program so as to compute the revised knowledge bases. As in the previous section, our translation uses situation calculus notations. The translation of an initial knowledge base D_{I} and the revision specification P denoted by Π_{inc}(P ∪ D_{I}) consists of the following: Algorithm 2 [Translating Revision Specs – without CWA about the initial database]

1. Initial Database If p is proposition in the initial knowledge base Π_{inc}(P ∪ D_{I}) contains

(1.1) holds(p, s)

If ¬q is proposition in the initial knowledge base Π_{inc}(P ∪ D_{I}) contains

(1.2) ¬holds(q, s)

2. Inertia Rules

(2.1) holds(F, res(r, s)) ← holds(F, s), not ab(F, r, s)

(2.2)

¬holds(F, res(r, s)) ← ¬holds(F, s), not ab(F′, r, s)

Since our initial knowledge base may be incomplete we need two different inertia rules.

3. Translating the revision rules

(a) Each revision rule of the type (1) is translated to the rules (3.a.1) and

(3.a.2)  ab(p′, r, s)  ←

holds(q_{1}, res(r, s)), …, holds(q_{m}, res(r, s)), ¬holds(s_{1}, res(r, s)), …, ¬holds(s_{n}, res(r, s))

(b) Each revision rule of the type (2) is translated to the rules (3.b.1) and (3.b.2). □

Definition 4 Let P be a revision specification and D_{I} be an initial knowledge base. If A is a consistent answer set of Π_{inc}(P ∪ D_{I}) then the set D_{R} = {f : holds(f, res(r, s)) ∈ A} ∪ {¬f : ¬holds(f, res(r, s)) ∈ A} is said to be a P-justified revision of D_{I}.

A knowledge base B is a r-i-model of (satisfies) an r-literal in(p) (out(p) respectively) if p ∈ B (¬p ∈ B, respectively). B is a r-i-model of the body of a rule if it satisfies each r-literal of the body. B is a r-i-model of a rule C if the following conditions hold: whenever B satisfies the body of C, then B satisfies the head of C. B is a r-i-model of a revision specification P if B satisfies each rule in P.

Proposition 4 Let P be a revision specification and D_{I} be a knowledge base. If D_{R} is a P -justified revision of D_{I}, then D_{R}÷D_{I} is minimal in the family {D÷D_{I} : D is a r-i-model of P }, where ÷ denotes the symmetric difference. i.e. A ÷ B = (A \ B) ∪ (B \ A). □

Specifying revisions that depend on the previous state

The revision specifications defined in the previous sections can only express the relationship between the elements of the revised knowledge base. Although it uses the implicit assumption that there is minimal change to the initial database, it can not explicitly state any relation between the initial knowledge bases and the revised knowledge base. For example if we would like to say that “all assistant professors with 20 journal papers are to be promoted to associate professors” we can not express it using revision specifications.

In this section we extend revision specifications to allow us to specify such update descriptions.

An extended revision rule can be of the following two forms: in(p) ← in(q_{1}), …, in(q_{m}), out(s_{1}), …, out(s_{n}),

was in(t_{1}), …, was in(t_{k}), was out(u_{1}), …, was out(u_{l})

(3)

out(p) ← in(q_{1}), …, in(q_{m}), out(s_{1}), …, out(s_{n}), was in(t_{1}), …, was in(t_{k}), was out(u_{1}), …, was out(u_{l})

(4)

where p, q_{i}’s, s_{j}’s, t_{i}’s and u_{j}’s are atoms.

An extended revision specification is a collection of extended revision rules. The statement “all assistant professors with 20 journal papers are to be promoted to associate professors” can be expressed using the following extended revision specification:

in(associate(X)) ← was in(assistant(X)), was in(haspaper(X, 20))

out(assistant(X)) ← was in(assistant(X)), was in(haspaper(X, 20)) Similar to the last section we define revisions with respect to an extended revision specification using extended logic programs and use situation calculus notation.

Algorithm 3 [Translating Extended Revision Specifications] Our translation will be same as in Algorithm 2 except the translation of the revision rules. The extended revision rules are translated as follows:

(a) Each extended revision rule of the type (3)

is translated to the rules

(3.a.1’) holds(p, res(r, s)) ← holds(q_{1}, res(r, s)), …, holds(q_{m}, res(r, s)), ¬holds(s_{1}, res(r, s)), …, ¬holds(s_{n}, res(r, s)), holds(t_{1}, s), …, holds(t_{k}, s), ¬holds(u_{1}, s), …, ¬holds(u_{l}, s)

(3.a.2’) ab(p′, r, s) ← holds(q_{1}, res(r, s)), …, holds(q_{m}, res(r, s)), ¬holds(s_{1}, res(r, s)), …, ¬holds(s_{n}, res(r, s)), not ¬holds(t_{1}, s), …, not ¬holds(t_{k}, s), not holds(u_{1}, s), …, not holds(u_{l}, s)

(b) Each extended revision rule of the type (4)

is translated to the rules

(3.b.1’) ¬holds(p, res(r, s)) ← holds(q_{1}, res(r, s)), …, holds(q_{m}, res(r, s)), ¬holds(s_{1}, res(r, s)), …, ¬holds(s_{n}, res(r, s)), holds(t_{1}, s), …, holds(t_{k}, s), ¬holds(u_{1}, s), …, ¬holds(u_{l}, s)

(3.b.2’) ab(p, a, s) ← holds(q_{1}, res(r, s)), …, holds(q_{m}, res(r, s)), ¬holds(s_{1}, res(r, s)), …, ¬holds(s_{n}, res(r, s)),

not ¬holds(t_{1}, s), …, not ¬holds(t_{k}, s),

not holds(u_{1}, s), …, not holds(u_{l}, s) □

The use of not ¬holds(t_{1}, s) and not holds(u_{l}, s) instead of holds(t_{1}, s) and ¬holds(u_{l}, s) in (3.a.2’) and (3.b.2’) is to be cautious when applying the inertia rules (GL92). For example if D_{I} = {assistant(john)} and we have the extended revision specification

out(assistant(X)) ← was in(haspaper(X, 20))

for the update called “promote” we would not like to have assistant(john) in D_{promote} because we are not sure if haspaper(john, 20) is false in D_{I}. We would rather have D_{promote} contain neither assistant(john) nor ¬assistant(john). Definition 5 Let P be an extended revision specification and D_{I} be an initial knowledge base. If A is a consistent answer set of Π_{inc}(P ∪ D_{I}) then the set D_{R} = {f : holds(f, res(r, s)) ∈ A} ∪ {¬f : ¬holds(f, res(r, s)) ∈ A} is said to be a P-justified revision of D_{I}.

Relationship with standard update

operators

In this section we discuss how rule based revision relates to standard revision and update operators.

When we consider a knowledge base to be a set of propositional facts (with CWA) it is easy to see that the concepts of update and revision (KM92) coincide. For such knowledge bases the following proposition relates the standard definition of updates with P-justified revision. Definition 6 For any revision rule S, f_{S} is the propositional formula obtained by replacing each out(a) in S by ¬a and each in(a) in S by a and treating ← as the implication. For any revision specification P, F_{P} is the propositional formula obtained by the conjunction of all the f_{S}’s, for all S’s in P. □ Proposition 5 Let P be a revision specification and D_{I} be a knowledge base.

D_{R} is a model (in the propositional sense) of D_{I} o F_{P} where o is the revision operator (KM92) iff D_{R} ÷ D_{I} is minimal in the family {D ÷ D_{I} : D is a r-model of P } □

When we consider a knowledge base to be a set of literals then a knowledge base may have several models and update and revision (KM92) may be different depending upon the definition of closeness between models and between theories (knowledge bases). Proposition 6 Let P be a revision specification and D_{I} be a knowledge base.

D_{R} is a model of D_{I} o F_{P} where o is the revision operator (KM92) iff D_{R} ÷ D_{I} is minimal in the family {D ÷ D_{I} : D is a r-i-model of P } □

From the above propositions it is clear that the Pjustified revisions computed using the translations suggested in this paper do not compute all the models of the standard revisions (KM92). In Example 1 both {a} and {b} are r-models of P_{1} minimally different from D_{I} and are also be the models of D_{I} o F_{P_{1}} but only {a} is a P_{1}-justified revision.

One possible way to obtain all the models would be to translate the revision specification P_{1} to a first-order theory instead of an extended logic program and minimize the abnormality using circumscription. That has been the approach of Reiter (Rei92) to specify database evolution. On the other hand in certain cases we might need revisions to be specified as rules instead of a formula and also in certain cases extended logic programs may be preferred over circumscription as a computing formalism.

Relation with A and its extensions

A is a specification language for representing effects of actions suggested by Gelfond and Lifschitz in (GL92). The e-propositions in A which are of the form

A causes F if P_{1}, …, P_{n}

corresponds to the extended revision rule

in(F) ← was in(P_{1}), …, was in(P_{n})

when the domain consists of only action A and F, P_{1}, …, P_{n} are positive atoms.

Revision specifications of the form (1) and (2) are similar to constraints in AR (KL94), an extension of A. Although the constraints in AR allow for formulas we believe if rules of the form (1) and (2) are used instead it may be possible to state when a domain description in the language of AR will have models with unique transition functions.

Conclusion

In this paper we considered the language of revision specifications for specifying revision conditions as rules. We presented a translation to extended logic programs that uses situation calculus notation so as to compute the revised knowledge base given a knowledge base consisting of atoms and a revision specification. We then considered knowledge bases that may be incomplete and presented a translation for computing revision for such a case. We also extended the language of revision specifications to allow rules explicitly relating the initial and the revised database. Finally we compared our approach with the standard revise and update operators and with the specification language A.

We believe a more thorough study is necessary to further relate extended revision specifications to standard update operators and also to further relate with languages for reasoning about actions. In particular the impact of using rule based constraints instead of constraint formulas in AR needs to be studied.

Acknowledgement

I would like to thank Prof. Wiktor Marek whose talk on “Revision Programs” in UT El Paso in Dec 93 triggered the ideas expanded on this paper. I would also like to thank the anonymous referees for their valuable comments.

References

M. Gelfond and V. Lifschitz. Classical negation in logic programs and disjunctive databases. New Generation Computing, pages 365–387, 1991. M. Gelfond and V. Lifschitz. Representing actions in extended logic programs. In Joint International Conference and Symposium on Logic Programming., pages 559–573, 1992. P. Gardenfors and D. Makinson. Revisions in knowledge systems using epistemic entrenchment. In Proc. 2nd international conference on theoretical aspects of reasoning about knowledge, pages 1413–1419, 1988. G. Kartha and V. Lifschitz. Actions with indirect effects. To appear in KR 94, 1994. H. Katsuno and A. Mendelzon. A unified view of propositional knowledge base updates. In Proc. of IJCAI-89, pages 1413–1419, 1989. H. Katsuno and A. Mendelzon. On the difference between updating a knowledge base and revising it. In Proc. of KR 92, pages 387–394, 1992. R. Kowalski. Database Updates in the Event Calculus. In The Journal of Logic Programming, 12 (1992), 121-146 W. Marek and M. Truszczyński. Revision programming. manuscript, 1994. W. Marek and M. Truszczyński. Revision specifications by means of programs. manuscript, 1994. R. Reiter. Formalizing database evolution in the situation calculus. In ICOT, editor, Proc. of the International Conference on Fifth Generation Computer Systems, pages 600–609, 1992.