Sound and Efficient Non-monotonic Inference

1 Introduction

Non-monotonic reasoning is widely perceived to be in­ efficient and several theoretical studies have confirmed that suspicion for a large class of theories (e.g., [Kautz and Selman, 1989]). Yet, many practical systems, in­ cluding inheritance reasoners, time map managers and logic programs with negation as failure , suggest that non-monotonic reasoning can be both practical and effi­ cient in many cases of interest. Stratified logic programs, for example , are tractable when negation is interpreted as 'negation as failure' [Van Gelder et a/., 1988) and in­ tractable when interpreted classically.

In this work, we aim to understand conditions that al­ low for sound and efficient non-nonmonotonic inference. For that, we appeal to the semantic framework recently introduced in [Geffner, 1995; Geffner and Bonet , 1995) in which systems of strict and defeasible rules are viewed as dynamic systems with a transition function f that maps states s; to sets f( si) of possible successors , and a plausi­ bility function 1r that determines the relative plausibility of those possible transitions.

Gisela Mendez

Depto de Matematicas Univ. Central de Venezuela Aptdo 47002, Caracas 1041 Venezuela

In this framework, the transition function f(si) is given by the collection of states Si+l such that the tran­ sitions from s; to Si+l violate a minimal set of default rules. The plausibility function 1r, on the other hand, is provided independently and it's role is to determine the assumptions one is willing to make about 'missing' infor­ mation. In particular, when the plausibility function 1r is uniform, i.e., it assigns the same plausibility number to all states, no assumptions are made and the resulting semantics is monotonic in the set of observations while non-monotonic in the set of rules. 1 On the other hand, when 7r is compatible with the Closed World Assumption (cwA), namely, 'lrcwa(s;) stands for the number of atoms true in state s; (the higher the number , the less plausi­ ble the state), the resulting semantics is non-monotonic in the observations and corresponds to the interpreta­ tions of negation as failure found in logic programs. In neither case, however, the semantics is adequate: ir. the first case is too weak, and in the second is too strong. Interestingly, however, while in the first case the seman­ tics is intractable, in the second case the semantics is tractable.

In this work we will look for plausibility functions that have good semantical and computational properties. W, will do so by identifying a set of core predictions to be accounted for that can be computed in polynomial time, can be justified in various ways, and are not tied to either Horn theories or closed world assumptions. The result­ ing functions will enable us to handle an interesting class of theories in a justifiable and efficient manner .

The plan of the paper is as follows. First , we review the semantic framework laid out in [Geffner, 1995) and [Geffner and Bonet, 1995) (Section 2). Then we con­ sider the virtues and limitations of the CWA interpreta­ tion and define the core predictions in three ways: by means of a procedure, a 3-valued logical interpretation and an epistemic interpretation (Section 3) . We then characterize other tractable conclusions that follow from the admissible plausibility functions (presuppositions), study semantic and syntactic conditions that guarantee the existence of such functions , and assess the admissibility of some plausibility orderings commonly used and show how such orderings can be constructed (Section 4). We end with a summary of the main ideas (Section 5).

1 For temporal theories , this semantics is very much like Gelfond's and Lifschitz's [1993] semantics for actions, and both are equivalent to Sandewall's [1991] form of chronolog­ ical minimization . See [Geffner, 1995].

2 The Basic Framework: A review

2.1 Language

We deal with theories T = (D, 0) comprised of a finite set of rules D and a finite set of observations 0. Rules can be either strict or defeasible and are represented by expressions of the form a1 /\ a2 /\ · · · /\ an => /3, and a 1 /\ a2 /\ · · · /\ an ---+ f3 respectively, with n 2: 1. The a/s, fJ's and the observations are assumed to be literals; i.e., atoms or their negation.

We often speak of variables rather than propositions. Thus, two literals a and ·a will be associated with the values t and f of an abstract boolean variable A. We say that a formula involves or refers to the variable A when the formula involves one of the literals a or ·a.

Each defeasible rule has a priority number represented by a non-negative integer. Intuitively, among a set of conflicting rules, i.e., rules with complementary conse­ quents, those with higher priority are preferred. In this work, we assume that the theories are weakly determin­ istic in the sense that whenever two rules are in con­ flict, one rule must have priority over the other. 2 These theories are common in certain domains and theories which don't comply with this condition can normally be mapped into a family of theories that do (by breaking the 'ties' among the rules that are in conflict).

We also assume that rules are acyclic. For that, we de­ fine the causal graph associated with a set of rules as the directed graph whose nodes are the variables and where for every rule there is a link connecting every variable referred to in the antecedent to the variable referred to in the consequent. The rules are acyclic when the causal graph does not contain cycles. Acyclic logic programs are an special case of these theories in which both defea­ sible rules and rules with negative heads are excluded. Other 'inheritance' and temporal theories can be repre­ sented in this framework in a straightforward way (see the references).

2.2 Semantics

The semantics of the theories T = (D, 0) is given by dynamic-systems type of structures (u, f, 1r, 0), where u is a ranking function that assigns a non-negative integer u(A) to every variable A, f is a state transition func­ tion, 7r is a plausibility function and 0 stands for the observations.

In temporal theories, the u-ranking of a variable is simply the time-point associated with the variable [Geffner, 1995]. In more general causal theories, there is no explicit notion of time and the role of the ranking u is 'to make it up': u assigns a 'time' point to every variable wit.h the only restriction that causes must precede their effects (i.e., variables in rule antecedents must have a smaller u-rank than variables in the consequent). There are of course many rankings u that satisfy this condi­ tion yet given certain conditions on the transition and plausibility functions f and 1r, the resulting semantics is insensitive to the particular u chosen [Geffner and Bonet, 1995]. Here for simplicity we will choose one particular ranking function u0 throughout the paper: the one that corresponds to the topological sort of the causal graph. Thus the rank of the variables that have no parents in the causal graph will be zero, while the rank of the rest of the variables will be the length of the longest paths in the graph leading to the variable.

2 A rule r has priority over a rule r' when the two rules are defeasible and r has higher priority, or when r' is defeasible and r is not.

Given the ranking u0 , the states Si at time i are defined as the truth-valuations of the variables A assigned to time i (i.e. , with u0(A) = i) . The state-transition func­ tion f maps states s; into a non-empty set f(s;) of pos­ sible successor states Si+l. Given a weakly-deterministic domain theory, f( s;) is defined as the collection of states s;+l that satisfy the consequents of all the rules that are applicable given Si, where a rule A ---+ f3 is applicable given Si when A is true in s; and no conflicting rule with higher priority is applicable in s;. 3

The plausibility function 1r determines the relative likelihood of the legal transitions by assigning to each state Si+l a non-negative integer 7r(Si+t). 4 'Better' states, i.e., states with higher plausibilities, have smaller numbers, and vice versa. Formally, the plausibility K 0 ( Si+tls;) of a transition from a state s; to a state si+1 E f( si) that satisfies the observations 0 at time i + 1 is defined as:

where 7r~ (!( si)) is a normalizing constant that refers to the plausibility of the best states s:+l E f(s;) that sat­ isfy the observations at i + 1. We also define K(s0), the plausibility of the 'transition' to s0 , as:

where 7r~ (So) is another normalizing constant that refers to the plausibility of the best initial states s~ that satisfy the observations at 0.

A legal trajectory r is a sequence of states s0 ,s1 , .. . ,sn , where n is the highest u0-rank, such that each s; satisfies the observations at i and s; E f(s;_t) for i > 0. The plausibility of a legal trajectory given the observations 0 is simply the sum of the plausibilities associated with its transitions, i.e. Ko(r) = Ko(so) + 2::::1 N Ko(s;is;_t) . The plausibility of illegal trajectories is ~sumed to be infinite (for the probabilistic interpretation of this model, see the references).

The semantics of a theory T = (D, 0) given a plau­ sibility function 1r is identified with its most plausible trajectories (recall that the transition function f is de­ termined by the domain theory D). We refer to the trajectories r that have a plausibility 1r( r) = 0 as nor­ mal trajectories. When normal trajectories exist , they are the most plausible trajectories. Yet such trajectories may fail to exist when predictions are refuted by observa­ tions. We call the theories that have normal trajectories predictive theories. To a large extent, they will be the focus of this work.

3 This definition of f is not general and assumes that the theory is markovian. See below.

4 The notation f(s;) and 1r(s;+l) is actually an abbrevi­ ation for f(i, si) and 1r(i, s;) as both functions depend not only on the state s; but also on the time point i.

Example. Let us consider a domain theory composed of a defeasible rule p --+ q and a strict rule r ::::} ·q. The ranking O'o assigns the variables P and R to the layer 0, and variable Q to layer 1, i.e., O'o(P) = O'o(R) = 0 and O"o( Q) = 1. The set So of states s0 are the four possible valuations of the variables P and Q, and the set sl of states sl are the two possible valuations of the variable Q. For any state s0 E So, f( so) denotes the states in sl that satisfy the consequents of all the rules applicable in s0 . Hence, when s0 does not satisfy either p orr, f(so) = {sq,s..,q}, when so satisfies pl\·r, f(so) = {sq}, and when s0 satisfies r, f(so) = {s..,q}. Given the observation p and the uniform plausibility function 'lru, i.e., the function that assigns the same plausibility number to all states, we get two normal trajectories: one corresponds top, ·r and q, and the other top, rand ·q. On the other hand, given the CWA-plausibility function instead, where 'lrcwa(si) measures the number of atoms satisfied by s;, we get only one normal trajectory that corresponds to p, ·r and q.

Non-Markovian Theories. The definition off above presumes that all the variables in the antecedent of a rule belong to the same 0'0-layer, and that the variable in the consequent of the rule belongs to immediately succeeding u0-layer. We call theories where this holds markovian. Many temporal theories are markovian in this sense, yet most non-temporal theories are not . There are two gen­ eral ways for dealing with non-markovian theories. One is to reformulate the notion of state: in the general case, a state s; is no longer a valuation over the variables in layer i alone, but over all the variables in layer j, j ::_:: i (see [Geffner and Bonet, 1995] for details). A second way is to transform the theories into equivalent marko­ vian theories. This can be easily done by introducing surrogate variables. For example, if a variable A belongs to layer i and some rule 'requires' A in layer i+ 1, we just introduce a new variable A' and relate it to A by means of two strict rules: a::::} a' and ·a::::} ·a'. The two meth­ ods are general and can be applied to any non-markovian theory. For this reason, and to keep things simple, we fo­ cus in this paper on theories that are markovian. All the results easily carry to non-markovian theories as well.

3 Tractable Inference without the CWA

In the semantic framework laid out above the defaults get compiled into the transition function f while the plausibility functions encodes the assumptions one is willing to make to 'complete' partially specified states. The CWA plausibility function, for example, presumes that variables whose values are not known are false. This is adequate sometimes, but it is often too strong. For example, if a rule ·w ::::} ·q is added above, the CWA as­ sumption would make the exception ·w more plausible than it's negation, not only failing to conclude q from p, but actually concluding ·q. This limitation of the CWA

ordering is not surprising though: the CWA ordering is determined without considering the rules in the theory. A better approach is to define the plausibility ordering by looking first at such rules, as done in the interpretations that view defaults as conditionals (e.g., [Lehmann, 1989; Pearl, 1990; Geffner, 1992]) . However , since extracting a reasonable plausibility ordering from the rules remains too difficult, what we will do instead is to define some core predictions that can be justified in simple terms and can be computed in polynomial time, and then focus on the plausibility functions that make those predictions sound. The resulting semantics will combine the proper­ ties of causal and conditional interpretations of defaults [Geffner, 1992], and will have a significant core of infer­ ences that can be computed efficiently.

3.1 The Core Predictions

The core predictions are conclusions that can be justi­ fied in simple, meaningful terms and which can be com­ puted in polynomial time. We will provide three different but equivalent characterization of them. The first is a tractable inference procedure very similar to other pro­ cedures used in non-monotonic systems (e.g., [Horty et a/., 1987]) . Basically, the procedure applies all the rules A --+ f3 whose antecedents have been either observed or derived as long no higher priority rule B --+ "'/3 with a conflicting consequent also has its antecedents observed or derived.

In the procedure, the rules with highest precedence in a set S of rules A --+ [ ·]p refer to the rules in S whose consequents are ranked lowest (i.e., have a mini­ mum O'o(P)). The symbol L represents the conclusions (literals) computed by the algorithm. We say that a rule A--+ f3 is applicable given L when A ~ L. The function new-applicable-rules(p, S) returns the rules that become applicable when S is known and p is derived; i.e. , the rules A --+ p such that A holds in {p} + S but not in S. The complement of a literal xis denoted as "'X. For simplicity, strict rules are handled as defeasible rules of higher priority. 5

Procedure A

L := 0 ; RULES := rules applicable given L while RULES not empty do SELECT := rules in RULES with highest precedence RULES := RULES - SELECT while SELECT not empty do pick a highest priority rule A --+ f3 from SELECT L := L + {/3} RULES := RULES + new-applicable-rules(/3, L) SELECT :=SELECT- {rules B--+ f3 & B--+ "'/3} end while end while

Proposition 1 The complexity of A is linear in the set of rules.

5 For weakly deterministic predictive theories that are pre­ dictive, strict rules can actually be replaced by defeasible rules with higher priority without affecting the meaning of the theory.

Proposition 2 Given the CWA plausibility function , A is sound and atomic-complete for weakly deterministic theories that are predictive.

We will refer the literals in L for a theory T as the core predictions ofT and denote them as Pd(T) .

3.2 A 3-Valued Interpretation

Two different models will shed some light into what this procedure actually computes. The first model is defined in terms a transition and a plausibility function but as­ sumes a 3-valued logic. The plausibility function 1T~wa · unlike 1rcwa, maximizes not 'falsehoods' but uncertain­ ties (don't know's). The transition function f(s;) , as before, maps a state s ; into the set of states Si+l that satisfies the consequents of all the rules applicable in s;. The only difference is that states are now 3-valued inter­ pretations; rules continue being applicable when their antecedents are true and no conflicting rules with higher priority are applicable.

The normal trajectories are defined as above. They now stand for 3-valued models so some literals may be neither true or false. We call this the 3-CWA interpreta­ tion. It 's very simple to check this interpretation makes the predictions computed by the procedure A sound and complete:

Proposition 3 Let T = (D, 0) be weakly-deterministic theory which is predictive relative to the 3-CWA interpre­ tation; namely T has a normal 3-CWA trajectory. Then this trajectory is unique and the core predictions are ex­ actly the literals that are true in that trajectory.

3.3 An Epistemic Interpretation

We consider now a different model where the rules are interpreted epistemically. Given a domain theory D with strict and defeasible rules of the form 'if A then /3', we will consider a new domain theory K(D) where those rules are replaced by their epistemic counterparts, i.e., epistemic rules of the form 'if KA then /3', where K is an intensional knowledge operator. We will interpret the resulting theories with a semantic structure consisting only of a transition function FK that maps sets of states S; into sets of states S;+l· The individual states s; are, once again, classical interpretations over the variables occurring in layer i, and FK(S;), in analogy to f(s;), is defined as the set of states si+1 that satisfy the conse­ quents of all the rules applicable in the set of states S;, where a rule 'if KA then /3' is applicable in S; when A holds in all the states s; E S; and no conflicting rule with higher priority is also applicable.

By the epistemic interpretation of a theory T = (D, 0) we will mean the succession So, S1 , ... , Sn of non-empty sets of states, such that So is the set of states that satisfy the observations at time 0, and S;, i > 0, is the set of states in FK(S;_ 1 ) that satisfy the observations at time i . The literals sanctioned by this interpretation are the literals that are not falsified by any such state.

Proposition 4 LetT= (D, 0) be a weakly determinis­ tic theory. Then T has a 3-CWA normal trajectory iffT has an epistemic interpretation. In either case, the lit­ erals that hold in both models correspond exactly to the core predictions.

4 Admissible Orderings

The core predictions are thus the conclusions that follow from an epistemic reading of the rules. The admissi­ ble plausibility functions are as the functions that make those predictions sound:

Definition 1 1r a is an admissible plausibility fun ction relative to a weakly-deterministic domain theory D with transition function f , if for any set of observations 0 , the core predictions Pd(T) are true in all the 1r a normal trajectories compatible with 0.

The semantics that results from the admissible plau­ sibility functions is stronger than many conditional in­ terpretations of defaults , since given a rule A ---> /3 /3 will be a core prediction of A, except in the pathological cases in which there is a higher priority rule A' ---> · /3 with A' ~ A. While conditional interpretations read such rules as saying that 'if A is all that is known, then /3 is true', the proposed interpretation reads them as 'if A is known and no exception is known , then /3 is true'. This is similar to the epistemic interpretation of tempo­ ·ral theories in [Shoham, 1988].

We say that a domain theory D is admissible when it admits an admissible plausibility ordering. We also say that a theory T = (D, 0) is admissible when there is normal trajectory compatible with one such admissible ordering. We call such trajectories the admissible normal trajectories ofT. A basic result for positive theories is: 6

Proposition 5 The CWA plausibility function is admis­ sible for positive domain theories. Moreover, a theory T = (D , 0) with a positive domain theory D has an ad­ missible normal trajectory iff T has a CWA normal tra­ jectory.

Moreover , since all the positive literals that can be obtained by the CWA interpretation for positive theories are 'core predictions' we also get that:

Corollary 1 Let T be a positive theory with a CWA nor­ mal trajectory. Then the atoms that are true in that trajectory correspond exactly to the atoms that are true in all the admissible normal trajectories of T (atomic soundness and completeness).

The account in [Geffner, 1994] is characterized exactly by these atoms. This does not mean, however , that there are no negative consequences to be extracted from posi­ tive theories. Actually, there may be plenty of them and their computation is tractable.

4.1 Tractable Presuppositions

The epistemic and 3-CWA interpretations sanction all the conclusions Pd(T) computed by the procedure A and nothing else. Yet we can obtain more conclusions from A by 'reductio ad absurdum'; i.e., by assuming a value for literals whose truth has not been determined and checking its repercussions. This operation leads to a sound and tractable extension of the set of core predic­ tions Pd(T) which in certain cases is complete.

6 Positive theories refer to theories with no rules with negated antecedents.

Let us define Pp0 (T) as the set of literals a rf: Pd(T) which if assumed to be false introduce new predictions j3 which are in conflict with the old ones; i.e. j3 E Pd(T + {-a}) and "-'/3 E Pd(T). Moreover, let us define Pp;(T) iteratively for i > 0, as the union of Pp;_1 (T) and the literals a rf: Pd(T+ Ps;_ 1(T)) such that for some literal (3, j3 E Pd(T + Pp;-l(T) + {""'a}) and "'/3 E Pd(T + Ps;-I(T)) .

We will call the literals in Pp0(T) simple presuppo­ sitions and the other literals in Pp;(T), i > 0, iterated presuppositions. Let us also define Pp(T) as the set of all simple and iterated presuppositions, i.e., Pp(T) = Pp;(T) for the smallest i such that Pp;(T) = Pp;+l(T) .

Proposition 6 All presuppositions are true in all the admissible normal trajectories (soundness). Moreover, computing all presuppositions is tractable.

Proposition 7 Let T be an admissible positive theory; i.e., a positive theory with admissible normal trajecto­ ries. Every literal that is true in all such trajectories is either a core prediction or a simple presupposition {com­ pleteness).

Corollary 2 For a positive T as above, computing the positive and negative consequences ofT is tractable .

4.2 Constructing Admissible Orderings

Semantic Conditions

Below we provide two semantic conditions that allow us to determine when a given plausibility function 1r is ad­ missible. S; and Si+1 refer to the collection of states s; and Si +l, i = 1, 2, ... , that satisfy two arbitrary sets of literals A; and Ai+l in layers i and i + 1. Si de­ notes the best states in S; according to 1r and 7r* ( S;) denotes the plausibility of the best states in S; . FK is the transition function associated with the epistemic in­ terpretation. The conditions are:

Proposition 8 If a plausibility function 1r satisfies con­ ditions 1- 2 for any two collections of states S; and S;+l as above, 1r is admissible.

Syntactic Conditions

Let us say that one rule r preempts another rule r' when r has priority over r' and the two rules have conflicting consequents. We will call the literals that occur in the antecedent of r exceptions relative to the rule r' or simply exceptions. Let's also say that a literal a is connected to a literal j3 in a given domain theory when there is a chain of rules r 1 , r 2 , ... , rn (i.e., the consequent of each rule r; occurs in the antecedent of the rule ri+1 for i = 1, . .. , n-1), where the literal a occurs in antecedent of r1 and j3 is the consequent of rn. Each literal is also 'connected' to itself.

Then we say that a domain theory is normal when for every atom a, if a is connected to an exception, then ·a is not connected to any exception.

Proposition 9 Normal domain theories are admissible Below we show how to construct admissible orderings for theories that are normal. Although this is not needed for accepting the core predictions and presuppositions , it will shed some light on the adequacy of some of the plausibility orderings that have been proposed.

Some Admissible Orderings

We will consider first a very simple class of normal the­ ories where there are no chains of rules. In other words, the ranking O"o assigns all the variables that occur in the antecedent of the rules to the 0-layer, and all the vari­ ables that occur in the consequent of the rules to the 1-layer. We call such theories, 2-layered theories.

For these theories, finding an admissible plausibility function reduces to finding an ordering on the states s0 that satisfies Condition 1 above. It 's is interesting to see how some of the standard plausibility orderings fare in this regard. For example, the uniform plausibility ordering 'lru will work only in theories in which there are no pairs of rules in conflict. The CWA ordering 'lrcwa, on the other hand, will work whenever there are no negative exceptions.

Let's consider now the plausibility function 'lrmin that minimizes default violations; i.e., 'lrmin(s) measures the number of rules violated in s where a rule A -. j3 is vi­ olated in s when s satisfies A but some state s' E f( s) fails to satisfy j3. Since 'lrmin does not reflect the rule pri­ orities, let's assume that all rules have the same priority. Does 'lrmin comply with Condition 1 above? Interestingly the answer is not: for example, the theory comprised of the rules: a -. b, c => ·b, ·a => d and f -t ·d is nor­ mal, and yet, the best 'lrmin states compatible with the literals c and f contain a state s0 where ·a holds that leads to d in contradiction with FK that yields ·d.

A modification of 1r min , however , yields a plausibility function that is admissible for all (2-layered) normal the­ ories. Given a states, let SA denote the 'closest' state to s where A holds, where the distance between two states is measured by the number of atoms that have different truth-values. Let us also say that a rule r : A -t j3 is preempted in a state s when the rule r is violated in the state SA (this is just the standard notion of violation when rules are understood as conditionals ; see [Nute, 1984]). Then the plausibility function 'lrpmt(s) that mea­ sures the number of rules preempted in s is admissible relative to all normal 2-layered theories.

Let 's finally consider the plausibility function 'lrz that corresponds Pearl's Z-ranking, which captures both the conditional reading of rules and certain independence as­ sumptions (see [Pearl , 1990] and the equivalent ranking due to Lehmann [1989]) . Basically, the states s with Z­ plausibility 0 are the states that don't violate any rule, while inductively, the states s' with Z-plausibility i are the states that violate rules A -. j3 which have been verified in states s with Z-plausibility j , j < i (a state s verifies a rule when s satisfies both the rule and its antecedent) . The Z-plausibility function is not admissi­ ble yet an admissible function 'lrw can be defined by a slight modification of the above definition: the states s' with W-plausibility i need to be inductively defined as the states s' that violate rules A ___. {3 such that all the states s that verify the rule A -+ {3 and that are closest to s' have a W-plausibility j, j < i. This W-plausibility ordering can be shown to exist for all 2-layered normal theories.

Proposition 10 The plausibility functions 7rpmt and 7rw are admissible relative to all 2-layered normal domain theories. The plausibility functions 7ru, 1rcwa , 1rmin and 7rz are not.

General Normal Theories. The plausibility functions 7rpmt and 7rw above can in principle be extended to n­ layered normal theories but the construction is complex. There is nonetheless a simple construction that applies to all normal theories. Let us say that a literal a is normal when a is not an exception and is not connected to any exception. Then, the plausibility function 1rxcp(s) that measures the number of non-normal literals made true by s is admissible:

Proposition 11 The plausibility function 1rxcp is ad­ missible relative to all normal domain theories.

Note that in the case of positive domain theories, the only non-normal literals are positive literals. In that case, the CWA-plausibility function can be thought as a stronger version of the function 7r xcp that assumes all positive literals to be non-normal.

The plausibility function 1rxcp has an additional useful property: it's decomposable in the sense that the plausi­ bility of a state is the sum of the plausibilities associated with each of the literals it satisfies (the plausibility of normal and non-normal literals is 0 and 1 respectively). As shown in [Geffner and Bonet , 1995], this guarantees that the behavior determined by 1rxcp is insensitive to the ranking cr used and that, like in Bayesian Networks [Pearl, 1988], every variable is independent of its non­ descendants given the value of its parents.

5 Summary

We have identified a basic core of inferences that can be justified in simple terms and have developed a semantics that makes those inferences sound. The semantics has good computational properties, combines elements from causal, conditional and extensional interpretations of de­ faults , and sheds some light on the adequacy of various plausibility orderings and on the scope of interpretations that view default rules epistemically.

Acknowledgments

I want to thank Yoav Shoham for the chance to spend time in Stanford with my family and for many useful discussions that led to this work. I also want to thank Nir Friedman and Joe Halpern (HG).