Syntactic Characterizations of Belief Change Operators

1 Introduction

In this paper, we provide syntactic characterizations and algorithms for a number of belief change operators proposed in the literature. We already characterized Winslett's 'possible models approach' (PMA) update op­ erators in [del Val, 1992b], where we explored in depth some of the operators in the PMA family, provided al­ gorithms to compute them and experimentally showed that they could be of practical value for (small) updates of quite large databases. In this paper , we show how other operators can be characterized in a. very similar way, and show how to design algorithms for comput.­ ing the result of applying these operators to disjunctive , negation and conjunctive normal form (DNF, NNF and CNF. respectively) databases. which return R dRtahR;;P in the same format .

The interest of these syntactic characterizations goes beyond, we believe, the usefulness of the algorithms that can be immediately derived from them. All the opera­ tors we discuss are based on some notion of minimal change, and the similarities among the various charac­ terizations we provide suggests that our techniques can be easily extended to other belief change operators bRsf"d on this not.ion that might be proposed in the future. as well as to variants of the operators discussed here (e.g. prioritized versions, as discussed in [del Val. 1992b; del Val, 1993]). Because of their formal nature and rel­ ative simplicity, the characterizations could also prove useful for the design of improved algorithms. facilitate proofs of their correctness, help identify syntactic re­ st.rict.ions with a positive impact on complexity, and help define useful notions of "approximate belief change" (see also [del Val , 1992a] on this last point).

Much AI work on belief change has taken as starting point the "AGM approach" to belief revision proposed by Alchourr6n, Giirdenfors and Makinson [Alchourr6n ef a/., 1985; Gardenfors, 1988] . Katsuno and Mendelzon

[1991a] have recently suggested, however, that at least two different belief change operations should be distin­ guished, ret>ision. and update. Loosely speaking, the for­ mer says that the beliefs may have been wrong and in need of revision, whereas the latter says that the be­ liefs were correct, but the world has in the meanwhile evolved and the belief.<> must be updated. Both types of belief change have been characterized by relation to some sets of properties or "postulates" (the AGM and the KM postulates, respectively). As shown by Katsuno and l\1endelzon [1991b; 1991a], most AGM-like revision operators are based on a "global" order of preferences Rssociated to each database, while all (KM) update op­ erators are based on a "pointwise" order in which each model of the database has an associated ordering. As we will see, this distinction is very directly reflected in our characterizations. In fact, except in the case of DNF databa.<;es, it has a direct impact on the complexity of the algorithms we present, an impact which is directly re­ lated to the fact. that in revision some models of the orig­ inal databa.<oe are pruned and fail to "generate" any mod­ els of t.he revised database. This added complexity can however be substantially reduced for Horn databases.

The structure of this paper is as follows. The first three sections of the paper are devoted to update oper­ ators, by which we mean operators satisfying the KM postulates; specifically, we consider Winslett's [1988] set inclusion based operator and Forbus' [1989] cardinality based operator. The following sections discuss revision operators, by which we mean operators satisfying at least the ''basic" AGM postulates for revision (that is, (R1)­ (R4) in the notation of[Katsuno and Mendelzon, 1991a]; in particular, they all have the property that 1/J revised with Jt equals V' 1\ J.' whenever this formula is satisfiable); specifically, we consider Dalal's [1988a] cardinality based approach and Satoh 's [1988] set inclusion based proposal, as well as the proposals of [Weber, 1986] and lBorgida, Hl85] . Related work is discussed in the concluding sec­ tion .

In the rest of the paper, we assume a propositional lan­ guage with a finite set P of symbols. Update operators are represented by<>, and revision operators with<>, both possibly subscripted. 1/.J always denotes the database and J1 the update formula, both of which are assumed to be sRtisfiable. If V' is in CNF or NNF, it consists of clauses or t.op level conjuncts c;, Cj, . . .. DNF( 1/J) represents some formula in disjunctive normal form equivalent to rl· and consisting of the conjunctions of literals V'i, 1/.'i, ... We require that all these conjunctions be satisfiable. J.t is assumed to be in DNF, and its disjuncts will be denoted by p;, J.ti, ... Literals are represented by l, l;, li, .... With a slight abuse of notation, if there is no ambiguity a con­ junction of literals will be treated interchangeably as a set of literals, and a DNF (CNF, NNF) formula as a set of disjuncts ( conjuncts). We also use, for any formula or set of formulas 1/J, Prop( 1/J) for the set of propositional symbols occurring in 1/J, and Mod(tjJ) for the models of 1/J. Finally, for any set S and binary relation ~. we use Min(S, ~)for the set of elements of S minimal under ~·

The following definitions will also be useful. De­ fine the "difference" between two models I and .] as Diil{I,J) = {p E P I I ~ p iff J ~ -.p}. the set of letters on which they differ, and the "distance" be­ tween two models as the cardinality of their difference, i.e. Dist(I,M) = IDiil{I,M)I. Similarly, define the dif­ ference between two conjunctions of literals '1/J; a.nd IIi as the set of literals in t/J; whose negation is in J.lj, i. c. Diil{ t/J; ,J.ti) = { l E t/J; I -./ E pj}, and define their dis­ tance analogously as Dist( t/J; ,J.ti) = I Diff( t/·; .1/j) I·

2 Winslett's set inclusion based update

The "possible models a.l?proach" to update was pro­ posed in [Winslett., 1988] . As other operators we IYill discuss, the PMA update operator ow selects a subset. of "preferred" models of the update formula. as models of the updated database. Specifically, ow collects. for each model M of the original database 1/·. the models of the update formula J.t which differ in fewest (in th t:> set-inclusion sense) propositional letters from M. For­ mally, we associate to each model /11 an ordering ~\ 1 ; over interpretations defined by: I ~~ J iff Di.fj( I . M) c;; Diil{J ,M) . The update operator ow is then defined by:

Example 1 Let 1/.· = (b 1\ c) V (-.a 1\ -.b 1\ c) and p. = (a 1\ -.b) V ( -.b 1\ -.c) . There a.re three models of t/J, namely, M1 = {a,b,c}, M2 = {-.a, b.c} and M3 = {-.a, -.b, c} , and three models of J.t , N1 = {a. -.b. c} , N2 = {-.a,-.b,-.c} and N3 = {a.,-.b,-.c} . Only N1 is minimal with respect to M1; with respect t.o M'.! both N1 a.nd N2 are minimal, and similarly with respect to M3 . Thus, Mod(t/J o p) = {N1, N2} . D

As shown in [del Val, 1992b]. the PMA update oper­ ator can be syntactically characterized as follows. We first need several definitions, motivated below. For J.ti , J.tk E p, 1/>; E DNF(t/J), let

where. by convention, V0 = false. /\0 = il' lt f. . (J'II drop the subscript. 1/.>; from now on when usiug any of these and similar functions, since the context will always make clear the appropriate subscript.)

Theorem 1 1

The basic idea. behind this theorem is as follows. First, we can see each t/J; E DNF( t/J) as a. partial model of the database t/J, and update each partial model inde­ pendently. For each t/J; E DNF(t/J), then, we need to select models of J1. which are closest to some model of rf'i. This is done in two steps. We first select, for each J.li E DNF(p) = J.I., the models of Jl.i which satisfy as many literals as possible from t/J;, i.e. the set of mod­ els of the formula b;j = /\( ( t/J; - Diil{ t/J; ,Jl.i )) U Jl.i ). For every N E Mod( b;i), there exists M N E Mod( t/J;) such that Dijj( N, M) = Prop( Diil{ t/J; ,Jl.i)). Clearly, no other model of Jl.i can be closer to M N than N, and similarly for models of any 1/k rf. J.I.*(Jl.j ); but this might not be true if we also consider models of some Jl.k E J.I.*(J.I.j ). In t.he second step, then, we further filter out the se­ lected models of Jl.i (which at this point are the mo~­ els of {Iii), by ensuring that any selected model N 1s such that the corresponding MN E Mod(tjJ;) differs from any model of some Jl.k E J.I.*(J.I.j) in some letter not in Prop( DifJ( tl'; , Pi)). This is done by "patching up" b;j by adding to it. the negation of a literal lk E Jl.k for each p k E p* ( J.li). Clearly, lk should not be in Diil{ t/J; ,Jl.i); and h should not be in b;i, since otherwise ...,fk 1\ b;j would be inconsistent. In other words, -./k must be in ll f.fJ (Jlk . Jli ) . If N E Mod(b;j 1\ -.lk), then no mo.del of /fk can be set-inclusion closer to MN than N. Fmally, since we have to choose some lk for each Jl.k E J.I.*(Jl.i ), thert> might be many ways to consistently combine th~se choices . and all possible combinations must be consld­ t>red. The models (if any) of patch(J.I.i) are exactly the models of some such consistent combination .

3 Forbus' cardinality based update

Forbus [1989] proposes a cardinality-based update oper­ at.or. which differs from the PMA only in the replace­ ment of PMA 's set-inclusion minimization of changes bv the minimization of the number of model differ­ t:';tces. Again. we assign to each interpretation M an ordering ~f 1 over interpretations according to which 1 ~~~ .] iff Di.st(I,M) ~ Dist(J,M) . Forbus' operator o , . is defined by:

\Ve now syntactically characterize the operator op. The reader should notice that the only differences with respect to the characterization of the PMA operator lie in the selection by 1-'HI-'i) of the disjuncts in 1-' to be used by negF(I-'F(I-'i )), and in the selection of literals from each 1-'k E 1-'HI-'i) to be negated and added to the formula 6;i .

1 This theorem is simply a more compact expression of theorem 1 in [del Val, 1992b]. There, we used neg(p*(l-'i)) for what here would be DNF(patch(l-'i )) . Considering the three cases gi,·en in that. paper, we have: if p*(l-'i) = 0 then zndch(Jt 1 ) = true; if DNF(patch(l-'i)) = 0, then patch(l-'i) := fa./.~c t.he remaining case can be obtained by using the tau­ tology (V 8 EDNFC .,.,( 1' A 8)) := -y A <p .

Formally, for 1-'i·l-'k E p, t/J; E DNF(t/;), define:

4 Update algorithms

The previous results make it trivial to design very effi­ cient algorithms for computing ow and <>F for databases represented as a DNF formula or under the 'model check­ ing approach' [Halpern and Vardi , 1991 ; Grahne and Mendelzon , 1991], in which the database is represented as a set of models . But storing databases in this way will often be unfeasible, so we need methods which will work with more common formats such as CNF and NNF. According to the next theorem, for CNF and NNF databases it suffices to update the subset of the database sharing symbols with the update formula .

Theorem 3 Let<> E {<>w,<>F}. Let t/J be an .f\TNF or CNF database, let t/Js = {c; E t/J I Prop(c;) n Prop(p) :f. 0} be th.e set of cla11ses or top level con)uucts sharmy some propositional symbols with 1-', and let 1/·u = l/·- 1/"s . Then t/J <> 1-' = (t/Js op) 1\ t/Ju.

This theorem has a dramatic effect on the cost. of com­ puting the update. Update formulas will typically be rather short; assuming that any particular symbol occurs only in a few number of clauses or top level conjuncts , this makes the cost of the update largely independent. of the total size of the database . In [del Val , 1992b] we prt'­ sented an algorithm for PMA update based on this the­ orem, whose worst. case complexity (for CNF input. and NNF output , and ignoring retrieval costs) is bounded by O((D.Ps lcd)(lpl(l-'mar)l~<l-l )) for 1111 > 1. 2 Here led represents the size (number of literals) of the clause Ci. with the product taken over all clauses in t/J s; Jl·ma;c is the maximum size of a disjunct in 1-'· and 11-'1 the number of disjuncts in 1-'· Since 1-' will typically be quite sma.ll, the crucial factor is clearly n.Ps led, which represents the worst ca.c:;e number of disjuncts in DNF( t/·s ). As ex­ perimentally demonstrated in that paper, the algorithm can efficient ly handle (small) updates of large databases.

2 The algorithm given there converts pa.t.ch{t1 1 ) t.o DNF. which is unnecessary, as it is easily seen from t.lworem 1. Without. this conve~sion , the cost i.s 0( (D.Ps lc;J )(I PI/it,,)), where lit. ~' is the total number of lit.erals in I'·

Since the theorem also holds for <>F, it is easy to see that an algorithm for <>F can be designed that, under the as­ sumption that the size of 1-' is bounded, has the same worst case complexity.

5 Dalal's cardinality based revision

As Forbus' operator <>F, Dalal's (1988a) revision operator o D uses an ordering induced by the number of proposi­ tional letters in which two interpretations differ. But whereas <>F collects some models of 1-' for each model of t/J, on ignores some models of 1/J which intuitively are "too different" from the models of 1-'· Formally, instead of associating an ordering to each model, on associates a total preorder $.p to each formula ,P, such that I S:t/1 J iff min.MeMod(.P) Dist(M,I) 5: minMeMod(t/1) Dist(M,J). The operator on is then defined by:

Example 2 Let t/J = (a 1\ b 1\ c) V (a 1\ -,b 1\ ..,c), and I' = -,a 1\ c. The models of t/J are M1 = {a, b, c} and Jlh = {a,...,b,-,c}; the models of 1-' are N1 = {-,a,b,c} and N2 = {-,a, ...,b, c}. Then Mod( t/J <>n p) = {Nl}, since N1 differs from M1 in exactly one literal. M2 does not '·generate" any model of the revised database: though Dist(N'.!,M'2) < Dist(N1,M2), N2 is ruled out, because Dist(N1 ,!111) < Dist(N2,M2) = Dist(N2,M1). In con­ trast. Mod( I/} <>F p) = {N1, N2}. 0

In order to obtain a syntactic characterization of on, w1~ need the following definitions:

;\1 inDist( tf'i, 1-') provides a measure of 'distance' between a conj unction of literals t/J; and a DNF formula p; :11 inDifJ{ 1/'i, p) collects all the 1-'i E 1-' whose distance from a given ~·; is minimal; finally, DNFmin(t/J, p) col­ lect-s t.he formulas in DNF( t/J) which fare best in terms of t.heir distance to 11 .. The following theorem provides a syntactic characterization of Dalal's revision operator.

Theorem 4

Again. very efficient algorithms can be designed to compute on for DNF databases or under the model checking approach. Unfortunately, theorem 3 does not hold for on .

Example 3 Let tf' = (aV-,b)l\b,p =-,a. Then t/Jonp::: (a 1\ b) ov ..,a = ..,a 1\ b. But DNF(t/Js) = {a, -,b}, and D !'H'min ( tf'S, J1) = { -,b}, so t/Ju 1\ ( t/Js on p) = b 1\ ( -,b 1\ ·a) ::: false. In contrast, using theorem 3 we obtain l'<>F JI = 1/J(r/\(t/Js<>FI-') = bl\(...,av(-,bl\...,a)) = bl\-,a.D

lnt.uitively. the problem lies in the 'model pruning' op­ erat-ion involved in revision. In example 2, M2 is pruned in t.he sense that. models of 1-' closest to M2 are ignored, something which is captured in theorem 4 by the fact. that a 1\ -,b 1\ ...,c ¢ DNFmin(tP,p). But as example 3 illustrates, using DNF min on tPs instead of ·1/.· might. se­ lect a set of disjunct all of which are inconsistent with 1/'. When (and only when) this is the case, using the ana­ logue to theorem 3 for ov will result in an incorrectly revised (in fact, inconsistent) database.

If we think of DNF disjuncts as partial models, the problem is that some of the disjuncts in DNF(lbs) do not represent partial models of the database ,P, and thus there is no need to update or revise these disjuncts. But checking whether this is the case is extremely costly, and thus the restriction to tPs can be seen as a way of guess­ ing partial models. If every model of the database is changed independently, as in update, the "bad guesses" will generate disjuncts which are inconsistent with ll'u (as -,b 1\ ...,a in example 3 with OF) and thus do not. result in spurious models of the modified database. In revision , in contrast, we need to prune some models of ,P, and as illustrated by example 3, performing the pruning opera­ tion of t/·s instead of l/· might rule out. all parti al models of ,P.

We can still develop revision procedures for C'NF and NNF databases , though at a substantially higher cost. than for update. We do so in two steps. We first. bound the set of clauses or top level conjuncts that needs to be considered (theorem 5) ; then we show that. t.his set. ra n be used to filter the disjuncts of DNF( t/·s ) in order to compute the revised database (theorem 6) . It will t.heu be easy to design an algorithm based on these results.

The set tPc of clauses or top level conjuncts that needs to be considered is the set of conjuncts 'connected' to f1 in the sense that they share propositional symbols with p or with another clause connected with p . Formally:

Theorem 5 Let tP be an NNF or CNF dat abast . J: ct 1/;c be as defin ed above and let «PN = ~t· - u·c . Tllf 11 tP ov fl = (tPc ov p) 1\ V'N·

We could thus compute the revised databas~> hy using theorem 4 to compute expression 1/.·c ov p in theorem :j. But computing DNF( 1/.·c ), as this procedure would re­ quire, is unnecessary. Instead , we can use ~t·c as a filt.er on tPs , in order to remove those disjuncts V'i E DNF(~ · s ) which, though perhaps at a minimal distance of p . are not partial models of ,P. This idea can be formali zed by making the definition of DNF min( 1/;s , JI) depend on tPC· Let DNF min ( 1/.·s, Jl, 1/>c ) be the set of 1/:; E DNF( !! ·s ) such that. :

1. 31/;k E DNF( !/;s ) : 1/Jc If -. 1/Jk and Mm.Dt sf(tr ;. p ) = MinDist( tPk, p); and
2. V,Pi E DNF(1/;s ) : if 1/;c If -.,pi then MinDist( tPi, 11) ~ MinDist( V'i , p).

Theorem 6 Let '1j; be an N N F or CN F database. t; 's and 1/;c be as defined above, and 1/;u = 1j;- 1/>s . Then

The following is a simple algorithm to compute ov : Procedure Dalal-Revise( ,P, p)

1. !\lake an array Distances of size IPmu·l + 1.
2. For each 1/;i E DNF(1/.>s), compute MinDiff(tPi,Jl) and k = MinDist(1/.>i,Jl), and store tPi and MinDiffl..l/>;, p) in Distances(k] .
3. Traverse Distances in ascending order, until an in­ dex m and a disjunct tPi E Distances[m] are found such that 1\( tPc - tPs) 1\ tPi is satisfiable (in which case DNFmin(tPs,p,,Pc) = Distances[m]).

The algorithm is clearly quite similar to the one pre­ sented in [del Val, 1992b] for PMA update, so many of the comments made there about efficiency and op­ timizat.ion apply here as well. Under the same imple­ mentation assumptions as were made there, it can be shown that. the worst case complexity of the procedure, for CNF input and NNF output and ignoring retrieval costs. is O((f1v:·s lcdliJllliti-'SATt.Pc ) , where SATt./!c is the cost . for any given ~·; E DNF('1/;s), of testing whether ( vc - t!·s ) f-- -. 'lj.>; .

As we can see, the crucial difference between this re­ sult and t.he cost of update lies in that there is no need for consist.ency checks in the latter, a difference which can be dired .ly traced, as mentioned above, to the model­ sPiect.ion operation represented by DNF min. Using 0([1 11 ,c led) as an upper bound for O((f1t.Ps lc;I)SATt.Pc) , an assuming the size of J1 is bounded by a constant, the additional cost. of Dalal 's revision with respect to the cost of Pl\lA update is in the worst case O(f1t.Pc -t.Ps lei I) , or in essence asymptotically exponential on the size of the dif­ ference v·c - 1/·s . This added cost can be greatly reduced if the database is Horn. In this case, SATt./!c will be lin­ ear on the size of 1/;c - 1/;s [Dowling and Gallier, 1984; Gallo and Urbani, 1989]. Notice also that in Dalal-Revise a huge number of disjuncts might be pruned, resulting in a potenti ally much smaller database growth than with update operators.

6 Satoh 's set-inclusion based revision

Satoh [1988] proposed what can be seen as the nat­ ural set. inclusion based alternative for revision to Dalal's cardinality-based approach. Define the set JJ od,1Jin Diff( 1}·, J1) of minimal differences between mod­ ~> Is of v and 11 as

Specialized t.o propositional logic, Satoh's revision oper­ ator o, can now be defined as:

Example 4 Let. V' and J1 be as in example 2. Then :1/od( ~· os p) =Mod( 'I/.· ov p) = {Nl}. Again, N2 is clos­ est to !lh , but is not a model of the revised database, since Di.tf( N 1 ,111!) is a strict subset of both Diff(N2,M2 ) and Di.ff( N'J .M!) . o The operator os can be syntactically characterized as follows . A natural syntactic counterpart to ModMinDi.fJ can be obtained by defining SynMinDiff(lj.·,p) as:

We ran t.lu·tt syut.actically mimic the model selection op­ eration in the definition of os by defining:

Theorem 7

In the case of CNF and NNF databases, it is again not possible to compute the revised database by consid­ ering only 1/Js, as can again be shown with example 3. We can solve the problem in a similar way as before. It would suffice to use 1/.Jc as in theorem 5, but an even tighter result. can be obtained by defining a version of MinPairs relative to 1/.·c. The idea, very much in the spirit of the definition of DNFmin(l,bs,Jt , 1/·c). is again to filter out. disjuncts 1/.·; E DNF(l/.·s) which could po­ tentially be taken as elements of a minimal pair , but which are not really partial models of 1/.·. Formally. de­ fine MinPairs( 1/Js, f.1, 1/Jc) to be the set of pairs < 1/·;. ft J > such that:

1. 1/J; E DNF( 1/Js) and Jti E J.L ;

Theorem 8 Let lj.· be an NNF o1· CNF database. and let 1/.Jc, 1/Js, 1/Ju be as above. Then

It is now easy to obtain a procedure to compute Satoh's revision similar to the one presented for Dalal's revision. As before, we have to compute DNF(I/·s ). In this case, however, we cannot have the various 1/·; E DNF(l/.·s) totally ordered by their distance t.o Jl . \Ye can use instead some data structure which supports ef­ ficient subsumption checks to store the various ditTert>ttt. values of Prop( Diff( 1/.·;, J.Lj) ), storing with each such \'rtltw t.lw set. of all formulas /\( 1/.·k - Di,IJ( 1/·k .Jif)) U ''' such I hat Prop(Diff( lj.J., pt)) = Prop(Diffi..l/.·;, Jli )) . (For example. we can use a trie as suggested in [de Kleer, Hl92] . with each terminal node storing all the associated formulas .)

Procedure Satoh-Revise( 1/..·, J.L)

1. D := 0.
2. For each ll·; E DNF( 1/.Js) and Pach Jlj E fl do:
3. D;j : = Prop( DifJ( ¢;, Jli)) 4. If there exists D ED such that D = D;j 5. then store 1\((l/·;- Di.fJ(lj.J; ,J.Lj))UJ.Lj) with D 6. else if [DE D implies D (f_ D;i], and 1/Jc - ll·s If·~· · ; 7. then store /\( (1/J;- Di.fJ(lj.J;, J.Li))UJlj) with D;j 8. D := (D- {DEDI D;j c D}) u {Dij}
4. Return l/.·u conjoined with the disjunction of al l for­ mulas stored with some DE V .

It is easy to see that under the assumption that the size of fl is bounded by a constant , this procedure has the same worst case complexity as the procedure Dalai­ Revise , since the number as well as the cost of the subset tests made for each 1/.J; will be bounded by a constant as well , and since in both procedures we might need to check every generated disjunct for satisfiability. Needless to say, we expect Dalal-Revise to perform much better in practice and to require much fewer satisfiability checks. Notice however the important fact that both procedures benefit equally from the restriction to Horn databases.

7 Other revision operators

Borgida [1985] proposes a revision operator oB such that lj.· o B tt is defined as 1/.J 1\ J.l if 1/.J 1\ J.l is satisfiable, or as 1/.J ow f1 otherwise, where ow is Winslett's update operator. In view of theorem 1, it is trivial to obtain a syntactic charact.erization of o B , and we omit it.

Weber [1986] proposes a revision procedure that elim­ inates first from l/· all symbols in ModMinDiJJ(lj.J, J.L) , and then conjoins J.L with the resulting database. Let fl = U ModMinDifJ(l/.·, J.L), and for any model M, let :\1 - n be the restriction of M to letters not in 0 . We­ her's revision operator ow is defined by:

\<\'Pber provides an alternative characterization of ow . Ld. !/·~ stand for the formula obtained by replacing every o1·cu rrence of p in lj· by q. For any propositional letter p, let l'fSp(l!·) = ¢frue V 1/.Jjal.e ; for a set of letters P = {PI· .... pn} . let 1·esp(lj.J) = resp 1 (resp~( ... (resp,.(l/.J)))) . Then t;: ow J.l = 7'esn(V') 1\p. [Weber, 1986, theorem 5.4] . Weber however provides no method to compute 0 other than by examining all models of 1/.J and all models of J.L, so this falls short of a purely syntactic characterization of the operator. Such characterization is however very easy to obtain in view of the results in the previous section.

Theorem 9 !J· ow J1 := resn(l/.J) 1\ J.L , where 0 = U SynMinDi.fJ(l/.·, J.L) .

Since the final value of 1) in the procedure Satoh­ Rfl·i.se is precisely SynMinDiJJ(l/.J , J.L), it is now easy to d·'sign an algorithm for ow.

8 Discussion

\Ye have provided syntactic characterizations and algo­ ritluns for a number of propositional belief change op­ erators proposed in the literature. To our knowledge, in fact., the operators we have characterized include all t hose proposed in the AI literature not based on condi­ tionals and whose result is independent of the syntactic form of the database. It is easy to see that there are close similarities among all the characterizations, which suggests that these techniques are very general. With the exception of ow , belief change can be computed by computing the formula O;j = 1\((1/.J;- Diff(lj.J;,J.Lj)) UJ.Lj) for some or all the 1/.J; E DNF( 1/.J) (DNF( 1/.Js) for CNF and NNF databases) and some or all the J.li E J.l· For ov and os. but not for ow, op, and oB, some of the 1/.J;'s havP to be pruned , with the resulting impact on com­ plexi ty for CNF and NNF databases; for ow , op, and oa, but not. for oo or os, b;j has in some cases t.o lw "patched up" by negating, if possible, sonw of the lit er­ als in other /-LJ.: 's in p. As mentioned in the int.roductiou , this generality suggests that the interest of these charac­ terizations goes beyond the usefulness of the algorithms derived from them.

Related work in update algorithms (such as [Chou and Winslett, 1991; Forbus, 1989; Grahne and Mendelzon, 1991]), all of which, unlike ours, assumes that. the mod­ els of the database are directly available, is discussed at some length in [del Val, 1992b] . As for revision oper­ ators, no strictly syntactic characterization of Weber 's and Borgida's approach for arbitrary databases and up­ date formulas was previously known . Satoh [1988) pro­ vides a second order characterization of os as defined for predicate calculus, but no same-order characteriza­ tion was known. Dalal [1988a; 1988b] characterizes his operator oo as follows. Let G('I/J) = vpEProp( t/J) resp (t/·), G 0 (1/J) = G(t/!), Gn(,p) = G(Gn- 1 (1/J)). Dalal shows that t/J o 0 p :: Gk ( t/J) 1\ p for the least k such that the right hand side is satisfiable. Thus, we can compute I} · oo J.1 by repeatedly applying the function G to the database resulting from the previous step, checking at. each step the consistency of the result with J.L. Our method also rl'­ quires (different) satisfiability checks; but since the func­ tion G does not. preserve the property of lwi np; H or11. Dalal's llll't.ltocl, unlike ours, caunot tak·~ adva iit a~·· ul' a restriction t.o Horn databases. We also no!P that lDahtl . 1988b, theorem 5.3] provides a method which comput<'S the revised database given the minimal dist.ancP in which models of p and 1/J differ. The value m used in step 4 of Dalal-Revise as an index into the array Distances is just. such minimal distance, a fact that we can use in ordPr to apply this last method.

An important area for further work is belief ch;mge in the presence of constraints or "protected formulas .. . We have characterizations of the result of applying l:'arh of t.he operat.ors discussed in t.he presence of prot··cll'd formulas , which are identical or very similar to those re­ ported in [del Val, 1992b] for PMA update , which again suggests that similar techniques can be shared acnoss belief change operators. Another area for further work is the extension of our results to predicate calculus. for which we conjecture that some of the techniques pre­ sented in [Chou and Winslett , 1992] can be adapted to deal with partial models (DNF disjuncts) and incorpo­ rated into the algorithms of this paper.