Computer Science ›› 2014, Vol. 41 ›› Issue (12): 206-210.doi: 10.11896/j.issn.1002-137X.2014.12.045

Previous Articles     Next Articles

Characterizing Expressive Power for Concept Descriptions and Terminological Axioms Boxes in Description Logic FL0

SHEN Yu-ming,WEN Xi-ming and WANG Ju   

  • Online:2018-11-14 Published:2018-11-14

Abstract: The two most important properties of a logic are its expressive power and the complexity of the reasoning problems,which are also an opposing relation in the logic.Bisimulations between interpretations are the effective way to characterize the expressive power,and a classical result is the van Benthem characterizing theorem,which gives an exact condition that a first-order formula with one free variable is equivalent to a modal logic formula.In this paper,a simulation for FL0(including atomic concept,top concept,conjunction concept and universal quantification) was given.Based on the simulation,the characterizing theorems of expressive power for concept descriptions and TBoxes are sufficient and necessary conditions that a first-order formula is equivalent to a concept description or a TBox is set up.The above results provide effective supports for the tradeoff between the expressive power and the complexity of reasoning problems.

Key words: Description logic,Concept description,Tterminological axioms box,eExpressive power

[1] Baader F,Nutt W.Basic description logics[M]∥Baader F,Calvanese D,McGuinness D,et al.,eds.The Description Logic Handbook:Theory,Implementation,and Applications.Cambridge:Cambridge University Press,2003
[2] Horrocks I,Patel-Schneider P F,Harmelen F V.From SHIQand RDF to OWL:The making of a Web ontology language[J].Journal of Web Semantics,2003,1(1):7-26
[3] Baader F,Sattler U.An overview of tableau algorithms for description logics[J].Studia Logica,2001,69(1):5-40
[4] Baader F,Brandt S,Lutz C.Terminological cycles in a description logic with existential restrictions[C]∥Gottlob G,Walsh T,eds.Proc.of the 18th International Joint Conference on Artificial Intelligence(IJCAI 2003).San Francisco:Morgan Kaufmann Publishers,2003:325-330
[5] 王驹,蒋运承,申宇铭.描述逻辑系统FL-循环术语集的可满足性及推理机制[J].中国科学(F辑),2009,39(2):205-211
[6] 常亮,史忠植,陈立民,等.一类扩展的动态描述逻辑[J].软件学报,2010,21(1):1-13
[7] 蒋运承,王驹,邓培明,等.描述逻辑FL-循环术语集的语义及推理[J].计算机学报,2008,31(2):185-195
[8] 史忠植,常亮.基于动态描述逻辑的语义Web服务推理[J].计算机学报,2008,31(9):1599-1611
[9] Ohlbach H,Nonnengart A,de Rijke M,et al.Encoding two-valued non-classical logics inclassical logic[M]∥Robinson A,Voronkov A,eds.Handbook of Automated Reasoning.Netherlands:Elsevier Press,2001:1403-1486
[10] van Benthem J.Correspondence theory[M]∥Gabbay D,Guenthner F.eds,Handbook of Philosophical Logic,Vol.2:Extensions of Classical Logic.Dodrecht,Netherlands:D.Reidel Publishing Company,1983:167-247
[11] Goranko V,Otto M.Model theory of modal logic[M]∥Blackburn P,van Benthem J,Wolter F.,eds.Handbook of Modal Logic.Netherlands:Elsevier Press,2007:246-329
[12] Baader F.A Formal definition for the expressive power of terminological knowledge representation languages[J].Journal of Logic and Computation,1996,6(1):33-54
[13] Borgida A.On the relative expressiveness of description logics and predicate logics[J].Artificial Intelligence,1996,82(1/2):353-367
[14] Kurtonina N,de Rijke M.Expressive of concept expression in first-order description logics[J].Artificial Intelligence,1999,107(2):303-333
[15] Lutz C,Piro R,Wolter F.Description Logic TBoxes:Model-Theoretic Characterizations and Rewritability[C]∥Proceeding of the Twenty-Second International Joint Conference on Artificial Intelligence(IJCAI 2011).Barcelona,Catalonia,Spain:AAAI Press,2011:983-988
[16] 申宇铭,王驹,唐素勤.描述逻辑 ALC概念及术语公理集的表达能力刻画[J].软件学报,2014,25(8):1794-1805
[17] Baader F,Kusters R,Molitor R.Rewriting concepts using terminologies[C]∥Proceeding of the 7th International Conference on Principles of Knowledge Representation and Reasoning (KR2000).Brechenrideg,Colorado USA:Morgan Kaufmann,2000:297-308
[18] Brandt S,Kusters R,Turhan A-Ya.Approximation and differ-ence in description logic[C]∥Proceeding of the 7th International Conference on Principles of Knowledge Representation and Reasoning (KR2002).San Francisco,CA,Morgan Kaufmann,2002:203-214
[19] Lutz C,Wolter F.Deciding inseparability and conservative ex-tensions in the description logic εL[J].Journal of Symbolic Computation,2010,45(2):194-228
[20] Kontchakov R,Wotler F,Zakharyaschev M.Logic-based ontology comparison and module extraction,with an application to DL-Lite[J].Artificial Intelligence,2010,174(15):1093-1141
[21] Ebbinghaus H D,Flum J,Thomas W.Mathematical Logic[M].Second Edition,Springer,1994

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!