计算机科学 ›› 2014, Vol. 41 ›› Issue (12): 206-210.doi: 10.11896/j.issn.1002-137X.2014.12.045
申宇铭,文习明,王驹
SHEN Yu-ming,WEN Xi-ming and WANG Ju
摘要： 表达能力和推理复杂性是一个逻辑的两个重要特征,也是一对相互制约的关系。解释之间的互模拟关系是从语义的角度刻画逻辑表达能力的一个有效途径,其代表性的结果是命题模态逻辑表达能力的刻画定理-van Benthem 刻画定理。文中给出了描述逻辑FL0(含构造子:原子概念、顶概念、概念交、全称量词约束)的模拟关系,建立了FL0中概念和术语公理集的表达能力刻画定理,即一阶逻辑公式与FL0概念和术语公理集等价的充分必要条件。上述结果为寻求表达能力与推理复杂性之间的最佳平衡提供了有效的支持。
| [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! |
|
||
首页