Relating Belief Revision and Circumscription

1 Introduction

During the last years, many formalisms have been pro­ posed in the AI literature to model commonsense rea­ soning. Particular emphasis has been put in the formal modeling of a distinct feature of commonsense reason­ ing, that is, its nonmonotonic nature. The AI goal of providing a logic model of human agents' capability of reasoning in the presence of incomplete or contradictory information has proven to be a very hard one. Neverthe­ less, many important formalisms have been put forward in the literature.

Two main approaches have been proposed to handle the nonmonotonic aspects of commonsense reasoning. The first one deals with this problem, by defining a new logic equipped with a nonmonotonic consequence oper­ ator. Important examples of this approach are default logic proposed in [Reiter, 1980] and circumscription in­ troduced in [McCarthy, 1980]. The second one relies on preserving a classical (monotonic) inference opera­ tor, but introduces a revision operator that accommo­ dates a new piece of information into an existing body of knowledge. Specific revision operators have been in­ troduced, among the others, in [Ginsberg, 1986] and in [Dalal, 1988]. A general framework for revision has been proposed by Alchourron, Gardenfors and Makinson in [Alchourr6n et al., 1985; Gardenfors, 1988]. A close vari­ ant of revision is update. The general framework for up­ date has been studied in [Katsuno and Mendelzon, 1989; 1991] and specific operators have been proposed in [Winslett, 1990] and [Forbus , 1989] .

*Work partially supported by the ESPRIT Basic Research Action N. 6810 COMPULOG II, N. 6471 MEDLAR and the Progetto Finalizzato Informatica & Calcolo Parallelo of the CNR (Italian Research Council)

In this paper we investigate the relationship between circumscription and many operators for belief revision and update. A first study of these relations has been done in [Winslett, 1989], where she relates her opera­ tor to circumscription. We expand her results showing similar connections between several other belief revision operators and circumscription. To this end, we also in­ troduce a variant of circumscription based on cardinality, rather than set-containment.

The established correlations highlight the relations be­ tween the two fields. Moreover , as side benefits, they provide us with the opportunity to import results in one field into the other one.

A distinct approach to model the nonmonotonic as­ pect of commonsense reasoning is via a logic of actions. Even though this aspect is out of the scope of this paper, we want to point out the results presented in [Kharta and Lifschitz, 1994] where it is shown how to express a very general logic of action using circumscription.

The paper is organized as follows: In Section 2 we re­ call some key definitions and results for belief revision and circumscription, introduce a variant of circumscrip­ tion (NCIRC) and explain the notation used throughout the following sections. In Section 3 we show the main re­ lations between revision operators and circumscription, while in Section 4 we show relations and reductions be­ tween the various operators. In Section 5 we focus on syntactically·restricted knowledge bases. Section 6 dis­ cusses the impact of our results with particular atten­ tion to the computational complexity analysis. Finally, in Section 7 we draw some conclusions.

2 Preliminaries

In this section we (very briefly) present the background and terminology needed to understand the results pre­ sented later in the paper . For the sake of simplicity, throughout this paper we restrict our attention to a (fi­ nite) propositional language.

The alphabet of a propositional formula is the set of all propositional atoms occurring in it. Formulae are built over a finite alphabet of propositional letters using the usual connectives-, (not), V (or) and 1\ (and). Addi­ tional connectives are used as shorthands, a-+ j3 denotes ·a V ;3, a = j3 is a shorthand for (a 1\ ;3) V ( ·a 1\ ·/3) and a :f. j3 denotes -, (a = ;3).

An interpretation of a formula is a truth assignment to the atoms of its alphabet. A model M of a formula F is an interpretation that satisfies F (written M f= F). Interpretations and models of propositional formulae will be denoted as sets of atoms (those which are mapped into 1) . A theory Tis a set of formulae. An interpretation is a model of a theory if it is a model of every formula of the theory. Given a theory T and a formula F we say that T entails F, written T f= F, if F is true in every model ofT. Given a propositional formula or a theory T, we denote with M (T) the set of its models. We say that Tis consistent, written TV= l_, if M(T) is non-empty.

2.1 Belief Revision and Update

Belief revision is concerned with the modeling of accom­ modating a new piece of information (the revising for­ mula) into an existing body of know ledge (the know ledge base), where the two might contradict each other. A slightly different perspective is taken by knowledge up­ date. An analysis of the relative merits of revision and update is out of the scope of this paper, or an interesting discussion on the differences between belief revision and update we refer the reader to the work [Katsuno and Mendelzon, 1991]. We assume that both the revising formula and the knowledge base can be either a single formula or a theory.

We now recall the different approaches to revision and update, classifying them into formula-based and model­ based ones. A more thorough exposition can be found in [Eiter and Gottlob, 1992]. We use the following conven­ tions: the expression card(S) denotes the cardinality of a set S, and symmetric difference between two sets S1, S2 is denoted by S1l1S2 . If Sis a set of sets, nS denotes the set formed intersecting all sets of S, and analogously US for union; mineS denotes the subset of S containing only the minimal Tw.r.t. set inclusion) sets in S, while maxc S denotes its maximal sets.

Formula-based approaches operate on the formulae syntactically appearing in the knowledge base K. Let C(K, A) be the set of the subsets of]{ which are consis­ tent with the revising formula A:

and let W(K, A) be the set of the maximal sets of C(K, A):

The set W(K, A) contains all the plausible subsets of]{ that we may retain when inserting A.

Ginsberg. In [Ginsberg, 1986] the revised knowledge base is defined as a set of theories: K *G A :::::: { K' U {A} I K' E W(K, A)}. That is, the result of revising ]{ is the set of all maximal subsets of ]{ consistent with A, plus A. Logical consequence in the revised knowledge base is defined as logical consequence in each of the theories, i.e. K *G A f= Q iff for all K' E W(K, A), K' U {A} f= Q. In other words, Ginsberg considers all sets in W(K, A) equally plausible and inference is de­ fined skeptically, i.e. Q must be a consequence of each set.

Model-based approaches instead operate by selecting the models of A on the basis of some notion of proxim­ ity to the models of]{. Model-based approaches assume K to be a single formula, if K is a set of formulae it is implicitly interpreted as the conjunction of all the ele­ ments. Many notions of proximity have been defined in the literature. We distinguish them between pointwise proximity and global proximity.

We first recall approaches in which proxirnity between models of A and models of ]{ is computed pointwise w.r.t. each model of K. That is, they select models of ]{ one-by-one and for each one choose the closest model of A. These approaches are considered as more suitable for knowledge update [Katsuno and Mendelzon, 1991]. Let M be a model, we define J.L(M, A) as the set con­ taining the minimal differences (w.r.t. set inclusion) be­ tween each model of A and the given M; more formally, J.L(M,A):::::: minc{Ml1N IN E M(A)}.

Winslett. The work . [Winslett, 1990] defines the models of the updated knowledge base as M (K *W A) = {N E M(A) I 3M E M(K) : M l1N E J.L(M, A)} . In other words, for each model of K it chooses the closest (w.r .t . set-containment) model of A.

Borgida. This operator * B, defined in [Borgida, 1985], coincides with Winslett's one, except in the case when A is consistent with ]{, in which case Borgida's revised theory is simply K U {A}.

Forbus. This approach [Forbus, 1989] takes into ac­ count cardinality: Let kM,A be the minimum cardinality of sets in J.L(M, A). The models of Forbus' updated the­ ory are M(K *FA) :::::: {N E M(A) I 3M E M(K) : card(M l1N) = kM,A}· Note that by means of cardinal­ ity, Forbus can compare (and discard) models which are incomparable in Winslett's approach.

We now recall approaches where proximity between models of A and models of ]{ is defined considering globally all models of I<. In other words, these ap­ proaches consider at the same time all pairs of models M E M(I<) and N E M(A) and find all the closest pairs. Let cS(K, A) ::::::min~ UMEM(K) J.L(M, A).

Satoh. In [Satoh, 1988], the models of the revised knowledge base are defined as M(K *s A) = {N E M(A) I 3M E M(K) : N l1M E cS(I<, A)}. That is, Satoh selects all closest pairs (by set-containment of the difference set) and then projects on the models of A.

Dalal. This approach is similar to Forbus', but global. Let kK,A be the minimum cardinality of sets in cS(K, A); in [Dalal, 1988] the models of a revised theory are de­ fined as M(I< *D A) :::::: {N E M(A) I 3M E M(I<) : card(N l1M) = kK,A}· That is, Dalal selects all clos­ ets pairs (by cardinality of the difference set) and then projects on the models of A.

The complexity of deciding I<* A f= Q (where * is one of { *G, *w, *B, *F, *s, *D}, I<, A and Q are the input) was studied in [Eiter and Gottlob, 1992]: in Dalal's approach, the problem is L\~[logn]-complete, while in all other approaches it is II~-complete.

2.2 Circumscription

Circumscription has been originally introduced in [Mc­ Carthy, 1980]. Further extensions have been proposed by several authors. Here we stick to the semantic for­ mulation of circumscription and restrict our interest to a propositional language. Following [Lifschitz, 1985], we define:

Definition 1 Let T be a propositional formula, X = {x1, ... , Xn} its alphabet, P and Z disjoint sets of letters partitioning X (i.e. PU Z =X) and ME M(T). M is called a P -minimal model ofT if there is no model N of T such that (NnP) ::j; (MnP) and (NnP) c (MnP).

Definition 2 The circumscription ofT w.r.t. the two sets of letters P and Z, denoted as CIRC(T; P, Z), is the set of all ?-minimal models of T, i.e. M f= CIRC(T; P, Z) iff M is a ?-minimal model ofT.

Informally, P is the set of letters we want to minimize, while letters in Z are allowed to vary. Notice that we are using a version of circumscription where fixed pred­ icates are not allowed. Due to the results of [de Kleer and Konolige, 1989] on eliminating fixed predicates, this restriction does not lead to any loss of expressiveness.

2.3 Cardinality-based Circumscription

The minimality criterion of circumscription is based on set-containment. We now introduce, for propositional languages, a version of circumscription based on cardi­ nality.

Definition 3 Let T be a propositional formula, X = { x1, ... , Xn} its alphabet, P and Z disjoint sets of letters partitioning X (i.e. P U Z =X} and ME M(T). M is called a ?-cardinality-minimal model ofT if there is no model N ofT such that INn PI< IM n Pl.

Definition 4 The cardinality-based circumscription of T w. r. t. the two sets of letters P and Z, denoted as NCI RC(T; P, Z), is the set of all ?-cardinality-minimal models ofT, i.e. M f= NCIRC(T; P, Z) iff M is a ?­ cardinality-minimal model ofT.

In other words, I am preferring models with the least number of true letters of the set P, rather than models with a least set of true letters.

2.4 Notations

In order to make formulae more compact and easier to understand, we introduce a number of notations that we use in the rest of the paper.

In the following sections, we make use of variable re­ naming. To make this clear, we explicitly mention over which alphabet a formula is built upon. More precisely, let X = {x1 , ... , xn} be a set of letters, we denote as T(X) a formula built over X. Given a new alphabet Y = {Yl, ... , Yn} one-to-one with X, with T(Y) we de­ note the formula with the same structure of T(X) but every occurrence of x; is replaced by y; for all i 2: 1 and i ~ n. For example, let

then the formula T(Y) is (Yl 1\ ( --.y3 V Y2)).

In order to make the formulae more compact and read­ able, we overload the boolean connectives to apply to sets of letters. For example, given three disjoint sets of letters W, S and R with the same number of elements k, we use the notation --.S as a shorthand for the formula ;\{--.sds; E S}, S = R to denote ;\{s; = r;l1 ::=; i ::=; k}, S ::j; R to denote ;\ { s; ::j; r; 11 ::=; i ::=; k} and W = ( S ::j; R) for ;\{w; = (s; ::j; ri)l1 ::=; i ::=; k}.

3 General Cases

In this section we establish relations between circum­ scription and the various belief revision operators. Due to the lack of space we cannot present complete proofs for all the results, but we provide a sketch of some of the proofs.

3.1 Dalal's revision

The links between the cardinality-based circumscription and Dalal's revision [Dalal, 1988] are very simple. This is due to the similarity of these operations: N C I RC takes the models with a minimum number of positive atoms of the set P, whereas Dalal's revision selects the models of A with a minimum number of differences with models of K.

To translate NCIRC(T; P, Z) into a Dalal's revision it is enough to revise the knowledge base with all literals in P negated. More precisely, we have

In fact, the cardinality-minimal models of T are ex­ actly the models of T closer to the knowledge base --,p. The above relation is simple because revision seems somewhat more powerful than NCIRC. In fact, it has N C I RC as a sub-case, where J{ is a set of literals. How­ ever, it can be shown that Dalal's revision can be trans­ lated into cardinality-based circumscription.

Given three disjoint sets of letters X, Y and W, each one containing n letters, we denote with f(X, Y, W) the formula K(Y) 1\ A(X) 1\ (W = (X ::j; Y)). f admits a model M iff Mx = (M n X) is a model of A and My = (M n Y) is a model ofT. Which letters of W will belong to Mw = (M n W) is uniquely determined by Mx and My. In fact, w; E Mw if and only if x; E Mx and y; (/; My or x; (/; Mx and y; E My.

If we force Mw to contain a minimal number of! etters, only the models of r where the differences between the assignments to X and Y are as few as possible, will be retained. Thus we obtain

where we minimize the letters in W, but not those in X U Y. More precisely we have:

Theorem 1 For any model M of K(X) *D A(X) there exists a model N of NCIRC(f(X, Y, W); W,X U Y) such that M = N n X. Furthermore, for any model N of NCIRC(f(X, Y, W); W, X U Y) N n X is a model of K(X) *D A(X).

Proof (sketch). We first prove that for any model Mx ~X of K(X)*vA(X) there exists two sets My ~ Y

and Mw C W such that M = MxUMyUMw is a model of NCI RC(K(Y) A A(X) A (W = (X :f. Y)); W, Xu Y) . Since Mx is a model of K(X) *D A(X), it follows that Mx FA and that there exist a model Nx E M(K(X)) such that card(Mx!:l.Nx) = k, where k is the mini­ mum distance between models of K and models of A. We define My= {y;lx; E Nx} and Mw = {w;l((x; E Mx)and(y; ~ My))or((x; ~ Mx)and(y; E My))} . Ob­ viously, it holds M F K(Y) A A(X) A (W = (X :f. Y)). Furthermore, we can prove by contradiction that M is a cardinality-minimal model.

We now show that for any model M of NCIRC(K(Y)AA(X)A(W =(X :f. Y));W,XUY) , the set Mx = M n X is a model of K(X) *D A(X) . It immediately follows that Mx F A(X), if Mx is one of the models of A closer to models of K the thesis follows , so assume to the contrary that there exists a N x ~ X, different from Mx , such that Nx F A(X), the distance of Mx from the closest model of K(X) is kM, the dis­ tance of N x from the closest model of K (X) is k N and kN < kM. Let Vx ~X be one of the models of K(X) closer toN, Ny = {y;ix; E Vx}, Nw = {w;l((x; E Nx )and(y; E Ny ))or((x; ~ Nx )and(y; ~ Ny ))} and N = N x U Ny U Nw. Obviously N is a model of K(Y) A A(X) A (W = (X :f. Y)) moreover, the cardi­ nality of N n W is kN, the cardinality M n W is kM . Since kn < kM it follows that M is not a cardinalityminimal model of K(Y) A A(X) A (W (X :f. Y)), hence contradiction arises. 0

3.2 Satoh's revision

The same reductions between Dalal's rev1s1on and cardinality-based circumscription hold between Satoh's revision [Satoh, 1988] and usual (set-containment-based) circumscription.

To reduce Satoh's revision into circumscription, we use the same relation adopted to reduce Dalal's revision into NCIRC

The models of T can be decomposed in a model of K, a model of A, and the difference between them. Circum­ scription minimizes W, hence makes them as close as possible, where closeness is w.r.t. set containment.

3.3 Winslett's update

Winslett's update method modifies models of K one-by­ one, replacing each one with the closest one within the models of A. Local proximity methods are better re­ lated to circumscription where all letters are minimized. Circumscription without varying letters is immediately expressed as

In order to correlate Winslett's update with circum­ scription, we must be sure that to each distinct model of K correspond incomparable models in the circumscrip­ tive theory. This is obtained by the following reduction:

The sub-formula Y :f. Z guarantees that every two models M and N of K, with different assignments to Y, are incomparable because it cannot be the case that (M n Y) ~ tN n Y) and (M n Z) ~ (N n Z) at the same time. The above reduction can be rephrased so as to eliminate varying letters (X) . In fact, we obtain:

where A(Y :f. W) denotes A where all occurrences of x; are replaced by y; :f. w; for all i ~ 1 and i ~ n .

3.4 Borgida's revision

Borgida's revision operator [Borgida, 1985] is very simi­ lar to Winslett's one, the only difference being that the result of the first one has to be K A A when not contra­ dictory. Since *B and *w coincide when K is a set of literals, the reduction

holds for * B .

In the other direction, one can find a direct trans­ formation from Borgida's revision into circumscription, very much like Winslett's one.

The fact that the result must be K A A can be taken into account by selecting the models of this formula as minimal.

where T is defined as follows:

This reduction coincides with Winslett's one, exception made for the sub-formula K(X) V ((Y = R) A (R :f. Z)). Given a model X of P, if there is a model of K with the same value, the formula T has a model (X; Y =X, R = · 0, Z = 0) that is surely minimal.

If such a model does not exist , the only models of T(X, Y, R, Z) are those having anY such that I<(Y) is true, R equal to Y and Z the complement of Y. Hence, we have only the models of Winslett's transformation, so the result coincides with the result of applying Winslett's revision. This is exactly the definition of revision given by Borgida.

3.5 Ginsberg's revision

Ginsberg's revision is quite similar to Satoh's principle of minimization. The main difference between them is that the latter minimizes distance given as set of liter­ als, while the first one maximizes the number of true formulae of K.

Two simple relations correlating Ginsberg's revision and circumscription are the following ones:

The first formula follows from the known fact that if J{ is a set of literals, then J{ *G A = J{ *sA (see [Eiter and Gottlob, 1992]).

Regarding the second reduction, remind that Gins­ berg's revision finds the maximal subsets J{' of J{ s.t. J{' and A are not contradictory, whereas the circumscription of a formula takes only the models with a maximal set of false variables. Hence, to revise a set of formulae, we have to include a formula /; if and only if a variable y; (not contained in the original formulae) is false. The transformation follows.

3.6 Forbus' update

While all the above reductions are quite simple and straightforward, what we found for Forbus' update oper­ ator *F [Forbus, 1989] is much more complex. Since the resulting formula is somehow cumbersome and difficult to read, we prefer to give a sketch of the steps needed in the reduction. Similarly to the other local-proximity model-based formalisms, we establish relations between Forbus' update and circumscription (or NCIRC) where all letters are minimized.

We first observe how circumscription and N C I RC can be expressed using Forbus' update. Reduction of N C I RC to For bus' operator is trivial:

It is also possible to reduce circumscription to Forbus' update. Very briefly, this can be obtained by adding a suitable number of new variables (O(n 3 )) and imposing that to each (set-containment) minimal model of T(X) corresponds a cardinality-minimal model over the ex­ tended alphabet.

The reduction of Forbus' update to circumscription is very similar to Borgida's one. We have only to take in account that Forbus' update is based upon a minimizza­ tion of the cardinality of the distances between models. Consider the formula:

K(X) *F A(X) = CIRC(T(X, Y, W, V); V, XU Y U W) where T(X, Y, W, V) expresses the fact that that X is a model of A, that Y is a model ofT, and Vis a valutation of the cardinality of the distance between them.

Now let

Given a model ofT and a model of A, this formula has exactly one model, namely the model in which X repre­ sents the model of A and Y the model ofT. The vari­ ables W represents the simmetrical difference between X and Y. The formula EQ(W, V) is the polynomial­ size formula that is true if and only if W and V have exactly the same number of positive literals. Finally, BEGIN(V) states that the positive literals of V are its first ones:

Such a formula imposes that V and W have the same number of true literals, and that the set V has all the true atoms "at the beginning", so if W have three positive literals then V = { v1, v2, va}.

3.7 AGM operators

In previous sections we showed how we can reduce spe­ cific belief revision operators to circumscription and vice versa. Here we present a general methodology to trans­ form any belief revision operator. The most general form of belief revision is given by the well-known postulates for revision (AGM postulates [Alchourr6n et al., 1985]). AG M postulates give eight basic properties that any be­ lief revision operator should satisfy. Operators ( * AGM) satisfying the AGM postulates can be expressed as:

where ~K is a transitive, reflexive and total relation based on K.

Note that not all the presented operators satisfy all AGM postulates. Updates and revisions defined by Borgida, Forbus, Satoh and Dalal are better generalized as reflexive and transitive orderings over pairs of models. The result of J( *A is J{ 1\A if consistent and M (K *A) = {JI3I E M(K). (I, J) E min(M(K) x M(A), ~)} otherwise.

In both cases, we must choose the minimal models of a formula w.r.t. a given ordering~ (or ~x). Any ordering over interpretations can be represented via a propositional formula LEQ( ·, ·) (resp. LEQx(-, ·)),such that LEQ(X, Y) (resp. LEQx(X, Y)) is true iff X~ Y (resp. X ~K Y). Using this formula, AGM revision operators can be reduced to circumscription via:

and LESSx(Y,X) represents the fact that Y <x X. More precisely, LESSx(Y,X) LEQx(Y,X) 1\ -.LEQ(X, Y). Note that K is missing in the circumscrip­ tion, since it is implicit in LEQx . The formula X # Z makes two models with different valuations over X in­ comparable. Models of[(X # Z)/\A(X)/\A(Y)/\(-.w = LEQx(Y, X))] assign false tow iff X is not a minimal model of A w.r.t. ~K. Therefore, for every assignment to X not being a minimal model of A, the models of the circumscription make w false. Conjoining the result with w, we get rid of the non-minimal models.

The other generalization is even more complex. In fact, we must enforce that we choose the models M of A such that there exists a model N of J{ and for all models M' of A and models N' of K it does not hold that M' # M, N' #Nand LEQ(M'N',MN).

We want to point out that these transformations are not necessarily polynomial. In fact, we do not know what is the size of the formula LEQ(X, Y) w.r.t. the size of X and Y. It might very well be exponential.

4 Relations among belief revision operators

In Section 3 we found relations between circumscription and belief revision operators. Here we focus on relations among the various revision operators.

In particular, we show that Satoh's and Ginsberg's operators can be reduced one to the other and that Winslett's one can be reduced to both. Note that these operators belong to three different classes of op­ erators, namely formula-based (Ginsberg), model-based with global proximity (Satoh) and model-based with lo­ cal proximity (Winslett). Therefore, our results make ev­ ident the similarities between all these operators, point­ ing out, at the same time, their differences.

Ginsberg's operator can be reduced to Satoh's opera­ tor via:

More complex, but still polynomial, is the reduction of Winslett's operator into Ginsberg's one:

K(X) *w A( X) = (W U Y U Z) *a F(X, Y, Z, W) where F(X, Y, Z, W) is:

F(X, Y, Z, W) = K(Y)AA(X)A(-.Yv-.Z)A(W-+ (X= Y)) Through the above reductions it is also possible to re­ duce *W to *S·

5 Syntactically-restricted Knowledge Bases

In this section we focus on knowledge bases of a re­ stricted syntactic form. Among the restricted cases, Horn knowledge bases are of particular interest for sev­ eral reasons. First of all, since Horn clauses can rep­ resent causality relations, they are expressive enough to represent many real situations. Moreover, reasoning with Horn knowledge bases is significantly simpler than reasoning with general ones (see [Dowling and Gallier, 1984]) and also revising them is, in general, simpler than revising general ones (see [Eiter and Gottlob, 1992]).

While reductions from circumscription to belief revi­ sion preserve the syntactic form of the original theory, reductions from belief revision to circumscription do not preserve the syntactic form of the formulae. As an exam­ ple, notice that the relation X :j; Y cannot be expressed as an Horn formula.

As a consequence, it is easy to apply results on re­ stricted cases of belief revision to circumscription, but the other way around is less likely to produce interesting results.

There are several reasons why the revision of Horn theories cannot be expressed as the circumscription of a Horn formula. First of all, results of Eiter and Got­ tlob show that reasoning with the revision of a Horn knowledge base is coNP-hard for all operators consid­ ered, while reasoning with Horn theories under circum­ scription is a polynomial task. As a consequence, reduc­ tions from belief revision to circumscription preserving the syntactic form cannot be done in polynomial time (assuming P :j; NP).

Secondly, the result of revising a Horn knowledge base with a Horn formula might be a non-Horn formula. For example, the result of {a, b} * (-.a V -.b) is a :j; b for all operators, and a :j; b cannot be expressed as an Horn formula. On the other hand, the circumscription of a Horn theory is an Horn theory.

6 Analysis and Discussion

In the previous sections we showed new relations relating belief revision operators and circumscription. These re­ lations point out the close connections between the two fields. Many side benefits can be obtained from the es­ tablished relations. In this section we want to point out the most important benefits obtained.

6.1 Compact Representation of NCIRC

In two recent papers [Cadoli et al., 1995a; 1995b] Cadoli, Donini and the present authors analyze the size of the explicit representation of circumscription and belief re­ vision operators. More precisely, taking as an example belief revision, it is determined the size of the smallest propositional formula !{1 that is equivalent to /{*A, where * is one of the belief revision operators analyzed.

As it turns out, the size of the explicit representa­ tion of the result of revising a knowledge base is, in general, exponential w.r.t. IKI + IAI. Differences arise between the various operators. The result of revising a knowledge base using Dalal's revision operator admits a polynomial-sized explicit representation, if we allow new variables in the representation. More precisely, there exists a formula /{ 1 using the letters of /{ and A and possibly new ones, whose size is polynomial in IKI + IAI, s.t. , for any q using only variables of/{ and A we have that K1 f= q if and only if/{ *D A f= q.

We show that N C I RC(T; P, Z) always admits an ex­ plicit representation whose size is polynomial w.r.t. ITI, via the proof given for Dalal's belief revision operator. N C I RC(T; P, Z) is the set of models of T with a least number of elements. Given T and P, we can compute the least number k of true letters, hence the explicit rep­ resentation can be obtained conjoining T with a formula stating that at least k letters of the set P must be true. That is:

where ATLEAST(k, P) is a formula of size O(n 3 ) that we do not show for the sake of brevity.

6.2 Computational Complexity Analysis

A valuable byproduct of the reductions presented in this work is the ability of importing complexity results ob­ tained in one field into the other one. For example, in the general case, inference using the belief revision op­ erators introduced by Satoh, Borgida and Winslett has the same complexity of inference under circumscription. While this result is not novel, it has been proven in [Eiter and Gottlob, 1993; 1992], several other interesting results can be obtained. As an example, it is known that de­ ciding whether a clause follows from the circumscription (with all letters minimized) of a theory composed of bi­ nary clauses (i.e. clauses with at most two literals) is a coNP-hard problem [Cadoli and Lenzerini, 1994]. We can use this result to prove that inference in the revi­ sion of a knowledge base composed of binary clauses is a coNP-hard problem for all operators except Dalal's one.

7 Conclusions

We have presented a complete analysis of the relations between belief revision operators on one hand and cir­ cumscription and its cardinality-based variant on the other hand. Furthermore, we have pointed out the many benefits that the established correlations can deliver to the analysis of both fields.

Our results greatly extends Winslett's results on trans­ forming her revision operator into circumscription pre­ sented in [Winslett, 1989]. Even though Winslett's anal­ ysis could be further extended to deal with other opera­ tors, our results provide us with more direct and simple translations.

Acknowledgments

We want to thank Marco Cadoli and Francesco M. Donini for helpful discussions on the content of this pa­ per.