first-order predicate logic (Borgida, 1994), for example.  Moreover, DL systems provide their users with various inference capabilities that allow them to deduce implicit knowledge from the explicitly represented knowledge.  For instance, the subsumption algorithms allow one to determine subconcept-superconcept relationships: C is subsumed by D ( C E D ) if and only if all instances of C are also instances of D, i.e., the first description is always interpreted as a subset of the second description. For example, the concept Car obviously subsumes the concept description Lemon, while ( at-least 10 repairs) is subsumed by ( at-least 8 repairs).

The traditional inference problems for DL systems, such as subsumption, inconsistency detection, membership checking, are by now well-investigated. Algorithms and detailed complexity results for realizing such inferences are available for a variety of DLs of differing expressive power - see, e.g., (Baader & Sattler, 2000) for an overview.

## 1.1 Least Common Subsumer

The least common subsumer (lcs) of concepts is the most specific concept description subsuming the given concepts. Finding the lcs was first introduced as a new inference problem for DLs by Cohen, Borgida, and Hirsh (1992). One motivation for considering the lcs is to use it as an alternative to disjunction. The idea is to replace disjunctions like C 1 ∪ · · · ∪ C n by the lcs of C 1 , . . , C n . Borgida and Etherington (1989) call this operation knowledge-base vivification . Although, in general, the lcs is not equivalent to the corresponding disjunction, it is the best approximation of the disjunctive concept within the available language. Using such an approximation is motivated by the fact that, in many cases, adding disjunction would increase the complexity of reasoning. 1 As proposed by Baader et al. (Baader & Küsters, 1998; Baader, Küsters, & Molitor, 199), the lcs operation can be used to support the "bottom-up" construction of DL knowledge bases, where, roughly speaking, starting from "typical" examples an lcs algorithm is used to compute a concept description that (i) contains all these examples, and (ii) is the most specific description satisfying property (i). Baader and Küsters have presented such an algorithm for cyclic ALN -concept descriptions; ALN is a relatively simple language allowing for concept conjunction, primitive negation, value restrictions, and number restrictions. Also, Baader et al. (1999) have proposed an lcs algorithm for a DL allowing existential restrictions instead of number restrictions.

Originally, the lcs was introduced as an operation in the context of inductive learning from examples (Cohen et al., 1992), and several papers followed up this lead. The DLs considered were mostly sublanguages of CLASSIC which allowed for same-as equalities, i.e., expressions like (same-as (madeBy) (model o madeBy)). Cohen et al. proposed an lcs algorithm for ALN and a language that allows for concept conjunction and same-as, which we will call S . The algorithm for S was extended by Cohen and Hirsh (1994a) to C O R E -
CLASSIC, which additionally allows for value restrictions (see (Cohen & Hirsh, 1994b) for experimental results). Finally, Frazier and Pitt (1996) presented an lcs algorithm for full CLASSIC.