Results on Translating Defaults to Circumscription

I Introduction

Three systems for nonmonotonic reasoning have been proposed so far ( [1], [2], [3]). Unfortunately little is known about their relative expressive power. It is clear that the logic of McDermott and Doyle is the most (may be over) powerful of the three. However, it is not clear a.t all what is the relationship between two most successful systems: default logic and circumscription. With the exception of the paper by Grosof [4] which dealt with translation of normal defaults into circumscription , very little has been done to explore this relationship ..

Recently McCarthy [5[ introduced the concept of generalized circumscription and simple abnormality theories. In this paper we would like to explore the problem of relative expressive power of default logic and generalized circumscription. We assume that the reader is familiar with the notion of generalized circumscription as presented in [6] and with the notion of simple abnormality theory as in [5]

Both systems have their advantages and disadvantages. The advantage of default logic lies in its conceptual simplicity (it is an easy specification language) and modular structure which is particularly useful in the presence of updates. The disadvantage is the lack of well developed reasoning methods. This is related to the fact that the language of default logic is not first order.

The situation is just the opposite as far as circumscription is concerned. Circumscription uses first order language (with possibly second order scheme) and hence inherits formal reasoning methods of first order logic. The representation of the problem in the form of circumscriptive scheme requires however more skill and is no longer so simple conceptually as the representation in default logic. The possibility of translation between two A possible translation could also help tn providing a semantical grounding for default theory . This is because circumscription, on the contrary to default logic, has a clear model theory, being a modification of the standard Tarskian semantics. Recently Lifschitz [6] showed that the new generalized circumscription (including the prioratized one) is in fact based still on the same semantic principle as the original circumscription - the concept of minimal models with respect to some relation of the partial order. A possible t ranslation from the default logic to circumscription could possibly lead to clear semantics for default logic based on the classical models instead of Kripke structures. Additionally, the semantics based on the notion of the partial order would be particularly attractive since it corresponds to our intuitions: partial order captures the notion of preference implicitly present in the meaning usually associated with default formulas. The semantics based on the partial order IS also probably the simplest one which has the property of beeing global * on the contrary to the local semantics of the classical monotonic logic.

Finally, the description of the class of default theories which can be translated to circumscription would help to establish the limits of the expressive power of the semantics based on the partial order between the models. This is particularly important task since it could draw the line around generalized and prioritized circumscription.

In this paper we introduce the notion of translation between default theories and simple abnormality theories (circumscription). We prove a number of negative and positive results. We are particularly interested in the so called modular translations in which the introduction of the new specific fact does not require recomputation of the whole translation from the beginning. The addition of new defaults or so called general facts (laws) may certainly force us to do such a recomputation. Our definition of modularity requires "additivity" of changes ~ on the level of specific facts . In other words we are interested in translations of default theories with fixed set of general facts and defaults and varying set of specific facts.

We show that normal defaults with prerequisites do not enjoy the property of modular translatability into the circumscription. In fact we prove even a stronger result which is not restricted to "the current version" of circumscription. We prove that no mechanism based on the partial order relation (minimality vs this order) can capture normal defaults with prerequisites. This pessimistic fact is rather surprising , particularly in the context of the other, positive result saying that seminormal defaults without prerequisites can be translated into circumscription in the modular way . We also characterize the maximal class of default theories which have a modular translation into circumscription.

*in a sense of McDermott, the global !!lemantics is the one in which the set of models of the set of formulas cannot be expressed as the intersection

of the sets of models of the formulas of this set

The paper is organized as follows: In the second section we introduce the concept. of order semantics and its relation to circumscription and default theories. In the third second section the main results of the paper are presented.

II Basi~ notions

A. Order semantics

Without loss of generality we consider here only the propositional language. Let L denote such a language. The formulas of L are built from atomic propositions (usually .denoted by letters X,Y) and usual propositional connectives. By ML we denote the set of propositional truth assignments to the formulas of this language, i.e the set of functions from L to the set {T,F} of truth values. By m(A) where A is a sentence of L and m is the truth assignment we denote the truth value of A under m. We will call the truth assignment m the model of A iff m(A) = true. Let :S be the partial order relation (reflexive and transitive) defined over the set ML. Let Wu{ u} be a subset of L. By F< we will denote the semantic consequence relation defined as-follows: W ~u iff u is true in all models minimal with respect to $ in the set of models of W.

The order semantics has two important interpretations: one is related to circumscription, the other is more in a style of default logic. It is not surprising that partial order relation provides a good semantical grounds for these two important nonmonotonic systems. The notion of partial order between the models (truth assignments) corresponds closely to a concept of preference which is the important source of nonmonotonic behavior of the systems under consideration. The general semantics for nonmonotonic logic based on the notion of preference order will be elaborated in a forthcoming paper.

B. Generalized Circums~ription and Order semantics

The generalized circumscription scheme ]6], ]5], has the form:

where A is the formula, X and X' are the predicate (propositional) variables of the same type and < ]R] is the preorder defined between different predicate (propositional) variables of the same type. In this approach ]6] all the predicates, functions and constants are treated as variables when predicate language is assumed. In our case, in the circumscription scheme, X and X' are propositional variables where X is identified with some atomic proposition of L and X' is additional propositional variable (metavariable really) . In general , all the atomic propositions of L will be treated as prppositional variables (not all of them,· obviously will vary in the process of circumscription) . Let us denote by Circum(T]X],X,R) the theory T together with the circumscription scheme. The above scheme with preorder relation was proposed to capture a new generalized version of circumscription proposed by McCarthy in ]5]. Intuitively, the preorder relation R is intended to generalize the partial order relation (set theoretical inclusion of extensions of the predicates) corresponding to the original version of circumscription ]1]. The scheme presented here shows that the new circumscription is essentially founded on the same principle - minimalization with respect to the preorder R. The circumscription scheme expresses the fact that we are looking for the predicate X which satisfies A and is ~ with respect to the preorder relation R. It is easy to see, that having the order relation R defined between the predicate variables we can build the order relation < between the models of the language under consideration in such ~ way that:

For example in the case of propositional language, if X is a propositional variable which is minimized in the circumscription, X' is the variable of the same type that X and Y is the set of propositional variables of the language L which are the parameters of the circumscription the corresponding order relation $ can be defined as follows

ml $ m2 iff( ml(Y)=m2(Y) for every YE }'} and (X]ml(X)) $ 1RJ (X'Im2(X)). Where (XJY) denotes the result of the substitution of Y for X.

In case when X is the sequence of variables the substitution is defined componentwise.

We will further consider the so called simple abnormality theories ]5]. The language of these theories is extended by additional propositional variables(in his paper they are predicates, since he deals with the predicate language) called abnormality variables. These variables are the primary target .of minimalization in circumscription. In other words the corresponding order relation between the set of models is induced by the order between abnormality variables. Because of the lack of space here the reader is referred to ]5] for a more detailed presentation. In the paper we will identify circumscription schemes with the partial order induced by them over the set of models . We will use more semantic oriented notation (T, $ ) to denote the theory T and partial order relation induced by the circumscription scheme. In particular, when the theory is not circumscribed, the corresponding order relation will make all the models incomparable.

C. Default logi~ and order semantics

We will use here a standard terminology introduced by Reiter ]3]. The defaults will therefore be denoted in a format of inference rules: Ar(B) . The formula A will be called the prereguisite of the default . The default will be called normal if B:C, seminormal if B::)C ( ]71). By W we will denote the set of facts and by D the set of defaults of the default theory (W,D) .

It turns out that the order relation between models has a direct and natural interpretations in terms of default statements. By E(m) let us denote the conjunction of all atomic propositions or their negations for which m is a model. This formula forms the finite representation of the set of all formulas which are true in the model m ( we assume there is a finite number of propositional constants in the language) .

On the beginning let us assume that the order relation :S has such a form that ml and m2 are the only models such that ml<m2 holds (strict inequality). All the other models are incomparable. We are going to "reconstruct" this order relation in terms of default and later generalize the same pattern of reasoning for the arbitrary order.

If ml<m2 we know that for any set W of formulas such that mlEM(W) (M(W) is the set of models of W) we have:

The explanation of this is simple: since m2 cannot be minimal in the set of models of W ( ml is there too) , it can as well be eliminated. This can be equivalently expressed by the following default rule:

Indeed , this rule says that if E(ml) is consistent with W, which means that the model ml belongs to the set of models M(W), than ~ E(m2) can be assumed. The latter, in model theoretic interpretation means that the model m2 is eliminated from the set of models of W. This is, however precisely what the above, model theoretic interpretation of the partial order, says.

Therefore, more generally

where 1- 0 denotes the syntactic consequence relation for default theories (i.e (W;D}I- 0 u iff u belongs to every extension of (W;D)) and ~ is the specific partial order relation assumed above.

Generally , with any partial order relation defined over the set of truth assignments of the propositional language we car associate the set of seminormal defaults without prerequisites in a sense that

Where D(~ ) indicates that the set of defaults D depends on the order relation ~ - The proof ts by a si'mple construction similar as above.

The default reconstruction of the partial order ~ does not play an important role in this paper (at least in the first part). We presented it here to show that the notion of order can be used to construct semantics for defaults , at least for some classes of them. The construction above will also be helpful m understanding the proofs.

Later in the paper we will use the following simple lemma:

Lemma 1: Let the order ~ have the following property: For any model ml of the formula A there exist a model m2 such that m2(~A)=true and m2<ml than:

This follows from the above considerations about default reconstruction of partial order.

We will now formally define the notions of translation and representation .

III Main results

A. The concept of translation

Both default theories and simple abnormality theories have t.wo components:

• specific facts
• general facts

General facts correspond . roughly speaking . to the time invariant properties of the real world which is modelled by a system under consideration and to some properties of the system itself. The general properties of the world have the form of general laws (like " all the ostriches are birds") , the defaults represent " general" attitude (preferences) of the reasoner . Sp~cific facts , on the other hand correspond to the particular instance of the world under consideration and may have the form "bird(joe)" or " ostrich(mary)" etc. The updates of specific facts and general facts have a different meaning - they occur on the different levels of abstraction. McCarthy in his characterization of simple abnormality theories makes a sharp distinction between these two types of facts:

-the general facts involve usually abnormality variables

-the specific facts do not involve abnormality variables

We will make this distinction explicit and view a default theory as a triple <WpW,,D> where Wr is the set of facts, W, is the set of general (monotonic) rules and finally D is the set of defaults. For the sake of conciseness of notation we will refer to both W r and D by D (a set of defaults and general rules). Abnormality theories will be viewed simply as < Abf>Ab,,~ > where the first two elements have the same meaning as in default theory and ~ is the partial order corresponding to circumscription scheme.

One must be very careful when defining the notion of translation. First of all we have to decide - what are we going to translate?

By translation, we mean reformulating the general facts represented in default theory into general facts specified in abnormality theory. For example (see [5]) the translations of general facts to abnormality theory set may have the form ~ab(aspectl , x) :::J~flies(x) or ostrich(x) :::J ab(aspect2 ,x) for the "bird" example. Intuitively, the abnormality predicates (propositions) reflect typical and atypical properties of objects under consideration. We insist that the specific facts remain unchanged since it is the case in simple abnormality theories (see [5]}. Therefore we are interested in translating specifications not particular instances.

Formally,we say that the set of defaults D is modularly translatable or representable Ql'. the order semantics iff there exist a set of formulas Ab, and the order relation ~ such that for every set W of the of specific facts from the language L and for every formula u we have

The set of formulas Ab, is expressed m some extended language L' :::JL, which results from L for example by simply adding propositional variables ,like abnormality variables. The order ~ is defined over the models of extended language L' In terms of circumscription this simply means that we can possibly minimize on abnormality predicates. In other words, the circumscription schema may involve additional variables

(abnormality variables) which do not belong to L. Notice that we do not limit here in any way the number of additional variables introduced to the language L. In order to establish translatability it is sufficient to find ~ extension of L which would make a translation possible.

Modularity is the desirable property of translation both from the conceptual and computational point of view. This is the case simply because every time an update is made and a new specific fact is taken into account we do not have to " recompute" or change the existing content of our database (i.e incremental updates of specific facts in default theories are also incremental for abnormality ones). Besides, from the conceptual point of view it preserves the clear distinction between specific facts and general facts by translating "separately" (or modularly) specific a.nd general facts. Finally, the modular translation is the only case when we really can say that the translation of the set of defaults into circumscription exists, 1.e there 1s a single reformulation of general facts ("time invariant" properties) expressed in the default theory in the abnormality theory.

We may certainly consider nonmodular translations (in fact as we will show in this paper , in many important cases we have to) in which the order :<::; is fixed (for the give D) but the set Ab, will depend on the set of specific facts W. In this case however each new specific fact added to the default theory will require a recomputation of the "old" translation . It is therefore hard to talk here about single translation of D, we rather get a family of translations. A good example of such a nonmodular translation is provided in database theory. The translation of Closed World Assumption into the completed database [8) is nonmodular. Indeed , the addition of new atomic facts changes the completion axiom.

Generally speaking, it may be just as difficult to compute the nonmodular translation as just to compute the extensions of the default theory. In such a situation translation does not make much sense. For instance, we could provide such an "expensive" translation, given the default theory A:~(B) by constructing a translation to the ordinary propositional theory in the following way: if A is derivable from W and ~B is not than translate W to Wu {B} otherwise leave W unchanged . This is the kind of nonmodular translation which w~ certainly want to avoid.

Finally let us point out that if the set of defaults D is changed than obviously even the modular translation allows both changing the :<::; order relation and the set Ab,. The same may happen if the new general rules are added . This is simply because we may then assume that this is not the instance of external world which has changed but rather specification of the system. We do not talk here about such changes restricting ourselves to the changes of the specific facts of the system.

B . Main Results - negative part

We are here interested m:

1. describing the class of default theories which can be modularly translated into abnormality theories.
2. Determining what is the advantage of abnormality propositions. In other words we would like to establish whether there exists a class of defaults which are translatable when the abnormality variables are used, but· are not translatable when we do not use

these additional variables(predicates).

We present now our mam negative result :

Theonm 2: e se o e au ts Th t f d f I D-- { A:~(B) } where B is independent of A ( i.e both {A , ~B} and {A,B} are consistent ) is not modularly translatable into abnormality theory , no mat ter how many abnormality

variables are introduced.

Proof

Suppose there is such a translation. Let Ab be the corresponding formula {Ab, ) and let :<::; be the resulting order relation . Let us take W to be {A) or any set which implies A. Without the loss of generality let us assume that both {A , ~B} and {A,B} are consistent . Than for any model ml such that ml(AAAbA~B)=true there must exist a model m2 such that m2(AAAbAB) is true and m2$ ml. Notice that { A,A b, ~B)} must be consistent. Indeed , otherwise the consistent theory {A,B) would be translated into the inconsistent one. Let now W= 0. By lemma 1 and the definition of our order relation S we have 0 t=:-:; Ab:J (A:JB) . Hence, since Ab is true in every minimal model of $ , we obtain simply by modus ponens, that

This is however not the case in the original default theory: it is not true that(0,D) i- 0 (A:JB) . Since the order relation and the formula Ab were chosen arbitrarily, we have proved our theorem.

Notice here that if either {A,B} or {A,~B} are inconsistent the situation 1s trivial, smce the above default IS totally redundant .

Let us now point out an important difference between the defaults A:jt(B) and :M1;~B) The second default is easily translatable by circumscription , the first one as our theorem points out is not . In his paper Grosof [4) claimed t hat he has provided translation of the normal defaults with prerequisites (i.e. of the first type) into circumscription, while in fact his construction is correct only for t he defaults of the second type. The important difference between these two types of defaults is best seen when we consider two default theories with defaults:

birdfxj:M{fly(x)) and :M~bird(xrl :Jflf(x)) J t' 1 d th

fly x b1r (x) :J y(x respec 1ve y an e same set of specific facts W= {black(a)} . If we do not know whether "a" is a bird or is not we do not want to conclude that if "a" is a bird that it would fly , since" a" may turn out to be an atypical bird . The first default would not give this answer (i .e(Bird(a) :Jfly(a)), while the second one would .

The above result is definitely a pessimist ic one, specially because normal defaults with prerequisites constitute the most important class of defaults. The result indicates that it is possible only to construct nonmodular translations. This in turn faces ·a danger that the overall cost of translation in terms of both the size of the abnormality theory and the time required to compute it may be higher than deduction using the original default theory. In fact the large size (the number of formulas) of abnormality theories corresponding even to simple defaults (see the papers ]6], ]5]) reinforces this apprehension.

Notice aJsc, t.hat our re"tlt can he formul ated even in t he stronger way: as long as circumscription is based on the minimalization versus some arbitrary order , t he modular translation of normal defaults with prerequisi t ies is impossible. This is because, a.s we demonstrated, no partial order between the models can capt ure normal defaults with prerequisites.

C. Main Results - positive part

We will now characterize those defaults which are translatable into simple abnormality theories. We will also address the second of our previous questions describing the class of defaults whose translatability require the presence of additional abnormality variables, i.e. the defaults which otherwise are not translatable. Therefore, the answer for our second question about the usefulness of additional abnormality variables is positive.

Lemma 3: Seminorma.l and normal defaults without prerequisites are modularly translatable into circumscription even without abnormality variables.

Proof

Let :M(i/\A) be a seminormal default without prerequisite. We can show that if we define the order relation :<:: between the models as ml :Sm2 iff ml(B/\A) = true and m2(~A)=true or if m 1

= m 2 than we have for every 11 , W :

where the partial order is defined on the truth assignments to the language L without introducing additional abnormality variables. Notice also that in this case Ab = 0. r

The translation obtained here is the direct consequence of the correspondence between defaults and partial order as described in the second section. We cannot apply this mechanism however for the arbitrary defaults which are not necessa.rilly seminormal. Indeed the default ~) such that B/\~D is not false would get us rather the order equivalent to the default ~~ This follows directly from the construction of the order relation a.s in section 2 or as in the lemma 2. It is interesting to observe that seminormal defaults are "special" from the point of view of the order semantics and that seminormality is in fact critical to translatability into the order semantics.

In general it can be showed that arbitrary combination (and also ordered combination) of seminormal defaults can be translated modularly into circumscription.

·"'~~ t?;,n~ default we mean the. default of th~ form ~ where n> l. If n= l we wtll talk about smgular defaults. Now let us present the result related to the usefulness of additional abnormality variables.

Lemma modularly abnormality 4: Multiple seminormal defaults are not translatable into circumscription unless variables are introduced .

Proof:

Let us consider a seminormal default D of the form

: M(B~ ·) /\A ) .. \1( B 2 /\A ) Th i;; def· ult i;; 11 01 r·'J>re,en tal>le l>) any order relation <. if il i;; to be defin Pd only on t he truth assignments for the language L wi t hout additional variables a.bi . We will demonstrate this by showing that if this default is to be representable by the order :<::, this order relation would also represent the other defaults: :M(Bl /\A) and :M(Bl /\A)

Let W= { ~Btv~B2} . The order :<:: must be defined in such away that for any model m such that m((~Btv~B2) /\~A) is true there must exist a model m' such that m':<::m and m'((~Bt)v~B2) /\ A) is true. This must be the case since A must be implied . But then if we take W={Bl/\~B2} we will get WI-:.:: A contrary to the definition of the default D. Therefore no order defined solely on truth assignments to L can help. In what sense, therefore, the extension of the language L by the new variables can help? To show this let us extend the the language L by the new propositional variable p. Let us now define the order relation on the structures of the extended language in the following way: For every model ml such that ml(~AAp)=true and every model m2 such that m2(Bl /\A) = true put m2 :<;ml. For every model m3 such that mS(~A/\~p)=true and every model m4 such that m4(B2/\A) = true put m4 :<;m3 . Make all the other models incomparable. It is easy to see that the order :<:: represents the default D.

Indeed for W={~Blv~B2} the models of Bl /\A and the models of B2/\A are the minimal elements of M(W) .

Therefore:

On the other hand if W= { ~Bl , B2} then there are minimal models in M(W) in which ~A is true (the models of ~A/\ p) . This blocks the inference of ·A. A similar situation arises when W={Bl/\~B2} . Therefore the extension of the language L by a. single propositional variable p allows to represent the default which otherwise would not be representable. This is achieved through "splitting" of the models of~A into two classes: models of ~A/\p and models of ~AA~p . The variable p has the same character as abnormality variables - it is irrelevant by itself, it only "helps" to define the order relation properly.

One may argue that multiple defaults ·are not practically applicable. We do not discuss this point here. We have only established the technical result which shows the essential difference between multiple and singular defaults.

We will discuss now the problems of representation of the various combination of the set of defaults. We will introduce here the notion of inference rule as the generalization of monotonic (modus ponens, generaliza.tio~resolution etc) and nonmonotonic (defaults)

inference rules.

Definition 1:

Let L be a propositional language. By the inference rule r over L we mean an arbitrary binary relation defined over P(L )xL where P(L) is the power set of L. If <W,<r> Er then we will say that <T is derivable from W by a single application of the inference rule r. We will say that the rule r is applicable to the set W if there exist the tuple <W,<r>Er for some <T not from W. We will assume that <W,<r >Er for any <rEW. By r(W) we will denote the following set k <W,\>Er) . If r is inapplicable to W we will put r(W) =W. We will define the following operations on inference rules which derive new inference rules from the given ones:

1. Intersection. Denoted by r 1 n r 2 . Intersection corresponds to a separate, independent application of the rules r 1 and r 2 and selecting only these formulas which could be obtained independently by the first and by the second inference rule.
2. Composition. <W,<r>Er 1 .r 2 iff <rEr 1 .r 2 (W). Composition of inference rules corresponds to priority (in this case of the second rule over the first one)

Our definition of inference rules is very general. We would like now to put some restrictions on them. First we assume that our rules are idempotent in a generalized sense th~t is r 1 .r 2 .r 1 (W= r 2 .r 1 (W) if r 1 (W);FW) . In this way we will treat a standard first order syntactical consequence relation as single inference rule r (than of course we have r.r(W) = r(W). To allow multiple extensions we do not assume in general that our inference rules have Church - Rosser property. We will now introduce the third operation of parallel composition, which under the above idempotence assumptions is definable in terms of the previously defined operations.

Definition 2.

By the parallel composition of the inference rules r 1 and r 2 we will mean the following operation:

Parallel compositiOn corresponds to the intersection of the set of formulas obtained by applying t 1 and r 2 in the different order. The reason for using "triple" composition is that the application of the rule r 1 may make the application of r 2 possible when it was not the case before. The second application of r 1 cannot however change anything according to our principle, therefore three compositions are enough.

Introduction of these formalisms will help in establishing the class of general inference rules which are representable by the order semantics. In a way therefore we will be able to determine the limits of this semantics. Besides that the formalism enables us to be more general and not to restrict ourselves to any particular semantics associated, for example, with combination of defaults (if they are our basic inference rules). For example for the same set of defaults a number of different definitions of the corresponding combination can be provided. Compare for example proposals of Reiter J3] and Lukaszewicz J9] or the different possible definitions of extensions of the default theory in which W = {A v B} and D = { A:M~C) B:M~D l} where CvD may (logic of McDermott and Doyle) or may not be implied (Reiter's default theory). We do not want in our study to comit ourselves to any of these possible semantics of the com bin at ion of defaults, since there is no agreement about them. Instead, we rather want to have a formal apparatus to express and study the problem of translatability for all these alternative definitions of combinations of defaults. Besides we can also define the ordered (prioratized) combination of defaults through the operation of composition applied to the default rules r 1 and r 2 .

Now let us define what does it mean for the general inference rule to be represented by the partial order between the structures of L.

Definition 3

The inference rule r over L is representable (translatable) by the partial order :::; defined over the set of truth assignments of some extended language L' iff there exist a formula Ab such that

Notice that if r is the syntactical consequence of propositional (predicate) logic than the corresponding partial order relation is trivial. It is defined over truth assignments of L in such a way that any two different assignments are incomparable. This definition is a generalization of the previous one in a sense that we can now talk about various combinations of defaults. Let us now present the main positive results of this section:

Theorem 5: If r 1 and r 2 are representable by the partial order so are r 1 .r 2 and r 1 Jr 2 .

The proof follows by the construction of the order relation corresponding to r 1 .r 2 (r 1 Jr 2 ) from the order

relations corresponding to r 1 and r 2 .

The operations of composition and parallel compositiOn of the inference rules are important - they correspond to the (ordered and unordered) composition of the set of defaults. We have here as the direct consequence of the theorem 2 and preceding lemmas the following result

Theorem 6: Arbitrary combination (ordered and unordered) of the set of seminormal defaults without prerequisites is representable by the circumscription.

The combination of defaults which we have in mind can have both the semantics in the Lukasiewicz and Reiter sense. In fact showing the representability for Lukasiewicz semantics is easier - we can apply directly theorem 2 (for parallel combination of the inference rules). To show it for Reiter's definition of extension requires transformation of the set of defaults to the equivalent set for which the parallel composition can be used. The main reason for why we have to do this is that in Reiter's definition of extension it is not sufficient to apply applicable defaults - the consequents of defaults should not contradict the premises of the

other defaults.

In fact we have even the stronger result - the complete characterization of the expressive power of the order semantics in terms of default theories.

Theorem 7: translatable to theory) iff it is unordered) of The default theory is modularly circumscription ( simple abnormality equivalent to the combination (ordered, the seminormal defaults without prrreq u is i tes Two sets of default s are considered equiYalent here if t hey lead to the same sets of conclusions for the same set of facts.

In one direction the theorem is the direct consequence of the previous one soundness). Completeness follows from the "reconstruction" of the set of defaults from the partial order relation as described In the first section. The above result provides therefore a precise limi t to the expressive power of the order semantics, if we restrict ourselves to the classical models.

IV Conclusions

It ts important to establish the formal criteria of translatability between different nonmonotonic systems. There are many potential advantages, inter alia, the possibility of determination of limits of the systems under consideration. In this paper we have provided such a criterion for two important nonmonotonic systems and we have established a number of positive and negative results. The negative result obtained here has rather disappointing consequences for a perspective of "clean" modular translations from the default theories to circumscription as long as circumscription is based on one fixed partial order relation induced over the set of models. In fact we proved that there is no partial order between the models which could capture the important class of normal defaults with prerequisites. One way out is to make a circumscription "conditional" by changing the circumscription axiom to the conditional formula "if C then < Circumscription axiom>. In this way instead of one single order relation we would have rather a family of order relations (possible semantic orders), and depending on the theory which is going to be circumscribed the particular circumscription axiom would be selected ( or in other words the particular order relation would be chosen). This will lead however to even more complex proof theory and may be not worth the effort overall.

The order semantics considered here is interesting by itself as an intuitive and attractive formally candidate for semantics of nonmonotonic logic. It remains to be investigated what are the limi ts of this semantics especially if w reconsider the order semantics also for nonclassical models like for example Kripke structures. As the semantical tool order semantics can be used to establish various equivalence results. For example one may be interested in determining whether one set of defaults is equivalent to another. We may also be interested in a more restricted quest ion whether two sets of defaults are equivalent modulo particular sublanguage, i.e. the set of conclusions if restricted to this sublanguage are the same. The other question which can be successfully answered on the basis of order semantics is the characterization of the class of formulas with respect to which the given system is monotone.

These topics and the extension of the order semantics to capture more expressive power are the subject of a forthcoming paper.

Acknowledgement

The comments of Alex Borgida, Ray Reiter and anonymous referee are gratefully acknowledged.

• I 1] McCarthy,J . "Circumscription - a form of nonmonotonic reasoning." AI. 13:1 {1980) 27-39.
• McDermott ,D. and Doyle,J . "Nonmonotonic log ic 1." AI. 13:1 (1980} 41-72.
• Reiter,R. "A logic for default reasoning." AI. 13:1 (1980) 81-132.
• Grosof,Benjamin "Default reasoning as circumscription." In Work$hop in Nonmonotonic Logic . AAAI , Oct , 1984.
• McCarthy ,John "Application of circumscription to formalize common sense knowledge." In Workshop in Nonmonotonic Logic. AAAI, Oct , 1984.
• Lifschitz, Vladimir "Some results on circumscription." In Workshop in Nonmonotonic Logic. AAAI , Oct , 1984.
• Reiter,R. and Criscuolo,G. "On interacting defaults." In International Joint Conference on Artificial Intelligence . AAAI , 1981, 270-276.
• Reiter, R. , "On closed world databases." In Logic and databases . Plenum Press, 1978, .
• Lukaszewicz,Witold "Considerations on default logic." In Work$hop in Nonmonotonic Logic . AAAI , Oct, 1984.