Computing Most Specific Concept in Description Logic with Transitive Roles and Existential Restrictions

Description logic is a logical reconstruction of the frame-based knowledge representation languages, with the aim of providing simple well-established declarative semantics to capture the meaning of structured representation of knowledge. The fundamentality of non-standard inferences in description logic, especially the current research progress and existing problems of the MSC (most specific concept) inference in description logic, are analyzed in this paper. Aiming at the insufficiency of the MSC inference in description logics which can not deal with transitive roles and existential restrictions, the MSC inference for description logic with transitive roles and existential restrictions εL\++ is studied. A kind of new εL\++-description graph is presented. The inference algorithm of approximating MSC in description logic with transitive roles and existential restrictions εL\++ is presented using description tree and description graph, and its correctness is proved using εL\++-description trees homomorphism and description graph homomorphism. As a by-product, the instance reasoning algorithm in description logic with transitive roles and existential restrictions εL\++ is presented using εL\++-description tree and description graph homomorphism, and its correctness is also proved. Theoretical foundation for the MSC inference for more expressive description logics such as ALε is provided through the MSC inference algorithm of εL\++.