Compiling Reasoning with and about Preferences into Default Logic
Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence. Automated Reasoning. Pages 168-174.
© 1997 International Joint Conferences on Artificial Intelligence
Abstract
We address the problem of introducing preferences into default logic. Two approaches are given, one a generalisation of the other. In the first approach, an ordered default theory consists of a set of default rules, a set of world knowledge, and a set of fixed preferences on the default rules. This theory is transformed into a second, standard default theory, where, via the naming of defaults, the given preference ordering on defaults is respected. In the second approach, we begin with a default theory where preference information is specified as part of an overall default theory. Here one may specify preferences that hold by default, or give preferences among preferences. Again, such a theory is translated into a standard default theory. The approach differs from previous work in that we obtain standard default theories, and do not rely on prioritised versions, as do other approaches. In practical terms this means we can immediately use existing default logic theorem provers for an implementation. From a theoretical point of view, this shows that the explicit representation of priorities adds nothing to the overall expressibility of default logic.
- [Baader & Hollunder, 1993] F. Baader & B. Hollunder. How to prefer more specific defaults in terminological default logic. Proc. Int 'I Joint Conference on Artificial Intelligence , p. 669-67 4, 1993. IJCAI
- [Boutilier, 1992] C. Boutilier. What is a default priority? Canadian Conference on AI, p. 140-147, 1992.
- [Brewka, 1994a] G. Brewka. Adding priorities and speci- ficity to default logic. Proc. European Workshop on Logics in Artificial Intelligence , p. 247-260 . Springer, 1994.
- [Brewka, 1994b] G . Brewka. Reasoning about priorities in default logic. Proc. AAAI Conference on Artificial Intelligence , p. 940-945, 1994.
- [Delgrande & Schaub , 1994] J . Delgrande & T . Schaub . A general approach to specificity in default reasoning . Proc. Fourth Int 'I Conference on Know/edge Repre- sentation and Reasoning, p. 146-157.
- Morgan Kauf- mann, 1994.
- [Doyle & Wellman, 1991] J. Doyle & M.P. Wellman. Im- pediments to universal preference-based default theo- ries. Artificial Intelligence, 49(1-3):97-128 , 1991.
- [Etherington & Reiter, 1983] D.W. Etherington & R. Reiter. On inheritance hierarchies with exceptions. Proc. AAAI Conference on Artificial Intelligence, p . 104-108, 1983.
- [Geffner & Pearl, 1992] H. Geffner & J . Pearl. Condi- tional entailment: Bridging two approaches to de- fault reasoning. Artificial Intelligence, 53(2-3) :209- 244, 1992.
- [Gordon, 1993] T. Gordon. The pleading game: An Ar- tificial Intelligence Model of Procedural Justice . PhD thesis, University of Darmstadt , Germany, 1993 .
- [Grosof, 1991] B. Grosof. Generalizing prioritization. Proc. Second Int 'I Conference on Knowledge Repre- sentation and Reasoning, p. 289-300.
- Morgan Kauf- mann, 1991.
- [Lifschitz, 1985] V. Lifschitz. Closed-world databases and circumscription. Artificial Intelligence, 27 :229- 235, 1985.
- Marek & Truszczynski, .1993]
- W . Marek & M. Truszczynski . Nonmonotonic logic: context-dependent reasoning. Springer, 1993 .
- [McCarthy, 1986] J. McCarthy. Applications of circum- scription to formalizing common-sense knowledge. Ar- tificial Intelligence, 28:89-116, 1986.
- [Pearl, 1990] J. Pearl. System Z: A natural ordering of defaults with tractable applications to nonmonotonic reasoning. Proc. of the Third Conference on Theoreti- cal Aspects of Reasoning About Knowledge, p . 121-135, 1990.
- [Poole , 1988] D.L. Poole. A logical framework for default reasoning. Artificial Intelligence, 36(1) :27-48 , 1988.
- [Reiter & Criscuolo, 1981] R. Reiter & G. Criscuolo. On interacting defaults. Proc. Int 'I Joint Conference on Artificial Intelligence , p. 270-276, 1981.
- [Reiter, 1980] R. Reiter. A logic for default reasoning. Artificial Intelligence, 13(1-2) :81-132, 1980 .
- [Touretzky et al., 1987] D.S . Touretzky, J.F. Horty, & R.H . Thomason . A clash of intuitions: The current state of nonmonotonic multiple inheritance systems. IJCAI
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
In many situations in nonmonotonic reasoning the appli cation of one default is preferred to another. Perhaps the best known example is inheritance of properties, where an individual is assumed to have properties by default according to the most specific class( es) to which it be longs. Hence an individual that is a penguin (and so a bird) does not fly by default, since penguins typically don't fly, even though birds do typically fly. Preferences are also found in decision making and in scheduling. For Torsten H. Schaub*
·Previously at LERIA, Universite d'Angers, France.
Institut fiir Informatik Universitiit Potsdam Postfach 60 15 53, D- 14415 Potsdam torsten@cs.uni-potsdam.de
example, in scheduling not all deadlines may be simul taneously satisfiable; preferences then may allow some compromise solution. In legal reasoning laws may apply by default, but the laws themselves may conflict; such conflicts may be adjudicated by higher-level principles.
Our goal in this paper is to explore preference order ings in nonmonotonic reasoning, specifically in default logic [Reiter, 1980]. In the next section we examine the general notion of preference orderings on defaults. We note that there is not a single way in which preferences should be applied. Rather what we will call specificity orderings, as are used in property inheritance, can be dis tinguished from preference or priority orderings. These notions have frequently been conflated previously in the literature; here our concerns lie solely with preference orderings.
In considering how preference orderings may be en forced in default logic, we consider first where a default theory consists of world knowledge and a set of default rules, together with (external) preference information between default rules. We show how such a default the ory can be translated into a second theory wherein pref erence information is now incorporated into the theory. So with this translation we obtain a theory in "stan dard" default logic, rather than requiring machinery ex ternal to default logic, as is found in previous approaches. We subsequently generalise this approach so that prefer ences may appear arbitrarily as part of a default theory and, specifically, preferences among default rules may (via the naming of default rules) themselves be part of a default rule. We again show how such a generalised de fault theory can be translated into a "standard" default theory where preference information is incorporated into the theory.
Previous approaches have generally added machinery to an extant approach to nonmonotonic reasoning. We remain within the framework of standard default logic, rather than building a scheme on top of default logic, for several reasons. First, there exist theorem provers for default logic. Consequently our approach can be immediately incorporated in such a prover. Second, it is easier to compare differing approaches to handling such orderings. Third, by "compiling" preferences into de fault logic, and in using the standard machinery of de fault logic, we obtain insight into the notion of preference orderings. Thus for example we implicitly show that ex plicit priorities provide no real increase in the express ibility of default logic.
2 Preference Orderings
This section discusses preference orderings in general; while we employ default logic, the discussion is indepen dent of any particular approach to nonmonotonic rea soning. We can use default rules 1 to express that (3 follows by default from a by ¥· Then we can write T < :r.f. to express a preference between two defaults. Assume that we have an ordered default theory. The ex act details are given in the next section; for the time being assume that we have a triple (D, W, <), where D is a set of default rules, W a set of formulas, and < is a strict partial order on the default rules in D.
Informally a higher-ranked default should be applied or considered before a lower-ranked default. But what exactly does this mean? Consider for example the de faults concerning primary means of locomotion: "ani mals normally walk", "birds normally fly", "penguins normally swim" :
If we learn that some thing is penguin (and so a bird and animal), then we would want to apply the highest-ranked default , if possible, and only the highest-ranked default. Significantly, if the penguins-swim default is blocked (say the penguin in question has a fear of water) we don't try to apply the next default to see if it might fly. This then is standard inheritance of default properties.
The situation is very different in the next example. We have the defaults that "Canadians speak English by de fault", "Quebecois speak French by default" , "residents of the north of Quebec speak Cree by default" :
Now if a resident of the north of Quebec didn't speak Cree, it would be reasonable to assume that that per son spoke French, and if they didn't speak French, then English.
Assume that we have a chain of defaults 81 < 82 < ... < 8m. Informally, we have the following pos~ibilities with respect to how the defaults may be applied.
1 Default logic is introduced shortly.
- Pl For the maximum i for which 8i is applicable, and for j > 0, no 8i+i is denied, 2 apply 8i if possible. No other default is considered. This is the situation in (1) .
- P2 Apply 8m if possible; apply 8m-1 if possible, con tinue in this fashion until no more than k (for fixed k where 1 ~ k ~ m) defaults have been applied. This is the situation in (2) with k = 1.
An example of a general instance of P2 is where a stu dent wishes to take k = 3 computing courses, out of m = 10 possible courses, and so provides a list of pref erences over the courses. There are two important sub cases of P2 corresponding to k = 1 and k = m. In the first case a maximum of one default is applied. In the second case one attempts to apply every default.
Pl is essentially (default property) inheritance. The ordering on defaults reflects a relation of specificity; one attempts to apply the most specific default possible. In approaches such as [Touretzky et al., 1987; Pearl, 1990; Geffner & Pearl , 1992] specificity is determined implic itly, emerging as a property of the underlying system. [Reiter & Criscuolo, 1981; Etherington & Reiter , 1983; Delgrande & Schaub, 1994] have addressed adding speci ficity information in default logic. For incorporating preferences (as given in P2) , [Boutilier, 1992; Brewka, 1994a; Baader & Hollunder, 1993] consider adding pref erences in default logic while [~cCarthy, 1986; Lifschitz, 1985; Grosof, 1991] do the same in circumscription. We note however that some of these latter papers include examples best interpreted as dealing with specificity (as given in (1)), and so would appear to conflate Pl and P2.
Our concerns in this paper are with specifying pref erences and priorities, as given in P2. We assume only that we are given a set of defaults and a priority policy on defaults, along with other world knowledge. We ob serve that the framework as given in P2 is significantly more general that that of Pl. For example it seems to be an intrinsic property of inheritance as given in Pl that the ordering on defaults is determined by relative specificity of the prerequisites. So if 81 < 82 then the an tecedent of 81 is less specific than the antecedent of 82. This is not the case for P2 though. Consider a variation on (2) where in the north of Quebec the first language is French, then English, then Cree: The resulting pref erence ordering is as follows.
Indeed for preferences, one need not have any antecedent information. That one prefers something (say, a car) h . d h . ht b d . Green t at IS re , t en green m1g e expresse as ·Green <
2 i.e. we don't have that the prerequisite is true and the consequent false.
=J:-e~d. In the most general case, we might have two de faults, with no relation between them, except for some given preference relation.
3 Default Logic and Ordered Default Logic
Default logic [Reiter, 1980] augments classical logic by default rules of the form "': p,~ ... ,f3n. For the most part we deal with singular defaults for which n = 1. [Marek & Truszczynski, 1993] show that any default rule can be transformed into a set of singular defaults; hence our one use of a non-singular rule in Section 5 is for nota tional convenience only. A singular rule is normal if {3 is equivalent to -y; it is semi-normal if {3 implies 'Y· We sometimes denote the prerequisite a of a default 6 by Prereq(6), its justification {3 by Justif(6) and its conse quent 'Y by Conseq(6). Empty components, such as no prerequisite or even no justifications, are assumed to be tautological. Defaults with unbound variables are taken to stand for all corresponding instances. A set of default rules D and a set of formulas W form a default theory (D, W) that may induce a single or multiple extensions in the following way.
Definition 3.1 Let (D, W) be a default theory and let E be a set of formulas. Define Eo = W and fori ~ 0:
Then E is an extension for (D, W) if E = U~o E; .
Any such extension represents a possible set of beliefs about the world at hand. The above procedure is not constructive since E appears in the specification of Ei+l · We define 3 r = U~o ri as the set of default rules gen erating extension E.
For adding preferences among default rules, a default theory is usually extended with an ordering on the set of default rules. In analogy to [Baader & Hollunder, 1993; Brewka, 1994a], an ordered default theory (D, W, <) is a finite set D of default rules, a set W of formulas, and a strict partial order < ~ D x D on the default rule. For simplicity we assume the existence of a default h = T + T E D where for every rule 6i =f. h we have 6i < h. This gives us a (trivial) maximally preferred default that is always applicable to "start things off".
4 Static Preferences on Defaults
We show here how ordered default theories can be trans lated into standard default theories. Our strategy is to add sufficient "hooks" to a default rule in a theory to enable the control of rule application. We begin with an ordered default theory (D, W, <) which is then trans lated into a standard default theory (D', W') such that the explicit preferences in < are "compiled" into D' and W'.
3 For simplicity, we refrain from parameterizing r by D and E.
To this end, we associate a unique name with each default rule. This is done by extending the original lan guage by a set of constants N 4 such that there is a bijec tive mapping n : D -+ N . We write n6 instead of n(6) (and we often abbreviate n6, by ni to ease notation). For default rule 6 along with its name n, we sometimes write n : 6 to render naming explicit. To reflect the fact that we deal with a finite set of distinct default rules, we adopt a unique names assumption (UNA) and domain closure assumption (DCA) with respect to N. That is, for a name set N = {n1 , .. . , nm}, we add axioms Vx. name(x) = (x = n1 V ... V x = nm) and (ni =f. nj) for all ni, ni E N with i =f. j . For convenience, we then write Vx E N. P(x) instead of Vx. name(x) :J P(x) . In the sequel, we use DCAiv and UNAN to abbreviate domain closure and unique names axioms for N.
The use of names allows the expression of preference relations between default rules in the object language. So we can assert that default ni : 7 is preferred to ni : T by ni -< ni, where -< is a (new) predicate in the obJect language. Finally, in discussions of preference relations, we sometimes write 6i < 6j or ¥ < 7 , to show a preference between two defaults; however it should be kept in mind that these latter expressions are not expressions within a default theory (as are given by -<), but expressions about a default theory.
If we are given Oi < 6j, then we want to ensure that before 6i is applied, that Oj be applied or found to be inapplicable. 5 We do this by first translating default rules so that rule application can be explicitly controlled. For this purpose, we need to be able to, first, detect when a rule has been applied or when a rule is blocked, and, second, control the application of a rule based on other antecedent conditions. For a default rule ~ there are '"f two cases for it to not be applied: it may be that the antecedent is not known to be true (and so its negation is consistent), or it may be that the justification is not consistent (and so its negation is known to be true) . For detecting this case, we introduce a new, special-purpose predicate bl(·). Similarly we introduce a special-purpose predicate ap(·) to detect the case where a rule has been applied. For controlling application of a rule we intro duce predicate ok(-). Then, a default rule 6 = ~ 1s '"f mapped to
4 This is done also in [Brewka, 1994b] . Theorist [Poole, 1988] uses atomic propositions to name defaults.
5 That is, we wish to exclude the case where 8; E r n and
8; E r m for n :::; m.
These rules are sometimes abbreviated by 6a, 6b,, 6b 2 , resp.
None of the three rules in the translation can be ap plied unless ok( n) is true. Since ok( ·) is a new predicate symbol, it can be expressly made true in order to po tentially enable the application of the three rules in the image of the translation. If ok( n) is true, the first rule of the translation may potentially be applied. If a rule has been applied, then this is "recorded" by assertion ap(n) . The last two rules give conditions under which the original rule is inapplicable: either the negation of the original antecedent a is consistent (with the exten sion) or the justification f3 is known to be false ; in either such case bl(n) is concluded.
This translation clearly says nothing about which de fault precedes what in order of application. However, for 6i < 6i we can now fully control the order of rule appli cation: if 6i has been applied (arid so ap(ni) is true), or known to be inapplicable (and so bl( ni) is true), then it's ok to apply 6i. So we would have something like (ap(nj) V bl(ni)) :J ok(n,), but adjusted to allow for the fact that we might have other rules with higher priority than 6, . Further, given that 61 < 62 < 63 we would want the order of application to be 63 then 62 then 61. Given the predicates bl(-) and ap(-) it is a straightforward mat ter to also assert that a maximum of one default in a priority order can be applied, or in the general case that k rules can be applied.
Taking all this into account, we obtain the following translation mapping ordered default theories in some language .C onto standard default theories in the lan guage .c+ obtained by extending .C by new predicates symbols(·--< ·), ok(-), bl(·), and ap(-), and a set of asso ciated default names:
Definition 4.1 Given an ordered de fault theory (D, W, <) over .C and its set of default names N = {n6 16 ED} , define T((D, W, <)) = (D', W') over c+ by
W' contains prior .world knowledge, together with as sertions for managing the priority order < on defaults.
The first part of W-< specifies that --< is a predicate drawn from strict partial order <. ok( n T) asserts that it is ok to apply the maximaliy preferred (trivial) default . The third formula in w-< controls the application of defaults: for every ni, we derive ok(ni) whenever for every ni with n, --< nj, either ap(nj) or bl(nj) is true. This axiom al lows us to derive ok(ni), indicating that 6, may poten tially be applied, whenever we have for a116j with 6i < 6i that 6i has been applied or cannot be applied.
This alone however gives necessary but not sufficient conditions for rendering 6i potentially applicable. If (6, ,6i) ¢<then (ni --< ni) ¢ W-<; however, for the last formula in W-< to work properly we must be able to conclude (in the extension) that --,( ni --< ni). This is ad dressed by adding the default rule in D-< that renders the resulting theory complete with respect to priority state ments. That is, for all resulting extensions E we have that (ni --< ni) E E or --,(ni --< ni) E E. We also have (n6 --< nT) E W' for every rule 6 f:. 6T by the definition of ordered default theories. Since < is a strict partial order, W' also includes the transitive closure of--< and no reflexivities, such as n --< n.
As an example, consider the defaults:
n .~ n ·~ n·~ n . T:T 1 · c, , 2 · c, , 3 · c, , T · ~ we obtain fori= J, 2, 3:
and analogously for 8T where Ai,Bi,Ci are T . Given that 61 < 82 < 6a, we obtain n1 --< n2, n2 --< na, n1 --< na alongwithnk--< nTfork E {1,2,3}aspartofW-<. From D-< we get --,( n, --< ni) for all remaining combinations of i,j E {1,2,3, T}. It is instructive to verify that ok(n3), along with (ap(na) V bl(na)) :J ok(n2), and ((ap(n2) V bl(n2))/\(ap(na)Vbl(na))) :J ok(nt) is contained in E2 in Definition 3.1; from this we get that n3 must be applied first, followed by n2 and then n1.
Now, given A1,A2 , A3 , we obtain subsequently C3 i\ ap(na) E Ea, ok(n2) E E4, C2/\ ap(n2) E Es, ok(nt) E E6, Ct/\ap(nt) E E7. Given additionally Ca :J -,B2 and C2 :J -,Ba, we get bl(n2) E Es instead of C2 1\ ap(n2) E Es because -,B2 E E4 . Suppose there is an extension containing C2 1\ -,Ba as opposed to C3 1\ -,B2. Then however we have neither ap(na) E Ea nor bl(n3 ) E E3 , which makes it impossible to derive ok(n2) and thus -,B3 cannot belong to such an extension.
The following theorems summarize the major prop erties of our approach, and demonstrate that rules are applied in the desired order:
Theorem 4.1 Let E be an extension of T((D, W, <)) for ordered default theory (D, W, <). We have for all 8,8' ED
- ok(n6) E E
- either ap(n6) E E or bl(n6) E E
- ok(n6) E E~ and Prereq(f>) E Ej and -,Justif(f>) ¢ E implies ap( n6) E Emax(i ,j)+l
- ok( n6) E E; and Prereq( f>) ¢ E implies bl( n6) E Ei+l
- ok(n6) E E; and -,Justif(f>) E E implies bl(n6) E Ej for some j > i
- ok(n6) ¢ E,_ 1 and ok(n6) E E; implies ap(n6), bl(n6) ¢ Ej for j ~ i
Notably, Theorem 4.1.5 allows us to detect blockage due to non-derivability of the prerequisite immediately after having the "ok" for the default at hand. For an extension E and its generating default rules r, we trivially have f>a E f iff ap(n6) E E, and f>b, E for f>b, E f iff bl(n6) E E.
Theorem 4.2 Let E be an extension of T((D, W, <)) for ordered default theory (D, W, <) and r, r, be defined wrt E . Then, we have for all {j E D
For all default rules f>, f>' ED such that {j < f>', we have
The minimum two-step delay between rules stemming from {j and those originated by f>' is due to to the fact that in Definition 3.1 the deductive closure of E; is de termined at Ei+l · The important overall consequence of this series of propositions is that we have full control over default application.
Using the above properties, we can show that any ex tension of a translated default theory is a regular exten sion of the underlying unordered default theory:
Theorem 4.3 Let E be an extension of T((D, W, <)) for ordered default theory (D, W, <) over C. Then EnC is an extension of (D, W).
The approach is equivalent (modulo the original lan guage) to standard default logic if there are no prefer ences:
Theorem 4.4 For a default theory (D, W) over C and a set of formulas E, we have that E is an extension of T((D, W, 0)) iff En C is an extension of (D, W) .
5 Dynamic Preferences on Defaults
We now consider situations where the presence of prefer ences is context-dependent. We deal with standard de fault theories (D, W) over a language already including · a predicate -< expressing a preference .relation by means of default names. In order to keep a finite domain clo sure axiom, we restrict ourselves to a finite set of default rules D, being in one-to-one correspondence with a finite name set N.
Since preferences are now available dynamically by in ferences from Wand D, we lack a priori complete infor mation about the ordering predicate -< , which was avail able in the rigid case by appeal to the explicit order < be tween rules and the "closed world default" '...,(<;-<.~'!/} . This however leads to a problem. Consider where our only preference is given by ':-<-<,: . Either the default would apply or it would not; in either case we would expect one extension only. However we also have the "closed world" default for preferences, given in D-< , that asserts that if there is no known or derived preference between rules, then no preference exists. An instance of D-< is '...,(~n-<-<;:0) . So if we simply have these two defaults then we run the risk of potentially having an unwanted extension where : -.(n-<.m) applies over : n...;m. Obviously we can't -.(n-<.m) n-<.m solve the problem by asserting that '...,(ln-<~) < :nn.(,;;' since our approach would now be circular . We address this issue by adding a new binary predicate -/< indicating that for defaults {j and 6' neither (n6 -< n6') E E nor ..,(n6-< n6·) E E . We add the following rule, where x,y are variables ranging over default names:
This rule accounts for situations where neither (x -< y) nor ..,(x -< y) is derivable. That is for names n and n', the only time this rule will apply is when n -< n' ¢ E and ..,( n -< n') ¢ E. So, since -/< is an introduced predicate, the only time we have n -/< n' E E is when the default theory has no information on whether the two defaults are in a· preference relation or not .
We now consider standard default theories in a lan guage C including the set of default narnes and proposi tions formed by binary predicate -< applied to variables and default names only; these are mapped onto theories in the language C* obtained by extending C with new predicate symbols(·-/<·), ok(-), bl(-), and ap(-):
Definition 5.1 Given a default theory (D, W) over C and its set of default names N = { n6 I {j E D} , we define T((D, W)) = (D', W') over C* by
where
In contrast to Definition 4.1, D and W now may contain preference information expressed by -< applied to default names. The first three axioms in W-< account for infor mation that was explicitly provided by ordered default theories in the rigid case. The last axiom is a straightfor ward extension of that found in the rigid case, now also accounting for the information provided by the default rule in D..: .
We note that Theorem 4.1 and Theorem 4.2 carry over to the general case except for Theorem 4.1.1. We get instead
In fact , ordered default theories are treated in the same way by our basic and general approach, except for dif ferent augmented languages:
Theorem 5.1 Let (D, W, <) be an ordered default the ory over .C. For each extension E ofT((D, W, <)) there is an extension E' ofT((D, WU{n6-< n6' I (6, 6') E<})) such that E n .C = E' n .C and vice versa.
As a consequence, our general approach yields all regular extensions (modulo the original language) if ( D, W) does not contain an occurrence of-<.
Given Theorems 4.3 and 5.1, one would expect that ordered default theories would enjoy the same properties as standard default logic. This indeed is the case, but with one important exception: normal ordered default theories do not guarantee the existence of extensions. For example, the image of the ordered default theory (under our translation)
has no extension. The full paper describes formally why this is the case. Informally the problem is that we have a preference n1 < n2; however, given W = {A} default n1 applies first, and once it has applied, n2 becomes ap plicable. Thus we have a preference ordering implicit in the form of the defaults and world knowledge, but where this implicit ordering is contradicted by the assertion n1 < n2. Not surprisingly then there is no extension. There are two immediate ways to resolve this problem. First , replace the rigid preference by ~;so we have n1~n2
this preference by default only. Second is to recognise that (5) is "buggy", in the same way that incorrect pro grams require modification. The lack of extension then indicates a problem in the specification of the original theory.
We conclude this section with the observation that our translation results in a manageable increase in the size of the default theory. For ordered theory (D, W), the translation T((D, W)) is only a constant factor larger than (D, W). 6
6 Discussion and Related Work
We have presented a very general framework for incor porating preferences into default logic. Via the naming of defaults we allow preferences to appear arbitrarily in D and W in a default theory. This allows preferences among preferences, preferences by default , preferences holding only in certain contexts, and so on. Strictly speaking, such generality isn't required: [Doyle & Well man, 1991], building on work by Arrow, argue that in any preference-based default theory, for coherence, one requires a "dictator" to adjudicate preferences. That is, there must be, essentially, some way of determining a unique, complete, priority ordering. So in this ·sense, all one needs is what we have called the rigid approach of Section 4. We provide the more general framework of Section 5 for two reasons. First, it allows the more flexible specification of preferences, leaving it up to the user to ensure that there is no ambiguity in preferences. In the case where there is ambiguity in preferences (for example we might have D :::> { ~, ~} ) one typ-- n1 "'"'n2 n2-<n1 ically obtains multiple extensions. Second, we feel that the general approach is of technical interest: arbitrary defaults may be "compiled" into standard default theo ries, and so in a certain sense the explicit representation of priorities adds nothing to the fundamental power or expressibility of default logic.
Of other work in default logic treating preferences, we have argued that [Reiter & Criscuolo, 1981; Etherington & Reiter, 1983; Delgrande & Schaub, 1994] treat a sepa rate problem, that of specificity orderings, as exemplified by (1) . [Baader & Hollunder, 1993] and [Brewka, 1994a] present prioritised variants of default logic in which the iterative specification of an extension is modified. In brief, a default is only applicable at an iteration step ( cf. Definition 3.1) if no <-greater default is applicable. 7 In contrast we translate priorities into standard default theories. There is insufficient space to fully compare approaches; see [Delgrande & Schaub, 1994] for a full discussion of these approaches with regard to how they address specificity in a theory.
6 This assumes we count the default in D..: as a single default.
7 These authors use < in the reverse order from us.
We conclude with an example from [Gordon, 1993], discussed in [Brewka, 1994b]. A person wants to find out if her security interest in a certain ship is "perfected", or legally valid. This person has possession of the ship, but has not filed a financing statement . According to the code UCC, a security interest can be perfected by taking possession of the ship. However, the federal Ship Mortgage Act (SMA) states that a security interest in a ship may only be perfected by filing a financing state ment . Both UCC and SMA are applicable; the question is which takes precedence here. There are two legal prin ciples for resolving such conflicts. Lex Posterior gives precedence to newer laws; here we have that UCC is more recent than SMA. But Lex Superior gives prece dence to laws supported by the higher authority; here SMA has higher authority since it is federal law. Apart from h, we get :
To preserve finiteness , we restrict our attention to name set N =No U N1 where No= {nT, ucc, sma} and N1 = {lp(x, y), ls(x, y) I x, y E No}, and the corresponding default instances. We have the facts: possess, ship, --.finstmt , newer(ucc, sma), fedlaw(sma) , stalaw(ucc), Vx, y, u, v E N0 . lp(x , y) -< ls(u, v) . [Brewka, 1994b] solves this problem by first generating 4 complete ex tensions. In a second step he rules out three of these extensions since they do not satisfy a certain prior ity criterion . In contrast, we obtain one extension, E 2 {-.perf, ucc-< sma}, and no other extension; this is the extension that Brewka ultimately obtains after rul ing out non-preferred extensions.
@inproceedings{ijcai1997p26,
title = {Compiling Reasoning with and about Preferences into Default Logic},
author = {Delgrande, James P. and Schaub, Torsten},
booktitle = {Proceedings of the Fifteenth International Joint Conference on
Artificial Intelligence, {IJCAI-97}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Martha E. Pollack},
pages = {168--174},
year = {1997},
note = {Automated Reasoning},
url = {https://ijcai.org/proceedings/1997/26},
}
TY - CPAPER TI - Compiling Reasoning with and about Preferences into Default Logic AU - Delgrande, James P. AU - Schaub, Torsten T2 - Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, IJCAI-97 PB - International Joint Conferences on Artificial Intelligence PY - 1997 SP - 168 EP - 174 UR - https://ijcai.org/proceedings/1997/26 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: