Default Inheritance Reasoning in Hybrid KL-ONE-Style Logics

1 Introduction

Hybrid KL-ONE-style logics (H-logics, for short - see e.g. [Nebel, 1990]) are knowledge representation formalisms of considerable applicative interest , as they are specif­ ically oriented to the vast class of application domains that are describable by means of taxonomic organiza­ tions of complex objects. These formalisms , that may be seen as term-oriented syntactic variants of subsets of first order logic, are usually structured into two modules: the terminological module, allowing the representation of "concepts" and their implicit structuring according to a partial order, and the assertional module, allowing to state that given individuals are instances of the concepts described by means of the terminological module.

In the last ten years H-logics have been intensively in­ vestigated, with the attention of researchers especially focusing on the analysis of their logical and computa­ tional properties. Little attention, however, has been paid to the problem of endowing these logics with de­ fault reasoning capabilities. This is despite the fact that default reasoning is an important item on the list of desiderata of H-logics users (see e.g. [Peltason et a/. , 1991]) , and despite the fact that in most domains that have a taxonomic nature (e.g. the natural species) , de­ fault information is abundant . Some researchers have recently addressed this problem (see e.g. [Baader and Hollunder, 1992; Brewka, 1987; Nado and Fikes, 1987]), but we think that their work has been successful only to a limited extent .

·This work has been partially funded by the Progetto Fi­ nalizzato "Sistemi lnformatici e Cal colo Parallelo" of the Ital­ ian National Council of Research

In this paper we will address the problem of extending H-logics with the ability to perform default inheritance reasoning, a kind of default reasoning that is specifically oriented to reasoning on taxonomies and that had been used mostly within formalisms of a much smaller ex­ pressive power than H-logics (see e.g. [Touretzky, 1986]) . Most systems dealing with default inheritance reasoning solve "conflicts" according to some sort of specialization principle, i.e. by relying on the partial order according to which the knowledge base is structured: as a first approximation we can say that , in case of conflicts, a default a -+ b is "preferred" to another default c -+ ·b if the precondition of the former precedes the precondition of the latter in the ordering; this accounts for the fact that the conclusion derivable from the former is more reliable than the one derivable from the latter.

This paper is organized as follows . In Section 2 we summarize the main notions of H-logics. In Section 3 we describe the integration of default inheritance capabili­ ties into H-logics, while in Section 4 we present an alger rithm for computing "extensions" (i.e. sets of derivable conclusions) . In Section 5 we show that , unfortunately, computing an extension is a computationally hard prob­ lem in our formalism, even if its monotonic fragment is computationally tractable. Section 6 concludes.

2 Basic Notions of H-logics

In this section we present the basic notions of H­ logics. For a more e;eneral presentation see [Nebel, 1990; Donini et a/., 1992j.

2.1 The Terminological Module

We assume two disjoint alphabets of symbols, called atoms and roles. Concepts (denoted below by C and D) are formed out of atoms (denoted by A and B) according to the following syntax rule:

This logic is usually known as A.CC. Other H-logics are obtained by allowing different concept-forming op­ erators. An interpretation I = (dz , .I) consists of a set f:!..I (the domain of I) and a function .I (the interpreta­ tion function of I) which maps every concept to a subset of f:!..I and every role to a subset of f:!..I x f:!..I in such a way that the following equations are satisfied:

Let A be an atom and C be a concept. A terminological axiom is an expression of type A ::::: C (concept definition) or A <· C (concept specialization). When A::::: C we say that A is the name of C. An interpretation I satisfies a terminological axiom 6 iff

Therefore, a concept definition lists necessary and suffi­ cient conditions for appartenance to A, whereas a con­ cept specialization lists necessary conditions only.

A terminology (TBox) is a finite set T of terminolog­ ical axioms. An interpretation I is a model of T iff it satisfies all terminological axioms in T. We say that C subsumes D wrt T (written D [;T C) iff DI <; CI for every model I of T, and that C is equivalent to D wrt T (written C =T D) iff CI = VZ for every model I of T . We will write C f.T D iff C is not equivalent to D wrt T.

2.2 The Assertional Module

We assume an alphabet of symbols called individuals (de­ noted below by a and b), disjoint from the alphabets of atoms and roles. An individual description is an ex­ pression of type a:C, where a is an individual and C a concept. A relation description is an expression of type (a, b} :R, where a and b are individuals and R is a role. A description is either an individual description or a re­ lation description. Finally, an ABox is a finite set of descriptions.

With respect to the semantics, we extend the interpre­ tation function .I of an interpretation I to individuals by mapping them to elements of the domain f:!..I, in such a way that ai f. bi if a f. b 1 .

An interpretation I satisfies a description a iff

An interpretation I is a model of an ABox A iff it satis­ fies all descriptions in A .

2.3 Reasoning in H-logics

A knowledge base in an H-logic is defined as the pair of a TBox and an ABox. We will say that an interpretation I is a model of an A Box A wrt a TBox T, iff I is a model of A and ofT. An A Box A is consistent wrt a TBox T iff it has a model wrt T. An ABox A and a TBox T imply a description a, written A FT a, iff all models of A wrt T satisfy a.

1 This restriction on individuals, the so-called unique name assumption, ensures that different individuals denotes differ­ ent elements of the domain.

With respect to an H-logic knowledge base, the fol­ lowing problems are usually considered interesting. Let T be a TBox and A be an ABox.

• Subsumption problem: Does a concept C subsume a concept D wrt T ?
• Consistency problem: Does there exist a model of A wrt T?
• Instance problem: Do A and T imply an individual description 2 a:C ?
• Realization problem: Let a be an individual occur­ ring in A. The set of the most specific concepts of which a is an instance is defined as

What is the set of the most specific concepts of which a is an instance?

Retrieval problem: Let C be a concept. What is the set of all the individuals a such that A FT a:C ?

Recent works on the computational properties of H- log­ ics (see e.g. [Hollunder, 1990]) have shown that the above problems are reducible to the consistency problem, for which there exists a well-known technique based on con­ straint propagation. In fact, the subsumption problem is reducible to the instance problem since D [;T C iff { a:D} FT a:C, whereas the instance problem is re­ ducible to the consistency problem since A FT a:C iff AU { a:-,C} has no model wrt T . Finally, the realization problem can be easily solved by reducing it to the in­ stance problem and the subsumption problem, while the retrieval problem can be reduced to the instance prob­ lem.

For reasons of space we will not describe the constraint propagation method here. The interested reader can consult [Hollunder, 1990].

3 Embedding Default Inheritance Reasoning in H-Logics

Until now we have described only the standard notions of H-logics. Let us now see how we can effectively for­ malize a minimal framework in which default inheritance reasoning in H-logics can be performed.

A default of type 1 is an expression of the form A~--+ C , while a default of type 2 is an expression of the form A 1-+ R.C, where A is an atom, R is a role and C is a concept. Informally, a default A ~--+ C means: "if a is an A and the assumption that a is a C does not lead to a "conflict", then assume that a is a C"; for example, the default Bird~-+Fly means: "if a is a bird and the assumption that a flies does not lead to a "conflict", assume that a flies" . On the other hand, a default A 1-+ R.C means: "if a is an A such that b is an R-filler of a and the assumption that b is a C does not lead to a conflict, then assume that b is a C"; for example, the default Italian-University 1-+ Faculty-Member. Italian means: "if a is an Italian uni­ versity, b is one of its faculty members, and the assump­ tion that b is an Italian does not lead to a conflict, assume that b is an Italian" .

2 0bserve that, in our case, A FT (a, b) :R holds iff (a, b) :R E A, since there are no role-forming constructs in the terminological module.

In all systems for default inheritance reasoning con­ flicts are solved (whenever possible) by applying the so­ called specialization principle, according to which prop­ erties belonging to a subclass are preferred to properties belonging to a superclass. For example, given that Opus is a penguin, that penguins typically do not fly, whereas birds do, the specialization principle let us infer, as de­ sired, that Opus does not fly even if his being a bird might lead us to conclude differently. This is a default that we would call "of type 1"; the same principle is ap­ plicable to "type 2" defaults too: for example, given that the faculty members of Italian universities are typically Italian, given that the faculty members of South Ty­ rolean universities are typically not Italian, that South Tyrolean universities are Italian universities 3 , that the University of Bozen is a South Tyrolean university, and that Professor Schmidt is a faculty member thereof, the specialization principle lets us to derive, as desired, that Schmidt is not Italian.

Whenever conflicts are not solvable by means of the specialization principle, like in the well-known "Nixon Diamond" example, multiple extensions are typically al­ lowed.

We now go on to describe how our framework allows us to perform default inheritance reasoning in the con­ text of H-logics. Our way to handle defaults will com­ ply with the specialization principle and with "credulous reasoning" (because of this, multiple extensions are al­ lowed) . Let us define a Hybrid Default Inheritance The­ ory (HDIT) as a triple (A, T, V), where A is an ABox, T is a TBox and V is a finite set of defaults. If V contains only defaults of type 1 (resp. type 2), we will say that the theory is an HDIT of type 1 {resp . type 2).

From a technical point of view, our definition of "ex­ tension" will be similar to the one given by Reiter for Default Logic [Reiter, 1980], i.e. an extension is a fix­ point of a consequence relation. However, unlike in De­ fault Logic, we will see that the specialization principle is "wired" in our definition. The following definition de­ fines a precedence relation over atoms, ~T,.A , a · induced by a HDIT T, an individual a and an ABox A. This relation will be used for fixing priority to defaults .

Definition 3.1 Given an HDITT =(A, T, V), an indi­ vidual a and an ABox A, the binary relation over atoms ~T,.A,a is defined as the smallest relation such that

1. if AFT a:A and A ~T B, then A ~T, .A,a B;
2. if A FT a:A, A FT a:C and A 1-+ C E V, then A ~T, .A , a B for all B 's such that C ~T B;
3. ~T,A, a is transitively closed.

We define the transitive closure of A wrt T, written Tci(A , T) , to be the set {a I AFT a} . Note that ~T,.A, can be seen as the taxonomy induced by the strict and defeasible information, altogether, in T and A. The fol­ lowing definition, which is the main definition of this paper, deals with the notion of "extension"; the defini­ tion is rather complex, and the examples that follow it will contribute in clarifying its import.

3 South Tyrol is, in fact, a German-speaking region ofltaly.

Definition 3.2 LetT = (A, T, V) be an !fDIT:.. Let r be an operator such that, for any A Box A, f(A, T) is the smallest ABox satisfying the following closure condi­ tions:

1. A~ f(A, T);
2. f(A, T) = Tcl(f(A, T), T);
3. for all de[aults A 1-+ C E V, for all de-!criptions a:A E f(A, T), it happens that a:C E f(A, T), un­ less AU{a:C} is not consistent wrt Tor there exists an atom B such that B ~T .A a A and A ~T ..4 a B and either - ' ' ' '
4. (a) B 1-+ DE V, and
5. (b) AU {a :C n D} is not consistent wrt T or
6. (a) B t-+ R.D E V, and
7. (b) (a, b) :R E A, and
8. (c) AU {a :C, b:D} is not consistent wrt T
9. for all defaults A 1-+ R.C E V, for all descriptions a:A E f(A, T) such ~hat (a, b):R E_r(A, T), it hap­ pens that b:C E r(A, T), unless AU {b:C} is not consistent wrt T or there exists an atom B such that B ~T,.A,a A and A ~T,.A,a B and either
10. (a) B 1-+ DE V, and
11. {b) AU {b:C, a:D} is not consistent wrt T or
12. (a) B t-+ R .D E V, and
13. {b) AU {b:C n D} is not consistent wrt T

An ABox £ is an extension of the HDIT theory T iff £ = f(£, T), i.e. iff£ is a jixpoint of the operator r .

In Definition 3.2, points 1 and 2 are as for Default Logic; point 3 handles conflicts between type 1 and type 1 de­ faults, and conflicts between type 1 and type 2 defaults ; point 4 (symmetrically to point 3) handles conflicts be­ tween type 2 and type 1 defaults, and conflicts between type 2 and type 2 defaults . Definition 3.2 sanctions that ( i) defaults which introduce conflicts cannot be applied and (ii) ambiguous situations are handled by means of multiple extensions (see Example 3.3 below) .

We now consider some examples to show how Defini­ tion 3.2 works. The following example shows how "con­ flicts between fillers" are solved (type 2 vs. type 2) .

Example 3.1 Let Tt = (At , Tt, Vt) be the HDIT that formalizes our "Professors" example, with At = {p:IU, (p,r):FM, b:STU, (b,s) :FM}, Tt ={STU<· IU} and 'Dt = {IU~-+FM. I, STU~-+FM.-,I}. Let Et = Tcl(At U {s:-,I,r:I}) and f(£t,Tt) = Et . It is not hard to show that r( Et , Tt) satisfies the conditions of Definition 3.2; therefore Et is an extension of Tt. In Et the inference according to which Professor Schmidt is not Italian is sanctioned, as we hoped.

In the next example we show how "conflicts between classes" are solved (type 1 vs. type 1) .

Example 3.2 Let T2=(.A2, 72, V2} be an HDIT that formalizes our "Bird" example, with .A2 = {o:P}, 72 = {P <- 8} and V2 = {8~---+F, P~-+-,F}. It follows that £2 = Tcl(.A2 U {o:-, F}) is an extension of T2; hence, the inference according to which Opus does not fly is licensed.

The next example shows, instead, how ambiguous situ­ ations are handled, yielding multiple extensions.

Example 3.3 Let T3 = (.A3, 73, V3} be an HDIT that formalizes an extended version of the well known "Nixon Diamond", with .A3 = { a:Anc, a:-,8}, 73 = 0 and V3 = {C~-+D, A~---+-,0, A~---+8, 8~---+C}. Let £3, = Tcl(.A3 U {a:D}) and £3 2 = Tcl(.A3 U {a:-,D}) be ABoxes. It follows that f(£3,,T3) = £3, and f(£3 2 ,T3) = £3 2 , thus T3 has two extensions, £3, and £3 2 · Furthermore, note that A-lr,c,; ,aC, for 1 ~ i ~ 2, since a:8~ £3;. In the case a:-,8~ .A3, A~r,c~,aC would be the case, with £~ = Tcl(.A3 U {a:8, a:-,D}), and thus £~ would be the unique extension of T3.

In the example below we show how conflicts between conflicting defaults of different type are solved (type 1 vs. type 2).

Example 3.4 Let T4 = (.A4 , 74 , V4} be an HDIT, with .A4 = {j:RE, (j ,g}:C}, 'Lt ={RE <· E, GT <- 'v'C.G} and V4 = {E~-+�T, REI-+C.-,G}, where RE, C, E, GT, G, stand for RoyaLElephant, Color, Elefant, Gray_Thing and Grey, respectively. It turns out that £4 = Tcl(.A4 U {g:-,G}) is an extension of T4 ; in £4 , as we hoped, the fact that the colour of j is not grey is sanctioned.

The next example shows, by means of a modified ver­ sion of the "Royal-Elephant" example, how strict and defeasible information interact.

Example 3.5 LetTs = (.As, 7s, Vs} be an HDIT with .As= {j:RE, (j,g):C}, 75 ={GT <- 'v'C.G,RE <- En'v'C.-,G} and Vs = {E~-+�T}. It turns out that £s = Tcl(As) is an extension of Ts. Note that the default E~-+�T is not applied in the computation of £s, since Royal-Elephants are not gray: the application of defaults is "blocked" by the presence of strict information conflicting with them.

Unfortunately, some HDITs may not have extensions. The following example shows that there exists an HDIT of type 2 with no extension.

Example 3.6 Let T6 = (.A6 , 76 , V6} be an HDIT with .A6 = { a:A, (a,a} :R }, 76 ={ A:8nC, o:8nCnE} and V6 = { A~-+R. E, 0~---+R . -,E} . It is easy to show that T6 has no extension.

It is easy to show that the same property holds for HDITs of type 1 too.

Finally, note that, given an HDIT T1=(.A1, 77, V7} such

that .A7={a:3R1 . (3R2)nc} 4, 77=0 and V1={C~-+R2 .D}, £7=Tcl(.A7 , 77) does not contain a:3R1. 3R2. D, since in our definition of extension the role-filler must be explic­ itly known. This is contrary to intuitions: hence, in order to handle this case too,. we must modify Definition 3.2, requiring that A and f(A, T) are "3-closed", i.e. if

·Note that 3Ri= 3R.T, with T:: ..,(..,An A).

I

A f=r a:3R.C al!_d either (a, b}_:R E A or b:C E A is false, then (a, b) :R E .A and b:C E .A, for some new individual b. For example, given the HDIT above, the "3-closure" of A1 is A1 = .At U {(a,b}:R1, ~:(3R2)nc, (b,c}:R2}. It follows that r(.A7, T1) = Tcl(A1U{ c: D}) = £7 and f(£7, T1) = £7 . Therefore, a:3Rt .3R2 .D E £7, as from intuitions. This case can be seen as a special case of the Skolemization process in Reiter's Default Theories.

The examples detailed above show that our formalism has a reasonable and simple behaviour. It is important to notice that these features are due to the fact that our formalism is not just the "H-fragment" of a stan­ dard non-monotonic logic, as its behaviour is informed by the "specialization principle" , a principle that is not present into standard non-monotonic logics and that is the reason for what we claim to be the superior (in terms of intuitivity) behaviour of our formalism.

In the Section 4 we describe an algorithm for comput­ ing an extension (whenever it exists) of an HDIT T.

4 Computing Extensions

In order to describe our algorithm, we introduce some definitions . LetT= (A,7,V) be an HDIT, a and b two individuals, A an ABox, 6 E V a default of the form A ~---+ C, rr E V a default of the form A 1-+ R .C . An instantiated default of T is either a pair i=(a, 6) or a triple i=(a, b, u). The function Consequent is defined to be such that Consequent(( a, 6) )=a:C and Consequent(( a, b, u) )=b:C. We say that an instantiated default (a, 6) is applicable in A wrt T iff A f=r a:A and the "unless" conditions of Definition 3.2, point 3, do not hold. Analogously, an inst_antiated default (a , b, u) js ap­ plicable in .A wrt T iff A f=r a:A, (a, b) :R E A and the "unless" conditions of Definition 3.2, point 4, do not hold. We will write A·r(A) as shorthand for the set of applicable defaults in .A wrt T .

Let us now discuss the EXT algorithm for computing extensions, which is similar to that described in [Ether­ ington, 1988] for Reiter's Default Theories . The exten­ sion is built by a series of subsequent approximations , each of them being an ABox. Each approximation An is built from the first component .A of an HDIT T by using applicable defaults , one at time. At each step, the instantiated default to be applied is chosen from those which have not yet been considered and which were ap­ plicable in the previous approximation and still are in the current "state" of the current approximation. When no more instantiated defaults are applicable, the algorithm continues with the next approximation . If two successive approximations are the same set, the algorithm is said to converge. The EXT algorithm is detailed in Table 1.

The following correctness and completeness theorem states that all and only the extensions of an HDIT T can be computed by the algorithm.

Theorem 4.1 LetT =(A, 7, V) be an HDIT. £ is an extension ofT iff the application of the EXT algorithm toT has a converging computation such that An = An-l and Tcl(.An, T) = £.

Therefore, it is not necessary to compute an entire ex­ tension £, since the corresponding An is sufficient. Fur-

Let T=(A, T, V) be an HDIT; begin Ao +- A; n +- 0; repeat n+-n+l;w0 +-A;Do +-0;i+-O; repeat A~+- (AT(w;) n AT(An-!}) \ D;; if not empty(A~) then choose 'Y from A~; D;+l +- D; U {-y}; w;+1 +- w; U {Consequent('Y)}; endif i +- i + 1; until empty(A~ 1 ); An+- Wi-lj until An = An-1; end

Table 1: The EXT algorithm computes an extension of an HDIT.

thermore, observe that, according to Theorem 4.1, the computation converges if and only if there exists an ex­ tension. The following example shows that, if there are no extensions, the computation does not converge.

Example 4.1 Consider the HDIT T6 of Example 3.6. It turns out that each approximation A; is such that A21: = A6 and A21:+1 = A6 U {a:E} , for each k ~ 0. Therefore A2 ~: :f A2k+1 for each k ~ 0, and the computation never stops.

Note however that, since the set of instantiated de­ faults of an HDIT T is finite, there is only a finite num­ ber of A Boxes An, computable by the EXT algorithm, such that Tcl(An, T) is an extension; it is thus possible to decide if there are cyclic computations like the one in Example 4.1. Therefore, it is straightforward to mod­ ify the EXT algorithm so that the computation always converges.

5 Complexity

In this section we will analyze the computational com­ plexity of computing an extension. In order to do so, first of all we will restrict our attention to HDITs for which deciding if an instantiated default is applicable is computable in polynomial time; for all the other HDITs, the problem of computing an extension is obviously in­ tractable. For our purpose, let T = (A, T, V) be an HDIT and C a concept. C is a simple concept wrt T iff C is a conjunction of atoms or negated atoms which are not names in T . We will say that Tis a restricted HDIT of type 1 iff (a) A contains only individual descriptions of the form a:C, where Cis a simple concept wrt T; (b) T contains only terminological axioms of the form A= C, where Cis an atom (or the negation of an atom) which is not a name in T , or axioms of the form A <· B, where B is not a name in T, and (c) V is a set of defaults of the form A ........ C, where C is a simple concept wrt T . The definition of a restricted HD/Ts of type 2 is similar to the case of type 1, but for the fact that V contains only defaults of the form A ........ S.C, where C is a simple concept wrt T. It may be shown that, in the case of restricted HDITs (either of type 1 or of type 2) decidi~g if an instantiated default is applicable is computable m polynomial time.

Unfortunately, notwithstanding the restrictions on HDITs, the problem of computing an extension is a hard problem.

Theorem 5.1 Finding an extension of a restricted HDIT of type 1 (or determining that it has no exten­ sion) is NP-Hard.

The proof of this theorem depends on the following re­ duction of the 3SAT problem [Garey and Johnson, 1979] to the problem of determining an extension. The reduc­ tion is similar to that described in [Kautz, 1989]. For a propositional formula u in 3CNF consider the restricted HDIT of type 1, Tu, obtained exactly from the expres­ sions which appear in the following rules. (A) for every symbol P which occurs in u, the following expressions appear in Tu, where A is a new atom and a an individ­ ual: A ........ P, A ........ ...,p, a:A. (B) for each clause XVYV Z of u, the following expressions appear in Tu, where A, .B, F and F:r:yz are new atoms: A::::: ...,x (we will use P Ill­ stead of ...,...,p), A ........ F:r:yz n-,yn...,z and F:r:yz ........ Fn-,B . (C) F <· F:r:yz and F 1-+ B appear in Tu. We can show that u is satisfiable iff Tu ·has an extension 5 . Therefore the problem of determining if a restricted HDIT of type 1 has an extension is also NP-Hard.

The same property holds for restricted HDITs of type 2. In fact we can consider the same HDIT Tu as above except that expressions of the form A 1-+ C are substi­ tuted with the expressions of the form A 1-+ R .C and (a,a):R.

Theorem 5.2 Finding an extension of a restricted HDIT of type 2 {or determining that it has no exten­ sion) is NP-Hard.

Among the problems listed in Section 2.3, let us ana­ lyze the complexity of the instance problem with respect to our formalism (we will leave the consistency problem aside as, in our context, it corresponds to the problem of answering if there exists a consistent extension) . Let us first define what the "instance problem" amounts to in our framework. One can say that, due to the pos­ sible presence of multiple extensions, there are actually two types of instance problems: the "credulous" one and the "skeptical" one. Let T be an HDIT and a:C be an individual description; the credulous instance problem is the problem of determining if there is an extension £ of T such that a:C E £ (in this case we will say that a is a credulous instance of C wrt T). The skeptical in­ stance problem is defined as the problem of determining if a:C is an element of the intersection of all the exten­ sions of T (in this case we will say that a is a skeptical instance of C wrt T). One can easily check that the realization problem can be defined in terms of the sub­ sumption problem and the credulous/skeptical instance problem, whereas the retrieval problem can be defined in terms of the credulous/skeptical instance problem.

5 Note that if u is satisfiable it must not be the case that a:F E £, where£ is an extension ofT".

Since, given an HDIT T, a:T is a credulous instance of C wrt TiffT has an extension, from Theorem 5.1 and Theorem 5.2 we have the following Corollary:

Corollary 5.1 The credulous instance problem for re­ stricted HD/Ts (either of type 1 or of type 2} is NP­ Hard.

Instead:

Theorem 5.3 The skeptical instance problem for re­ stricted HD/Ts (either of type 1 or of type 2} is co-NP­ Hard.

The proof of Theorem 5.3 wrt HDITs of type 1 (resp. type 2) is similar to the one for Theorem 5.1 (resp. Theo­ rem 5.2), except that in the reduction we do not consider rule (C). Therefore, an arbitrary propositional 3CNF formula u is unsatisfiable iff a:F holds in all extensions of Ta.

6 Conclusion

In this paper we have shown how we can extend H-logics in such a way that they allow default inheritance reason­ ing, thus creating a formalism that combines the expres­ sive power of a language for the description of taxonomic organizations of complex objects with the taxonomy­ oriented style of default reasoning which is typical of "inheritance systems with exceptions" .

The importance of our work lies in bringing these de­ fault reasoning capabilities into a family of logics that have gained wider and wider acceptance because of their reasonable expressive power, good computational prop­ erties, intuitive "object-oriented" syntax and wide spec­ trum of applicability.

We have presented an algorithm that computes exten­ sions and shown that it is correct and complete. More­ over, we have shown that, even if the "H-fragment" of our formalism were tractable, computing an extension or deciding that there are no extensions would be NP-Hard; similarly, also the (credulous or skeptical) instance prob­ lem, the realization problem and the retrieval problem are intractable.

0 ur formalism has been designed with the aim of pro­ viding the minimal framework that would allow one to study the interaction of H-knowledge and default inher­ itance knowledge in a meaningful way. Quite obviously, extensions to this framework may be conceived that en­ able the expression of more general concepts: any H-logic that contains ACC may be profitably used.

For that matter, the formalism could also be straight­ forwardly extended to the representation of default rules of a different nature; for example, we might have de­ faults of the form a : /31, ... , f3n/'Y, where a, !31, .. . , f3n and 'Y are ACC concepts. Recently, Baader and Hol­ lunder [1992] have embedded this types of defaults into H-logics. However, their formalism, unlike ours, does not support the taxonomy-oriented brand of non-monotonic reasoning informed by the "principle of specialization"; it can thus be seen as (and has the disadvantages of) an "H-fragment" of a standard non-monotonic logic (in their case, Reiter's Default Logic).