How to Prefer More Specific Defaults in Terminological Default Logic
Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence. Knowledge Representation. Pages 669-674.
© 1993 International Joint Conferences on Artificial Intelligence
Abstract
In a recent paper we have proposed terminological default logic as a formalism which combines both means for structured representation of classes and objects, and for default inheritance of properties. The major drawback which terminological default logic inherits from general default logic is that it does not take precedence of more specific defaults over more general ones into account. The pres e nt paper addresses the problem of modifying terminological default logic such that more specific defaults are preferred. It turns out that the existing approaches for expressing priorities between defaults do not seem to be appropriate for this purpose. Therefore we shall consider an alternative approach for dealing with prioritization in the framework of Reiter's default logic. The formalism is presented in the general setting of default logic where priorities are given by an arbitrary partial ordering on the defaults. We shall exhibit some interesting properties of the new formalism, compare it with existing approaches, and describe an algorithm for computing extensions.
- F . Baader and B. Hollunder . How to prefer more specific defaults in terminological default logic. Re- search Report RR-92-58, DFKI Saarbriicken, 1992.
- F. Baader and B. Hollunder. Embedding defaults into terminological knowledge representation for- malisms. In Proceedings of KR '92, Cambridge, Mass., 1992.
- P. Besnard. An Introduction to Default Logic. Sym- bolic Computation Series . Springer, 1989.
- R. J. Brachman, D. L. McGuinness, P . F. Patel- Schneider, L. A . Resnick, and A. Borgida. Liv- ing with CLASSIC: When and how to use a KL- ONE-like language . In J . Sowa, editor, Principles of Semantic Networks, pages 401-456.
- Morgan Kauf- mann, San Mateo, Calif., 1991.
- G. Brewka. Preferred subtheories: An extended log- ical framework for default reasoning. In Proceedings of IJCAI'89, Detroit, Mich., 1989. IJCAI
- G. Brewka. Nonmonotonic Reasoning: Logical Foundations of Commonsense. Cambridge Univer- sity Press, Cambridge, 1991.
- J . P. Delgrande and W . K. Jackson. Default logic revisited. In Proceedings of KR'91, Cambridge, Mass., 1991.
- M. L. Ginsberg, eJ. Readings in Nonmonotonic Rea- soning. Morgan Kaufmann, Los Altos, Cal., 1987.
- U. Junker and G. Brewka. Handling partially or- dered defaults in TMS. In Proceedings of the 1st European Conference on Symbolic and Quantita- tive Approaches for Uncertainty, Marseille, France, 1991.
- V. Lifschitz. Computing circumscription. In Pro- ceedings of IJCAI'85, Los Angeles, Calif., 1985 .
- E. Mays and B. Dionne. Making KRsystems useful. In [15], pages 11-12.
- R. McGregor. Statement of interest. In K. von Luck, B. Nebel, and C. Peltason, editors, State- ment of Interest for the 2nd International Work- shop on Terminological Logics . Document D-91-13 , DFKI Kaiserslautern, 1991.
- pBACK . System presentation. In [15), page 186 .
- L. Padgham and B. Nebel. Combining classification and nonmonotonic inheritance reasoning: A first step. In Z. W. Ras and J . Komorowski, editors, Methodologies for Intelligent Systems (ISMIS'93). North-Holland, Amsterdam , 1993. To appear.
- C. Peltason, K. v. Luck, and C. Kindermann (Org .). Terminological logic users workshop -Proceedings. KIT Report 95, TU Berlin, 1991.
- D. L. Poole. A logical framework for default rea- soning. Artificial Intelligence, pages 27-47, 1988.
- R. Reiter. A logic for default reasoning. Artificial Intelligence, 13(1-2):81-132, 1980.
- R. Reiter and G. Criscuolo. On interacting defaults. In Proceedings of IJCAI'Bl, Vancouver , BC, 1981.
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
Early knowledge representation formalisms such as se mantic networks and frames comprise both means for structured representation of classes and objects, and for default inheritance of properties. However, these for malisms did not have a well-defined formal semantics, and subsequent formalisms trying to overcome this prob lem usually · concentrated on one of these two means of representation. Nonmonotonic inheritance networks are concerned with defeasible inheritance, sometimes in combination with strict inheritance, but the nodes in these networks are unstructured objects or classes . 1
·This work has been supported by the German Ministry for Research and Technology (BMFT) under research con tract ITW 9201.
1 There are some attempts to generalize this approach to structured classes, but they work in a very restricted setting, and it is not clear how to obtain more general results in this
Terminological representation formalisms , on the other hand can be used to define the relevant concepts of a probl~m domain in a structured and well-formed way. This is done by building complex concept descriptions out of atomic concepts (unary predicates) and roles (bi nary predicates) with the help of operations provided by the concept language of the particular formalism. In ad dition, objects can be described with respect to their relation to concepts and their interrelation with each other . The concept descriptions are interpreted as uni versal statements, which means that they do not allow for exceptions. As a consequence, the terminological sys tem can use descriptions to automatically insert concepts at the proper place in the concept hierarchy ( classifica tion), and it can use the facts stated about objec~s to deduce to which concepts they must belong, but obJects cannot inherit properties by default .
The problem addressed in this paper is how to bring together both means of representation originally present in semantic networks and frames, without losing the advantages of terminological formalisms, such as being equipped with a formal and well-understood semantics and providing for automatic concept classification. An integration of defaults would often greatly enhance appli cability of terminological systems, or would at least make their use more convenient in most applications (see, e.g., [15] which shows that embedding defaults into termino logical systems is an important item on the wish list of users of such systems) . For this reason , several existing terminolo~ical systems, such as BACK [13], CLASSIC [4], K-Rep [llJ, or LOOM [12], have been or will be extended to provide the user with some kind of default reasoning facilities . As the designers of these systems themselves point out, however, these approaches usually have an ad hoc character, and thus do not satisfy the requirement of having a formal semantics .
As a first attempt to give a formally well-founded so lution to this problem, an integration of Reiter's default loe;ic into a terminological formalism was proposed in [2J . One reason for selecting default logic, out of the wide range of nonmonotonic formalisms , was that Re iter's default rule approach fits well into the philosophy of terminological systems . Most of these systems already provide their users with a form of "monotonic" forward rules, and it turned out that these rules can be viewed as specific default rules where the justifications are ab sent. A second pleasant feature of terminological default logic , as introduced in [2], is that it becomes decidable provided that applicability of default rules is restricted to objects explicitly present in the knowledge base. It should be noted that this constraint is also imposed on the monotonic rules in terminological systems.
direction (see, e.g., [14]) .
The major drawback which terminological default logic inherits from general default logic is that it does not take precedence of more specific defaults over more general ones into account. For example, assume that we have a default which says that penguins cannot fly, 2 and another one which says that birds can fly, and that clas sification shows that penguins are a subconcept of birds . Intuitively, for any penguin the more specific first default should be preferred, which means that there should be only one default extension in which the penguin cannot fly. However , in default logic the first default has no priority over the second one, which means that one also gets a second extension where the penguin can fly. This behaviour has already been criticized in the general con text of default logic, but it is all the more problematic in the terminological case where the emphasis lies on the hierarchical organization of concepts.
In the present paper we shall consider the problem of modifying terminological default logic such that more specific defaults are preferred. After a short recapitu lation of default logic and its specialization , termino logical default logic , in Section 2, we shall consider the existing approaches for expressing priorities between de faults, and shall point out why they do not seem to be appropriate for our purpose (see Section 3) . For this reason we present in Section 4 an alternative ap proach for dealing with prioritization in the framework of Reiter's default logic. The formalism is presented in the general setting of default logic where priorities are given by an arbitrary partial ordering on the de faults. For terminological default theories the priori ties between defaults will be induced by the position of their prerequisites in the concept hierarchy. We shall ex hibit some interesting properties of the new formalism, and shall compare it with existing approaches. It turns out that every extension according to our definition (S extension) is an extension according to Reiter 's definition (R-extension) ; however, R-extensions which are not com patible with the partial ordering on defaults are excluded by our formalism. Not all default theories with an R extension have an S-extension, but every normal default theory has an S-extension. If the defaults are further restricted to prerequisite-free normal defaults then our approach coincides with the one of Brewka and Junker [5; 9]. In Section 5 the problem of how to compute S extensions will be addressed.
2 Default Logic
This section briefly reviews Reiter's default logic and its specialization, terminological default logic .
2 The reader who is surprised that this is only taken as a default property should have a look at the cover of [8] .
Reiter's default logic Reiter [17] deals with the problem of how to formalize nonmonotonic reasoning by introducing nonstandard, nonmonotonic inference rules, which he calls default rules. A default rule is any expres sion of the form
where a, {3, 1 are first-order formulae . 3 Here a is called the prerequisite of the rule, f3 is its justification, and 1 its consequent. For a set of default rules 1), we denote the sets of formulae occurring as prerequisites, justifications, and consequents in 1J by Pre(V), Jus(V), and Con(V), respectively.
A default rule is closed iff a, f3, 1 do not contain free variables. It is semi-normal iff its justification im plies the consequent, and it is normal if its justification and consequent are identical. A default theory is a pair (W, 1J) where W is a set of closed first-order formulae (the world description) and 1J is a set of default rules. A default theory is closed iff all its default rules are closed.
Intuitively, a closed default rule can be applied, i.e., its consequent is added to the current set of beliefs , if its prerequisite is already believed and its justification is consistent with the set of beliefs . Formally, the conse quences of a closed default. theory are defined with ref erence to the notion of an extension (called R-extension in this paper), which is a set of deductively closed first order formulae defined by a fixed point construction (see [17], p.89) . In general, a closed default theory may have more than one R-extension, or even no extension. De pending on whether one wants to employ skeptical or credulous reasoning, a closed formula 6 is a consequence of a closed default theory iff it is in all R-extensions or if it is in at least one R-extension of the theory.
To generalize the notion of an R-extension to arbi trary default theories one just assumes that a default with free variables stands for all its ground instances . In Reiter's original semantics the world description and the consequents of all defaults have to be Skolemized before building ground instances (over the enlarged signature) . As shown in [2] Skolemization leads to both semantic and algorithmic problems, which is the reason why we shall dispense with it in the case of terminological default theories .
Terminological default logic For lack of space we shall not formally introduce a particular terminological language (see e.g. [2] for details) . Instead we shall just mention the features of terminological languages which will be important for the following. The terminologi cal part of such languages allows one to build complex concept descriptions out of atomic concepts (unary pred icates) and roles (binary predicates). For our purposes it suffices to know that a concept description C can be regarded as a first-order formula C( x) with one free vari able x. The subsumption hierarchy between concepts corresponds to implication of formulae: C is subsumed by D iff Vx: C(x)--+ D(x) is valid.
3 For the sake of simplicity we consider only defaults with one justification . However , our results can easily be ex tended to the general case of defaults with finitely many justifications.
The asserlional part of the language can be used to state that an object is an instance of a concept C, or that two individuals are connected by a role R. Logically, this means that one has constant symbols a, b as names for objects, and can build formulae C(a) and R(a, b) by respectively substituting a for the free variable in C( x) and applying the binary predicate R to the constants a, b. A finite set of such formulae is called an A Box. Important inference problems for ABoxes are whether a given ABox is consistent, and whether an object a is an instance of a concept C, i.e. , whether C(a) is a logical consequence of the given ABox. It should be noted that the formulae C( x) obtained as concept descriptions of a terminological language belong to a restricted subclass of all first-order formulae with one free variable. For this reason the subsumption, consistency and instantiation problems are usually decidable for these languages.
A terminological default theory is a pair (A, V) where A is an ABox and V is a finite set of default rules whose prerequisites, justifications, and consequents are concept descriptions. Obviously, since A Boxes can be seen as sets of closed formulae, and since concept descriptions can be seen as formulae with one free variable, 4 terminological default theories are subsumed by Reiter's notion of an open default theory. However, as motivated in Section 3 and 4 of [2), we do not Skolemize before building ground instances. This means that an open default of a termi nological default theory is interpreted as representing all closed defaults which can be obtained by instantiating the free variable by all object names occurring in the ABox. With this interpretation , it is possible to com pute all R-extensions of terminological default theories (see [2], Section 5 and 6).
3 Approaches to Prioritization
When conflicts occur in reasoning with defaults it is quite obvious that the more specific information should prevail over the more general one. In the context of terminologi cal default theories this means that for an instance of the concepts C and D a default with prerequisite C should be preferred if Cis subsumed by D. As mentioned in the introduction this requirement is not taken into account by Reiter's approach . If we assume that P, B, and Fare concept descriptions defining penguins, birds, and flying objects, where P is subsumed by B , then the termino logical default theory consisting of the world description {?(Danny)} and the defaults
has two R-extensions. One of them contains F(Danny) and the other one ·F(Danny), and the semantics gives no reason for preferring the second one , in which the more specific default was applied.
4 The formulae occurring in one rule are assumed to have identical free variables.
To overcome this kind of problem several approaches for realizing priorities among defaults have been pro posed in the literature. The priorities may be induced by specificity of prerequisites (as described above), but may also come from other sources (such as reliability of defaults) .
Reiter and Criscuolo show how some kind of prioritiza tion between defaults can be achieved without changing the formalism by encoding the priority information into the justifications of semi-normal defaults [18] . Although our simple example from above could be handled with this approach, it is not clear how to treat more complex situations . Reiter and Criscuolo do not describe a gen eral method for solving these problems; they just "focus on certain fairly simple patterns of default rules ." An other problem is that, even if one starts with normal defaults (as in our example), one ends up with semi normal defaults when realizing priorities this way. But this means that one has to face the undesirable prop erties of non-normal defaults, such as non-existence of extensions.
In order to avoid the introduction of semi-normal de faults Brewka [6] takes the ideas underlying prioritized circumscription [10] and defines an iterated version of default logic, which he calls prioritized default logi c. As pointed out by Brewka himself, this approach makes sense only if it is restricted to prerequisite-free normal defaults . In this restricted case , prioritized default logic yields a prioritized version of Poole's approach to default reasoning [16), and it seems to exhibit a quite reasonable behaviour. One reason why this is nevertheless not an appropriate formalism for treating specificity in termi nological default theories is that the defaults have to be put into levels of priorities which are totally ordered. However, subsumption between prerequisites only gives us a partial ordering on defaults.
In [5 ; 9] prioritized prerequisite-free normal default theories are generalized to ordered default theories which allow for an arbitrary partial ordering on defaults . We shall describe this approach in more detail because in combination with an approach for approximating defaults with prerequisites by prerequisite-free normal defaults- it yields a first solution to our problem of treating specificity in terminological default theories, even though we shall argue that it sti ll exhibits some undesirable properties. In addition , the default theories with specificity we shall propose in the next section turn out to be a generalization of ordered default theories to defaults with prerequisites .
An ordered default theory is a triple (W, V, <), where W is a set of closed first-order formulae, V is a set of closed prerequisite-free normal defaults , and < is a strict partial ordering on V such that { d' E V I d' < d} is finite for every dE V.
The principal idea is to consider total extensions of the partial ordering when computing extensions of the ordered default theory (which we shall call B-extensions in the following) . Any enumeration d1 , d2 , ... of V that is compatible with the partial ordering (i.e., i < k if di < dk) defines a B- extcnsion as follows. One starts with W, and in the i-th step of the iteration , the consequent /3; of the default d; = : /3;/ /3; is added if /3; is consistent with the set of formulae obtained after step i - 1. Otherwise, the current set of formulae remains unchanged . The limit of this process is the extension.
Even though ordered default theories allow for prior ities given by a partial ordering, this approach cannot directly be used to realize specificity in terminological default theories . The reason is that the restriction to prerequisite-free defaults is too severe. In fact, for ter minological default theories the priorities we wanted to consider were induced by subsumption relationships be tween the concept descriptions in the prerequisites. But this means that for prerequisite-free terminological de faults we no longer have a need for prioritization .
The situation is, however, not as bad as it seems . As shown in [3 ; 7), the closed normal default a : f3/ j3 can be approximated by the closed prerequisite-free normal default :a ----> /3/a----> j3. Thus one could start with a normal terminological default theory, determine the priorities between defaults from their prerequisites, and then transform the defaults into the corresponding ones without prerequisites. This way one ends up with an ordered default theory which approximates the termi nological default theory, and which handles priorities in duced by specificity of prerequisites in the terminological default theory.
However, we claim that this approach is still not satis factory because it gives us a lot more than we bargained for. As pointed out in [7), the approximation not only gets rid of prerequisites, but also equips the defaults with properties of classical implication , such as reasoning by cases and reasoning using contrapositives of the original defaults. For example, assume that , in addition to the concept descriptions for penguins , birds , and flying ob jects, we have a description W for objects having wings, and that the only subsumption relation is the one be tween penguins and birds. If we consider the termino logical default theory consisting of the world description {?(Danny)} and the defaults
then the preferred extension should be the one in which Danny has wings , but does not. fly. The approach we have described yields this extension ; but it also yields another one in which Danny does not have wings, be cause as soon as the (approximation of the) first default has fired, the contrapositive of the third one can be fired, which gives us -.W(Danny) .
This shows that in this approach the defaults no longer behave like simple forward rules . But the similarity of default rules with the monotonic forward rules of ter minological systems was one of our reasons for choosing default logic in the first place.
4 Default Theories with Specificity
To overcome the problems pointed out in the previous section we shall now propose a new approach for han dling priorities among defaults with prerequisites. The semantics will be very close to Reiter 's semantics, and the properties of our theory will also resemble those of Reiter's theory.
A default theory with specificity is a triple (W, 'D, <) consisting of a closed default theory (W, 'D) and a strict partial ordering < on 1) such that { d' E 1) I d' < d} is finite for every d E 1) .
In the terminological case, W is an ABox, and 1) is ob tained by instantiating the terminological default rules by all constants occurring in the ABox. For two instanti ated terminological default rules d1, d2 with prerequisites C1(al), C2(a2) we have d1 < d2 iff they are concerned with the same object (i .e., al = a2) and cl is more spe cific than C2 (i .e ., C1 is subsumed by C2 but not vice versa) . The restriction on the ordering is satisfied since 1) is finite by definition of terminological default theories .
Our definition of an extension for a default theory with specificity is modelled on Reiter's iterative characteriza tion of R-extensions (see [17], Theorem 2.1) . The main idea for treating priorities is that the consequent of a de fault can only be added during an iteration step if the de fault is not blocked by a preferred default, i.e., there does not exist a smaller default that is currently active. For a set E of closed formulae, and a closed default d = a : j3 h we say that d is active in E iff its prerequisite is a con sequence of E (i .e., a E Th(£) 5 ), its justification is con sistent with E (i.e., -.j3 ~ Th(E)), and its consequent is not a consequence of E (i.e ., 1 ~ Th(E)) .
Definition 4.1 Let (W, 1), <) be a default theory with specificity, and let £ be a set of closed formulae. We define Eo := W, and for all i ~ 0
E;+l := E; U {'y I 3d E 'D: d =a : /3/F, a E Th(E;) , -.j3 ~ £, and all d' < d are not active in E; }.
Then£ is an S-extension of iff£= U;~o Th(E;) .
The only difference to Reiter's characterization is the additional requirement that smaller defaults must not be active in the current state of the iteration. With this definition of an extension we get the intuitively correct result in our example with the three defaults concern ing penguins, birds, and objects with wings. In fact, for any penguin the second default (asserting that birds nor mally have wings) can only fire after the more specific default (asserting that penguins normally cannot fly) has been applied. But this means that the third default (as serting that winged objects normally can fly) will never become applicable for a penguin (before its prerequisite becomes derivable, the negation of its justification must have been added). This means that our definition of an S-extension chooses from the two existing R-extensions the one which respects priorities.
Our first theorem states that this will always be the case, i.e., that the set of all S-extensions is always a subset of the set of all R-extensions.
Theorem 4.2 Let £ be an S-extension of the default theory with specificity (W, V, <). Then £ is an R extension of (W, 'D).
Proof idea. Even though the definition of an S extension closely resembles Reiter's characterization of an R-extension, this theorem is not at all obvious. The idea for a proof is to take an S-extension £ which has been obtained from the sequence E0 , E1 , ... ,and to use it to construct a sequence F0 , F1, ... as in the characteri zation of R-extensions. It is easy to see that E- C F for all i ~ 0, but the converse is not true . I~ fact: the consequent 'Y of a default d may be added to F; but not to E; because d is blocked by a smaller de fault which is active. A straightforward way to prove that F; ~ £ = U;>o Th(E;) would thus be to show that the set of active defaults blocking d decreases along our F-iteration. Unfortunately, the set of defaults block ing d may also increase because prerequisites of smaller defaults which have not been derivable at step i may become derivable in a later step of the iteration . For this reason, the proof of the theorem uses a more com plex induction argument , first on i and then on the . d ' s1ze of the sets Di of defaults potentially blocking d, where DJ := {d' = a': f3'h' I d' < d and (a' fl. Th(.f!i ). V d' is active i~ Ej)} (see [1) for details). Our restnctwn on the partial ordering makes sure that the sets DJ are finite. 0
5 By Tl1(E) we denote the deductive closure of the set of formulae E.
Since not all default theories have R-extensions it fol lows that a default theory with specificity need not have an S-extension. But even if we have R-extensions there need not exist S-extensions of a default theory with specificity. This is demonstrated by the following ex ample. Assume that W is empty, and consider the three defaults :/3//3, : -.j3j-.j3 and j3: aj-.a. We assume that the first default is smaller than the second one, and that there are no other comparabilities with respect to <. !his default theory has the R-extension Th( { -.j3}) , but It does not have an S-extension. In fact, an S-extension would. prefer the first default, which yields {3; but then the third default (which is a modified version of the well known one-rule example of a default theory having no R-extension) would become relevant.
.As in the case without specificity, normal default the ones with specificity have much nicer properties than arbitrary default theories with specificity.
Theorem 4.3 Every closed normal default theory with specificity has an S-extension.
The proof is a relatively straightforward adaptation of Reiter 's proof for R-extensions (see [1) for details).
For normal default theories with specificity we also have "orthogonality of S-extensions" (see [17), Theo rem 3.3) , but we do not have "semi-monotonicity" (see [17), The_o~em 3.2). For defaults with priorities, semi monotomCity cannot be expected to hold since by adding a default of high priority one should of course be able to change the extensions considerably.
If we further restrict the attention to normal defaults without prerequisites then the notion of an S-extension coincides with that of a B-extension, which shows that our approach is a generalization of ordered default the ories (see [1) for a proof).
Theorem 4.4 Let V be a set of closed prerequisite-free normal defaults. Then £ is an S-extension of the default theory with specificity (W, V, <) iff [ is a B-extension of the ordered default theory (W, V, <).
5 Computing S-extensions
Since all S-extensions are R-extensions, one could first generate all R-extensions of a default theory, and then for each R-extension £ directly use the definition of S extensions to check whether £ is an S-extension. For terminological default theories this provides us with an effective procedure for computing all S-extensions. In fact, in [2) it is shown how to compute all R-extensions of .a terminological default theory. Since one has only fimtely many closed defaults, and since the instantiation problem for the terminological languages we use is de cidable, the iteration in the definition of an S-extension is effective as well.
However , there may exist a lot more R-extensions than S-extensions, and computing R-extensions is rather ex pensive . For this reason, it would be preferable to have an algorithm for directly computing S-extensions. The idea behind the algorithm presented below is to make an iteration similar to the one in the definition of an S extension, but without already having the final set [for controlling which consequents of defaults are added. Af ter the iteration becomes stable (which will always be the case for finite sets of closed defaults) one has to check an additional condition to make sure that the result really is an S-extension.
The main problem is to determine which sets of con sequents are candidates for being added in each step of the iteration. Of course there can be more than one correct choice because there may exist more than one S-extension. If we look at the definition of Ei+l in Defi nition 4.1 we see that the defaults whose consequents are added are defaults active in E; that are minimal w.r.t. the priority order <. Which subset of their consequents is taken depends on the set£ used for the iteration . Since our algorithm does not know the final £ it has to consider arbitrary subsets, but we shall see that there are some constraints that reduce the number of possible choices . It should be noted that neither a greedy procedure (which takes maximal subsets that are consistent with what has already been computed) nor an overly modest procedure (which adds only one consequent in each step) would be complete (see [1) for examples). In the following (non deterministic) algorithm, E; will always be a subset of WU Con(V), and J; will be a subset of -.Jus(V) (where, for a set :F of formulae, -.:F := { -.{3 I j3 E :F} ).
Algorithm 5.1 Let (W, V, <)be a closed default theory with specificity. If W is inconsistent then Th(W) is the only 5-extension. Otherwise we define Eo := W and lo := 0. Now assume that E; (i ~ 0} is already defined. Consider
vi+I :={dE vI dis active in E; and no d' < d is active in E;},
and choose a non empty subset Di+l ofVi+1 that satisfies -.{3 fl. Th(E; u Con(Di+I) u J; u -.Jus(V;+1 \ i\+1))
for all j3 E Jus(D;+I) ·
If there is no such set, then Ei+l := E;, Ji+l := J;. Other;!!ise each choice yields new sets E;+ 1 := E; U Con(Vi+l) and ];+1 := J; U -,J us(Vi+1 \ Di+1). The set£:= ui~O Th(E;) is an 5-extension iff l.for all d =a: !3h E u~l V; we have ...,!3rt£, and 2. for all ...,/3 E U;~ 1 J; we have -,{3 E £.
A proof of soundness and completeness of this algo rithm can be found in [1] . The idea behind the sets J; is as follows. If the consequent of a minimal active default is not included in E;+1 , then the reason must be that its justification is not consistent with the final exten sion. Thus, if we exclude such a default from Di+l, we know that the negation of its justification must belong to the extension. The condition on fji+l corresponds to the fact that defaults whose consequents are added to an S-extension must have justifications that are consistent with the extension. The condition on fji+l can only en sure local correctness of our choices. For this reason we have to check the two conditions on £ to ensure global correctness.
For terminological default theories, all the steps of the algorithm are effective, provided that the consistency and instantiation problem for the underlying terminolog ical language is decidable (an assumption which is usu ally satisfied). In addition, since one has only finitely many closed defaults, the iteration will become stable after finitely many steps.
6 Conclusion
We have addressed the question of how to prefer more specific defaults over more general ones. This problem is of general interest for default reasoning, but is even more important in the terminological case where the empha sis lies on the hierarchical organization of concepts. Of the existing approaches for handling priorities among de faults, Brewka's ordered default theories turned out to come nearest to what is needed for solving the speci ficity problem in terminological default theories. But its restriction to prerequisite-free normal defaults seems to be too severe to make it an adequate solution in the terminological case.
Therefore we have proposed a new approach, called default theories with specificity, for handling priorities among defaults with prcr·equisites. The properties we could prove for this formalism demonstrate that it is a quite reasonable extension of Reiter's default logic and of Brewka's ordered default theories. In addition it correctly handles examples for which the other ap proaches give unintuitive results. We have also described a method for generating the extensions of a default the ory with specificity. This method is effective provided that the base logic is decidable, and one has only finitely many closed defaults. These restrictions are satisfied in the terminological case, which means that terminological default logic with specificity is decidable.
An interesting point for further research is to consider priorities on terminological defaults which not only take subsumption between prerequisites of defaults into ac count, but also the role relationships in ABoxes.
Acknowledgements We should like to thank Peter Patel-Schneider for interesting discussions on specificity of defaults , and Bernhard Nebel for helpful comments on a draft of this paper.
@inproceedings{ijcai1993p94,
title = {How to Prefer More Specific Defaults in Terminological Default Logic},
author = {Baader, Franz and Hollunder, Bernhard},
booktitle = {Proceedings of the Thirteenth International Joint Conference on
Artificial Intelligence, {IJCAI-93}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Ruzena Bajcsy},
pages = {669--674},
year = {1993},
note = {Knowledge Representation},
url = {https://ijcai.org/proceedings/1993/94},
}
TY - CPAPER TI - How to Prefer More Specific Defaults in Terminological Default Logic AU - Baader, Franz AU - Hollunder, Bernhard T2 - Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, IJCAI-93 PB - International Joint Conferences on Artificial Intelligence PY - 1993 SP - 669 EP - 674 UR - https://ijcai.org/proceedings/1993/94 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: