A Causal Theory of Ramifications and Qualifications

1 Introduction

This paper is concerned with the problem of determin­ ing the indirect effects or ramifications of actions. The problem is usually investigated, as in [Kartha and Lif­ schitz, 1994), in a framework in which action domains are described in part by state constraints. (Informally, a state constraint is a formula that says of a proposition that it is true in every possible state of the world.) Our main objective is to argue that an adequate theory of ramifications requires the representation of information of a kind that is not conveyed by state constraints. In particular, what is required is the representation of the causal relations (or, more generally, the determination relations) that hold between states of affairs. It turns out that this is also the information that is needed for an adequate theory of derived action preconditions or qualifications.

Previous approaches to the problem of ramifications have assumed a definition of the following kind: A ram­ ification, roughly speaking, is a change (not explicitly described) that is implied by the performance of an ac­ tion. In our approach, we substitute the word "caused" for the word "implied." In determining the ramifica­ tions of actions, it is not enough, we say, to infer that a change must occur when an action is performed; it is necessary to infer that the action causes the change to occur. As we will see, this stronger requirement makes it possible to avoid unintended ramifications and to infer derived qualifications. (The need for the latter is ar­ gued in [Ginsberg and Smith, 1988] and [Lin and Reiter, 1994].) Again roughly speaking, our theory of qualifi­ cations is this: An action ·cannot be performed if the performance of the action implies a change that it does not cause. 1

·partially supported by National Science Foundation grant #IRI-9306751.

1 Partially supported by an IBM Graduate Fellowship and by NSF grant #IRI-9306751.

The main points can be illustrated by the following example. Imagine that Fred the turkey is on a walk. Consider the action of making Fred dead. Intuitively, as an indirect effect of performing the action, Fred will no longer be walking. The reason is that Fred's being dead causes him to stop walking. Now consider the action of making Fred walk, but suppose that Fred is dead. Intuitively, the action cannot be performed. The reason is as follows : Fred can walk only if he is alive, but making him walk does not cause him to be alive; so unless he is already alive (or something in addition is done to cause him to become alive) he cannot be made to walk.

The conclusions reached in the previous paragraph are supported by the following facts . Intuitively, Fred can be made to not walk by making him not alive, but he cannot be made to be alive by making him walk. If the indirect effects of an action are the facts made true by making the direct effects of the action true, then we should expect Fred's not walking to be an indirect effect of making him not alive, but we should not expect Fred's being alive to be an indirect effect of making him walk.

In general, facts about what can and cannot be done by doing something else are contingent upon underlying causal connections and other relations of determination. (For a discussion of noncausal determination relations see [Kim, 1974].) State constraints say nothing about these , so it is not surprising that background knowledge in the form of state constraints should prove to be in­ adequate. In the recent literature on reasoning about action, the inadequacy of state constraints has been ob­ served by Elkan [1992] and by Brewka and Hertzberg [1993].

1 A similar proposal by Lin [1995] appears in these proceedings.

The central problem addressed in this paper is that of properly defining the set of possible next states after performing an action, given specific direct effects and background knowledge in the form of "causal laws." 2

For the standard framework in which background knowledge is given in the form of state constraints, this problem was solved by Winslett [1988]. It is not clear, however, how ·Winslett's definition should be modified to accommodate causal laws. Accordingly, after an ini­ tial discussion of notation and terminology in Section 2, we go on in Section 3 to reformulate Winslett's defini­ tion, obtaining an equivalent definition of a quite dif­ ferent form. On the basis of this reformulation, in Sec­ tion 4 we present our definition for the framework with "causal laws," represented as inference rules. In Sec­ tion 5, we show how ramification and qualification con­ straints can be encoded by inference rules. We also show that the framework with inference rules properly extends the standard framework.

In Sections 6- 8, we give a semantic account of "causal laws," replacing inference rules by a rule-like conditional, for which a modal, partial state semantics is defined. Doing so allows us to clarify the sense in which our theory of ramifications and qualifications is a causal theory.

2 Notation and Terminology

We begin with a standard language of propositional logic, based on a fixed set of atoms. We represent an interpretation for the language by a maximal consistent set of literals. Informally, we think of an interpretation as a logically possible state of the world. For conve­ nience, we sometimes use the word "state" to mean an interpretation. By an explicit effect we mean a set of for­ mulas. Intuitively, these are the formulas that an action is explicitly said to cause.

The central problem in determining the ramifications of an action is to properly define Res( E, S), the set of possible next states after performing an action with the explicit effect E in the state S. We address this problem in frameworks in which background knowledge is given in the form of state constraints and "causal laws."

By a formula constraint we mean a formula. We will require every given formula constraint to hold in ev­ ery possible next state, so a formula constraint func­ tions (in this respect) as a state constraint. A stan­ dard example of a formula constraint is the formula (Walking :J .Alive) [Baker, 1991].

We will write an inference rule as an expression of the form

where ¢ and '1/J are formulas. Informally, we will think of ( 1) as expressing a relation of determination between the states of affairs that make ¢> and '1/J true. One kind of determination relation is causal. As an example, we think of the rule ·Alive::::}--, Walking as expressing the "causal law" that not being alive causes not walking. Of course, walking does not similarly cause being alive, which shows that the causal relation, like the inference rule, is "noncontrapositive."

2 Throughout this paper, we use the term "causal law" in place of the more accurate but less familiar term "determi­ nation relation." Causal laws are in any case prime examples of determination relations.

The standard derivability relation f- of propositional logic is easily extended to take account of inference rules. Let f be a set of formulas, and C be a set of inference rules. We say that r is closed under C if for every rule ¢::::} '1/J E C, if¢ E f then '1/J E f. For any formula¢, we write

to mean that ¢> belongs to the smallest set of formulas containing r that is closed with respect to propositional logic and closed under C.

3 Possible Next States: Constraints

The standard framework in which the problem of rami­ fications is addressed is one in which background knowl­ edge is given in the form of state constraints. For this framework, the problem was solved by Winslett [1988].

Definition W For any interpretationS, any explicit ef­ fect E, and any set B of formula constraints, Res~ (E, S) is the set of interpretations S' such that

• ( 1) S' satisfies E U B, and
• no other interpretation that satisfies E U B differs from Son fewer atoms, where "fewer" is defined by set inclusion.

Intuitively, Res~ (E, S) is the set of possible next states after performing an action with the explicit effect E in the state S, given background knowledge B.

As an example, let

S {Alive, Walking}

B {Walking:JAlive} .

Then

Here, -.Walking is a ramification.

It is not clear how to modify Winslett's definition to accommodate background knowledge in the form of in­ ference rules. Accordingly, the remainder of this section will be devoted to reformulating it .

In order to explain our reformulation, we present a series of definitions in which we introduce, in successive steps, first the assumption of inertia (which is needed to solve the frame problem) and then background knowl­ edge in the form of formula constraints. Each definition will take the following form: For any interpretation S and explicit effect E, Res(E, S) is the set of interpreta­ tions S' such that S' is precisely the set of literals that are derivable from E and the available background in­ formation (possibly including information provided by the assumption of inertia). Throughout this paper the symbol L will be used to stand exclusively for literals.

In Definition 1, we do not assume the principle of inertia, nor do we include formula constraints. Conse­ quently, every literal in any possible next state must be derivable from E alone.

Definition 1 For any interpretation Sand any explicit effect E, Res 1 ( E, S) is the set of interpretations S' such that

Clearly, if the set { L : E f- L} is an interpretation then this interpretation is the only element of Res 1 ( E, S). Otherwise, either E does not imply a value for every atom or E is inconsistent. Since E is required to specify not only the values of the atoms that change but also the values of those that do not, the frame problem is unsolved in Definition 1.

Consider, for example, the state S = {p, q} and an action that makes p false. Choosing E = { ·p 1\ q}, we have Res 1 (E,S) = {{·p,q}} .

In the next definition (Definition 2), we assume the principle of inertia, but do not yet include formula con­ straints. Here the frame problem is solved by the as­ sumption of inertia, which makes it possible to specify only the values of the atoms that change. The values of the other atoms are assumed to remain the same in S' as in S . The literals in S n S' are those whose val­ ues are preserved by inertia. We obtain Definition 2 by adding the literals in SnS' as additional premises to the derivability condition in Definition 1.

Definition 2 For any interpretation S and any explicit effect E, Res 2 (E, S) is the set of interpretations S' such that

Consider again the state S = {p, q} and an action that makes p false. Choosing E = { ·p}, we have Rei ( E, S) = { { ·p, q}}. Because of the assumption of inertia, Res 2 (E, S) may be nonempty even when the ex­ plicit effect does not imply a value for every atom.

Given an interpretationS and an explicit effect E, the solutions to the equation that appears in Definition 2 are the interpretations S' that are fixpoints of the function .AX. { L : ( S n X) U E f- L}. The following example shows that there may be more than one fixpoint. Let

Then

The definition of the transition function for the lan­ guage A of Gelfond and Lifschitz [1993] corresponds to the special case of Definition 2 in which the explicit ef­ fect E is required to be a consistent set of literals. Under this restriction, Rei(E, S) will always be a singleton.

We are now ready to reformulate Winslett's definition for the framework with inertia and background knowl­ edge in the form of formula constraints. We obtain Defi­ nition 3 by simply adding B to the premises of the deriv­ ability condition in Definition 2.

Definition 3 For any interpretation S, any explicit ef­ fect E, and any set B offormula constraints, Res1(E, S) is the set of interpretations S' such that

Winslett's definition expresses the idea of minimizing change. Definition 3 has a very different form; it is given in terms of a fixpoint condition. Despite this difference, the two definitions are equivalent, as the following propo­ sition shows.

Proposition 1 For any interpretation S, any explicit effect E, and any set B of formula constraints, Res~ (E, S) = Res1(E, S).

Proof. For the left-to-right direction, assume that S' E Res~ (E, S). LetS" be a model of (S n S') U E U B. It follows that S n S' ~ S", so S n S' ~ S n S". Since S' E Res~ (E, S) and S" is a model of E U B , we know that S n S' is not a proper subset of S n S". Thus, S n S' = S n S". It follows that S" = S', since S, S', and S" are interpretations. So S' is the unique model of (S n S') U E U B. Therefore, S' = {L : (S n S') U E U B f- L}, and so S' E Res1(E, S) . For the right­ to-left direction, assume that S' E Res1(E, S). Then S' = { L : ( S n S') U E U B r L}. It follows that S' is the unique model of (S n S') U E U B. Let S" be a member of Res~ (E, S) such that S n S' ~ S n S" . We will show that S' = S". We know that S" is a model of E U B. Since S n S' ~ S n S", S" is a model of S n S'. So S" is a model of (S n S') U E U B. Therefore, S" = S'. D

4 Possible Next States: Causal Laws

Given our reformulation of Winslett's definition, it is now a simple matter to define the possible next states in the presence of background knowledge in the form of "causal laws," represented as inference rules.

We obtain the definition for Res in the present frame­ work by replacing f- in Definition 2 by f-c. We do not include formula constraints (by similarly modifying Defi­ nition 3), because, as we will see, for the purpose of defin­ ing Res they are easily represented by inference rules. 3

Definition 4 For any interpretation S, an; explicit effect E, and any set C of inference rules, Resc ( E, S) is the set of interpretations S' such that

For example, let

Then

Again, ·Walking is a ramification.

3 Definition 4 is closely related to the definition of "rule up­ date" in [Przymusinski and Turner, 1995), which generalizes revision programming [Marek and Truszczynski, 1994].

One advantage of Definition 4 over Definition 3 is il­ lustrated by the following variation on the previous ex­ ample. Let

with Cas before. Then Res~(E, S) is empty, whereas

Intuitively, Res~(E, S) is correct. Since we cannot make Alive true by making Walking true, we cannot perform an action in state S whose explicit effect is {Walking}, because this effect implies a change {namely, making Alive true) that the action does not cause. 4 This is an example of a derived qualification.

Another advantage of using causal laws is illustrated by the domain introduced in [Lifschitz, 1990] in which there are two switches and a light. Let

Then

The second state in Res~(E, S) is anomalous, and results from the unintended ramification ...., Up2. In [Lifschitz, 1990] and [Kartha and Lifschitz, 1994], this ramification is blocked by declaring Up1 and Up2 to be "in the frame" and On to be "not in the frame ." By constrast, the use of inference rules in place of formula constraints makes the frame/nonframe distinction unnecessary for the purpose of limiting possible ramifications. For instance, let C contain the inference rules

Then

Notice that in each of the previous examples, Res~(E, S) is a subset of Res~(E, S) . The following proposition shows that this relationship holds whenever B and C are related as above.

Proposition 2 Let C be a set of inference rules, and let B = { ~ => '1/J : ~ => '1/J E C}. For every interpretation S and explicit effect E, Res~(E, S) ~ Res~(E, S).

Proof. Suppose that S' E Res~(E, S) . So S' = {L : (S n S') U E f-c L} . It follows that S' = {L: S' f-c L}. Therefore, for any formula ~, S' f-c ~ if and only if S' f= ~ - Now consider any formula~=> '1/J in B such that S' f= ~ - We know that S' f-c ~,and since~=> '1/J belongs to C, it follows that S' f-c '1/J. Therefore S' f= '1/J, which shows that S' is a model of B. Clearly, S' also satisfies E, so we have shown that S' satisfies E U B. Let S" be a model of EUB such that SnS' C SnS" . We need to show that S" = S'. Since S' and S 71 are interpretations, it is enough to show that S' ~ S".

4 lnt.uitively, since not being alive causes not walking, the conditional (Walking :::> Alive) holds in every possible state of the world, and in this sense Walking implies Alive . How­ ever, the inference rule (·Alive=>....,Walking) does not cap­ ture this intuition. This is a deficiency in the representation of causal laws which is remedied in Sections 6-8.

Since B = { ~ => '1/J : ~ => '1/J E C}, we have { L : S" f-c L} ~ { L : S" U B f- L} . Finally, since S" satisfies B, { L : S" U B f- L} = S" . o

5 Ramification and Qualification Constraints

Lin and Reiter [1994] draw a pragmatic distinction be­ tween two kinds of state constraints: ramification con­ straints, which yield indirect effects, and qualification constraints, which yield action preconditions. As they observe, the same distinction was drawn earlier by Gins­ berg and Smith [1988]. In the language of inference rules , we can give a syntactic form to this distinction. Suppose that ~ is a formula constraint. If we wish ~ to function as a ramification constraint, we write the rule

If instead we wish ~ to function as a qualification con­ straint we write the rule

In Definition 3 all formula constraints function as ram­ ification constraints. The correctness of our encoding of ramification constraints is demonstrated by the following proposition .

Proposition 3 Let B be a set of formula constraints, and let C = {True=> ~ : ~ E B}. For every interpreta­ tion S and explicit effect E, Res~ ( E, S) = Res~ ( E, S).

Proof. Due to the special form of the rules in C , it is clear that for any set r of formulas and any formula ~, we have rUB f- ~ if and only if r f-c ~ - Hence, S' E Res~ ( E, S) iff S' = { L : ( S n S') U E U B f- L} iff S' = {L : (S n S') U E f-c L} iff S' E Res~(E, S) . o

The preceding proposition also shows that the frame­ work of Definition 3 is subsumed by that of Definition 4.

As an example of a domain in which a state constraint is intended to function as a qualification constraint, we consider a simplified version of a domain from [Lin and Reiter, 1994]. Imagine an ancient kingdom in which there are two blocks . Either block may be painted yel­ low, but by order of the emperor at most one of the blocks is permitted to be yellow at a time . Consider a state in which the second block is yellow. Intuitively, in this state it is not possible to paint the first block yel­ low. Representing the emperor's decree by a ramification constraint does not conform to this intuition. Indeed, let

Then

So painting the first block yellow changes the color of the second block! On the other hand, if we represent the em­ peror's decree as a qualification constraint by redefining Cas

then Res~ (E , S) is empty, which conforms to our intu­ ition that it is impossible to paint the first block yellow in state S .

The following straightforward proposition shows that rules of the form we write for qualification constraints cannot lead to ramifications, but can only rule them out.

Proposition 4 Let C be a set of inference rules, and let <P be a formula. Let C' = C U { ·</> ::::} False}. For all interpretations S and S', and any explicit effect E , S' E Res~,(E,S) iff S' E Res~(E,S) and S' f= ¢;.

Brewka and Hertzberg [1993], who also use inference rules to represent causal laws, propose a modification of Winslett's definition [1988] in which causal laws play a role in the definition of minimal change between states. Because of the role that minimal change continues to play in their definition, they cannot express qualification constraints in the manner shown above. Nor do they ob­ tain derived qualifications of the kind illustrated by the Walking/Alive example. 5 Notice that the causal law -.Alive :::}--, Walking has neither the form of a ramifica­ tion constraint nor the form of a qualification constraint. In fact , as illustrated in Section 4, it sometimes leads to ramifications and sometimes qualifications.

6 The Logic of S-Conditionals

Representing "causal laws" by inference rules is conve­ nient, but not ultimately satisfactory, for two reasons. First , an inference rule is not an object language sen­ tence , and therefore, unlike, for example, a formula con­ straint, is not interpreted declaratively. As a result, whereas Definitions 1- 3 of Section 3 may be recast in semantic terms by simply replacing the derivability rela­ tion 1- by the consequence relation f=, this is not true of Definition 4. Secondly, although a causal law in­ tuitively implies its corresponding material conditional (indeed, it implies the corresponding strict conditional, which says that the material conditional holds in every possible state of the world), an inference rule does not . In this section, we prepare to remedy these deficiencies in the representation of "causal laws" by defining a new conditional logic C6 .. t, which is an extension of S5 modal logic.

5 Even in cases where derived qualifications are not in­ volved, Brewka and Hertzberg may obtain results ctifferent from those of Definition 4.

A specific Cfla.t language is given by a fixed set of atoms. The formulas of the language are formed from its atoms and expressions of the form (1) , i.e .,

(where¢; and 1/J are formulas ofpropositionallogic) , using propositional connectives and the modal operator 0 . We say that the language is "flat," because the operators D and ::::} are not allowed to occur in ¢; or 1/J. 6 In the context of a Cflat language, an expression of the form (1) will be called an s-conditional , and may be read as: the truth of ¢; determines the truth of 'f/;. 7 Informally, an s-conditional ¢;::::} 1/J is true just in case in every part of every possible state of the world in which ¢; is true, 1/J is true as well .

An S5 structure can be defined as a pair (E, S), where E is a nonempty set of interpretations, and S is a distin­ guished interpretation in E. A Cfla.t structure is obtained by replacing the set E by a set n of sets of interpreta­ tions.

A structure for a Cfla.t language is a pair (n, S), where n is a nonempty set of nonempty sets of interpretations (of the atoms of the language), and S is an interpretation such that {S} En. The elements of n are called partial states. By S(it) we designate the set of states, defined as: S(n) = {S : {S} En} . (The set S(it) corresponds to the set E in an S5 structure.) We impose the following structure condition: for every partial state U E n, there is a state S E S(it) such that S E U. This reflects the natural requirement that every partial state be a part of some state.

For any set U of interpretations and any formula¢; of propositional logic, we write U f= ¢; as an abbreviation for the expression: for all S E U, S f= ¢; . Furthermore, for any set r of formulas of propositional logic, we write u F= r as an abbreviation for the expression: for all <P E r, u F= ¢;.

We define when a structure (it, S) satisfies a formula <P (in symbols, (it, S) f= <P) as follows . For all formulas ¢; and 1/J (except in the last clause below),

In the last clause, ¢; and 1/J are formulas of propositional logic.

Let T be a set of formulas. A model ofT is a structure that satisfies every formula in T . We say that T entails a formula <P (in symbols, T f= <P) if every model of T is a model of </J .

6 Restricting </>and 1jJ in this way is not essential. In fact , the language Cfla.t is a simplified version of a more general language C, in which </>and 1/J are permitted to be arbitrary formulas, possibly containing D and :::} . The advantage of Cfla.t is that it is possible to give its semantics using a simpler model structure than is required for C.

7 An alternative reacting is: <f>'s being true is a sufficient conctition for 1/J's being true. This reacting is our motivation for the name "s-conctitional."

It is easy to see that an s-conditional entails its corre­ sponding strict conditional, that is,

It is also easy to see that an s-conditional does not necessarily entail its contrapositive. For example, let S1 = {a,b}, S2 = {a,·b}, Sa= {·a,·b} , and

Observe that M f= a::::} b, but M ~ ·b::::} ·a. These are two important properties of causal laws.

7 S-Conditionals and Inference Rules

In this section we briefly investigate the semantical re­ lationship between s-conditionals and inference rules. Throughout this section we will use the term formula to mean a formula of propositional logic.

For any set U of interpretations, by Th(U) we mean the set of formulas <P such that U f= </J. For any set I' of formulas , by Mod(r) we mean the set of interpretations that satisfy r.

Throughout the remainder of this section, let C be a fixed set of s-conditionals.

Fact 1 Let (0, S) be a model of C. If U E 0 then Th(U) is closed under C.

A model (0, S) of C is called maximal if there is no model (0', S') of C such that 0 is a proper subset of 0'. It is clear that the maximal models of C can differ only in their second components.

Even when (0, S) is maximal, the converse of Fact 1 may fail to hold. This is due to the structure condition which requires every set U E 0 to contain an interpreta­ tionS' such that {S'} E 0. This complication motivates the following definition.

Let I' be a set of formulas . We say that I' is com­ pletable wrt a set of inference rules if there exists a max­ imal consistent superset I'' of I' such that I'' is closed under the inference rules.

Fact 2 Let (0, S) be a maximal model of C . For any set U of interpretations, if Th(U) is closed under C and completable wrt C then U E 0.

In the next section we will use the following lemma to justify a reformulation of Definition 4.

Lemma 1 Let (0, S) be a maximal model of C, and let I' be a set of formulas that is completable wrt C. For any formula </J, I' f-c </J if and only if for all U E 0, if u F= r then u F= </J.

Proof. For the left-to-right direction, assume that I' f-c </J. Suppose U E 0 and U f= I'. Then Th(U) is logically closed, closed under C (by Fact 1), and con­ tains I'. Since r f-c <P, we know that <P is in the smallest such set. So <P E Th(U). By the definition of Th, U f= </J.

For the right-to-left direction, assume that for all U E 0, if U f= I' then U f= </J. Let I'' be the smallest logi­ cally closed set that is closed under C and contains I'.

We will show that I'' is completable wrt C. Since I' is completable wrt C, we know there is a maximal consis­ tent superset I'" of I' that is closed under C. Thus, I'" is a logically closed set that is closed under C and contains I'. Since I'' is the smallest such set, I'' ~ I'". Hence, I'' is completable wrt C. Notice that I''= Th(Mod(I'')). Thus, by Fact 2, Mod(I'') E 0 . Moreover, since I'~ I'', Mod(I'') f= I'. Since Mod(I'') E 0, Mod(I'') f= </J. Thus, by the definition of Th, <P E I''. By the choice of I'', r f-c </J. 0

8 Causality versus Implication

In this section, we recast Definition 4 semantically, rep­ resenting causal laws as s-conditionals, instead of as in­ ference rules. Doing so will allow us to clarify the sense in which our theory of ramifications and qualifications is a "causal" theory.

Definition 4' Let C be a set of s-conditionals, and let M = (0, S") be a maximal model of C . For any stateS and explicit effect E , Resfr(E, S) is the set of states S' such that

The following proposition shows that Definitions 4 and 4' agree where both are defined.

Proposition 5 Let C be a set of s-conditionals. Let M = (0, S') be a maximal model of C . For any stateS and explicit effect E, Rest(E, S) = Resf.r(E, S).

Proof. For any set I' of formulas of propositional logic, let >.(I')= {L: for all U E 0, if U f= I' then U f= L}. It will be sufficient to show that for any interpretation S, s = {L : r f-c L} iff s = >.(r).

For the left-to-right direction, let S be an interpreta­ tion and r be a set of formulas of propositional logic such that S = {L : I' f-c L} . Because S = {L : I' f-c L} and S is an interpretation, Th( { S}) = { </J : I' f-c <P} . Clearly, Th( {S}) contains I' and is closed under C, which shows that I' is completable wrt C. By Lemma 1, {L : r f-c L} = >.(r). So s = >.(r).

For the right-to-left direction, let S be an interpreta­ tion and I' a set of formulas of propositional logic such that S = >.(r) . Since >.(I') is consistent, we know there is a U E 0 that satisfies I'. Moreover, since >.(I') = S, we know that for every such U, U f= L for every L E S . This shows that { S} belongs to 0 and satisfies I'. By the definition of Th, since { S} f= I', I' ~ Th( { S}) . By Fact 1, since {S} E 0, Th( {S}) is closed under C. So I' is completable wrt C. By Lemma 1, {L: I' f-c L} =>.(I'). So S = { L : I' f-c L}. o

Given Propositions 3 and 4, it follows from Propo­ sition 5 that s-conditionals of the forms True::::} <P and ·<P::::} False function (wrt Definition 4') as ramification and qualification constraints, respectively. It is interest­ ing to note that the first of these says that <P holds in ev­ ery partial state, whereas the second says that ·<P holds in no partial state. Because partial states have truth value gaps, these meanings are distinct. Thus, ramifica­ tion and qualification constraints are now distinguished semantically as well as syntactically.

In order to further explain what is distinctive about our theory, it will be convenient to assume, for the time being, that (S n S') u E is finite . Moreover, in order to simplify notation, whenever (S n S') U E appears in a formula we will take it to stand for the (finite) conjunc­ tion of its elements. Using this convention, we can say that S' E Res't(E, S) if and only if

Given an S' E Res't(E, S), we will say that a literal L E S' is a ramification if (S n S') U E ~ L. Assume that L is such a ramification. It is interesting to contrast the condition

from Equation (3), which roughly speaking says that L is caused, with a similar condition

which says that L is implied, in the sense that in every possible state in which (S n S') U E is true, L is true. Since, by (2), (S n S') U E => L entails D ( ( S n S') U E :::> L), it is clear that the former condi­ tion is stronger than the latter.

If we wished to require merely that ramifications be implied, rather than caused, we would instead impose the fixpoint condition

This condition corresponds to Definition 3. To see this, let B be a set of formula constraints, DB = {D¢ : ¢> E B}, and M be a maximal C11 .. 1 model of DB. 8 It can be shown that

It follows that S' is a fixpoint of Equation ( 4) if and only if S' belongs to Res1 ( E , S) .

Let ¢> be a formula of propositional logic. It is inter­ esting to observe that in C11 .. 1 the state constraint D¢ is logically equivalent to the s-conditional ·¢ => False, which has the form of a qualification constraint. This may seem puzzling, since qualification constraints do not lead to ramifications, while state constraints tradition­ ally have been used to do precisely that . The puzzle is resolved, however, by recalling that in the causal theory of Definition 4' a requirement stronger than the usual one is placed on ramifications: namely, the requirement that ramifications be caused (as in Equation 3) and not merely implied (as in Equation 4) .

Acknowledgements

The authors would like to thank Vladimir Lifschitz for many useful discussions on the subject of this paper. We are also grateful to Nicholas Asher , Chitta Baral, Enrico Giunchiglia, G. Neelakantan Kartha, and Rob Koons for their comments.

8 The elements of DB are state constraints; each of them says of the corresponding formula in B that it is true in every possible state of the world.