学位论文 > 优秀研究生学位论文题录展示

基于OBDD的描述逻辑推理算法研究

作　者: 李德波
导　师: 古天龙
学　校: 桂林电子科技大学
专　业: 计算机应用技术
关键词: 描述逻辑有序二叉决策图 OBDD-Tableau TBox 一致性推理系统
分类号: TP18
类　型: 硕士论文
年　份: 2011年
下　载: 18次
引　用: 0次
阅　读: 论文下载

内容摘要

描述逻辑作为一类知识表示的形式化工具，在信息系统、软件工程、自然语言处理等领域已得到了成功应用。特别是随着近年来语义Web的发展，描述逻辑更是扮演着重要的角色，目前已成为语义Web本体语言OWL的逻辑基础。随着基于描述逻辑的本体在e-Science和语义Web中的广泛应用，给描述逻辑将来的推理算法提出了一系列的挑战，特别是在处理大规模问题时表现得尤为突出。Tableau算法是目前描述逻辑中最主要的推理方法，但其并不是在所有情况下都表现最好。因此，有必要针对不同特征的本体寻找相应地更合适的推理算法。有序二叉决策图(OBDD)是一种基于图的数据结构，是布尔函数的一种压缩表示形式，可以对信息进行高效压缩，能有效地处理大规模问题，在模型检测和验证等领域已经得到了成功应用。结合OBDD的数据结构特点和Tableau算法在处理角色名较多时具有的优势，本文做了基于OBDD和Tableau的描述逻辑推理算法相关研究，其主要内容如下：(1)针对OBDD的数据结构特点，给出了基于OBDD的SHOIQ的TBox 一致性判定算法。该算法首先将SHOIQ知识库转化为可满足等价的ALCIb知识库，应用扁平化规则进行预处理；接下来对TBox构造多米诺模型，然后将该模型转化为布尔函数；最后将布尔函数转换为OBDD表示形式，并在其基础上进行可满足性判定。(2)针对基于OBDD的描述逻辑推理算法在处理角色名较多的本体时存在的局限，结合Tableau算法在这方面的优势，给出了基于OBDD-Tableau的ALCIO的TBox一致性判定算法。该算法首先将ALCIO的TBox映射为命题层和模态层，用OBDD来进行命题层的可满足性判定，然后用Tableau进行模态层的可满足性判定，进而来判定ALCIO的TBox一致性。并从理论上证明了算法的可靠性、完备性和可终止性。(3)针对以上两种推理算法，开发了相应的原型推理系统：DLR_SHOIQ和DLR_ALCIO(OBDD-Tableau)。实验结果表明，在对本体规模较大但角色名较少的TBox进行一致性判定时，纯OBDD的推理算法在性能上优于纯Tableau的推理算法；在本体规模较大但角色名较多时，纯OBDD的推理算法效果劣于纯Tableau的推理算法，但OBDD-Tableau推理算法在这种情况下优于纯OBDD的推理算法和纯Tableau的推理算法；在本体规模较小时，由于创建OBDD的时间开销，OBDD-Tableau的推理算法略低于纯Tableau的推理算法。

全文目录

摘要  3-4
Abstract  4-8
第一章绪论  8-13
  1.1 研究背景  8-9
  1.2 问题的提出  9-10
  1.3 本文的工作  10-11
  1.4 论文的组织结构  11-13
第二章相关知识介绍  13-25
  2.1 描述逻辑  13-18
    2.1.1 描述逻辑综述  13-14
    2.1.2 描述逻辑语言表示  14-16
    2.1.3 描述逻辑推理算法  16-18
  2.2 本体推理工具  18-20
  2.3 有序二叉决策图(OBDD)  20-23
    2.3.1 OBDD 的定义及原理  20-21
    2.3.2 OBDD 的相关算法  21-23
    2.3.3 OBDD 的应用  23
  2.4 小结  23-25
第三章基于OBDD 的SHOIQ 判定算法  25-32
  3.1 算法的基本思想  25
  3.2 算法过程  25-31
    3.2.1 预处理  25-27
    3.2.2 构造多米诺模型  27-28
    3.2.3 多米诺模型构造转化为对应OBDD 构造  28-29
    3.2.4 实例分析  29-31
  3.3 小结  31-32
第四章基于OBDD-Tableau 的ΑLCΙО判定算法  32-43
  4.1 算法的基本思想  32-33
  4.2 算法过程  33-42
    4.2.1 知识库的预处理  33
    4.2.2 分层处理  33-35
    4.2.3 构造OBDD-Tableau  35-40
    4.2.4 实例分析  40-42
  4.3 小结  42-43
第五章算法的实现与分析  43-54
  5.1 系统设计与实现  43-47
    5.1.1 实现平台及相关介绍  43-44
    5.1.2 系统框架  44-47
  5.2 系统演示  47-49
    5.2.1 DLR_SHOIQ 推理系统演示  47-48
    5.2.2 DLR_ALCIO_(OBDD-Tab leau)推理系统演示  48-49
  5.3 算法分析  49-53
  5.4 小结  53-54
第六章结束语  54-56
  6.1 主要研究工作  54
  6.2 研究展望  54-56
参考文献  56-60
致谢  60-61
作者在攻读硕士期间主要研究成果  61

基于OBDD的描述逻辑推理算法研究

内容摘要

全文目录

相似论文