Chinese Journal of Computers   Full Text
Title	Computing Most Specific Concept in Description Logic with n-Ary Existential Quantifier
Authors	JIANG Yun-Cheng1),2) TANG Su-Qin3)
Address	1)(School of Computer Science, South China Normal University, Guangzhou 510631) 2)(State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 100190) 3)(College of Computer Science and Information Engineering, Guangxi Normal University, Guilin, Guangxi 541004)
Year	2009
Issue	No.8(1500—1510)
Abstract &   Background	Abstract Description Logics (DLs) are a logical reconstruction of the frame-based knowledge representation languages, with the aim of providing a simple well-established declarative semantics to capture the meaning of structured representation of knowledge. The fundamentality of non-standard inferences in DLs, especially the current research progress and the existing problems of the MSC (Most Specific Concept) inference in DLs, are analyzed in this paper. Aiming at the insufficiency of the MSC inference in DLs which can not deal with n-ary existential quantifier, the MSC inference for the DL with n-ary existential quantifier εL(n) is studied, where n-ary existential quantifier is a new concept constructor in DLs. A kind of new εL(n)-description graph is presented. The inference algorithm of approximating MSC in εL(n) is presented using description tree and description graph, and the correctness of inference algorithm of approximating MSC is proved using εL(n)-description trees embedding and εL(n)-description tree and description graph homomorphism. As a by-product, the instance reasoning algorithm in εL(n) is presented using εL(n)-description tree and description graph homomorphism, and the correctness of instance reasoning algorithm is also proved. Theoretical foundation for the MSC inference for more expressive DLs with n-ary existential quantifier such as εLU(n) and ALε(n) is provided through the MSC inference algorithm of εL(n). Keywords description logics; n-ary existential quantifier; description tree; description graph; non-standard inferences; MSC Background Description Logics (DLs) are a class of knowledge representation formalisms in the tradition of semantic networks and frames, which can be used to represent the terminological knowledge of an application domain in a structured and formally well-understood way. DL systems provide their users with inference services that deduce implicit knowledge from the explicitly represented knowledge. They are employed in various application domains, such as semantic Web, ontologies, databases, and software engineering. Important characteristics of DLs are high expressivity together with decidability, which guarantee that reasoning algorithms always terminate with correct answers. Standard inference problems such as the subsumption and the instance problem are now well-understood. In applications of DL systems it has turned out that building and maintaining large DL knowledge bases can further facilitated by procedures for other, non-standard inference problem, such as computing the least common subsumer and the most specific concept, and rewriting and matching of concepts. The inference algorithm of approximating MSC in εL(n) is presented, and the correctness of inference algorithm of approximating MSC is proved. The work is supported by the National Natural Science Foundation of China under grant Nos.60663001 and 60573010, the Open Foundation of the State Key Laboratory of Computer Science of Chinese Academy of Sciences under grant No.SYSKF0904, and the Natural Science Foundation of Guangxi Province of China under grant Nos.0640030, 0991100 and 0832103.