期刊文献+

基于OBDD的εL^(¬)本体判定算法

Research on OBDD-based decision algorithm for εL^(¬) ontology
下载PDF
导出
摘要 有序二叉决策图(OBDD)是一种新型的数据结构,在较大状态空间规模的模型检测和验证等领域中,已经得到了成功应用,并且在逻辑公式的可满足性判定方面也具有巨大的应用潜力。通过采用OBDD实现了描述逻辑εL(¬)判定算法。以基于OBDD的SHIQ判定算法为基础,针对描述逻辑εL(¬)进行了优化,应用标准化规则取代了FLAT规则,重构了知识库模型,进而将该模型转化为满足3CNF(每个从句含有3个变元的合取形式)约束的布尔函数并利用OBDD进行可满足性判定,并以实例对算法过程进行了演示。 As a state-of-the-art data structure,Ordered Binary Decision Diagram (OBDD) has been successfully applied in large-scale state space of model checking and verification;there are some attractive potentials for it to be applied in the satisfiability-checking of logical formulas.In this paper,an OBDD-based decision algorithm for the description logic εL(¬) is presented.Taking an OBDD-based decision algorithm of the description logic SHIQ as the basis,some strategies for optimizing the algorithm were proposed for εL(¬),and FLAT rules introduced in the former algorithm were replaced by some normalization rules,the model of knowledge bases is reconstructed,so that it could be transformed into Boolean formula in 3CNF(Conjunctive Normal Form with 3 Variables per Clause) forms,then,the satisfiability of Boolean formulas was checked by OBDD,and the algorithm procedure was carried out by an example.
作者 高申 古天龙
出处 《桂林电子科技大学学报》 2010年第2期132-136,共5页 Journal of Guilin University of Electronic Technology
基金 广西自然科学基金(0832006Z)
关键词 描述逻辑 一致性 Tableau-算法 有序二叉决策图 description logic consistency Tableau-algorithm ordered binary decision diagram
  • 引文网络
  • 相关文献

参考文献13

  • 1史忠植,董明楷,蒋运承,张海俊.语义Web的逻辑基础[J].中国科学(E辑),2004,34(10):1123-1138. 被引量:71
  • 2BAADER F, NUTT W, HORROCKS I, et al. Handbook of Description Logic[M]. Cambridge: Cambridge University Press, 2007:47-100.
  • 3DRECHSLER R, SIELING D. Special Section on BDD: Binary Decision Diagrams in Theory and Practice[J]. International Journal on Software Tools for Technology Transfer, 2001, 2 (3):112-136.
  • 4GROOTE J F, TVERETINA O. Binary decision diagrams for first-order predicate Iogic[J]. Journal of Logic and Algebraic Programming, 2003, 57(1-2) : 1-22.
  • 5PAN G Q, SATTLER U, VARDI MY. BDD-based decision procedures for the modal logic K[J].Journal of Applied Non-Classical Logics, 2006, 16(1-2) : 169-208.
  • 6RUDOLPH S, KROTZSCH M, HITZLER P. Description Logic Reasoning with Decision Diagrams-Compiling SHIQ to Disjunctive Datalog[C]. //Proc. of the 7th International Semantic Web Conference, Berlin : Springer, Z008: 435-450.
  • 7梅婧,林作铨.从ALC到SHOQ(D):描述逻辑及其Tableau算法[J].计算机科学,2005,32(3):1-11. 被引量:34
  • 8石莲,孙吉贵.描述逻辑综述[J].计算机科学,2006,33(1):194-197. 被引量:42
  • 9BAADER F, BRANDT S, LUTZ C. Pushing the (L Envelope [C] //Proc. of the 19th International Joint Conference on Artificial Intelligence IJCAI-05, Edinburgh: Morgan-Kaufmann, 2005:364-369.
  • 10SUNTISRIVARAPORN B. Dresden University of Technology Department of Computer Science Institute for Theoretical Computer Science[EB/OL].(2005-09-14 )[2009-12-18]. http ://lat. inf. tu-dresden, de/-meng/toyont.html.

二级参考文献97

  • 1刘亚彬,陈岗.基于描述逻辑的空间推理研究[J].计算机科学,2004,31(8):110-112. 被引量:3
  • 2杨志飞,古天龙,钟艳如.基于OBDD的装配序列自动推理技术研究[J].桂林电子工业学院学报,2005,25(1):43-47. 被引量:2
  • 3Description Logic. home page http://dl.kr.org/.
  • 4Baader F, Nutt W. Basic Description Logics. In: Baader F, McGuinness, Nardi D, et al. eds. The Description Logic Handbook, Chapter2. Cambridge Univ Press,2003.
  • 5De Giacomo G, Lenzerini M. TBox and ABox Reasoning in Expressive Description Logics. KR 1996. 316-327.
  • 6Brachman R J, Levesque H J. The tractability of subsumption in frame-based description languages. In:Proceedings of the 4th National Conference of the American Association for Artificial Intelligence (AAAIr84) ,Austin, TX, 1984. 34-37.
  • 7Baader F, Horrocks I, Sattler U. Description logics as ontology languages for the semantic web. In: Hutter D, Stephan W, eds.Festschrift in honor of Jorg Siekmann, Lecture Notes in Artificial Intelligence. Springer, 2003.
  • 8Brachman R J, Sehmolze J G. An overview of the KL-ONE knowledge representation system. Cognitive Science, 1985,9 (2) : 171-216.
  • 9Mays E,Dionne R,Weida R. K REP system overview. SIGART Bulletin, 1991,2(3).
  • 10Peltason C. The BACK system-an overview. SIGART Bulletin,1991,2(3):114-119.

共引文献131

;
使用帮助 返回顶部