Borgida, A. and Patel-Schneider, P.F. (1994)
"A Semantics and Complete Algorithm for Subsumption in the
CLASSIC Description Logic", Volume 1, pages 277-308.
Abstract: 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.
Click here to return to the JAIR home page.