高级检索

    描述逻辑系统FLEN中概念的最小公共包含算法研究

    Computing the Least Common Subsumer in Description Logic FLEN

    • 摘要: 描述逻辑中的非标准推理是目前研究者们所关注的焦点问题,它主要包括:最具体概念、最小公共包含、匹配问题及概念的重写等.过去人们主要研究那些不含数量限制的描述逻辑系统,研究的是描述逻辑系统FLEN中的一种重要的非标准推理——概念的最小公共包含,它同时含有数量限制和存在限制,是对前人工作的推广.首先定义了FLEN中概念的描述树及描述树之间的同态关系,给出了概念之间包含关系的推理算法,然后通过两棵概念描述树的笛卡儿积给出了两个概念的最小公共包含推理算法并指出了概念A,B的最小公共包含概念LCS(A,B)的大小size(LCS(A,B))是随着size(A),size(B)呈指数增长的.

       

      Abstract: 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.

       

    /

    返回文章
    返回