User Tools

Site Tools


Structural Subsumption and Least Common Subsumers in a Description Logic with Existential and Number Restrictions

Ralf Küsters and Ralf Molitor

The least common subsumer (lcs) of a set of concept descriptions is the most specific concept description that subsumes all of the concept descriptions in the given set. By computing the lcs, commonalities between concept descriptions can be made explicit. This is an important inference task useful in several applications, including, for instance, the bottom-up construction of description logic knowledge bases. Previous work on the lcs has concentrated on description logics that either allow for number restrictions or for existential restrictions. Many applications, however, require to combine these constructors. In this work, we present an algorithm for computing the lcs in the description logic ALEN which comprises both constructors---number and existential restrictions---as well as concept conjunction, primitive negation, and value restrictions. To prove correctness of our lcs algorithm, we develop a structural characterization of subsumption in ALEN.