ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2018, Vol. 55 ›› Issue (12): 2715-2724.doi: 10.7544/issn1000-1239.2018.20170766

• 人工智能 • 上一篇    下一篇

面向异构语义映射的D3L转换算法及其性质研究

赵晓非1,2,3,史忠植2,冯志勇3   

  1. 1(天津工业大学计算机科学与软件学院 天津 300387);2(中国科学院计算技术研究所智能信息处理重点实验室 北京 100190);3(天津大学计算机科学与技术学院 天津 300072) (zhaoxiaofei1978@hotmail.com)
  • 出版日期: 2018-12-01
  • 基金资助: 
    国家“九七三”重点基础研究发展计划基金项目(2013CB329502);国家自然科学基金项目(61035003);江苏省计算机信息处理技术重点实验室开放基金项目(KJS1737);中国博士后科学基金项目(2018M631740)

Transformation Algorithm and Its Properties for D3L with Heterogeneous Semantic Mapping

Zhao Xiaofei1,2,3, Shi Zhongzhi2, Feng Zhiyong3   

  1. 1(School of Computer Science and Software Engineering, Tianjin Polytechnic University, Tianjin 300387);2(Key Laboratory of Intelligent Information Processing, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190);3(School of Computer Science and Technology, Tianjin University, Tianjin 300072)
  • Online: 2018-12-01

摘要: 桥规则为分布式动态描述逻辑(distributed dynamic description logics, D3L)提供了描述语义映射和知识传播的重要机制.现有的研究仅针对包含原子元素的同构桥规则.将研究扩展到了被包含端存在复合元素的异构桥规则的D3L推理问题.定义了分布式知识库的正则性.通过对桥规则进行形式变换并针对不同情形转换为已有的语言机制,提出了将动态描述逻辑DSROIQ作为局部本体语言的D3L知识库转换为单一DSROIQ知识库的算法,接着研究了该转换的性质,证明了该算法可以在多项式时间内终止、算法的目标知识库与原始知识库在可满足性上是等价的,进而证明了在上述桥规则存在的情况下正则D3L知识库的集中式推理具有与单一DSROIQ知识库推理相同的最坏时间复杂度.该算法使得D3L推理可以获得与现有的分布式推理方法相同的最坏时间复杂度并且解决了后者难以处理异构复合桥规则的问题.

关键词: 分布式动态描述逻辑, 异构桥规则, 正则性, 集中式推理, 计算复杂度

Abstract: Bridge rules provide an important mechanism describing semantic mapping and propagating knowledge for D3L (distributed dynamic description logics). The current research focuses on the homogeneous bridge rules which only contain atomic elements. In this paper, the research is extended to the D3L reasoning problem with the heterogeneous bridge rules which contain composite elements in the contained end. The regularity of distributed knowledge base is defined. Through the alternation of the bridge rules and transforming different forms into existing language mechanism, we present a algorithm which can convert the D3L knowledge base with dynamic description logic DSROIQ as local ontology language into a single DSROIQ knowledge base. Then we study the properties of the algorithm. We prove that the algorithm will terminate in polynomial time and the satisfiability of the target knowledge base is equivalent to the satisfiability of the original knowledge base. Thus, we prove that the worst-case time complexity of the centralized reasoning on regular D3L knowledge base with such bridge rules is the same as that on single DSROIQ knowledge base. The method proposed in this paper makes the reasoning for D3L to obtain the same worst-case time complexity as the existing distributed reasoning methods and solves the problem that the latter can not handle heterogeneous composite bridge rules.

Key words: distributed dynamic description logics (D3L), heterogeneous bridge rules, regularity, centralized reasoning, computation complexity

中图分类号: