Curb Your Theory! A Circumspective Approach for Inclusive Interpretation of Disjunctive Information

1 Introduction

Circumscription [McCarthy, 1980]looks to many as one of the most promising principles for formalizing com­ monsense reasoning. However, as recently pointed out by Raymond Reiter [Reiter, 1992], it runs into problems in connection with disjunctive information. The mini­ mality principle of circumscription often enforces the ex­ clusive interpretation of a disjunction a V b by adopting the models in which either a or b is true but not both . There are situations in which an inclusive interpretation is desired and seems more natural. Consider the follo­ wing example due to Reiter. Suppose you throw a coin into an area which is divided into a black and a white field. Circumscription applied to

black_field(coin) V white_field(coin)

excludes that the coin falls into both fields and tells you that the coin is either in the white or in the black field . This is certainly not satisfactory. An extension of this example is even more impressive. Imagine a handful of coins thrown onto a chessboard; circumscription tells us that no coin touches both a black and a white field . It is not clear whether any of the well-known variants of circumscription ( cf. [Etherington, 1988]) can suitably handle inclusive disjunction of positive information.

·This is a short version not providing detailed proofs of all results. Full proofs and more results will appear in an extended report .

Yuri Gurevich

Electrical Engineering and CS Department University of Michigan

Ann Arbor, MI 48109-2122, USA

In this paper we suggest an approach to tackle the problem pointed out by Reiter . We present the curb me­ thod, which is a generalization of circumscription able to handle inclusive disjunctions of positive information properly. Our method relies on the new concept of mi­ nimal upper bound models. Intuitively, a minimal up­ per bound model corresponds to a minimal model for the inclusive interpretation of disjuncts. Using this con­ cept, we develop the notion of a "good" model of a first­ order theory. Although the concept is more involved than circumscription, we show that "good" models can be captured like circumscriptive models in second-order logic. 1 Furthermore, inferencing from the good models of a propositional sentence is feasible in quadratic space; we show that for a reasonable approximation of the good models this problem is no harder than inference from cir­ cumscriptive models.

The rest of this paper is organized as follows. Section 2 considers additional examples and introduces informally the concept of good models . Section 3 provides a formal definition and a logical description. Section 4 examines aspects of computational complexity, and Section 5 ad­ dresses approximation issues. Section 6 reviews related work and concludes the paper.

2 Good models

Let us consider two additional scenarios in which an in­ clusive interpretation of disjunction is desirable. Models are represented by their positive atoms .

Example 1: Suppose there is a man in a room with a painting, which he hangs on the wall if he has a hammer and a nail. It is known that the man has a hammer or a nail or both. This scenario is represented by the theory T1 in Figure 1. The desired models are h, n, and hnp, which are encircled. Circumscribing T1 by minimizing all variables yields the two minimal models hand n (see Figure 1) . Since p is false in the minimal models, cir­ cumscription tells us that the man does not hang the painting up. One might argue that the variable p should not be minimized but fixed when applying circumscrip­ tion. However, starting with the model of T1 where h, n and p are all true and then circumscribing with respect to h and p while keeping p true, we obtain the models hp and np, which are not very intuitive. If we allow p to vary in minimizing h and n, the outcome is the same as for minimizing all variables. On the other hand, the model hnp seems plausible. This model corresponds to the inclusive interpretation of the disjunction h V n. 0

1 By using a second-order predicate constant. However, it is quantification which counts for the order of a formula [van Benthem and Doets, 1983].

Example 2: Suppose you have invited some friends to a party. You know for certain that one of Alice, Bob, and Chris will come, but you don't know whether Doug will come. You know in addition the following habits of your friends. If Alice and Bob go to a party, then Chris or Doug will also come; if Bob and Chris go, then Alice or Doug will go. Furthermore, if Alice and Chris go, then Bob will also go. This is represented by theo~y T2 in Figure 2. Now what can you say about who w1ll

come to the party? Look at the models of T2 in Figure 2. Circumscription yields the minimal models a, b, and c, which interpret the clause a V b V c exclusively in the sense that it is minimally satisfied. However, there are other plausible models. For example, abc. This model embodies an inclusive interpretation of a and b within a V b V c; it is also minimal in this respect. abd is another model of this property. Similarly, bed is a minimal model for an inclusive interpretation of b and c. The models ad, bd and cd are not plausible, however, since a scenario , 0 in which Doug and only one of Alice, Bob or Chns are present does not seem well-supported. 0

In the light of these examples, the question arises how circumscription can be extended to work satisfactory. An important insight is that such an extension must take disjunctions of positive events seriously and allow inclusive (hence nonminimal) models, even if such mo­ dels contain positive information that is not contained in any minimal model. On the other hand, the fruit­ ful principle of minimality should not be abandoned by adopting models that are intuitively not concise. Our idea is the synthesis of both: adopt the minimal inclu­ sive models. That is, adopt for minimal models M1, M2 any model M which includes both M1 and M2 and is a minimal such model; in other words, M is a minimal upper bound ( mub) for M1 and M2.

To illustrate, in Example 1 hnp is a mub for h and n (notice that hn is not a model), and in Example 2 abc is a mub for a and c; abd is another one, so several mub's can exist. In order to capture general inclusive interpre­ tations, mub's of arbitrary collections Mt, M2, M3, .. . of minimal models are adopted .

It appears that in general not all "good" models are obtainable as mub's of collections of minimal models. The good model abed in Example 2 shows this. It is, ho­ wever, a mub of the good models a and bed (as well as of abc and abd) . This suggests that not only mub's of coll­ ections of minimal models, but mub's of any collection of good models should also be good models.

Our approach to extend circumscription for inclusive interpretation of disjunctions is thus the following: adopt as good models the least set of models which contains all circumscriptive (i .e. minimal) models and which is closed under including mub's. Notice that this approach yields in Examples 1 and 2 the sets of intuitively good models, which are encircled in Figs. 1 and 2.

3 Capturing good models formally

We give in this section a formal semantical definition of good models of a first-order sentence, and we provide a logical sentence which describes the good models . We assume ZFC, i.e. Zermelo-Fraenkel Set Theory with the Axiom of Choice, as a standard metamathematical frame [Suppes, 1972].

As for circumscription, we need a language of higher­ order logic ( cf. [van Benthem and Doets, 1983]) over a set of predicate and function symbols , i.e . variables and constants of finite arity n 2: 0 of suitable type. Recall that 0-ary predicate symbols are identified with propo­ sitional symbols.

We use set notation for predicate membership and in­ clusion. q E p means that p(q) is true, p ~ q that p im­ plies q, and p C q that p strictly implies q. (3p~q ~(. . . ) denotes 3p(p0q & ... ) where (} is E, ~' or C; Slffillarly (VpOq)( . . . ) denotes Vp(p(}q---+ .. . ). A sentence is a for­ mula in which no variable occurs free; it is of order n + 1 if the order of any quantified symbol occurring in it is < n [van Benthem and Doets, 1983].

- A structure M consists of a nonempty set IMI and an assignment I(M) of predicates, i.e. relations (resp. func­ tions), of suitable type over IMI to the predicate (resp. function) constants. The object assigned to constant C, i.e. the extension of C in M, is denoted by [C]M or simply C if this is clear from the context. Equality is interpreted as identity. A model for a sentence rp is any structure M such that rp is true in M (M I= rp).

Let p = p1, .. . , Pn be a list of first-order predicate con­ stants and z = z1, ... , Zm a list of first-order predicate or function constants disjoint with p . For any structure M, Jet M~{z be the class of structures M' such that IMI = IM'I, and [C]M = [C]M' for every constant C not occurring in p or z. The pre-order ~:Jz on Mt{;z is defined by M1 ~tJ;z M2 iff [p;]M, ~ [p;]M, for all 1 ~ i ~ n . The pre-order ~p ; z is the union of all ~tJ;z over all structures. We write M:t etc. if z is empty; ~:: and ~p are partial orders on M~ resp. all structures.

The circumscription of p in a first-order sentence rp(p, z) with z floating is the second-order sentence [Lif­ schitz, 1985]

which will be denoted by Circ( rp(p, z)) (p and z will be always presupposed) . Here p', z' are lists of predicate and function variables matching p and z and p C p' stands for (p' ~ p) & (p' f p), where (p' ~ p) is the conjunction of all (Pi ~ p;), 1 ~ i ~ n . The following is a straightforward consequence of the definitions.

Proposition 3.1 [Lifschitz , 1985] M I= Circ( rp(p, z)) iff M is ~p;z-minimal among the models of rp(p, z).

3.1 formal definition and logical description

We formally define the concept of a "good" model as follows . First define the property that a set of models is closed under minimal upper bounds.

Definition 3.1 Let rp(p, z) be a first-order sentence. A set M of models of rp(p, z) is ~p ;z - c/osed iff, for every M' ~ M and any model M of rp(p, z) , if M is ~p;z-minimal among the models of rp(p, z) which satisfy M' ~p; z M for all M' EM' then ME M .

Clearly the set of all models is closed . Further, every closed set must contain all ~p ;z-minimal models of rp(p,z) (let M' = 0) ; the empty set is closed iff rp(p,z) has no minimal model. We define goodness as follows .

Definition 3.2 A model M of rp(p, z) is good with re­ spect to p ; z iff M belongs to the least p ; z-closed set of models of rp(p, z) .

Notice that good models only exist if a unique smallest closed set exists. The latter is immediately evident from the following characterization of goodness.

Proposition 3.2 A model M of rp(p, z) is good with re­ spect to p; z iff M belongs to the intersection of all p ; z­ closed sets.

In the rest of this section we show how to capture goodness by a logical sentence Curb(rp(p,z);p,z) whose models are precisely the good models of rp(p, z). Similar to circumscription, p are the minimized predicates (here under the inclusive interpretation of disjunction), z are the floating predicates, and all other predicates are fixed.

For ease of exposition, we restrict ourselves here to the simplest case where p contains a single unary pre­ dicate p (hence the domain D of p is IMI 1 = IMI) and z is empty. The generalization to arbitrary p and z is straightforward.

We consider in the following an arbitrary but fixed as­ signment to all constant symbols except p over a fixed universe, i.e. we consider structures in some fixed M~. We assume that p 1 , q 1 , r 1 , . . . range over the extensi­ ons [p]M' in the models M' of rp(p) from M~, and that p 2 , q 2 , r 2 , ... range over families of such extensions. Technically, this can be asserted by adding rp(p 1 ), rp( q 1 ) etc. and Vq E p 2 (rp(q)), Vq E q 2 (rp(q)) etc. in suitable places.

We now express a mub of the family p 2 as the formal expression Mub, which says that q 1 is a minimal upper bound of p2.

The formula Cl(p2) says that p2 is closed under minimal upper bounds.

Using Cl(p2), we define a formula Good(p2) as the smallest p; z-closed set, which intuitively captures the good models of rp(p) from M~ .

Good(p 2 ) is true within M~ for a unique p 2 .

Proof. Assume this is false for some M, i.e. M I= Good(p2) & Good(q2) for some p2 ,q 2 such that p2 f q 2. Let r 2 = p 2 n q 2 . Clearly M I= Cl(r 2 ). Since r 2 c p 2 or r 2 C q 2 , it holds that M t Cl( r ) & ·(p 2 ~ r 2 ), say. This implies M ~ Good(p ). This gives the desired contradiction. 0

Using Good(p2), we define the curb of rp(p) as the sentence Curb(rp(p);p) :

Theorem 3.4 A model M of rp(p) is good with respect top iff M I= Curb(rp(p);p) .

It should be clear how Curb(rp(p);p) generalizes to Curb(rp(p;z);p,z) for arbitrary p and z.

3.2 second-order definition of Curb(rp(p,z);p,z)

Notice that Curb(rp(p);p) is a third-order sentence (due to 3p 2 (- · ·) and Vr 2 (- · ·) within Good(p 2 )), while Circ(rp(p)) is second-order. We present in this section an equivalent definition in terms of a second-order sentence Curb · ( rp(p ); p) which characterizes the good models of rp(p). A second-order sentence Curb·(rp(p,z);p,z) for arbitrary p and z is obtained analogously.

The rationale of what we are going to do in this section is as follows. We first define the metalinguistic notion of a-goodness for all ordinal numbers a . Roughly speaking, a model of a first-order theory T is a-good if it can be obtained from the minimal models by iteratively adding a times all minimal upper bounds. The notion of a­ goodness of a model can be expressed in a two-sorted second-order logic whose one sort are the ordinal num­ bers. We show that in each structure, it is sufficient to consider only those ordinals a for which it holds that llall ~ IIDII, where D is the domain of p. But precisely these ordinals are isomorphic to well-orderings of parts of D and are thus expressible in second-order logic. Our last step thus consists in converting the two-sorted de­ finition of goodness into plain second-order logic (with no specially interpreted predicates) by replacing ordinals with well-orderings.

Definition 3.3 good(p 1 ) +-+dJ 3a. a-good(p 1 ), where

We show that this notion of goodness is equivalent to the one captured by Curb(<p(p);p).

Lemma 3.5 A model M of <p(p) is good with respect to p iff good( [p]M) holds true.

Proof. (Sketch) Let q 2 = {p1 : good(p 1 )} . ( i) We show that M f= Cl(r 2 ) implies q2 <; r 2 . Prove by in­ duction on a, that for every r 2 such that M F= Cl(r 2 ), r 2 contains every a-good r 1 . (ii) We show that M F= Cl(q 2 ). Suppose r 2 <; q2 and M f= Mub(r 2 ,q 1 ). Define /1 = sup{ a :. r 1 E r 2 , r1 is strictly-a-good}. It follows that q 1 is (/1 + 1 )-good, hence q 1 E q 2 . ( i) and ( ii) imply M F= Good(q 2 ). The result follows from Lemma 3.3 and Theorem 3.4. 0

An important observation is that goodness of any p 1 is equivalent to a-goodness for an a which depends on the domain D of M.

Lemma 3.6 For every domain D there exists an ordi­ nal av such that good(p1) +-+ av-good(p1) for every p 1 . Moreover, llavll S IIDII·

Proof. (Sketch) Show by induction on a, that if p 1 is strictly-a-good then IIP 1 II ~ llall · The lemma follows . 0

Now consider the extension of second-order logic where it is allowed to use ordinals of cardinality S IIDII· Formally, one can think about a two-sorted structure. Greek letters range over ordinals. We define recursively a second-order predicate constant G( a, p1 ), which cap­ tures a-goodness within the logical language.

In particular, G(O,p 1 ) +-+ Circ(<p(p 1 )). If G(jJ,r 1 ) is equivalent to /1-goodness of r 1 for /1 < a, then G( a, p 1 ) says that there is no q 1 C p 1 such that every ( < a)-good subset r 1 of p 1 is also a subset of q 1 .

Lemma 3.7 G(a,p 1 ) is true iffp 1 is a-good .

Proof. By induction on a . The case a = 0 is trivial. Suppose a > 0.

"+-": Suppose p1 is a-good. By definition of a­ goodness, there is a collection q2 that witnesses this fact . In particular, M ub( q2, p1) holds. Suppose that q1 satis­ fies q1 C p1. By the definition of Mub( q2, p1 ), p1 is a minimal extension of p such that r 1 <; p1 for every r 1 E q 2 . Thus there exists r 1 E q 2 such that r 1 Cf: q 1 . Since r 1 E q 2 , r 1 is /1-good for some /1 < a . By the hypothesis, G(/1,r 1 ) is true. Hence G(a,p 1 ) is true.

"-+": Suppose G(a,p 1 ) is true. Take q 2 = {r 1 : r 1 <; p 1 , r 1 is /1-good for some /1 < a}. Check that Mub(q 2 ,p 1 ) holds true. By contradiction suppose Mub(q2,p 1 ) fails. Clearly p1 is an upper bound of q2. Consequently, p 1 is not a minimal upper bound. Hence there exists q 1 such that q 1 C p1 and for every r1 E q2, r 1 <; q 1 . By the hypothesis, for every such r 1 there exists a /1 < a such that G(/1, r 1 ) is true. Thus q 1 contradicts G( a, p 1 ). It follows from the definition of a-goodness that p1 is a-good. 0

Corollary 3.8 p 1 is good iff there exists an ordinal a such that II all S liD II and G( a, p 1 ) is true .

Ordinals of cardinality S IIDII can be expressed as well-orderings of a part of D within second-order logic, however . A well-ordering R on a set S is a total ordering which is well-founded, i.e. R satisfies

(every nonempty subset X of S has the first element.) The following proposition is well-known.

Proposition 3.9 Let S be a set. For every ordinal a such that llall S IISII there is a well-ordering R(x, y) of a subset E <; S which is isomorphic to a, i.e. (E,R) := ( {/1 : 11 <a}, s).

Now let WO(R) be a formula which states that R is a well-ordering of a part of the domain, and let IS(R1 , R2) be a formula which says that the well-ordering R2 is a strict initial segment of the well-ordering R1, hence a(R2) < a(R1) where a(R) is the ordinal represented by R. Formulating WO and IS in second-order logic is easy. Using WO and IS, the predicate constant G 2 , which is informally equivalent toG, is defined as follows .

Now Curb"(<p(p);p) is defined by

Theorem 3.10 M f= Curb"(<p(p);p) iff M is a model of <p(p) which is good with respect to p.

Proof. M is a good model of <p(p) +-+ good([p]M) holds true +-+ there exists an a such that llall S IIDII and G(a,p) holds +-+ there exists a well-ordering R of E <; D, where Dis the domain ofp, such that G(a(R),p) is true +-+ there exists an R such that G 2 ( R, p) is true +-+ Curb"(<p(p) ;p) is true . 0

Remark: Curb"(<p(p);p) involves a second-order predi­ cate constant G 2 ; it can be eliminated by a more invol­ ved construction, at least over all infinite structures .

4 Computational complexity

An important aspect of any reasoning method is, of course, its computational complexity ( cf. [Garey and Johnson, 1979] for basic concepts and definitions) . It is clear that our method is in the full first-order case highly undecidable, just as any of the well-known me­ thods in nonmonotonic reasoning. We give here a more detailed account of the propositional case. Notice that in this case, a structure M is a truth-value assignment to the propositional variables and p and z are sets of propositional variables. In particular, we consider the inference problem.

Problem: CURB-INFERENCE

Instance: Disjoint sets P, Z of propositional vari­ ables and propositional formulas F, G.

Question: Does Curb(F; P, Z) imply G?

This problem can be easily shown to be coNP-hard, as here Curb(F; P, Z) is consistent iff F is consistent; hence, it is intractable. It may seem at first glance that the problem needs exponential space, in particular since checking whether a truth-value assignment is a good mo­ del seems difficult. The straightforward algorithm, try­ ing to generate this model starting from the minimal models by iteratively including minimal upper bounds, is clearly exponential in both time and space. Howe­ ver, the algorithm GOOD in Table 1 below shows that model checking is feasible in polynomial space . The cor-

ALGORITHM GOOD(M, F, P, Z) : boolean;

input: truth-value assignment M, propositional formula F, sets P, Z of propositional variables, P n Z = 0. output: "true" iff M is wrt toP; Z a good model of F.

if (M ~F) then return false; minimal := true; for each M1 <P;Z M do if (M1 I= F) then minimal:= false; if minimal then return true; for each M1 , M2 <P;z M, M1 "iP;Z M2, M2 "iP;Z M1 do ifGOOD(M1,F,P,Z) then if GOOD(M2, F, P, Z) then begin mub :=true; for each M3 with M1, M2 <P;Z M3 <P;Z M do if GOOD(M3, F, P, Z) then mub :=false; if mub then return true; end; return false;

Table 1: Algorithm for the good model property

rectness of GOOD follows from Theorem 5.2 of the next section, which implies that we can limit ourselves to con­ sider minimal upper bounds of pairs of models . GOOD can be straightforwardly implemented such that its body uses only space linear in the input size. Furthermore, it is easily shown by induction that the recursive depth is bounded by IPI. Consequently, the algorithm runs in quadratic space.

Theorem 4.1 CURB-INFERENCE is feasible in qua­ dratic space.

Proof. Curb(F(P, Z); P, Z) ~ G iff there exists a mo­ del M ofF which is good with respect toP; Z, such that M ~ G. Cycling through all truth assignments to find such an Musing GOOD is clearly possible in quadratic space; hence the result . 0

5 Approximation

In this section we briefly address possibilities to approxi­ mate the full set of good models by a subset. A suitable approximation may even be more intuitive than the full set of good models. The assumption that a "good" set of models accepted by an agent is closed under mini­ mal upper bounds is, of course, an idealization. Which inclusive models the agent accepts will depend on the particular situation; finding a general rationale for this is deary difficult. We consider here the two possibilities of building inclusive models within bounded depth and from a bounded number of disjuncts.

5.1 bounded depth

The first approximation is to limit iterated inclusion of minimal upper bounds. Informally, we choose only the models that are a-good for some a such that llall ~ 11811, where the ordinal 8 is a limit on the depth in building minimal upper bounds. The results of Sec­ tion 3.2 make it clear that the good models within depth 8 can be captured by a second-order sentence Curb 6 (tp(p,z);p,z) as long as 8 is second-or.der expressi­ ble. Notice that circumscription appears as the case 8 = 0, i.e. Curb 0 (tp(p,z);p,z) is equivalent to Circ(tp(p,z)).

Concerning computational complexity, the inference problem is in the propositional case for finite constant 8 as easy (and as hard) as circumscription.

Theorem 5.1 The 8-bounded version of CURB-INFE­ RENCE, i.e. deciding if Curb 6 (F(P, Z); P, Z) implies G, for 8 a finite constant is complete for the nf level of the polynomial hierarchy [Meyer and Stockmeyer, 1972].

Proof. We sketch a proof of membership in llf. Curb\F(P, Z); P, Z) ~ G iff there is a 8-good model M of F such that M ~ G. Guess M and ~ IPI wit­ nesses M1 , ... , Mm for M (i.e., good models such that M is a minimal upper bound), and for each M; witnes­ ses etc. to a recursive depth ~ 8. The guess consists of ~ IPI 6 truth-value assignments, and is thus polynomial in the input size. Checking whether M is a minimal upper bound of M 1, ... , M m etc. is possible in polyno­ mial time with an NP oracle. Consequently, deciding if Curb 6 (F(P,Z);P,Z) ~ G is in NPNP = Ef, which im­ plies that "Inference" is in llf. IIf -hardness for 8 = 0 (i.e. circumscription) was shown in [Eiter and Gottlob, 1991]. The construction used in the proof can be easily generalized to arbitrary finite constant 8. 0

5.2 bounded disjunctions

Another attempt is to limit the cardinality of model sets from which minimal upper bounds are formed. Intui­ tively, this corresponds to limiting the number of inclu­ sively interpreted disjuncts by a cardinal K > 0. The concept of closed,. set is defined by adding in the defini­ tion of closed set the condition "liM' II ~ K"; goodness,. is the relative notion of goodness.

Clearly, goodness1 is equivalent to circumscription. For K ~ 2, we obtain over finite structures (i .e. IMI is finite) the following result .

Theorem 5.2 Over finite structures, for every K ~ 2 a model of tp(p, z) is good,. with respect to p; z iff it is good with respect to p; z.

Proof. We show this for p = p, p unary, and em­ pty z under above notational conventions; the proof is easily generalized. Show by induction on IIP 1 II that every a-good p 1 is a-good2 . The case IIP 1 II = 0 is tri­ vial. For IIP 1 II > 0, let q 2 = {q 1 : q 1 C p 1 , good(q 1 )} .

Mub( q 2 , p 1 ) holds. If q 2 = 0, the statement trivially holds. In the other case, let r 1 E q 2 be maximal with respect to ~- As IMI is finite, such an r 1 exists . Let s 1 E q 2 such that s 1 ~ r 1 . Such an s 1 must exist . Then Mub( {r 1 , s 1 }, p 1 ) holds, and by the induction hypothesis r 1 and s 1 are good 2 ; hence, p 1 is good 2 and the state­ ment holds. Clearly, every p 1 which is good" is good. Hence the result follows. 0

Theorem 5.2, which fails for arbitrary structures, im­ plies a dichotomous result on the expressivity of K­ bounded disjuncts: Either we get only the minimal mo­ dels or all models obtainable by unbounded disjuncts. Limiting simultaneously the number of disjuncts and and the depth in building minimal upper bounds can be used to cut down the set of good models .

6 Related work and conclusion

Inclusive interpretation of disjunctive models has been investigated in logic programming [Ross and Topor, 1988; Sakama, 1989; Ross, 1989; Chan, 1991] .

The Disjunctive Database Rule (DDR) [Ross and To­ por, 1988] has been proposed to allow cautious deriva­ tion of negative literals from a disjunctive database. The DDR allows all models in Examples 1 and 2, hence also the unintuitive ones. Moreover, it depends on syntactical representation [Chan, 1991], which however is customary for semantics of logic programming. Thus, the DDR is basically different from our method.

A more sophisticated approach that allows also to deal with negative clauses was introduced in (Sakama, 1989; Chan, 1991] by the equivalent concepts "Possible Mo­ dels Semantics" (PMS) and "Possible Worlds Semantics" (PWS) . This approach has recently been generalized to cover Negation by Failure [Sakama and Inoue, 1993]. In Examples 1 and 2, PMS and PWS coincide with curb. However, if the clause h V n V p is added to T1 , which has no effect on the models, then PMS and PWS adopt all models . Hence , PWS and PMS are syntax-dependent and basically differ from our method.

Another approach to treat disjunction inclusively is the weak well-founded semantics (WWF) for disjunc­ tive logic programs in [Ross , 1989] . In case of negation­ free programs, this semantics coincides with the DDR [Ross, 1989], which implies syntax-dependency of WWF . Hence, WWF is basically different from curb.

In this paper we presented a new approach to nonmo­ notonic commonsense reasoning that seems to be more appropriate than circumscription in many cases, namely, when disjunction of positive information is naturally in­ terpreted in an inclusive fashion . Our method of curbing theories differs significantly from all previous approaches to treat disjunction inclusively. It is syntax independent and yields the more intuitive models . We have shown that Curb is second-order definable and have derived some relevant complexity results. We also have fostered two ways of approximating the curb of a theory.

We believe that this new approach deserves further in­ vestigations . On the one hand , it is tempting to find new and better algorithms for inferencing under curb or its approximations . On the other hand, the inclusive inter­ pretation of disjunction is not always desired . Sometimes it seems that a hybrid approach which interprets cer­ tain predicates (or certain connectives) inclusively and others exclusively is more appropriate, cf. [Ross, 1989; Sakama, 1989; Chan , 1991] . Our ongoing research deals with all these topics.

Acknowledgments

The authors thank C. Sakama for clarifying comments .