  This paper analyzes the correctness of the subsumption algorithm used in
CLASSIC, a description logic-based knowledge representation system that is
being used in practical applications. In order to deal efficiently with
individuals in CLASSIC descriptions, the developers have had to use an
algorithm that is incomplete with respect to the standard, model-theoretic
semantics for description logics. We provide a variant semantics for
descriptions with respect to which the current implementation is complete, and
which can be independently motivated. The soundness and completeness of the
polynomial-time subsumption algorithm is established using description graphs,
which are an abstracted version of the implementation structures used in
CLASSIC, and are of independent interest.
