Inconsistency Management and Prioritized Syntax-Based Entailment

1 Introduction

It is noticeable, although very natural, that the notion of ordering (between logical formulas, between models, between subsets of formulas) has emerged from studies in nonmonotonic reasoning and belief revision as playing a crucial role. In both cases, the existence of such orderings is a direct consequence of a set of axioms which plausible inference, or revision processes, must obey. Makinson and Gardenfors [23] have pointed out that some nonmonotonic inference systems can be expressed in terms of the appro­ priate revision of a related set of propositional sentences, both inference and revision being guided by the ordering. Namely, given a set of sentences 8 and a revision procedure, given a formula a to be added to 8, inferring ~ from a in the context defined by 8 can be achieved by checking whether ~ is a consequence of the result of revising 8 by a; the revision process takes care of the case when 8u {a} is inconsistent. The ordering underlying these operations helps altogether coping with inconsistency, solving a revision problem, and guiding a nonmonotonic inference. In this paper we shall assume that a set of formulas is equipped with a complete preordering structure (or priority ranking) which, contrarily to G:trdenfors' [13] view, is not related to the semantical entailment ordering between sentences. This kind of ordering has been considered by Brewka [4], Geffner [15], Nebel [24], Cayrol [5) in the recent past. Especially Nebel has used it to define syntax-based revision procedures, such that two semantically equivalent knowledge bases may, upon the arrival of some input inconsistent with them, result in non-semantically equivalent revisions. A first idea to revise an inconsistent knowledge base 8 is to select one of its maximal consistent subbases; another natural idea is to keep as many sentences as possible, i.e. consider a consistent subbase of 8 of maximum cardinality. The latter option helps reducing the number of revision candidates. The presence of an ordering on 8 leads to refine both approa­ ches. Besides, one does not need to select a single preferred subbase when defining a non-trivial notion of inference from an inconsistent knowledge base. The task of this paper is precisely to study inferences of the form "8 entails ~ if ~ can be classically inferred in all the preferred consistent subbases of8". Here we shall focus on two meanings of"preferred": one, already considered by Brewka and Geffner, that com­ bines priorities and maximal consistent subbases; another, which has not been studied in the literature, combines priorities and consistent subbases of maximum cardinality. Borrowing from G1lrdenfors the image that nonmonotonic reasoning and belief revision are two sides of the same coin, we pursue Nebel's work on syntax-based revision, by studying the other side of that particular coin; namely we study the properties of inference based on the two kinds of preferred subsets of formulas, and give algorithms for computing these inferences. Inconsistency-tolerant inferen­ ces are interesting since they can overcome some limitations of the kind of nonmonotonic inference that is the exact counterpart of G:trdenfors' revision theory (see [14]). This kind of inference is also at work in possibilistic logic [10], [8] and in System Z [25]. This approach suffers from what we call the "drowning effect": all formulas which are not sufficiently entrenched are inhibited; this is an attenuated form of the fact that in classical logic anything follows from an inconsistent set of sentences; a particular case of this effect is the property inheritance blocking [25], [16].

2 Nonmonotonic Inference Relations Generated by a Flat Belief Base

Throughout this paper, ;t is a propositional language assumed finite for simplicity, since we deal with cardinali­ ties. Formulas will be denoted by greek letters a,~ ... . ; T (resp. 1.) denotes any tautology (resp. contradiction); n denotes the set of classical interpretations (denoted by ro,ro', ... ) associated with ;t; j.t(a) denotes the set of models of a. A belief base 8 is a non-empty set of formulas {cp1, ... ,%} of ;t, Subsets of8 will be denoted by A, B, ... ; IAI is the cardinality of A. Let Cn(A)= { cpe ;t ,AF=cp}.

As discussed e.g. in [24], there are two ways of considering a set 8 of sentences that describes an epistemic state: the first one is townsider it logically (8 is then called "belief set"), i.e. it can be represented equivalently by the set of its models and in this case it behaves as its closure under Cn. In this spirit, Glirdenfors and Makinson [14] generate nonmonotonic inference relations from sets of sentences which are consistent and closed under Cn; namely, ~ is inferred from a with respect to 8 iff~ is derivable from a in all the "selected" maximal subsets of 8 consistent with a, where the selection function is to be defined. The second way is to consider the belief base "syntactically", i.e. each formula of 8 is a distinct piece of information; 8 is then more than the set of its models; for instance, {p,q} is different from {pAq} since the former can be viewed as obtained from two experts, one asserting p and the other one q, while the latter has to be taken as a whole; in particular, in a revision context, p could be rejected or ignored independently from q in the former case, which is not true in the latter. Here, we assume neither that a belief base 8 is closed under Cn, nor that 8 is consistent. The inconsistency generally comes from the defeasible status of the pieces of information in 8; in particular, it may come from the combination of several independent (consistent) knowledge bases, as in [1]. The syntactic approach to nonmonotonicity or belief revision was used in different ways [11] [12] [24]. We first briefly deal with the non-prioritized case, for which inference can be based on maximal consistent subbases.

Definition 1: Ac8 is inclusion-maximal a -consistent if and only if Au {a} is consistent and there is no strict superset B of A with B~ such that Bu{a) is consistent.

A natural way of selecting among these subbases A is to choose those of maximal cardinality, which leads to:

Definition 2: Ac8 is cardinality-maximal a -consistent if and only if Au {a) is consistent and for any Bt;;8 such that Bu{a} is consistent, then IBI$IAI.

The obvious way of generating a nonmonotonic inference relation from 8 is then:

Definition 3: a t-v-8 ~ (resp. a t-v- ~ ~) if and only if for every inclusion-maximal (resp. cardinality-maximal) a­ consistent subset A of8, we have Au{a}t-~.

If a= T, we recover in the case of inclusion maximality Brewka's definition of ~-strong provability from 8. Since any cardinality-maximal a-consistent subset of 8 is inclusion-maximal a-consistent, we have:

Thus, t-v-~ is more adventurous than t-v-8. Beyond complexity considerations, the choice of cardinality for discriminating among subbases is justified by adopting the point of view (well-known in model-based diagnosis) that 8 is a set of independently generated pieces of information which can "fail" to be true with a small probability £; thus, the greater the number of rejected formulas, the smaller the probability that all of them fail (actually, En if n formulas are rejected). This justifies cardinality-based preferences. However we do not claim that inferences based on cardinality are always the best way of defining an inference relation since it may be too adventurous in some cases. The choice of a selection mode may be application-dependent (e.g. the use of cardinality in diagnosis).

Both t-v-8 and t-v- ~ fall in the class of consequence relations

based on preferential models, in the sense of Shoham [29]. Definition 4: ro~ ro' iff {cpie8,roF=cpi}~{cpie8,ro'F=cpi}; ro $~ ro' iffl{cpie8, O>l=<pi}l $l{cpie8, ro'F=cpi}l. It is clear that $8 is a partial pre-ordering, while $~ is a complete pre-ordering. In the following, we take the convention that given a preordering on .n, maximal elements are preferred ones.

Proposition 2: ro is maximal w.r.t. ~8 (resp. ~~)iff

{ cpe 8,roF=cp} is an inclusion-maximal (resp. cardinality­ maximal) consistent subset of8.

This leads to the following result (see [5] for (i)) Proposition 3:

See Sec. 4 for properties of t-v-8 and t-v- ~ in a general setting. A shortcoming of reasoning with maximal consistent sub­ sets is their usually large number (see [24] for complexity consideration). To reduce their number, one may select them w.r.t. cardinality, or attach priorities to the formulas (see Sec. 3 &4) as proposed in [4] [15] [24] [1].

3 Prioritized belief bases

3.1 Introduction

Most of the time, when revising an inconsistent knowledge base, it is not reasonable to give all formulas the same importance (in a belief revision terminology, the formulas in a belief base are not all equal regarding to rejection); for instance, if some formulas are more certain than others we wish to reject the least certain first; formulas may also be ordered according to their arrival time in the belief base and then the oldest ones might be preferably rejected in order to restore consistency. More generally, we assume that formulas of 8 are ranked by a complete pre-ordering ~. or equivalently, that 8 consists in a collection (81·· .. ,8 0 ) of belief bases, where 81 contains the formulas of highest priority, and 8 0 those of lowest priority. We shall denote< the associated strict relation and "' the associated equivalence. 8 will be called a prioritized belief base, and~ a priority relation. The idea of selecting a preferred subbase induced by the priorities is not a new one since it goes back at least to [27]. This idea has been also put forward in the framework of nonmonotonic reasoning with prioritized circumscription [22]. hierarchic autoepistemic logic [20] and more specifically Brewka's preferred subtheories [4] which extend Poole [26]'s logical approach (corresponding to the case of only two priority levels). Preferred subtheories have also been further studied (and in different ways) in [15]. [5]. in possibilistic logic by [8]. in knowledge base combination by [1] and extensively in the context of belief revision, in [24]. Boutilier [3] gives a characterization of Brewka's preferred subtheories in terms of conditional logics. Roos

[28] studies a particular case of Brewka's work. The selection of preferred subbases of 8 presupposes that the preordering ~be extended to compare sets of formulas. We argue that there might be not a single way to do it and we give several possible choices. This problem has been considered in specific cases in [4], [16], [8] and from a more general point of view in [6].

3. 2 From priorities on formulas to preferences between subbases

The general idea is to account for priorities in order to further select some maximal consistent subbases. In this spirit we now give some possible definitions for extending the priority relation ~ on 8 into a preference relation « on

28. Let A=A1u ... uAn, B=B1u ... uBn be two consistent subsets of8 (where Ai=AnSi and Bi= BnSi). Definitions 5:

- "best out" ordering: let A be a consistent subset of 8 and a(A) the highest priority of a formula of 8 which is not in A, i.e. a(A)=Min { i,3q>E 8i\Ai} with the convention Min0= . 1 . . bo n+ 1; see [8]. The best-out ordenng re auon wntes: A « 8 B iff a(A)~a(B). This ordering depends only on the most prioritary layer where there is at least one formula from 8 missing in the considered subbase. «~ is a complete pre­ ordering. Note that this ordering is very rough since it does not take into account formulas of lower priority (of level~ a(A)); consequently, the induced preference is not very selective, since some of the preferred subsets may not be maximal for set-inclusion. Indeed, let k be the maximal index such that 81 u .. . 8k is consistent. Then A=81 u ... 8k . b 0 . I I II . ts a « 8 -maxtma e ement as we as any conststent subbase of 8 containing A.

- inclusion-based ordering: this is the strict ordering defined by A « ~cB iff 3 i such that AicBi and for any j<i, Aj=Bj (c denotes strict inclusion). An equivalent definition of this ordering has been proposed by Geffner [15]:

To see it, it is enough to consider ~E Bi\Ai in the above definition. This equivalence does not hold anymore if the inc priorities define only a partial ordering [6]. The « 8 - maximal consistent elements are of the form A=A 1 u ... u An such that i) A 1 is a maximal consistent subbase of 81; ii) A 1 u ... u A i is a maximal consistent subbase of 81u ... u8i for i=1,n.

Clearly, when only one layer is presen~ in 8, we recover the tnc . maximal consistent subbases. The « 8 -maximal consistent elements are called preferred subtheories by Brewka and strongly maximal consistent subbases in [8] with another characterization: if I.nc (A)=max{k, A1u ... uAk-1 is consistent}, A is a « ~c -maximal consistent element iff inc VaE8i\Ai, Inc(Au{a})=i, for i=1,n. Note that « 8 maximal consistent elements are also maximal for bo(th & 1 ) t1 inc. . . 1 « 8 e converse is .a se . Las y, « 8 ts a stnct partta ordering, which means that there may be several incompara­ ble preferred subtheories. The dual ordering, exchanging V and 3 in Geffner's definition, has been studied in the scope of abduction in [6].

- lexicographic ordering: this is the complete preordering whose strict part is A «lex B iff 3i such that IAi kiBil and for any j<i, IAji=IBjl and\e equivalence part is A .)ex B iff for any i,IAii=IBil. 8

The complete preordering «lex generalizes th~ cardinality8

based selection of subbases of Section 2 to the prioritized case and refines the inclusion-based ordering. Any lexicographically maximal consistent subbase of 8 is strongly maximal consistent but the converse is false (as seen in Sec. 2; see an example in Sec. 4). This ordering has been proposed in [8] with a different formulation: namely, consider the increasingly ordered multiset List(8\A) of layer

levels of formulas of 8 not present in A, then A « lex B . 8 iff List(8\A) ~L List(8\B) where ~L is the lexicographic ordering. Similarly to Brewka's constructive definition for preferred subtheories, we can give an equivalent characterization for « ~x -maximal consistent bases: they are of the form A=A 1 u ... uAn such that i) A 1 is a cardinality-maximal consistent subbase of S1; ii) A1u ... uAi is a cardinalitymaximal consistent subbase of 81 u ... u8i for i= 1,n.

Dc:finition 6: A subbase A of 8 is said to be« ~ 0 (resp. «;c. « lex)-maximal. a-consistent iff Au {a} is consis8 . . 1 bo ( tnc lex) tent and A ts maxtma w.r.t. « 8 resp. « 8 , « among the a-consistent subbases of 8. 8

3.3 Semantics

Now, these (pre-)orderings on 28 induce (pre-)orderings on .Q, which provide us with clearer semantics. Definition 7: let ro, ro' E .Q, [ro] be the set of formulas

satisfied by ro.

4 Nonmonotonic Inference Relations Generated by a Prioritized Belief Base

We now generalize the inference relations defined in Sec. 2 to the prioritized case.

4. 1 Inference relations generated by best-out preorderings: the drowning effect

Definition 8: let 8=(81 , ... ,8n) be a belief base and a be a formula. The addition of a to 8, denoted by Add(a,8), is the belief base obtained by adding to 8 a new level, at the highest priority, containing only a. More formally, Add(a,8)=(8o={ a} .81 , ... ,8n)·

D f . . · 9 bo r:t 'ff & bo . al e m1hon : a ~ 8 .., 1 .or any ~ 8 -max1m aconsistent subbase A of8, Au{a}1-~.

Similarly to what we noticed in 3.2, the set of maximal a­ consistent elements for ~ :o has a least element, namely 81 u ... 8k i~~-consistent and 81 u .. 8k+ 1 is a-inconsistent. Hence a~ 8 ~ <::::> {a}u81 ... u 8k1-~, and no sentence of lower priority (i.e. level>k) is involved in the inference. This is the drowning effect. The semantic counterpart is

Proposition 5: a ~ ~ 0 ~ <::::> V roe J.{, (a), such that a([ro]n8) is maximal, roe J.{,(~).

In the terminology of possibility theory, a([ro]n8) is a kind bo of degree of impossibility of interpretation ro, and a ~ 8 ~ corresponds to the non-trivial deduction of possibilistic logic [10], also called expectation-based non-monotonic inference in [14]. Namely let us define for any formula cp, 2(cp)=min{k,8tu . .. 8ki-cl>}. Then 2 is closely related to a necessity measure, i.e . .e(cpAijf)=max( 2(cjl),2('1f)) in a scale of integers running opposite to the unit interval.

It is easy to check that the ordering defined by 2(cp):S:2('1f) is an expectation ordering [14] and a qualitative necessity measure [9], and that it is induced from 8 by the most compact ranking of interpretations (following Pearl [25]) and by the principle of minimum specificity of possibilistic logic. The non-monotonic inference is usually given by

a definition given under various guises by Glirdenfors and Makinson, Pearl, and Dubois and Prade. The relationship between the drowning effect laid bare by definition 9 and the blocking of property inheritance in Pearl's System Z can be viewed in the following example [2].

Example 1: Let p, b, f, w respectively mean penguin, bird, fly, winged and consider the set of defaults {p~--,f. b~f.p~b,b~w} . Using the default ordering procedure of System Z, the two defaults p~--,f and p~b are granted higher priority because they correspond to a more specific reference class. In [2] it has been shown that it corresponds to the following layered classical belief base 8= 81 u82 where 8t={--,pv--,f,--,pvb} and 82={--.,bvf,--.,bvw} and the inference made possible by System Z is exactly ~ ~ 0

(expressed in the terminology of possibilistic logic in the above mentioned paper). It is easy to check that b ~ b 8 o f, bo bo b~8 w,p~8 -f

but because of the drowning effect, p ~ :o w does not

hold due to the presence of a conflict in 81 u82 (Inc(8)=2). Hence penguins cannot inherit from birds the property of having wings. The inference relationships studied in the following will cope with this problem.

4. 2 Inference relations generated by inclusionbased and lexicographic preorderings

Since the preference relations defined in Section 3 generalize the criteria of Section 2, based on inclusion and cardinality, the following definitions naturally extend definition 3.

D f . · · 10 L-lnC R 'ff f InC . al e IDihon : a ·- 8 .., 1 or any « 8 -maxam a-consistent subbase A of 8, Au{a}1-~. This definition is also in [24] [5]. a ~ l;x ~ iff for any « l;x -maximal a­ consistent subbase A of 8, Au {a} 1-~.

Example 2: let8=(St=fa,--,a}, S2={--,avb,avc}, S3=f-,b}, S4={--,c}). Then the two subbases A={a,--,avb,avc,--,c} and

B= { --,a,--,avb,avc,--,b} are both « ~c -maximal consistent, . lex . . lex but only B 1s « 8 -maxamal a-consistent. Thus, ~ 8 --.,a inc holds but not ~ 8 -,a

Example 3: let us consider again the belief base of Section 4.1. Now, it is easy to check that p ~ ~c w and lex inc lex p ~ 8 w; thus, ~ 8 and ~ 8 escape the drowning p~oblem . I . . 3 me d The next result, genera azmg Prop. , states that ~ 8 an ~:x inferences can be defined equivalently. by means of preferential models a 1a Shoham (see [5] for ~me):

8 Proposition 6: let a~..l; ro is maximal in J.{, (a) w.r.t. inc lex inc ~ 8 (resp.~ 8 ) iff [ro]n8 is maximal w.r.t. « 8 (resp. lex

« 8 ) among the consi~tent subsets of Add(a,8). me lex Prop,osition 7: a ~ 8 ~ (resp. a ~ 8 ~) iff for any me lex . . ro ~ 8 -maximal (resp. ~ 8 -maxamal) m J.{, (a), we have roe Jvt.,(~).

Sketch of proof: (::::)) follows from Proposition 4 and the me lex definitions of a ~ 8 ~. a ~ 8 ~-

( ¢=) let A be a « ~c- maximal a-consistent subbase of 8. Let robe a model of Au {a}; then [ro] n 8 ;:;.:1 A. As the implies. that [ro) n 8 is «~c- maximal and due to Prop. 6,

I . inc f' . 1 . A inc . al re at1on « 8 re mes se.t me us1on, « 8 -maxam . IOC · al . H( ) s· il f & leX c.o as ~ 8 - maxam m v·v a . tm ar proo 10r « 8 .

We also give other equivalent formulations:

. . inc . inc Propos1taon 8: If CX*.l, a r.- 8 ~ 1ff r.- Add(cx,S)~· The same holds for lex -ordering instead of inc-ordering. Sketch of proof for « ~nc: _let A~S; A is « ~c -maximal ex­ consistent iff Au {a} is « ~~d( cx,S) -maximal consistent sub­ base of Add(cx,S). Indeed in Add(cx,S) the frrst level is a sin­ gleton {a}, so set-inclusion verifications are equivalent on the first level Ao· Similar proof for « ~x.

Proposition 9:

bo inc lex a '"" 8 ~ ::::) a '"" 8 ~ ::::) a r.- 8 ~ (as shown with Examples 2 and 3, the converses are false).

4. 3 Properties .

Proposition 10: r.- 1 ;c -inferences satisfy Supraclassicality, Left logical equivalence, right weakening, And, Weak conditionalization, Consistency preservation, Cumulativity, Or (System Pin [21]).

Proposition 11: r.- i:c-inferences do not satisfy Weak rational monotony [14] (nor a fortiori, Rational monotony).

Proof: a counterexample for Weak rational monotony is 8=

Proposition 12: the class of r.- ~nc inference relations

stricti y includes the class of GID-denfors and Makinson [ 14] 's comparative relations and is strictly included in the class of Kraus et al. [21]'s preferential relations.

Sketch of proof: for the first inclusion, we need to show that for any expectation ordering E there is an S such that "'E="' ;\ n being the number of levels induced by E, this can be done by considering the belief set S 9btained by pu-· &- · I I Th me r.t · · ttlng every .ormula at 1ts E- eve . en a r.- 8 ,... IS eqmvalent to S* a I- ~ where the revision S* a is a partial meet in the sense of Gru-denfors. The strictness of the inclusion is a corollary of Proposition 11. The second inclusion comes from the fact that preferential models are strictly more general than ours since the partial ordering is defmed on so­ called states; each state is labelled by a single interpretation, where an interpretation may label distinct states.

The properties of lex-infeiences stem from this result:

Proposition 13: any r.- :x-inference is a rational inference relation, i.e. satisfies all properties in proposition 10 plus Rational monotony.

1 Sketch of proof: from proposition 7, the fact that ,;;;;xis complete, and Gardenfors and Makinson's characterization of nonmonotonic inference by ranked models.

The last result states the other direction, i.e. that the class of lex-inferences contains the class of comparative inference relations.

Proposition 14: for any comparative inference relation "' there is a belief baseS such that r.- is equal to r.- ~x.

Corollary 15: the class of lex-inferences is equal to the class of comparative inference relations.

As a conclusion, what we gain with inclusion-based inferences is that we avoid the drowning effect, but at the same time we lose Rational monotony; now, with lex­ inferences, we still avoid the drowning effect and we furthermore recover Rational monotony.

5 Computing Nonmonotonic Inference Relations from a Belief Base

In this section we briefly describe a procedure for computing inclusion-based and lex-inferences. The procedure pre­ supposes the existence of an A TMS computing incremen­ tally the set of minimal candidates [7], which are defined as minimal sets of assumptions of a belief base whose deletion restores the consistency (i.e., a minimal candidate is the complement of a maximal consistent subbase). Note that, due to Proposition 8, it is 1 sufficient to have a procedure deciding if r.-::~ (resp. r.-;xp).

me

Decision procedur~ for I-- 8 ~ 8$ E- {0} {set of «me -preferred subbases of81u ... Sk} 8 k E- 0; {working level}; StopE- False Repeat 1 k E- k+1 ; New-8$ E- 0; Answer E-Yes 2 For each Bin 8$ do · 3 l:k E- set of justifications obtained from 8k I 4 Compute the set Ck of minimal candidates of Bul:k using an A TMS~ 5 For each C in Ck do 6 If Bu(Sk\C)I=-,~ then StopE- True; Answer E- No3 else If B u (Sk \C) ~ ~ then If k = n then StopE- True; Answer E- No 4 else New-8 f.eE---New-8 $u{Bu(Sk 'C)} ; 5 If New-8 $=0 then Stop E- True 8$E-New-8$

until Stop

Deciding whether ,._,lex~ holds is very similar, except at (4) s where only candidates of minimal cardinality are computed, and at (6) where the test is not done any more, since it is not guaranteed that Bu{8k\C} will lead to a lex-preferred subbase of8.

1 This means th~t an assumption Aj is associated to each formula <llj of Sk, m the followmg way: let { Ci 1, ... ,C i pl a set ?f ~~aus.es equivalent to <p j; then we replace <p j 'by the JUstiflcatiOns Ar-+Ci, 1 ·... ,Ar+Ci,p·

2 This means that we obtain the maximal consistent sub-bases of BuSk such that all rejected formulas are formulas of 8k.

3 If there is a « inc -preferred consistent sub-base of 81 u ... 8k 8 . deriving -,~ then there will be a «me -preferred consistent subS base of 8 deriving -,~ and it is not worth going on.

4 If we are at the last level, fmding a preferred sub-base not deriving ~ is sufficient to conclude "no".

5 Note that in the case where Bu(Sk'C)I=~, we do nothing, even if k < n: indeed, in this case, it is guaranteed that this sub-base will lead only to preferred sub-bases of 8 deriving ~. so it is not necessary to go on computing them.

The procedures are based on the constructive characterization of preferred maximal consistent subbases and the following results: i) for any k and for each « ~c­ preferred subbase B of 81 u ... 8 k there is a « inc -prefened 8 subbase A of8 such that An(81u ... 8k)=B (this is not true for lex-preferred subbases); ii) for any «inc (resp. « lex)- 8 inc 8 preferred subbase A of8 and for any k there is a « 8 (resp. lex « 8 )-preferred subbase B of 81 u ... u8k such that An(81 u ... u 8k)=B.

6 Applications and Conclusion

In this paper we started by noticing the limitations of several approaches to non-monotonic reasoning such as expectation-based inferences, possibilistic logic and System Z, which cope with inconsistency at the expense of taking away too many pieces of knowledge (the drowning effect). We then proposed two ways of coping with this problem: the first one, inferring a conclusion iff it is deducible from all inclusion-based preferred subbases, avoids it but fails to satisfy Weak rational monotony. The second one, less cautious, inferring a conclusion iff it is deducible from all lex-preferred subbases, still avoids the drowning effect and enables us to recover Rational Monotony.

There are many situations where all this can be applied, of which we mention some examples. First in default rea­ soning, Geffner and Pearl [16] have already used inclusion­ based prioritized inference to mend System Z. Here we have shown that the lexicographically-preferred subbases led to another solution recovering property inheritance. It would be interesting to compare this solution to the approach based on maximum entropy [17]. A second potential application is model-based diagnosis (in this spirit, see [19]) where 8 describes the functioning of the system to diagnose (the levels reflecting the certainty of the rules, and the reliability of the components); a corresponds to the observed situation; then each of the maximal consistent subbases correspond to a consistency-based diagnosis (where the absent formulas correspond to faulty components). In the non-gradual case, subbases of maximum cardinality corres­ pond to a minimum number of faulty components. Lex­ inferences are a generalisation of this principle, and are thus very natural in this context. Other potential applications are consistency maintenance in temporal data bases (where recent informations are preferred to older ones), prioritized constraint satisfaction problems (where overconstrained problems are solved by taking priorities into account), or to minimisation of surprizes in a logic of time and action.

Acknowledgements: This work has been partially supported by the European ESPRIT Basic Research Action n° 6156 entitled "Defeasible Reasoning and Uncertainty Management Systems (DRUMS-2)". Thanks also to Thomas Schiex for checking the algorithm.