Towards Generalized Rule-based Updates

1 Introduction

Marek and Truszczriski 's recent work on rule-based up­ dates [Marek and Truszczriski , 1994] provided a new framework for updates in more general knowledge do­ mains. Generally, they addressed the following problem: given an initial knowledge base B , i.e. a set of ground atoms, and a set of update rules P with the forms 1 :

1 P was called a revision program in [Marek and Truszcznski, 1994] .

Norman Y. Foo

School of Computer Science and Engineering University of New South Wales NSW 2052, Australia

E-mail: norman@cse.unsw.edu.au

where A, B1 , .. ·, Bm , C1 , · · ·, Cn are ground .atoms, what is the resulting knowledge base B' after updating B by P? The intuitive meaning of ( 1) (or (2)) is that if B1 , · · ·, Bm are in the knowledge base, and C1 , · · ·, Cn are not in the knowledge base, then A should be (or not be) in the knowledge base.

For example, given a knowledge base B = {A, D} and a set of update rules P = {in(C) +- in(A) ,out(B) , out( D) +- in( C), out(B)}, where A, B , C and D ~re ground atoms, then after. updating B by P , accordmg to Marek and Truszczriski's approach, we would expect to have a resulting knowledge base B' ={A, C}.

Relationships between rule-based updates and logic programming have been studied by Baral [Baral , 1994] and Przymusinski and Turner [Przymusinski and Turner , 1995]. In particular, they showed that Marek and Truszczriski's formal procedure of specifying B' can be reduced to a computation of the answer set of a cor­ responding extended logic program (we will review this procedure in next section). However , there are two limi­ tations with Marek and Truszczriski's rule-based update: the initial knowledge base should be complete, i.e. any ground atom not in the initial knowledge base is treated as its negation ; and update rules only contain classical negations. For instance, following ideas of [Baral , 1994] and [Przymusinski and Turner, 1995], rules (1) and (2) are translated into the following inference rules respec­ tively in the corresponding extended logic program:

In this paper, we consider a simple generalization of rule-based updates wher~> a knowledge base can be in­ complete, eg. a set of ground literals, and update rules have the following form:

where each L; (0:::; i:::; n) is a literal , and not represents negation as failure (or called weak negation) . As a literal can be a negative atom, the above rule actually may contain two types of negations, i.e. classical and weak negations. The intuitive semantics of this rule can be interpreted as follows : if facts L1 , · · ·, Ln are true in the knowledge base, and there are no explicit representations saying that facts Lm+l , · · ·, Ln are true in the knowledge base, then fact La should be true in the knowledge base.

Such generalized rule-based update is important in many applications. For example, in a secure computer system, a formal specification of users' access rights is usually required, and the access policy of the system can be represented by a knowledge base. An update of this knowledge base must be performed whenever new ac­ cess control rules are applied to the system. Generally, two types of negations are needed to specify access con­ t_rol rules . Let B = {Member( A, G) , M ember(B , G) , Access(A, F), ...,Access(B , F)} represent the current ac­ cess policy of the system, where Member( A , G) and Member( B, G) mean that users A and B are members of group G, and Access( A, F) and ...,Access(B, F) indicate that user A can access file F and user B cannot access file F respectively. Suppose that new users C and D are added into group G and a global access control rule is now applied to each member of group G:

This rule actually says that any user belonging to group G can access file F unless it is explicitly stated that the user is iwt allowed to access F . Updating B by P = {Member(C,G) +- , Member(D,G) +- , Access(x , F) +- M ember(x , G) ,not --,Access(x , F)} , from our intuition , we would expect that Access(C, F) and Access(D, F) are obtained, while facts Access( A , F) and -,Access( B , F) remain persistent .

As we will see next , previous rule-based update ap­ proaches are not suitable to deal with this generalized rule-based update properly. To overcome the difficulty, we argue that necessary preferences between update rules and inertia rules with respect to the update must be taken into account . From this motivation, we propose prioritized logic programs (PLPs) by adding preferences into extended logic programs. Formal semantics of PLPs is provided in terms of the answer set semantics of ex­ tended logic programs. We then show that the procedure of generalized rule-based update can be formalized in the framework of PLPs. The minimal change property of the update is also investigated.

2 A Motivating Example

In this section we first review the concept of extended logic programs proposed by Gelfond and Lifschitz [Gel­ fond and Lifschitz, 1991] and then discuss an example of generalized rule-based update in the framework of ex­ tended logic programs.

2.1 Preliminaries

A language C of extended logic programs is determined by its object constants, function constants and predi­ cates constants. Terms are built as in the corresponding first order language; atoms have the form P(t1 , ···, in) , where i; (1 ::; i::; n) is a term and Pis a predicate sym­ bol of arity n; a literal is either an atom P(t1 , · · ·, tn) or a negative atom --,P(t 1 , · · · , tn) · A rule is an expression of the form:

where each Li (0 ::; i ::; n) is a literal. La is called the head of the rule, while L1 , · · ·, Lm , not Lm+l , · · ·, not Ln is called the body of the rule. Obviously, the body of a rule could be empty. A term, atom, literal , or rule is ground if no variable occurs in it. An extended logic program II is a collection of rules. The following is an example of extended logic program ITo:

To evaluate a extended logic program, Gelfond and Lifschitz proposed the answer set semantics for extended logic programs. For simplicity, we treat a rule r in II with variables as the set of all ground instances of r formed from the set of ground literals of the language of II . In the rest of paper, we will not explicitly declare this assumption whenever there is no ambiguity in our discussion.

Let II be an extended logic program not containing not and Lit the set of all ground literals in the language of II . The answer set of II, denoted as Ans(IT) , is the smallest subset S of Lit such that

• (i) for any rule La +- L1 , · · ·, Lm from II , if L1, · · ·, Lm E S, then La E S;
• (ii) if S contains a pair of complementary literals, then S =Lit.

Now let II be an extended logic program. For any subset S of Lit , let II 5 be the logic program obtained from II by deleting

• (i) each rule that has a formula not L in its body with L E S, and
• (ii) all formulas of the form not L in the bodies of the remaining rules.

We define that Sis ap. answer set of II, denoted Ans(IT), iff Sis an answer set ofii 5 , i.e. S = Ans(IT 5 ).

Consider an extended logic program II1 obtained from II0 by adding other two rules in II0 : II1 = ITo U { ..... student(Peter) +- , Age(Peter, > 25) +-}.

It is not difficult to see that II1 has a unique an­ swer set set: {·Student(Peter) , Age(Peter, > 25) , Employed( Peter)} .

2.2 An Example

As we mentioned earlier , in previous formulations a spec­ ification of rule-based update can be represented by an extended logic program [Baral , 1994; Przymusinski and Turner, 1995). By illustrating a simple example here, we will show that these methods are not suitable for speci­ fying generalized rule-based updates .

Example 1 Suppose B = {-.A, B , C} is a knowledge base, and P = {·B f- not B , A f- C} is a set of up­ date rules. Consider an update of B by P . Obviously, fact ·A should change to A by applying the second rule of P. Fact B , on the other hand, seems persistent be­ cause B is true in the initial knowledge base, and -.B can only be derived from the first rule of P if fact B is absent from the current knowledge base. Therefore, from our intuition, the resulting knowledge base should be {A, B, C} .

Now we follow the principle of Baral and Przymusin­ ski and Turner's methods [Baral , 1994; Przymusinski and Turner, 1995) to specify the above update proce­ dure within an extended logic program 2 . Firstly, we need to extend the language of our domain by adding new propositional letters with the form N ew-L if L is a propositional letter in the originallanguage 3 . In this ex­ ample, the extended language will include propositional letters A , B , C , New-A , New-Band New-C. Then an extended logic program II(B, P) is formed by the follow­ ing rules:

Initial knowledge rules: -.A f- , B f- , c f- , Inertia rules: New-A f- A ,not -.New-A, New-B f- B,not ·New-B, New-C f- C ,not -.New-C, ·N ew-A f- -.A, not New-A, ·New-B f- -.B,not New-B, ·New-C f- ·C,not New-C , Update rules: ·New-B f- not New-B , New-A f- New-C.

Generally speaking, an answer set of program II(B, P) represents a possible resulting knowledge base after up­ dating B by P , where literal New-Lin the answer set denotes the persistence of literal L if L E B , or a change of L if ·L E B or L tf. B with respect to this update.

2 The formalism used here, of course, is different from theirs.

3 For simplicity, here we restrict the language to be propositional.

It is easy to see that the above II(B, P) has two answer sets: in one N ew-B is true where in the other N ew-B is false. Obviously this solution is not consistent with our previous observation. ·

Observing program II(B, P) , it is not difficult to see that a conflict occurs between inertia rule New-B f- B , not -.New-Band update rule ·New-B f- not New-B , that is, applying New-B f- B , not ·N ew-B will defeat -.New-B f- not New-B , and vice versa. This conflict leads II(B, P) to have two different answer sets with an indefiniteness of New-B . ·

On the other hand, it seems that the inertia rule New-B f- B , not ·New-B should override the update rule ·N ew-B f- not N ew-B during the evaluation of II(B, P) in order to obtain the desired solution. But this preference information cannot be expressed in Gelfond and Lifschitz 's extended logic programs.

From the above discussion, we argue that to represent such generalized rule-based update properly, necessary preferences between inertia rules and update rules have to be taken into account during the evaluation of the up­ date. We approach this problem from a general ground: we will first propose prioritized logic programs where preferences between rules can be explicitly expressed, and then formalize the generalized rule-based update in the framework of prioritized logic programs.

3 Prioritized Logic Programs (PLPs)

In this section we propose prioritized logic programs (PLPs) which extend Gelfond and Lifschitz's extended logic programs [Gelfond and Lifschitz , 1991) by adding preference information into programs. We first describe the syntax of PLPs and then provide an answer set se­ mantics for PLPs.

· 3.1 Syntax

The language ,eP of PLPs is a language £ of extended logic programs just with the following augments:

• Names: N, N1, N2, · · ·.
• A strict partial ordering (i.e. antireflexive, antisymmetric and transitive) < on names.
• A naming function N , which maps a rule to a name.

Terms, atoms, literals and rules in PLPs are defined as the same in extended logic programs. For the naming function N , we require that for any rules r and r' in a PLP (see the followi~g definition) , N(r) = N(r') iff r and r' indicate the same rule.

A prioritized logic program (PLP) P is a triplet (II ,N , <) , where II is an extended logic program, N is a naming function mapping each rule in II to a name, and

< is a relation representing all strict partial orderings on names.

The following is an example of prioritized extended logic program.

'P1 = ({P f- not Q, not R, Q f- not P , R f- not P}, {N(P f- not Q, not R) = N1 , .N(Q f- not P) = N2 , N(R t- not P) = N3}, {N1 < N2 , N2 < N3}). To simplify our presentation, we usually represent P1 as the following form:

P1 :

N1 : P f- not Q, not R ,

N2 : Q f- not P ,

N3 : R f- not P ,

N1 < N2,N2 < N3.

We also use notations Pl(II) , Pl(.N) , and Pl( <) to de­ note the sets of rules , naming function 's values and <­ relation of P 1 respectively.

Consider the following program:

P2 :

N1 : P f- not Q, not R ,

N2 : Q f- not P ,

N3: R t- not P ,

N1 < N2,N2 < N3,N1 < N3 .

Obviously, the only difference between P 1 and P 2 is that there is one more relation N1 < N3 in P2 . As we men­ tioned earlier, < is a strict partial ordering (i .e., antire­ flexive, antisymmetric and transitive) , we would expect that P1 and P2 are identical in some sense. Furthermore, if we rename rules in P 2 as follows ,

P'2:

N{ : P f- not Q, not R ,

N2 : Q f- not P ,

N~ : R f- not P ,

N{ < N2,N~ < N~,N{ <N~,

'P'2 would be also identical to P 2 and hence to P1 too from our intuition. To make this precise, we first intro­ duce <-closure as follows.

Definition 1 Given a program P = (II ,.N, <) .

'P(<+) is the <-closure ofP iffP(<+) is the smallest set containing P( <) and closed under transitivity.

We also need to define a renaming function as follows. A renaming function Rn maps a PLP P = (II, .N, <) to another PLP P', i.e. Rn(P) = P' = (II',.N', <'), such that (i) P(II) = P'(II'); (ii) for each rule r E P(II) 4 , N(r) = N E P(.N) iff .N'(r) = N' E P'(.N') (N and N' are not necessarily different) ; (iii) for any rules r 1 and r2 in P(II) , .N(ri) = N1 , .N(r2) = N2 E P(.N) , and N1 < N2 E P( <) iff .N'(ri) = N{, .N'(r2) = N2 E P'(.N'), and N{ < N2 E P' ( <'). It is easy to see that applying a renaming function to a PLP will only change the names of rules in the PLP.

4 0f course, r is also in P'(II').

Two prioritized extended logic programs P1 and P2 are identical iff there exists a renaming function Rn, mapping P2 to P' 2 such that P1 (II) = P' 2 (II'), P1 (.N) = P'2(.N'), and PI(<+)= P'2(<'+).

We have defined that a prioritized extended logic pro­ gram is an extended logic program by associating with a partial ordering < to it. Intuitively such ordering repre­ sents a preference of applying rules during the evaluation of a query of the program. In particular, if in a program P , relation .N(r) < .N(r') holds, rule r would be pre­ ferred to apply over rule r' during the evaluation of P (i.e. ruler is more preferred than rule r'). Consider the following classical example represented in our formalism:

P3:

N1 : Fly(x) f- Bird(x) , not ·Fly(x),

N2 : ·Fly(x) f- Penguin(x) , not Fly(x) ,

N3 : Bird(Tweety) f- ,

N4 : Penguin(Tweety) f- ,

N2 < N1.

Obviously, rules N1 and N2 conflict with each other as their heads are complementary literals 5 , and applying N1 will defeat N2 and vice versa. However, as N2 < N1 , we would expect that rule N2 is preferred to apply first and then defeat rule N1 after applying N2 so that the desired solution ·Fly(Tweety) could be derived.

3.2 Answer Sets for PLPs

Now we are ready to provide the semantics of PLPs. The semantics of PLPs is defined in terms of the answer set semantics of extended logic programs described earlier.

In program P3 , we have seen that rules N1 and N2 conflict with each other. Since N2 < N1 , we try to solve the conflict by applying N2 first and defeating N1. How­ ever, in some programs, even if one rule is more preferred than the other, these two rules may not affect each other at all during the evaluation of the program. In this case, the preference relation between these two rules does not play any role in the evaluation and should be simply ignored. This is illustrated by the following program:

Although heads of N1 and N2 are complementary liter­ als , applying N1 will not affect the applicability of N2 and vice versa. Hence N1 < N2 should not be taken into account during the evaluation of P 4 . The following definition provides a formal description for this intuition.

5 Precisely, N2 is the name of rule -,Fly(x) +-- Penguin(x), not Fly(x) . Whenever there is no confusion in the context, we just simply refer a rule by its name.

Definition 2 Let II be an extended logic program and r a rule with the form La f- L1 , · · ·, Lm , not Lm+1 , · · ·, not Ln (r does not necessarily belong to IT) . Rule r is defeated by II iff for any answer set Ans(IT) of IT, there exists some L; E Ans(IT) , where m + 1 < i < n .

Now our idea of evaluating a PLP is described as fol­ lows. Let P = (IT,N, <). If there are two rules rand r' in P(II) and N(r) < N(r'), r' will be ignored in the evaluation of P, only if keeping r in P(II) and deleting r' from P(II) will result in a defeat of r', i.e. r' is de­ feated by P(II) - { r'}. By eliminating all such potential rules from P(IT) , Pis eventually reduced to an extended logic program in which the partial ordering < has been removed. Our evaluation for P is then based on this extended logic program.

Let us consider program P 3 once again. Since N2 < N1 and N1 is defeated by P 3 - {Nl} (i.e. the unique answer set of P 3 - {Nl} is {Bird(Tweety) , Penguin(Tweety), ·Fly(Tweety)}), rule N1 should be ignored during the evaluation of P 3 . For program P4 , on the other hand , although N1 < N2 , relation N1 < N2 will not affect the solution of evaluating P4 as P4(Il) - {N2} does not defeat N2 (i .e. the unique answer set of P 4(rl)- {N2} is {P} ).

Definition 3 Let P = (II, N, <) be a prioritized ex­ tended logic progrom. We define a reduct of P with re­ spect to <, denoted asp<, as follows.

In above definition , clearly p< is an extended logic program obtained from II by eliminating some rules from II . In particular, if N ( r) < N ( r') and II - { r'} defeats r', rule r' is eliminated from II. This procedure is contin­ ued until a fixed point is reached . Note that due to the transitivity of<, we need to consider each N(r) < N(r') in the <-closure of P . It is also not difficult to note that the reduct of a PLP may not be unique generally.

Example 2 Using Definition 1 and 3, it is not difficult to conclude that P 1, P 3 and P4 have unique reducts as follows respectively:

·

Pi = {P f- not Q} , P~ = {P f- not Q, not R} , Pi = { ·Fly(x ) f- Penguin(x) , not Fly(x), Bird(Tweety) +-- , Penguin(Tweety) f-} , Pi = P4(II).

Now it is quite straightforward to define the answer set for a prioritized extended logic program.

Definition 4 Let P = (IT ,N , <) be a PLP and Lit the set of all ground literols in the language of P . For any subset S of Lit, S is an answer set of P , denoted as AnsP(P) , iff S = Ans(P<) .

Example 3 Immediately from Definition 4 and Exam­ ple 2, we have the following solutions:

which , respectively. are also consistent with our intu­ itions. ·

3.3 Basic Properties of PLPs

We now discuss some properties of PLPs. To simplify our presentation, let us introduce some useful notations. Let II and P be an extended logic program and a PLP respectively. We use AN S(IT) to denote the classes of answer sets of II. Suppose P = (II , N , <) is a PLP. From Definition 3, we can see that a reduct p< of P is generated from a sequence of extended logic pro­ grams: II = II0 ,II1,II2, · · ·. We use notation {II;} (i = 0, 1, 2, · · ·) to denote this sequence and call it a reduct chain of P . Then we can prove the following use­ ful solutions 6 .

Theorem 1 Let P = (II,N,<) be a PLP, and {II;} (i = 0, 1, 2, · · ) a reduct chain of P . Suppose each II; has answer set(s). Then for any i and j where i < j , ANS(ITj) ~ ANS(IT;).

Theorem 2 Let P = (II , N , <) be a PLP. Then a sub­ setS of Lit is an answer set ofP iff S is an answer set of each IT; for some reduct chain {II;} (i = 0, 1, 2, · · ) ofP, where each IT; has answer set(s) .

4 Generalized Rule-based Update

Consider a language .C of extended logic programs as described in section 2.1. We specify that a knowledge base B is a set of ground literals of .C and P is a set of rules of .C with form (3) that are called update rules . Note that we allow a knowledge base to be incomplete. That is, a literal not in a knowledge base is treated as unknown.

We will use a prioritized logic program to specify an update of B by P. For this purpose , we first need to extend language .C by the following way. We specify .C~ew to be a language of PLPs based on .C as described in section 3.1 with one more augment: For each predicate symbol P in .C, there is a corresponding predicate symbol N ew-P in .C~ew with the same arity of P .

6 All proofs of theorems presented in this paper were given in our manuscript [Zhang and Foo, 1997] .

To simplifying our presentation, in .C~ew we use no­ tation N ew-L to denote the corresponding literal L in C. For instance, if a literal Lin .Cis -.P(x). then nota­ tion New-L simply means -.New-P(x). We use Litnew to denote the set of all ground literals of .C~ew. Clearly, Litnew =Lit U {New-L I L E Lit} . Now we are ready to formalize our generalized rule-based update.

Definition 5 Let B, P , .C and .C~ew be defined as above. The specification of updating B by P is defined as a PLP of C~ew· denoted as Update(B, P) = (11(8, P) , N , <) , as follows :

1. 11( B, P) consists of followzng rules:

Initial knowledge rules : for each L in B. there is a rule L r- ;

Inertia rules: for each predicate symbol P inC,

there are two rules:

N ew-P(x) r- P(x), not -.N ew-P(x) 7 , and

-.N ew-P(x) r- -.P(x), not N ew-P(x) ,

Update rules : for each rule

LarLJ ,· ·· , Lm , notLm+I ····, notLn inP,

there is a rule

N ew-Lo r- N ew-L1 , · · ·, N ew-Lm.

not N ew-Lm+I , · · ·, not N ew-Ln ;

1. Naming function N assigns a unique name N for each rule in 11(8, P) ;
2. For any inertia rule with name N and update rule with name N', there is a partial ordering between N and N': N < N'.

Comparing Definition 5 with the update specification described in Example 1, we can see that the difference between these two approaches is that in our formulation preference relations between inertia and update rules are explicitly expressed. We specify inertia rules to be more preferred than update rules in. Update(B, P).

The intuitive idea behind this is that a preference or­ dering between an inertia rule and an update rule in Update(B, P) will affect the evaluation of Update(B, P) only if these two rules conflict with each other , eg. ap­ plying one rule causes the other inapplicable. On the other hand, a fact in the initial knowledge based B is always preferred to persist during an update whenever there is no violation of update rules 8 . Therefore, when conflicts occur between inertia and update rules , iner­ tia rules should override the corresponding update rules. Otherwise, the preference ordering does not play any role in the evaluation of Update(B, P). Also note that there will be at most 2k · l instances of relation < in Update(B, P) , where k is the number of predicate sym­ bols of .C and l is the number of update rules in P.

7 x might be a tuple of variables.

8 Note that an update rule in Update(B, P) is defeasible if it contains a weak negation not in the body.

Finally, on the basis of Definition 5, we can formally define a knowledge base B' resulting from updating B by P in a straightforward way.

Definition 6 Let B, P , .C and .C~ew be specified as be­ fore, and U pdate(B, P) the specification of updating B by P as defined in Definition 5. A set of ground literals of .C , B', is called a possible resulting knowledge base with respect to the update specification Update(B, P), iff B' satisfies the following conditions:

1. if Update(B, P) does not have an answer set, then B'=B;
2. if Update(B, P) has a consistent answer set, say Ansp ( U pdate(B, P)) , then
3. B' = {L I New-L E AnsP(Update(B, P))} ;
4. B' =Lit if Ansp(Update(B, P)) = Litnew ·

Example 4 Example 1 continued. Let B = {-.A, B, C} and P = {-.B r- not B , Ar-C} . From Definition 5, the specification of updating B by P , Update(B, P) , is as follows :

Initzal knowledge rules:

<:

NI : -..4 r- ,

N2 : Br- ,

N3 :Cr- ,

Inertia rules:

N4 : New-A r- A ,not -.New-A ,

N5 : New-B r- B ,not -.New-B,

N6 : New-C r- C ,not -.New-C,

N7 : -.New-A r- -.A,not New-A ,

N8 : -.New-B r- -.B ,not New-B ,

N9 : -.New-C r- -.C,not New-C ,

Update rules:

N1o : -.New-B r- not New-B,

N11 :New-A r- New-C ,

N4 < N10 , N5 < N1o , N6 < N10 ,

N1 < Nu, Ns < Nu , Ng < Nu .

Now from Definitions 3 and 4, it is not diffi­ cult to see that U pdate(B, P) has a unique answer set: {-.A, B,C,New-A,New-B,New-C}. Note that in Update(B, P) , only ordering N5 < N1o is used in U pdate(B, P)'s evaluation, while other orderings are use­ less (see Definition 3). Hence, from Definition 6, the only resulting knowledge base B' after updating B by P is: {A,B,C}·

Example 5 Let us consider the secure computer system domain described in section 1 again. Let

Consider the update of B by P. Ignoring the detail , using the approach presented above, we get a unique resulting knowledge base

·

5 Update and Minimal Change

In this section we investigate the minimal change prop­ erty for the generalized rule-based update described pre­ viously. Let B be a consistent knowledge base and r a rule with the form (3). B satisfies riff if facts L1 , · · ·, Lm are in B and fact Lm+l , · · ·, Ln are not in B, then fact La is in B. Let P be a set of rules with the form (3). B satisfies P if B satisfies each rule in P .

Let B and B' be two knowledge bases. We use Dif J(B, B') to denote the set of different ground atoms between B and B', i.e.

where notation ILl indicates the corresponding ground atom of ground literal L, and M in(B, P) to denote the set of all consistent knowledge bases satisfying P but with minimal differences from B, i.e.

Then we have the following result.

Theorem 3 Let B be a knowledge base, P a set of up­ date rules, and U pdate(B, P) the specification of updat­ ing B by P as defined in Definition 5. If B' is a consis­ tent resulting knowledge base with respect to the update specification U pdate(B, P) , then B' E M in(B, P) .

The above theorem guarantees that our generalized rule-based update satisfies the principle of minimal change. However, it should be noted that not every ele­ ment of M in(B, P) could be a resulting knowledge base of updating B by P. The following example illustrates the case.

Example 6 Let B ={A, B} and P ={-.ArB, --.B r not B}. Using our approach, updating B by P will give us a unique resulting knowledge base B' = {-.A, B} . However, it is not difficult to see that Min(B, P) also contains another element : B" ={A, --.B}. Although B" satisfies P and has minimal difference from B, it does not represent an intuitive solution of updating B by P according to our previous discussion. ·

6 Concluding Remarks

In this paper we considered generalized rule-based up­ dates in the framework of prioritized logic programs. We should mention that Marek and Truszczriski's rule-based update is embeddedable into our framework. For exam­ ple, if our update rules only contain classical negations , our formulation is reduced to Przymusinski and Turner's described in [Przymusinski and Turner, 1995].

Finally, we have noticed that the issue of logic pro­ grams with preferences has also been explored recently by some other researchers (eg. [Brewka, 1996]) . In fact , we can further extend our prioritized logic programs by associating with dynamic preference so that our priori­ tized logic programs can be used as a more general tool in broad areas of knowledge representation and reasoning. A detailed comparison between our PLPs and others' work and other applications of PLPs in reasoning about change is beyond the scope of this paper and was rep­ resented in our full version manuscript [Zhang and Foo, 1997].

Acknowledgements .

This research is supported in part by a grant from the Australian Research Council. We thank to Chitta Baral for many valuable comments on an earlier draft of this paper .