首页    期刊浏览 2024年10月04日 星期五
登录注册

文章基本信息

  • 标题:Concept Implicate Tree for Description Logics
  • 本地全文:下载
  • 作者:Tingting Zou ; Ansheng Deng
  • 期刊名称:The Open Cybernetics & Systemics Journal
  • 电子版ISSN:1874-110X
  • 出版年度:2015
  • 卷号:9
  • 期号:1
  • 页码:2545-2553
  • DOI:10.2174/1874110X01509012545
  • 出版社:Bentham Science Publishers Ltd
  • 摘要:

    Description logics are a class of knowledge representation languages with high expressive power, and the computational complexities of the queries of these expressive description logics are PSPACE-complete. Moreover, knowledge compilation can be regarded as a new direction of research for dealing with the computational intractable reasoning problems. In fact, knowledge compilation based on description logic has been investigated in recent years. However, when the compiled knowledge base is exponential in the size of original knowledge base, the queries are not fast enough. Therefore, we propose a new knowledge compilation method for description logic so that the queries can be done in linear time in the size of the query. In this paper, we first introduce concept implicate tree for ALC concept. Then, we present an algorithm, which can transform an ALC concept into an equivalent concept implicate tree, and prove that each branch of the tree is an implicate of this concept. Finally, we prove that the queries are computable in linear time. Our method has an important property that no matter how large the concept implicate tree is, any query can be done in linear time in the size of the query.

国家哲学社会科学文献中心版权所有