Least Common Subsumers and Most Specific Concepts in a Description Logic with Existential Restrictions and Terminological Cycles

1 Introduction

Computing the most specific concept of an individual and the least common subsumer of concepts can be used in the bottom-up construction of description logic (DL) knowledge bases. Instead of defining the relevant concepts of an ap­ plication domain from scratch, this methodology allows the user to give typical examples of individuals belonging to the concept to be defined. These individuals are then general­ ized to a concept by first computing the most specific concept of each individual (i.e., the least concept description in the available description language that has this individual as an instance), and then computing the least common subsumer of these concepts (i .e., the least concept description in the avail­ able description language that subsumes all these concepts). The knowledge engineer can then use the computed concept as a starting point for the concept definition.

The least common subsumer (lcs) in DLs with existential restrictions was investigated in [Baader et al., 1999]. In par­ ticular, it was shown there that the lcs in the small DL ££ (which allows for conjunctions, existential restrictions, and the top-concept) always exists, and that the binary lcs can be computed in polynomial time. Unfortunately, the most sp.e­ cific concept ( msc) of a given ABox individual need not exist in languages allowing for existential restrictions or number restrictions. As a possible solution to this problem, Kiisters and Molitor [2001] show how the most specific concept can be approximated in££ and some of its extensions. Here, we follow an alternative approach: we extend the language by cyclic terminologies with greatest fixpoint (gfp) semantics, and show that the msc always exists in this setting. Of course, then one must also be able to compute the lcs w.r.t. cyclic ter­ minologies with gfp-semantics. For the DL ACN (which al­ lows for conjunctions, value restrictions, and number restric­ tions) it was shown in [Baader and Kiisters, 1998] that the most specific concept always exists if one adds cyclic con­ cept definitions with gfp-semantics. One reason for Kiisters and Molitor to choose an approximation approach rather than an exact characterization of the most specific concept using cyclic definitions was that the impact of cyclic definitions in description logics with existential restrictions was largely un­ explored.

*Partially supported by the DFG under grant BA 1122/4-3.

The paper [Baader, 2003a] is a first step toward overcom­ ing this deficit. It considers cyclic terminol?gies in££ w:r.t. the three types of semantics (greatest fixpomt, least fixpomt, and descriptive semantics) introduced by Nebel [1991], and shows that the subsumption problem can be decided in poly­ nomial time in all three cases. This is in stark contrast to the case of DLs with value restrictions. Even for the small DL :F £ 0 (which allows conjunctions and value restrictions only), adding cyclic terminologies increases the complexity of the subsumption problem from polynomial (for concept descrip­ tions) to PSPACE. The main tool in the investigation of cyclic definitions in££ is a characterization of subsumption through the existence of so-called simulation relations on the graph associated with an ££-terminology, which can be computed in polynomial time [Henzinger eta!., 1995].

This characterization of subsumption can be used to char­ acterize the lcs w.r.t. gfp-semantics via the product of this graph with itself (Section 4). This shows that, w.r.t. gfp se­ mantics, the lcs always exists, and that the binary lcs can be computed in polynomial time. (The n-ary lcs may grow ex­ ponentially even in££ without cyclic terminologies [Baader eta!., 1999].)

The characterization of subsumption w.r.t. gfp-semantics can be extended to the instance problem in££. This allows us to show that the msc in££ with cyclic terminologies inter­ preted with gfp semantics always exists, and can be computed in polynomial time (Section 5).

In the next section, we introduce££ with cyclic terminologies as well as the lcs and the msc. Then we recall the impor­ tant definitions and results from [Baader, 2003a]. Section 4 formulates and proves the new results for the lcs, and Sec­ tion 5 does the same for the msc.

2 Cyclic terminologies, least common subsumers, and most specific concepts

Concept descriptions are inductively defined with the help of a set of constructors, starting with a set Nc of concept names and a set N R of role names. The constructors deter­ mine the expressive power ofthe DL. In this paper, we restrict the attention to the DL ££, whose concept descriptions are formed using the constructors top-concept (T), conjunction (C n D), and existential restriction (:Jr.C). The semantics of ££-concept descriptions is defined in terms of an interpreta­ tion I= (6I, .I). The domain 6I of I is a non-empty set of individuals and the interpretation function .I maps each concept name A E Nc to a subset AI of 6I and each role r E N R to a binary relation ri on 6 I. The extension of .I to arbitrary concept descriptions is inductively defined, as shown in the third column of Table 1.

A terminology (or TBox for short) is a finite set of con­ cept definitions of the form A = D, where A is a concept name and D a concept description. In addition, we require that TBoxes do not contain multiple definitions , i.e., there cannot be two distinct concept descriptions D1 and D2 such that both A = D1 and A = D2 belongs to the TBox. Con­ cept names occurring on the left-hand side of a definition are called defined concepts. All other concept names occurring in the TBox are called primitive concepts. Note that weal­ low for cyclic dependencies between the defined concepts, i.e., the definition of A may refer (directly or indirectly) to A itself. An interpretation I is a model of the TBox T iff it satisfies all its concept definitions, i.e., AI = DI for all definitions A = D in 'T.

An A Box is a finite set of assertions of the form A( a) and r(a, b) , where A is a concept name, r is a role name, and a, b are individual names from a set N1. Interpretations of ABoxes must additionally map each individual name a E N1 to an element a I of!::!. I . An interpretation I is a model of the ABox A iff it satisfies all its assertions, i.e., ai E AI for all concept assertions A( a) in A and (ai, bi) E ri for all role assertions r(a, b) in A. The interpretation I is a model of the ABox A together with the TBox Tiff it is a model of both T and A.

The semantics of(possibly cyclic) ££-TBoxes we have de­ fined above is called descriptive semantic by Nebel [1991] . For some applications, it is more appropriate to interpret cyclic concept definitions with the help of a fixpoint seman­ tics.

Example 1 To illustrate this, let us recall an example from [Baader, 2003a]: !node =: Node n :ledge. I node.

Here the intended interpretations are graphs where we have nodes (elements of the concept Node) and edges (represented by the role edge), and we want to define the concept lnode of all nodes lying on an infinite (possibly cyclic) path of the graph. In order to capture this intuition, the above definition must be interpreted with greatest fix point semantics.

Before we can define greatest fixpoint semantics (gfp­ semantics), we must introduce some notation. Let T be an ££-TBox containing the roles Nrole, the primitive concepts Nprim, and the defined concepts N de f = {A1, . . . , Ak} . A primitive interpretations .J for T is given by a domain 6 :J, an interpretation of the roles r E Nrole by binary relations r:l on 6:l, and an interpretation of the primitive concepts P E N prim by subsets p:J of 6 :J . Obviously, a primitive interpretation differs from an interpretation in that it does not interpret the defined concepts in N de f · We say that the in­ terpretation I is based on the primitive interpretation .J iff it has the same domain as .J and coincides with .J on Nrole and Nprim· For a fixed primitive interpretation .J, the inter­ pretations I based on it are uniquely determined by the tuple (Af, ... , AD of the interpretations of the defined concepts in Ndef. We define

Interpretations based on .J can be compared by the following ordering, which realizes a pairwise inclusion test between the respective interpretations of the defined concepts: if I 1 , I2 E Int(.J) , then

It is easy to see that -5_s induces a complete lattice on Int(.J), i.e., every subset of Int(.J) has a least upper bound (lub) and a greatest lower bound (glb ). Using Tarski 's jixpoint theorem [Tarski, 1955] for complete lattices, it is not hard to show [Nebel, 1991] that, for a given primitive interpretation .], there always is a greatest (w.r.t. -5_s) model ofT based on.]. We call this models the greatest jixpoint model (gfp-model) of/. Greatestfixpoint semantics considers only gfp-models as admissible models.

Definition 2 LetT be an ££-TBox and A an ££-ABox, Jet A, B be defined concepts occurring in T , and a an individual name occurring in A. Then,

• A is subsumed by B w.r.t. gfp-semantics (A f;;;gJp,T B ) iff AI ~ BI holds for all gfp-modelsi ofT
• a is an instance of A w.r.t. gfp-semantics (A Fgfp,/ A( a)) iff ai E AI holds for all models I of A that are gfp-models of/.

On the level of concept descriptions, the least common sub­ sumer of two concept descriptions C, D is the least concept description E that subsumes both C and D. An extensions of this definition to the level of (possibly cyclic) TBoxes is not completely trivial. In fact, assume that A1 , A2 are con­ cepts defined in the TBox T It should be obvious that taking as the lcs of A 1 , A2 the least defined concept B in T such that A1 r;;,gfp,T B and A2 r;;,gfp,T B is too weak since the lcs would then strongly depend on what other defined con­ cepts are already present in T However, a second approach (which might look like the obvious generalization of the def­ inition of the lcs in the case of concept descriptions) is also not quite satisfactory. We could say that the lcs of A1 , A2 is the least concept description C (possibly using defined con­ cepts ofT) such that A1 r;;,gfp,T C and A2 r;;,gfp,T C. The problem is that this definition does not allow us to use the expressive power of cyclic definitions (with gfp-semantics) when constructing the lcs. For example, consider the TBox T consisting of the following concept definitions:

The intended interpretation is similar to the one in Example 1, with the only difference that now nodes may have colors, and we are interested in blue (red) nodes lying on an infi­ nite path consisting of blue (red) nodes. Intuitively, the lcs of Bluelnode and Redlnode describes nodes lying on an in­ finite path (without any restriction on their color), i.e., the concept I node from Example 1 should be a definition of this lcs. However, this cannot be expressed by a simple concept description. It requires a new cyclic definition.

Consequently, to obtain the lcs we must allow the origi­ nal TBox to be extended by new definitions. We say that the TBox 72 is a conservative extension of the TBox h. iff 1i ~ 72 and h. and 72 have the same primitive concepts and roles. Thus, 72 may contain new definitions A = D, but then D does not introduce new primitive concepts and roles (i.e., all of them already occur in h.), and A is a new concept name (i.e., A does not occur in h,). The name "conservative exten­ sion" is justified by the fact that the new definitions in 72 do not influence the subsumption relationships between defined concepts in h. (see [Baader, 2002] for a proof).

Lemma 3 Let h., 72 be££-TBoxes such that 72 is a conser­ vative extension ofh,, and let A, B be defined concepts in h. (and thus also in 12). Then A r;;,gfp,Ti B iff A r;;,gfp,12 B.

Definition 4 Let h. be an ££-TBox containing the defined concepts A, B, and let 72 be a conservative extension of h. containing the new defined concept E. Then E in 72 is a least common subsumer of A, Bin h. w.r.t. gfjJ-semantics (gfp-lcs) iff the following two conditions are satisfied:

1. A r;;,gfp,12 E and B r;;,gfp,12 E.
2. If 13 is a conservative extension of 72 and F a defined concept in 13 such that A r;;,gfp,1j F and B r;;,gfp,1j F, then E r;;,gfp,Ta F.

In the case of concept descriptions, the lcs is unique up to equivalence, i.e., if E1 and E2 are both least common subsumers of the descriptions C, D, then E1 = E2 (i.e., E1 r;;, E2 and E2 r;;, E1). In the presence of (possibly cyclic) TBoxes, this uniqueness property also holds (though its for­ mulation is more complicated).

Proposition 5 Let h. be an ££-TBox containing the defined concepts A, B. Assume that 72 and T:j are conservative ex­ tensions ofh. such that

• the defined concept E in 72 is a gfp-lcs of A, Bin h,;
• the defined concept E' in T:j is a gfp-lcs of A, Bin h,;
• the sets of newly defined concepts in respectively 72 and T:j are disjoint.

For13 := 7;,U7:j, wehaveE =: 9 Jp,1j E' (i.e., E r;;,gfp,Ta E' and E' r;;,gfp, 7j E).

The notion "most specific concept" can be extended in a similar way from concept descriptions to concepts defined in a TBox.

Definition 6 Let h. be an££-TBox and A an£ £-ABox con­ taining the individual name a, and let 72 be a conservative ex­ tension of h. containing the defined concept E. Then E in 72 is a most specific concept of a in A and h. w.r.t. gfp-semantics (gfp-msc) iff the following two conditions are satisfied:

1. A Fgfp,12 E(a).
2. If 13 is a conservative extension of 72 and F a de­ fined concept in 13 such that A f=gfp,Ta F(a), then E r;;,gfp,Ta F.

Uniqueness up to equivalence of the most specific concept can be formulated and shown like uniqueness of the least common subsumer.

3 Characterizing subsumption

In this section, we recall the characterizations of subsump­ tion w.r.t. gfp-semantics developed in [Baader, 2003a]. To this purpose, we must represent TBoxes and primitive inter­ pretations by description graphs, and introduce the notion of a simulation on description graphs.

Before we can translate ££-TBoxes into description graphs, we must normalize the TBoxes. In the following, let T be an ££-TBox, Ndef the defined concepts ofT, Nprim the primitive concepts ofT, and Nrole the roles ofT

We say that the ££-TBox T is normalized iff A = D E T implies that D is of the form

form,£~ O,Pl, ... ,Pm E Nprim,r1, ... ,re E Nrole,and B1, ... ,BeE Ndef· Ifm = e = 0, then D = T.

As shown in [Baader, 2003a], one can (without loss of gen­ erality) restrict the attention to normalized TBox. In the fol­ lowing, we thus assume that all TBoxes are normalized. Nor­ malized ££-TBoxes can be viewed as graphs whose nodes are the defined concepts, which are labeled by sets of prim­ itive concepts, and whose edges are given by the existential restrictions. For the rest of this section, we fix a normalized ££-TBox T with primitive concepts Nprim, defined concepts Ndef, and roles Nrole·

Definition 7 An ££-description graph is a graph 9 = (V, E, L) where

• V is a set of nodes;

• E ~ V x Nrole x V is a set of edges labeled by role names;
• L: V --+ 2Nprim is a function that labels nodes with sets of primitive concepts.

The normalized TBox T can be translated into the follow­ ing ££-description graph 9r = (Ndef, Er, Lr) :

• the nodes of9r are the defined concepts ofT;
• if A is a defined concept and

its definition in T, then

• Lr(A) = {Pt, ... ,Pm},and
• A is the source of the edges (A, r1, Bt), .. . , (A, re, Be) E Er.

Any primitive interpretation .J = (6_.:1, . .:1) can be translated into the following ££-description graph 9.:1 (6..:1, E.:J, L.:1):

• the nodes of 9.:1 are the elements of 6. .:1;
• E.:1 := {(x,r, y) I (x,y) E r.:l};
• L.:1(x) = { P E Nprim I X E p.:J} for all X E 6_.:1.

Conversely, every ££-description graph can be viewed as representing either an £ .C-TBox or a primitive interpretation.

Simulations are binary relations between nodes of two££­ description graphs that respect labels and edges in the sense defined below.

Definition 8 Let 9i = (Vi, Ei, Li) (i = 1, 2) be two ££­ description graphs. The binary relation z ~ vl X v2 is a simulation from 91 to 92 iff

• (S2) if(v1,v2) E Zand(v1 ,r,v~) E Et,thenthereexistsa node v~ E V2 such that (v~,v~) E Z and (v2 ,r , v~) E E2.

We write Z: 91 ;:::: 92 to express that Z is a simulation from 9t to 92.

It is easy to see that the set of all simulations from 91 to 92 is closed under arbitrary unions. Consequently, there always exists a greatest simulation from 91 to 92 . If 91, 92 are finite, then this greatest simulation can be computed in polynomial time [Henzinger eta!., 1995]. As an easy consequence of this fact, the following proposition is proved in [Baader, 2003a].

Proposition 9 Let 91 , 92 be two finite ££-description graphs, Vt a node of 9t and v2 a node of 92· Then we can decide in polynomial time whether there is a simulation Z: 9t;::: 92 such that (vt, v2) E Z.

Subsumption w.r.t. gfp-semantics corresponds to the exis­ tence of a simulation relation such that the subsumee simu­ lates the subsumer:

Theorem 10 LetT be an £.C-TBox and A, B defined con­ cepts in T Then the following are equivalent:

The theorem together with Proposition 9 shows that sub­ sumption w.r.t. gfp-semantics in £.C is tractable. The proof of the theorem given in [Baader, 2003a] depends on a charac­ terization of when an individual of a gfp-model belongs to a defined concept in this model.

Proposition 11 Let .J be a primitive interpretation and I the gfp-model ofT based on .J. Then the following are equiva­ lent for any A E Ndef and X E 6. .:J:

This proposition is also important in the proof of correctness of our characterization of the instance problem (Theo­ rem 17).

4 Computing the lcs

We will show how the characterization of subsumption w.r.t. gfp-semantics given in Theorem 10 can be used to charac­ terize the gfp-lcs (see [Baader, 2002] for more details and proofs). Let 1i be an £.C-TBox, let 97i = (Ndef, E7i, L7i) be the corresponding description graph, and let A, B be de­ fined concepts in 1i (i.e., elements of Ndef ). In principle, the lcs of A, B in 1i is defined in a TBox whose description graph is the product of g7i with itself.

Definition 12 Let 9t = (V1, Et. Lt) and 92 = (V2, E2, L2) be two description graphs. Their product is the description graph 9t x 92 := (V, E, L) where

• v := Vt X V2;
• E := {((vt,V2),r,(v~,v~)) I (v1,r,v~) E Et 1\ (v2, r, v~) E E2};
• L( Vt, v2) := Lt ( v1) n L2(v2 ).

The description graph 97i x 97i yields a TBox T such that 9r = 97i x 97i . Now, 12 := 1i U T is a conservative extension of 1i. In fact, g7i x 97i is based· on the same primitive concepts and roles as g7i, and the set of defined concepts in T is Ndef x Ndef, which is disjoint from Ndef.

Computing the (binary) product of two ££-description graphs can obviously be done in polynomial time, and thus the gfp-lcs can be computed in polynomial time.

Theorem 14 Let 1i be an £.C-TBox, and let A, B be defined concepts in 11. Then the gfp-lcs of A, Bin 1i always exists, and it can be computed in polynomial time.

5 Instance and most specific concepts

One motivation for considering cyclic terminologies in £ .C is the fact that the most specific concept of an ABox individ­ ual need not exist in £.C (without cyclic terminologies). An example is the simple cyclic ABox A:= {r(b,b)}, where b has no most specific concept, i.e., there is no least ££­ concept description D such that b is an instance of D w.r.t. A [Kusters and Molitor, 200 1]. However, if one allows for cyclic TBoxes with gfp-semantics, then the defined concept B with B = 3r.B is such a most specific concept.

5.1 The instance problem w.r.t. gfp-semantics

Let 'T be a normalized £.C-TBox and A an £.C-ABox. In the following, we assume that r is fixed and that all instance problems for A are considered w.r.t. this TBox.

In this setting, A can be translated into an ££-description graph 9A by viewing A as a graph and extending it appropri­ ately by the graph 9T associated with T. The idea is then that the characterization of the instance problem should be simi­ lar to the statement of Proposition 11 : the individual a is an instance of A in A iff there is a simulation Z: 9T ~ 9A such that (A, a) E Z.

Before giving an exact definition of9A, we consider an ex­ ample that demonstrates that a too simple-minded realization of this idea does not work. Let

The ABox A itself can be viewed as an ££-description graph consisting of a single node a with label {P}. Since A = 3r.A is in 'T and A( a) is in A, we extend this graph by an r-loop from a to a. Figure 1 shows the graph 9 obtained this way as well as the ££-description graph 9T corresponding toT.

Obviously, there is a simulation Z: 9T ~ 9 such that ( B , a) E Z. However, it is easy to see that a is not an in­ stance of B. The reason for this problem is that node labels and edges in 9T state facts that must hold for all individu­ als that are instances of the defined concept labeling a given node whereas assertions of the ABox make statements about properties of particular named individuals. The construction of 9 in the above example mixes these different things, and thus leads to unfounded conclusions.

In order to separate edges and labels coming from ABox assertions from the ones coming from TBox definitions, we do not "identify" the node a with the node A if A( a) belongs to A (as done in the construction of 9 above) . Instead, we do a "one-step expansion" of the definition of A. The right-most graph in Figure 1 shows the graph 9A obtained this way in our example. Obviously, there is no simulation Z : 9T ~ 9A such that ( B , a) E Z .

Below, we give a formal definition of the ££-description graph 9A associated with the ABox A and the TBox r in the general case.

Definition 15 Let 'T be an £.C-TBox, A an £.C-ABox, and 9T = (V, E, L) be the ££-description graph associated with T. The ££-description graph 9A = (VA, EA, LA) associ­ ated with A and 'Tis defined as follows:

• The nodes of 9 A are the individual names occurring in A together with the defined concepts of/, i.e., VA:= V U {a I a is an individual name in A}.
• The edges of 9A are the edges of 9, the role assertions of A, and additional edges linking the ABox individuals with defined concepts:

• if u E VA is a defined concept, then it inherits its label from 9T, i.e. , LA(u) := L(u) if u E V . Otherwise,

u E VA\ Vis an ABox individual, and then its label is derived from the concept assertions for u in A:

Here P denotes primitive and A denotes defined con­ cepts.

Before we can characterize the instance problem via the existence of certain simulation relations from 9T to 9A, we must characterize under what conditions a gfp-model of r is a model of A. In the following we assume that primitive interpretations .J also interpret ABox individuals. We say that the simulation Z: 9A ~ 9.:J respects ABox individuals iff {x I (a , x) E Z} = {a.:l} for all individual names a occurring in A.

Proposition 16 Let .J be a primitive interpretation and I the gfp-model of/ based on .J. Then the following are equiva­ lent:

1. I is a model of A.
2. There is a simulation Z: 9A ~ 9.:J that respects ABox individuals.

The following characterization of the instance problem is an easy consequence of this proposition and Proposition 11.

Theorem 17 Let 'T be an £ .C-TBox, A an £C-AB ox, A a defined concept in r and 'a' an individual name occurring in A. Then the following are equivalent:

1. A Fgfp,T A(a).
2. There is a simulation Z: 9T ~ 9A such that (A, a) E Z.

The theorem together with Proposition 9 shows that the instance problem w.r.t. gfp-semantics in £.Cis tractable.

Corollary 18 The instance problem w.r.t. gfjJ-semantics in £ .C can be decided in polynomial time.

5.2 Computing the gfp-msc

Let Ti. be an £.C-TBox and A an £.C-ABox containing the individual name a. Let 9A = (VA, EA, LA) be the ££­ description graph corresponding to A and Ti. , as introduced in Definition 15. In order to obtain the gfp-msc of a, we view 9 A as the ££-description graph of an£ .C-TBox 72, i.e., let 72 be the TBox such that 9A = 9T?.· By the definition of9A, the defined concepts of72 are the defined concepts ofTi. together with the individual names occurring in A. It is easy to show that 72 is a conservative extension of Ti.. To avoid confusion we will denote the defined concept in T2 corresponding to the individual name bin A by Cb .

Using the results of the previous subsection, we can show [Baader, 2002] that Ca is the gfp-msc of a.

Lemma 19 The defined concept Ca in 72 is the gfjJ-msc of 'a 'inAandTi..

Given Ti. and A, the graph 9A can obviously be computed in polynomial time, and thus the gfp-msc can be computed in polynomial time.

Theorem 20 Let Ti. be an£ .C-TBox and A an£ C-AB ox con­ taining the individual name 'a'. Then the gfp-msc of 'a' in Ti and A always exists, and it can be computed in polynomial time.

[Baader, 2003a] F. Baader. Terminological cycles in a de­ scription logic with existential restrictions. In Proc. IJ­ CA/'03, 2003.

[Baader, 2003b] Franz Baader. The instance problem and the most specific concept in the description logic £ .C w.r. t. terminological cycles with descriptive semantics. LTCS­ Report 03-01, TU Dresden, 2003. See http://lat.inf.tu­ dresden.de/researchlreports.html.

[Baader and Kiisters, 1998] F. Baader and R. Kiisters. Com­ puting the least common subsumer and the most specific concept in the presence of cyclic A.CN -concept descrip­ tions. In Proc. KJ'98, Springer LNAI 1504, 1998.

[Baader eta/., 1999] F. Baader, R. Kiisters, and R. Molitor. Computing least common subsumers in description logics with existential restrictions. In Proc. IJCA/'99, 1999.

[Cote eta/., 1993] R. Cote, D. Rothwell, J. Palotay, R. Beck­ ett, and L. Brochu. The systematized nomenclature of hu­ man and veterinary medicine. Technical report, SNOMED International, Northfield, IL: College of American Pathol­ ogists, 1993.

[Henzinger eta/., 1995] M. R. Henzinger, T. A. Henzinger, and P. W. Kopke. Computing simulations on finite and infinite graphs. In 36th Annual Symposium on Foundations of Computer Science, 1995. IEEE Computer Society Press.

[Kiisters, 2001] R. Kiisters. Non-standard Inferences in De­ scription Logics, Springer LNAI 2100, 2001 .

[Kiisters and Molitor, 2001] R. Kiisters and R. Molitor. Ap­ proximating most specific concepts in description logics with existential restrictions. In Proc. Kl 2001, Springer LNAI 2174,2001.

[Nebel, 1991] B. Nebel. Terminological cycles: Semantics and computational properties. In J. F. Sowa, editor, Prin­ ciples of Semantic Networks. Morgan Kaufmann, 1991 .

[Spackman, 2000] K. Spackman. Managing clinical termi­ nology hierarchies using algorithmic calculation of sub­ sumption: Experience with SNOMED-RT. J. of the Amer­ ican Medica/Informatics Association, 2000. Fall Sympo­ sium Special Issue.

[Spackman, 2001] K. Spackman. Normal forms for descrip­ tion logic expressions of clinical concepts in SNOMED RT. J. of the American Medica/Informatics Association, 2001 . Symposium Supplement.

[Tarski, 1955] A. Tarski. A lattice-theoretical fixpoint theo­ rem and its applications. Pacific Journal of Mathematics, 5, 1955.

6 Conclusion

In [Baader, 2003a] we have shown that subsumption in£ .C re­ mains polynomial if one allows for cyclic terminologies with greatest fixpoint (gfp) semantics. In Section 5.1 of this pa­ per we have complemented this result by showing that the instance problem in £ .C with cyclic terminologies interpreted with gfp-semantics is also polynomial. Thus, all the standard inferences in £.C remain polynomial if one allows for cyclic terminologies with gfp-semantics. Our main motivation for considering cyclic terminologies with gfp-semantics in £.C was that the most specific concept of an ABox-individual then always exists. In fact, we have shown in this paper that both the least common subsumer (lcs) and the most specific con­ cept (msc) can be computed in polynomial time in £.C with cyclic terminologies interpreted with gfp-semantics. Thus, also two of the most important non-standard inferences in DLs [Kiisters, 200 1] remain polynomial in this context.

It should be noted that there are indeed applications where the expressive power of the small DL £.C appears to be suf­ ficient. In fact, SNOMED, the Systematized Nomenclature of Medicine [Cote eta/., 1993] uses £.C [Spackman, 2000; 2001].

Subsumption [Baader, 2003a] and the instance problem [Baader, 2003b] are also polynomial w.r.t. descriptive se­ mantics. For the lcs, descriptive semantics is not that well­ behaved: in [Baader, 2003] we have shown that w.r.t. de­ scriptive semantics the lcs need not exist in £.C with cyclic terminologies. In addition, we could only give a sufficient condition for the existence of the lcs. If this condition ap­ plies, then the lcs can be computed in polynomial time. In [Baader, 2003b] similar results are shown for the msc w.r.t. descriptive semantics.

One problem left for future research is the question of how to obtain a decidable characterization of the cases in which the lcs (msc) exists w.r.t. descriptive semantics, and to deter­ mine whether in these cases it can always be computed in polynomial time.