Computing the Least Common Subsumer in Description Logic FLEN

Description logics are formalisms that can represent knowlwdge. Every description logic system contains two parts: One is knowledge base and the other is reference service. Typically, these services include subsumption and instance checking, both of which are called standard inference in description logic. But standard inferences provide little help in constructing and maintaining large DL knowledge bases, so researchers proposed another kind of inferences called nonstandard inference. Nonstandard inference in description logic is a main issue that researchers are focusing on, it mainly includes the most specific concept, the least common subsumer, matching, rewriting and so on. Previous works mainly concerntrates on kinds of description logic systems which dont contain number restriction. Analyzed in this paper is the least common subsumer in description logic FLEN, which contains the number restriction and existential restriction at the same time. It will provide some probabilities to solve the matching problem in description logic with existential restriction and number restriction. Firstly the FLEN-concept description tree and the homomorphisms on description trees are defined and then the subsumption relationship between concepts is characterized by computing the homomorphisms between their description trees. After that the product of two description trees is defined and an algorithm to compute the least common subsumer is proposed by the product of the description trees, and it is pointed out that the size of least common subsumer of two concept descriptions A,B is exponential of the size of A and B.