主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
王驹,陈光喜,余泉.描述逻辑εL的二阶线性推理机制.软件学报,2017,28(2):216-233
描述逻辑εL的二阶线性推理机制
Second-Order Linear Reasoning Mechanisms for Description Logic εL
投稿时间:2015-08-20  修订日期:2015-10-17
DOI:10.13328/j.cnki.jos.004950
中文关键词:  描述逻辑  保守扩充  模块本体抽取  二阶线性推理机制  DL-Lite家族
英文关键词:description logic  conservative extension  ontology module extracting  second-order linear reasoning mechanism  dl-lite family
基金项目:国家自然科学基金(61463044,61363030);广西自然科学基金(2013GXNSFAA019330);广西可信软件重点实验室开放基金;桂林电子科技大学计算机软件创新团队基金(kx201419);广东省数学教育工程技术研究中心开放基金
作者单位E-mail
王驹 广西可信软件重点实验室(桂林电子科技大学), 广西 桂林 541004  
陈光喜 广西可信软件重点实验室(桂林电子科技大学), 广西 桂林 541004 chgx@guet.edu.cn 
余泉 黔南民族师范学院 数学系, 贵州 都匀 558000  
摘要点击次数: 996
全文下载次数: 808
中文摘要:
      基于描述逻辑的本体的保守扩充理论、模块抽取理论、通用模块构建理论及其相关算法是本体工程中本体构建、本体融合及重构的核心理论与工具.国际上该领域已有Lutz等人使用形式构模方法证明了ALC的保守扩充判定算法复杂度是二阶时间指数的,而轻量级的系统εL的算法复杂度是一阶时间指数的.但当前文献中的形式构模方法思路复杂,难以把握,几乎不能在实用的工程层面上实现.提出一种面向轻量级的描述逻辑系统家族(DL-Lite family)的统一的二阶线性推理机制,并给出该推理机制的完备性证明.该方法直观,思路清晰,从而在工程中容易实现.同时,该方法对εL,FL0,FLε,vL等DL-Lite家族的所有系统都有效.在该线序推理系统下,可以根据“空间换时间”的原则,设计和实现关于保守扩充判定的图推理机制,其复杂性(相对于空间的大小)是多项式的.
英文摘要:
      In the framework of description logics, the theories and their related algorithms of conservative extensions, modularity and module extraction are the core notions and vital tools in engineering semantic Web construction, ontology construction, ontology merging and reuse. Among other important contributions in this area, Lutz, et al. have shown that the conservative extension problem for ALC is decidable but its complexity is 2ExpTime-complete while the complexity of the deciding algorithm for light-weight εL is 1ExpTime-complete. Their deciding algorithms are basically depends on tableau algorithm which is substantially a reasoning mechanism in first-order predicate logic. Although, theoretically speaking, those results and algorithms are significant and valuable, both existing theories and methods appear to be complicated, difficult to understand, and hard to implement by engineers working on the semantic Web and ontology construction. This paper will not discuss and analyze the current theories and their algorithms. Instead, it independently proposes a second-order linear reasoning mechanism for all members of DL-Lite family. A proof of the completeness of the second-order deduction system is provided. The proposed mechanism is intuitive, easy to manipulate, and much easier to implement in the engineering sector. It is uniformly applicable for members of DL-Lite family such as εL, FL0, FLε, and vL. Most of all, this system is consistent with graph deduction that facilitates design and construction of the necessary graphs by using space to exchange with time cost. As a result, the time complexity is reduced significantly such that if the space and deduction graphs are sophisticatedly equipped, the deciding time can be reduced topolynomial.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利