A Cumulative-Model Semantics for Dynamic Preferences on Assumptions

1 Introduction

In the absence of complete information, it is necessary to base decisions and conclusions on assumptions. If those assumptions were arbitrary, the resulting decisions and conclusions would be arbitrary as well. Depending on the given information, best assumptions are chosen.

Different ways for defining best assumptions (or de­ fault rules) have been studied in nonmonotonic reason­ ing. A sound and declarative method is provided by preferences on assumptions. They are e.g. used in prior­ itized circumscription [McCarthy, 1986; Lifschitz, 1985; Grosof, 1991] and for preferred subtheories [Brewka, 1989]. Preferences decide which assumptions will be selected first in presence of conflicts between assump­ tions. In absence of conflicts, they don't have any effect. Furthermore, preferences enable a preferential semantics leading to clear logical properties, as well as construc­ tive characterizations in form of inductive definitions. Finally, they allow to express the important specificity principle in inheritance systems in a clear way. All these points are difficult to achieve in alternative approaches such as default logic. A problem, however , is how to specify preferences:

1. Static preferences are specified outside the logical theory to which they apply. They are given in form of priorities [McCarthy, 1986; Lifschitz, 1985] or in form of a partial order on assumptions [Brewka, 1989; Grosof, 1991]. Specifying such an ordering is a minutely work. It would be preferable to write down quantified and conditional statements on pref­ erences in the logical theory itself.
2. Implicit preferences are used in conditional ap­ proaches lGeffner and Pearl, 1992; Kraus et al., 1990]. Default rules of the form a; f--.- /i can be (partially) ordered by exploiting specificity relations between the contexts a;. However, other kinds of preference knowledge cannot be expressed. We refer the reader to [Brewka, 1994] who argues in favour of explicit preferences.

In order to allow a clear, explicit, and flexible specifica­ tion of preferences, we embed them in the logical the­ ory itself. As a consequence, preferences on assumptions can depend on (other) assumptions and thus become dy­ namic. We argue that those dynamic preferences are quite natural in human commonsense reasoning and il­ lustrate this by the following example:

Jim and Jane have the following habits:

1. Normally, Jim and Jane go to at most one attraction each evening.
2. Jim prefers the theatre to the night club.
3. Jane prefers the night club to the theatre.
4. If Jim invites Jane then he respects her preferences (and vice versa).
5. Normally Jim invites Jane .
6. An exception to 1 is Saturday.
7. An exception to 5 is Jim's birthday, where Jane invites Jim.

If no further information is given we conclude that Jim and Jane will go to the night club. When we learn that Jim has birthday we revise this and conclude that they go to the theatre. However, the day in question is a Satur­ day. Hence , they should go to both attractions. Finally the news tell that the theatre is closed for work. Thus we again conclude that they go to the night club.

Dynamic preferences have been examined in the scope of the TAsso-project on graphic configuration under uncertainty. The default reasoning system EXCEPT II uses dynamic preferences for determining an or­ der in which assumptions are inspected [Junker , 1992; Junker , 1995]. Problems are provided by cyclic prefer­ ences , as well as by new preferences that contradict the already chosen part of the order. Brewka succeeded to integrate dynamic preferences into default logic [Brewka, 1994] and logic programming [Brewka, 1996]. Defaults are applied in a certain order that is chosen initially. The dynamic preferences obtained as consequences of defaults must be consistent with this order.

Both approaches do not guarantee the existence of so­ lutions. Furthermore, they miss a clear preferential se­ mantics as well as a constructive characterization. In this paper, we present a solution to these problems:

1. In section 2, we show how to embed assumptions and preferences in a logical language.
2. We seek a preferential semantics for static prefer­ ences in section 3. We analyse limits of existing approaches and elaborate a preferential semantics based on cumulative models [Kraus et a/., 1990].
3. We extend this semantics to dynamic preferences in section 4. The resulting nonmonotonic inference relation inherits all properties of Lehmann's system C [Kraus et a/., 1990].
4. This semantics then points out how to modify the constructive approach in [Brewka, 1989; Junker and Brewka, 1991] to dynamic preferences.

Finally, we discuss a simple example in section 5, as well as related work in section 6.

2 Preferences in a Logical Language

In this section, we show how to express preferences on assumptions in a first-order language. For this purpose, assumptions must be named by ground terms. Similar to circumscription , we do not change the syntax of a logical language, but introduce special predicate symbols:

• a unary predicate symbol c for chosen assumptions 1 .
• a binary predicate symbol <---- for preferences.

If t , h , t 2 are ground terms then c(t) means that an as­ sumption of name t is chosen and t 1 <---- t 2 means that the assumption of name t 1 is preferred to the assumption of name t 2 . Let ,C be a first-order language having the predicate symbols c, <---- and an unsatisfiable constant l_ .

Named default rules in the sense of [Poole, 1988] can easily be translated to this quite technical representa­ tion. A default rule d : a :J 1 of name d means that a normally implies I· It can be written as a 1\ c(d) :J I·

We write our example directly in the translated form. We abbreviate night club by nc and theatre by th. Fur­ thermore, we introduce the terms onev , gov(x), invv for naming default rules:

1 In fact c(t) corresponds to ·ab(t) .

1. Vx.c(gov(x)) :J go(x)
2. c( onev) 1\ go( nc) 1\ go( th) :J j_
3. invites(jim, jane) :J gov(nc) <---- gov(th)
4. invites(jane, jim) :J gov(th) <---- gov(nc)
5. c( invv) :J invites(jim, jane)
6. saturday :J ·c( onev)
7. hasBirthday(jim) :J ·c( invv) 1\ invites(jane, jim)

Since the assumptions invv , onev influence decisions about the assumptions gov(nc) and gov(th) , but not vice versa, we put them into a level of higher priority by adding the following preferences:

In order to simplify the discussion in this paper , we fol­ low [Poole, 1988] and suppose that all possible assump­ tions are given explicitly. Furthermore, we suppose that the set of these assumptions is finite :

1. Let N be a finite set of ground terms of ,C that serve as names of assumptions.
2. Let A:= {c(t) It EN} be the corresponding set of assumptions.

Thus, only assumptions from A will be selected and only preferences between elements of N will be relevant.

Given a logical theory r ~ £ , we consider subsets of A that are consistent w.r .t . r . Let Cr :={A~ A I Aur ~ l_} be the set of these assumption sets. The following sections show how to define preferred elements of Cr.

3 Static Preferences

In this section, we suppose that static preferences in form of a strict partial order -< ~ N x N are given.

We first examine existing approaches for defining pre­ ferred assumption sets. The first one follows the idea of a preferential semantics [Shoham, 1987]. We lift the partial order -< on assumption names to a partial order -<a on assumption sets and select the -<a-minimal ele­ ments of Cr. We use an order proposed in [Geffner and Pearl, 1992; Grosof, 1991] , where worse assumptions are exchanged by better assumptions:

A ~ A is called G-preferred assumption set of r iff 1. A E Cr and 2. A* -<a A implies A* tJ. Cr .

The order -<a is transitive and irrefiexive [Geffner and Pearl, 1992]. Since the set A is finite the existence of G-preferred assumption sets is thus guaranteed.

The second approach considers a partial order an in­ complete specification of a strict total order < ~ N x N [Brewka, 1989] . A strict total order on a finite set N uniquely defines an enumeration t1 , ... , tn of N that respects < in the sense that tj < tk iff j < k for all j ,k=1, ... , n.

We inspect the assumptions in increasing order and se­ lect them if this selection is consistent w .r. t. the already chosen assumptions:

Definition 3.2 Let < C N x N be a strict total order and t1 , ... , tn be the en-;;meration of N that respects<. Let A 0 := 0 and

Then A, is the selection of<. A is a B-preferred as­ smnption set iff A is the selection of a strict total order < which satisfies -< <;; <.

This constructive definition immediately gives rise to an algorithm for computing B-preferred assumption sets for decidable sub-languages£. [Junker and Brewka, 1991] shows that every B-preferred assumption set is a G­ preferred one, but the inverse is not true. A counterex­ ample is the partial order h -< t3, t 2 -< t 4 and th~ the­ ory f o = { · c(t1) V ·c(t2), ·c(t1) V ·c(t3) , ·c(t1) V ·c(t4) , ·c(t2) V · c(t3) , ·c(t2) V ·c(t4)} . When deter­ mining B-preferred theories, we must start an enumera­ tion by t 1 or t 2 . Thus , we obtain two B-preferred sets, namely {c(t1)} and {c(t2)}. The set {c(t3),c(t4)} is G­ preferred, but not B-preferred. Hence, G-preferred as­ sumption sets cannot serve as a preferential semantics for B-preferred assumption sets.

Thus , we have two approaches for treating static pref­ erences on assumptions. G-preferred assumption sets seem to be too weak since we would not accept the worst choices { c( t3 ) , c( t4 )} as long as the better choices { c( t 1)} and { c(t2)} are possible.

If we vary the example we observe that there is no strict partial order -<' on assumption sets that produces B-preferred assumption sets as minimal elements of Cr . Consider the following theories and their B-preferred as­ sumption sets:

Assume that the -<'-minimal elements of Cr coincide with the B-preferred assumption sets . From the last case, we infer that { c(t3), c(t4)} is -<'-smaller than the sets 0, { c( t 3)} , and { c( t 4)}. The second and third cases show that neither {c(tl)}, nor {c(t2)} are -<'-smaller than {c(t3), c(t 4)}. Hence, the set {c(t3 ), c(t4)} must be a B-preferred set of fa which is a contradiction. We conclude that the simple semantical framework is not sufficient to give a preferential semantics to B-preferred assumption sets.

Rescue comes from Lehmann's more general frame­ work [Kraus et al., 1990], which is based on structures of the form C := ( S, l , <---) where S is a set of states and ~ <;; S x S is an antisymmetric relation on states. Each state s E S is labelled with a set l(s) of worlds (i.e. log­ ical interpretations). A state s satisfies a theory f if all interpretations in l( s) satisfy f . Let Sr be the set of all states satisfying f . A state s is a <--minimal element of Sr iff s E Sr and s· <-- s implies s· ~ Sr . 1/J can non­ monotonically be inferred from f (written as f 1---c 1/;) iff all <--minimal elements of Sr satisfy 1/;.

The existence of <--minimal states is ensured by the following property: The order <-- is called smooth on a set X iff for all s E X there exists a <--minimal state s· in X such that s· = s or s· <-- s. C = (S , l , <--) is called a cumulative model iff the order <-- is smooth on Sr for all theories f. Lehmann has shown that each cumulative model defines a nonmonotonic inference relation satisfy­ ing the following basic properties. Properties 4 and 5 together are called cumulativity:

1. a 1---c a
2. if f= a= {3, a f---c 1 then f3 f---c 1
3. if f= a :J /3, 1 f-vc a then 1 1---c f3
4. if a 1\ f3 f---c / , a f---c f3 then a f---c 1
5. if a f---c {3, a f---c 1 then a 1\ f3 1---c 1

For a given partial order -< on assumption names, we will define a particular cumulative model producing the B-preferred assumption sets as minimal states . A B­ preferred set is determined by choosing a total comple­ tion of the given partial order. We make this explicit by including this order in a state. Furthermore, a state contains an assumption set A and a non-empty set of worlds that satisfy A. This set of worlds will serve as the label of a state.

Definition 3.3 Let A <;; A be an assumption set, W be a non- empty set of worlds satisfying A , and < <;; N x N be a strict total order s. t. -< <;; <. The triple s : = (W, A,<) is called a static state. Let S be the set of a·ll static states.

A static state s := (W, A,<) is labelled with the set l(s) := W of worlds . Let Sr be the set of ail static states satisfying a theory f. The usage of a set of worlds in­ stead of a single world means that static states represent incomplete information. Iff contains a disjunction a v b then a state satisfying f will contain worlds that satisfy a and worlds that satisfy b.

If a state s := (W, A ,<) satisfies f then all worlds w in W satisfy f , as well as A. Since W is not empty, fUA is consistent in this case:

We compare two static states (W1, A1, < 1) and (W2,A2,<2) if they have the same total order<= < 1 = < 2 . This order < gives rise to the following lexico­ graphical order .

Definition 3.4 Let < be a strict total order and t 1 , .. . , tn be the enumeration of N that respects < . Then <L <;; 2A x 2A is defin ed as follows : A1 <L A2 iff there exists an k s. t . c(tk) E A1 - A2 and

The order <L is a strict total order and it is smooth on Cr for all theories r. B-preferred sets are obtained in the following way:

Lemma 3.1 A is the selection of < iff A is the <L ­ minimal element of Cr.

We prefer a static state (WI,AI, <) to (W2,A2,<) if AI <L A2:

Definition 3.5 Let si := (WI, AI , <I) and s2 := (W2, A 2 , < 2 ) be two static states. The relation -<s ~ S x S is defined as follows: si -<s s2 iff 1. <I= < 2 and 2. A1 <f A2.

The resulting relation -<s is a strict partial order which is smooth on all Sr. Therefore, ( S, l, -<s) is a cumula­ tive model and has ·all the desired properties. We now establish the link to B-preferred assumption sets:

Theorem 3.2 A is a B-preferred assumption set of r iff there exists a -<s -minimal states := (W, A,<) in Sr .

Thus, we established a preferential semantics for B­ preferred assumption sets. Note that this result corrects the approach in [Roos, 1992] who gave a first trial for such a semantics.

4 Dynam.ic Preferences

In this section, we extend the preferential semantics and the constructive characterization to dynamic pref­ erences. First, we modify the notion of a state. Given a triple (W, A,<), we consider all preferences, i.e. ground formulas of the form ti +- t 2, that are satisfied by the state. A preference t 1 +- t 2 is satisfied by the state if it is satisfied by all worlds in W.

Definition 4.1 Let A~ A be an assumption set, W be a non-empty set of worlds satisfying A, and < ~ N X N be a strict total order such that t 1 < t 2 if all worlds w E W satisfy ti +- t2 (for ti, t2 E N ). The triple s := (W, A,<) is called a dynamic state. Let 1J be the set of all dynamic states.

A dynamic state s := (W, A,<) is labelled with the set l(s) := W of worlds. Let 'Dr be the set of dynamic states satisfying the theory r . If s := (W, A,<) satis­ fies a theory r then r u A is consistent and < respects all preferences that can be derived from r U A in the following way:

Let WruA be the set of all worlds satisfying fUA. Then:

Lemma 4.1 Let A ~ A and < ~ N x N be a strict total order. s := (WruA, A,<) is a dynamic state iff r u A ~ l_ and +--r,A ~ <.

We compare two dynamic states SI = (WI, AI, <I) and s2 = (W2,A2,<2) even if the orders <I and <2 are dif­ ferent . s1 is smaller than s2 iff there is an a E AI - A2 such that <I and <2, as well as AI and A2 agree on the elements that are <-smaller than a:

Definition4.2 Let SI := (WI ,AI,<I) and s2 := (W2, A2, <2) be two dynamic states. Let UI , .. . , Un and vi, ... , Vn be the two enumerations of N s.t. the first one respects <I and the second· one respects < 2. Let -<n ~ 2D x 2D be defined as follows : AI -<n A2 iff there exists a k s.t. c(uk) E AI- A2 and

Lemma 4.2 -<n is a strict partial order.

Thus, we obtained a simple preferential semantics for dynamic preferences. We require that the total order of a state respects the preferences that are satisfied by all worlds of the state and we use a kind of lexicographical order for comparing states with different base orders.

Before showing that -<n is smooth and that D := ('D, l , -<D) is a cumulative model, we give a constructive characterization of the -<n-minimal states of 'Dr. We will , step by step, construct an assumption set A, as well as a corresponding order <. Since preferences are dynamic we have to avoid certain pitfalls.

1. We can obtain cyclic preferences such as h +- t2 and t2 +- ti. A relation +- has a cycle iff its transitive closure +-+ is not irreflexive.
2. We can obtain preferences t 2 +- h although we have already chosen ti < t2.

If the first case is obtained by the initial preferences which are derived from r then there is no dynamic state satisfying r :

Definition 4.3 A theory r is called D-consistent iff r is consistent and +-t, 0 is irrefiexive.

Lemma 4.3 There exists a dynamic state satisfying r iff r is D-consistent .

The question is what to do if any of the two problematic cases above is obtained after adding an assumption a to a set A of already selected assumptions. The answer is quite simple: Don't select a because otherwise the current construction will not lead to a dynamic state. This modifies the constructive definition as follows :

Definition 4.4 Let r be a consistent theory. Let < ~ N x N be a strict total order and ti, ... , tn be the enu­ meration of N that respects<. Let B; :=A; U{c(ti+I)}. We define Ao := 0 and

Then A; is the dynamic selection of ti, .. . , t; and An zs the dynamic selection of<. The sequence ti, ... , t; zs correct iff

for j = 0, ... , i- 1. The order< is correct iff it , ... , t; is correct for all i = 1, . . . , n.

A is a D-preferred assumption set of f iff A is the dynamic selection of a correct strict total order <.

We now explore the properties of these definitions . First of all , dynamic selections are consistent and correct or­ ders respect the dynamic preferences they produce:

Lemma 4.4 Let f be a consistent theory and < ~ N X N be a strict total order. Let A be the dynamic selection of <. Then f U A~ L If< is correct then +-r,A ~ <.

Correct. sequences it, ... , t; can be constructed incre­ mentally. In each step , we pick a best element ti+t among the non-enumerated assumptions and add it af­ ter k ti+t must be a best element w.r .t. the preferences <-r,A, in order to guarantee that it, .. . ,t;,ti+t is cor­ rect. Let R; := N- {it, ... , ti}:

The existence of such best elements is insured since cyclic preferences are avoided:

Lemma 4.5 Let f be a D-consistent theory. Let it , ... , t; be a correct sequence of elements of N and A; its dynamic selection. Then there exists an enumeration ti+t, ... , tn of N- {it , ... , ti} s.t. it , . .. , tj is correct for all j = 1, .. . ,n.

Consider a. dynamic state s := (W, A,<) in Dr. If A is the dynamic selection of < then < is correct and s is a -<D-minimal state in Dr. Otherwise, there exists a state that is -<D-sma.ller:

Lemm.a 4.6 Let f be a D-consistent theory and s := ( W, A, <) be a dynamic state in Dr. Let A · be the dy­ namic selection of<.

1. If A = A* then < is correct. 2. If A= A* and s* -<D s then s* tf. Dr.

These lemmas allow to establish the two main theorems of the paper. First , -<D-minimal states have a construc­ tive characterization:

Theorem 4. 7 Let f ~ £ be a theory. A is a D-preferred assumption set of f iff there exists a dynamic state (W, A, <) that is a -<D -minimal element of Dr .

Second, we can now demonstrate the smoothness of -<D:

Lemma 4.8 -<D is smooth on Dr for f ~ £.

Theorem 4.9 D := (D, 1, -<D) is a cumulative model.

Therefore , the nonmonotonic inference relation f-.-D has t.he five basic properties of system C.

It is straightforward to adapt our approach to Lehmann's preferential models. A preferential model is a triple C := (S, I, -<) where Sis a set of states, I a func­ tion mapping each state to a single world, and -< is a strict partial order on states that is smooth on all Sr, i.e. the set of states satisfying a theory f. Preferential models additionally support reasoning by cases:

We obtain a. preferential model by restricting dynamic states (W, A, <) to those where the set W of worlds is a singleton , i.e. contains only one world. Further work is needed to adapt the constructive approach to this preferential-model semantics .

5 Example

We determine the D-preferred assumption sets of our initial example. Let fa be the set of formulas 0. - 8 and

We consider two correct strict total orders <t and <2 where

Due to formulas 7. and 8., the assumptions oneD, invD are smaller than the assumptions goD(nc) and goD(th). These formulas have been included to give the assump­ tions oneD, invD a higher priority. Now we consider the dynamic selections Ai,i off; and <i:

Aa,t = {c(oneD) , c(invD), c(goD(nc))} * Aa,2 = {c(oneD), c(invD), c(goD(th))} At ,t = {c(oneD) , c(goD(nc))} At ,2 = {c(oneD), c(goD(th))} * A2,t = {c(goD(nc)) , c(goD(th))} A2,2 = {c(goD(th)), c(goD(nc))} * A3,t = {c(goD(nc))} A3,2 = {c(goD(nc))} *

Since a normal invitation c(invD) implies goD(nc) +­ goD(th) the order <2 is not correct w.r.t. fa . Since the theory ft implies goD(th) +- goD(nc) the order <tis not correct w.r.t. ft , f 2, and f3 . As a consequence, each f ; has a unique D-preferred assumption set (marked with a *) and we obtain the following inferences: ·

The conclusions change from fa to f t since the prefer­ ences change. The change from ft to f 2 is due to the removal of a conflict. The final change is due to a new inconsistency.

6 Related Work

Brewka has extended Reiter's default logic by dynamic preferences on defaults [Brewka, 1994]. As in our ap­ proach, defaults are named by constants and prefer­ ences between defaults are expressed by a binary pred­ icate symbol. The additional expressiveness of default logic, however, makes it difficult to establish a prefer­ ential semantics. Even normal defaults as considered in [Brewka, 1994] do not have a cumulative-model seman­ tics as shown by Makinson. In order to compare both approaches, we restrict our attention to normal defaults without prerequisites, which correspond to assumptions.

Brewka requires that a theory r contains axioms stat­ ing that the predicate symbol +- represents a strict par­ tial order . These axioms ensure that no cyclic prefer­ ences are obtained. In our approach, we did not want to change the original theory r and therefore required a corresponding property on the meta-level. Brewka de­ termines preferred assumption sets as follows . An as­ sumption set A ~ A is a BD-preferred iff 1. it is the (static !) selection of a strict total order < ~ N x N and 2. r u Au {tt +- t2 I it < t2} is consistent . Here, a. total order on assumptions is chosen initially and veri­ fied in the end by comparing the chosen preferences with those that are implied by ruA. Unfortunately, there are examples that don 't have BD-preferred assumptions:

The order it < t2 is not compatible with its (static) selection {c(tt)} , but correct w.r .t . its dynamic selection {c(t3)}. The selection of c(tt) fails in the second case since the preference t2 +- tt contradicts the order tt < t 2. An analogue argument holds for t 2 < tt.

The example shows that cyclic dependencies between preferences and assumptions make the search for pre­ ferred assumption sets quite difficult. Therefore, we in­ terleave the construction of an order and an assumption set and we do not choose assumptions that have draw­ backs on the already chosen part of the order.

7 Conclusion

We showed how preferences on assumptions can directly be e~pressed in a logical theory. The resulting system offers a high degree of freedom for "programming" pref­ erence rules: Preferences can be used in implications, in quantified statements, and can themselves depend on other assumptions.

Finding a clear mathematical treatment of dynamic preferences turned out to be a non-trivial task. We de­ veloped a preferential semantics based on Lehmann's cu­ mulative models and an equivalent constructive charac­ terization. The resulting nonmonotonic logic

1. allows to program preference rules,
2. satisfies all properties of Lehmann's system C,
3. can be implemented for decidable sublanguages.

In order to keep the presentation simple and intuitive, we considered only finite assumption sets in this paper. In a. long version of the paper, we will generalize the results to infinite assumption sets and well-founded orders on assumptions.

Thus, an important milestone in the design of an applicable and powerful nonmonotonic logic has been achieved. It can be applied to default reasoning in inher­ itance system, to diagnostic reasoning, and to decision making. Future work will concentrate on algorithms and applications. Furthermore, we will elaborate a variant of our approach in Lehmann's system P which additionally supports reasoning by cases.

Acknowledgements

I would like to thank Gerd Brewka, Markus Junker, and the anonymous reviewers for helpful comments that im­ proved the quality of this paper. The paper would not have been written without the moral support of my wife Isabelle, my son Kevin, and my daughter Celine.