|
|
|
| Non-Standard Inferences in Description Logics |
| TANG Su-Qin1,2,CAI Zi-Xing1 ,WANG Ju2,JIANG Yun-Cheng2 |
1.School of Information Science and Engineering,Central South University,Changsha 410083
2.School of Computer Science and Information Engineering,Guangxi Normal University,Guilin 541004 |
|
|
|
|
Abstract Description Logics belong to a kind of formalization method for representing knowledge in the knowledge engineering. Solving the standard and non-standard inferences has become an important research area of description logics in recent years. The significance and research advance on standard and non-standard inferences in description logics are summarized in this paper. The definition of Least Common Subsumer(LCS), Most Specific Concept(MSC), Rewriting, Matching, Debugging and Conservative Extensions, and the actualizing technologies of these Reasoning are given. Problems of the LCS, MSC, Matching, non-standard reasoning of hybrid terminological cycles in description logics and their research advance are discussed in particular. Finally, some prospects of non-standard inference in description logic are discussed.
|
|
Received: 09 June 2009
|
|
|
|
|
|
[1] Baader F, Calvanese D, McGuinness D, et al. The Description Logic Handbook: Theory, Implementation and Applications. Cambridge, UK: Cambridge University Press, 2003
[2] Shi Zhongzhi, Dong Minkai, Jiang Yuncheng, et al. A Logical Foundation for Semantic Web. Science in China: Series E, 2004, 34(10): 1123-1138 (in Chinese)
(史忠植,董明楷,蒋运承,等.语义Web的逻辑基础.中国科学E辑, 2004, 34(10): 1123-1138)
[3] Baader F, Horrocks I, Sattler U. Description Logics // Staab S, Studer R, eds. Handbook on Ontologies: International Handbooks on Information Systems. London, UK: Springer, 2004: 3-28
[4] Grau B C, Horrocks I, Kazakov Y, et al. Modular Reuse of Ontologies: Theory and Practice. Journal of Artificial Intelligence Research, 2008, 31(1): 273-318
[5] Horrocks I. DAML+OIL: A Description Logic for the Semantic Web. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, 2002, 25(1): 4-9
[6] Jiang Yuncheng, Shi Zhongzhi, Tang Yong, et al. Fuzzy Description Logic for Semantics Representation of the Semantic Web. Journal of Software,2007, 18(6): 1257-1269 (in Chinese)
(蒋运承,史忠植,汤 庸,等.面向语义Web语义表示的模糊描述逻辑.软件学报, 2007, 18(6): 1257-1269)
[7] Jiang Yuncheng, Tang Yong, Wang Ju. Fuzzy ER Modeling with Description Logics. Journal of Software, 2006, 17(1): 20-30 (in Chinese)
(蒋运承,汤 庸,王驹.基于描述逻辑的模糊ER模型.软件学报, 2006, 17(1): 20-30)
[8] Jiang Yuncheng, Tang Yong, Wang Ju, et al. Description-Logic-Based Temporal ER Model with Attribute Dependencies. Journal of Computer Research and Developmen, 2007, 44(10): 1765-1773 (in Chinese)
(蒋运承,汤 庸,王 驹,等.基于描述逻辑的带属性依赖时序ER模型.计算机研究与发展, 2007, 44(10): 1765-1773)
[9] Berardi D, Calvanese D, Giacomo G D. Reasoning on UML Class Diagrams. Artificial Intelligence, 2005, 168(1/2): 70-118
[10] Artale A. Reasoning on Temporal Class Diagrams: Undecidability Results. Annals of Mathematics and Artificial Intelligence, 2006, 46(3): 265-288
[11] Baader F, Kusters R. Non-Standard Inferences in Description Logics: The Story so Far // Gabbay D M, Goncharov S S, Zakharyaschev M, eds. Mathematical Problems from Applied Logic I. New York, USA: Springer, 2006, Ⅳ: 1-75
[12] Brandt S. Standard and Non-Standard Reasoning in Description Logics. Ph.D Dissertation. Dresden, Germany: TU Dresden. Institute for Theoretical Computer Science, 2006
[13] Sirin E, Parsia B, Grau B C, et al. Pellet: A Practical OWL-DL Reasoner. Journal of Web Semantics: Science, Services and Agents on the World Wide Web, 2007, 5(2): 51-53
[14] Tsarkov D, Horrocks I. FaCT++ Description Logic Reasoner: System Description // Proc of the 3rd International Joint Conference on Automated Reasoning. Seattle, USA, 2006: 292-297
[15] Haarslev V, Moller R. RACER System Description // Proc of the 1st International Joint Conference on Automated Reasoning. Seattle, USA, 2001: 701-706
[16] Baader F, Brandt S, Kusters R. Matching under Side Conditions in Description Logics // Proc of the 17th International Joint Conference on Artificial Intelligence. Seattle, USA, 2001: 213-218
[17] Küsters R, Molitor R. Computing Least Common Subsumers in ALεN // Proc of the 17th International Joint Conference on Artificial Intelligence. Seattle, USA, 2001: 219-224
[18] Baader F, Sertkaya B, Turhan A Y. Computing the Least Common Subsumer w.r.t. a Background Terminology. Journal of Applied Logic, 2007, 5(3): 392-420
[19] Baader F. Least Common Subsumers and Most Specific Concepts in a Description Logic with Existential Restrictions and Terminological Cycles // Proc of the 18th International Joint Conference on Artificial Intelligence. Acapulco, Mexico, 2003: 319-324
[20] Jiang Yuncheng, Wang Ju, Zhou Shengming, et al. LCS and MSC Reasoning of Hybrid Terminological Cycles in Description Logic εL. Journal of Software, 2008, 19(10): 2483-2497 (in Chinese)
(蒋运承,王 驹,周生明,等.描述逻辑εL混合循环术语集的LCS和MSC推理.软件学报, 2008, 19(10): 2483-2497)
[21] Jiang Yuncheng, Wang Ju, Deng Peimin, et al. Semantics and Reasoning of Terminological Cycles in Description Logic FL. Chinese Journal of Computers, 2008, 31(2): 185-195 (in Chinese)
(蒋运承,王 驹,邓培民,等.描述逻辑FL循环术语集的语义及推理.计算机学报, 2008, 31(2): 185-195)
[22] Baader F. Using Automata Theory for Characterizing the Semantics of Terminological Cycles. Annals of Mathematics and Artificial Intelligence, 1996, 18(2): 175-219
[23] Kusters R. Characterizing the Semantics of Terminological Cycles in ALN Using Finite Automata // Proc of the 6th International Conference on Principles of Knowledge Representation and Reasoning. Trento, Italy, 1998: 499-511
[24] Nebel B. Terminological Cycles: Semantics and Computational Properties // Sowa J F, ed. Principles of Semantic Networks. Los Altos, USA: Morgan Kaufmann Publishers, 1991: 331-362
[25] Francesco D. Complexity of Reasoning // Beader F, McGuinness D L, Nardi D, eds. The Description Logic Handbook: Theory, Implementation and Applications. Cambridge, UK: Cambridge University Press, 2003: 96-136
[26] Nebel B. Terminological Reasoning Is Inherently Intractable. Artificial Intelligence, 1990, 43(2): 235-249
[27] Lutz C. Complexity of Terminological Reasoning Revisited // Proc of the 6th International Conference on Logic for Programming and Automated Reasoning. Tbilisi, Georgia, 1999: 181-200
[28] Kazakov Y, de Nivelle H. Subsumption of Concepts in FL0 for (Cyclic) Terminologies with Respect to Descriptive Semantics is PSPACE-Complete // Proc of the Description Logic Workshop. Rome, Italy, 2003: 56-64
[29] Horrocks I, Kutz O, Sattler U. The Even More Irresistible SROIQ // Proc of the 10th International Conference of Knowledge Representation and Reasoning. Lake District, UK, 2006: 452-457
[30] Schlobach S, Cornet R. Non-Standard Reasoning Services for the Debugging of Description Logic Terminologies // Proc of the 18th International Joint Conference on Artificial Intelligence. Acapulco, Mexico, 2003: 355-360
[31]Lutz C, Walther D, Wolter F. Conservative Extensions in Expressive Description Logics // Proc of the 20th International Joint Conference on Artificial Intelligence. Hyderabad, India, 2007: 453-458
[32] Baader F, Kusters R, Molitor R. Computing Least Common Subsumers in Description Logics with Existential Restrictions // Proc of the 16th International Joint Conference on Artificial Intelligence. Stocknolm, Sweden, 1999: 96-103
[33] Baader F. Computing the Least Common Subsumer in the Description Logic εL w.r.t. Terminological Cycles with Descriptive Semantics // Proc of the 11th International Conference on Conceptual Structures. Dresden, Germany, 2003: 117-130
[34] Baader F, Kusters R. Computing the Least Common Subsumer and the Most Specific Concept in the Presence of Cyclic ALN-Concept Descriptions // Proc of the 22nd Annual German Conference on Artificial Intelligence. Bremen, Germany, 1998: 129-140
[35] Baader F, Turhan A Y. On the Problem of Computing Small Representations of Least Common Subsumers // Proc of the 25th Annual German Conference on Artificial Intelligence. Aachen, Germany, 2002: 99-113
[36] Calvanese D, Lenzerini M, Nardi D. Unifying Class-Based Representation Formalisms. Journal of Artificial Intelligence Research, 1999, 11: 199-240
[37] Kusters R, Borgida A. Whats in an Attribute? Consequences for the Least Common Subsumer. Journal of Artificial Intelligence Research, 2001, 14(1): 167-203
[38] Nebel B. Reasoning and Revision in Hybrid Representation Systems. New York, USA: Springer-Verlag, 1990
[39]Baader F. The Instance Problem and the Most Specific Concept in the Description Logic εL w.r.t.Terminological Cycles with Descriptive Semantics // Proc of the 26th Annual German Conference on Artificial Intelligence. Hamburg, Germany, 2003: 64-78
[40] Baader F. A Graph-Theoretic Generalization of the Least Common Subsumer and the Most Specific Concept in the Description Logic εL // Proc of the 30th International Workshop on Graph-Theoretic Concepts in Computer Science. Zarós, Greece, 2004: 177-188
[41] Küster R, Molitor R. Approximating Most Specific Concepts in Description Logics with Existential Restrictions. AI Communications, 2001, 15(1): 47-59
[42] Kusters R, Molitor R. Computing Most Specific Concepts in Description Logics with Existential Restrictions. Technical Report, 00-05, Dresden, Germany: Dresden University of Technology, 2000: 1-26
[43] Baader F, Kusters R, Borgida A, et al. Matching in Description Logics. Journal of Logic and Computation, 1999, 9(3): 411-447
[44] Baader F, Kusters R. Matching in Description Logics with Existential Restrictions // Proc of the 7th International Conference on Knowledge Representation and Reasoning. Trento, Italy, 2000: 261-272
[45] Baader F, Narendran P. Unification of Concepts Terms in Description Logics. Journal of Symbolic Computation, 2001, 31(3): 277-305
[46] Giacomo G D, Lenzerini M. A Uniform Framework for Concept Definitions in Description Logics. Journal of Artificial Intelligence Research, 1997, 6(1): 87-110
[47] Buchheit M, Donini F M, Nutt W, et al. A Refined Architecture for Terminological Systems: Terminology=Schema+Views. Artificial Intelligence, 1998, 99(2): 209-260
[48] Nebel B. Terminological Cycles: Semantics and Computational Properties // Sowa J, ed. Principles of Semantic Networks. San Francisco, USA: Morgan Kaufmann, 1991: 331-362
[49] Nebel B. Reasoning and Revision in Hybrid Representation Systems. Berlin, Germany: Springer-Verlag, 1990: 125-156
[50] Baader F. Terminological Cycles in a Description Logic with Existential Restrictions // Proc of the 18th International Joint Conference on Artificial Intelligence. Acapulco, Mexico, 2003: 325-330
[51] Wang Ju, Jiang Yuncheng, Shen Yuming. Satisfiability and Reasoning Mechanism of Terminological Cycles in Description Logic vL. Science in China: Series F, 2009, 39(2): 205-211 (in Chinese)
(王 驹,蒋运承,申宇铭.描述逻辑系统vL循环术语集的可满足性及推理机制.中国科学F辑, 2009, 39(2): 205-211)
[52] Brandt S, Model J. Subsumption in εL w.r.t.Hybrid TBoxes // Proc of the 28th Annual German Conference on AI. Koblenz, Germany, 2005: 34-48
[53] Jiang Yuncheng, Wang Ju, Zhou Shengmin, et al. Hybrid Reasoning of Terminological Cycle in Description Logic εL. Journal of Computer Research and Development, 2009, 46(1): 15-22 (in Chinese)
(蒋运承,王 驹,周生明,等.描述逻辑εL循环术语集的混合推理.计算机研究与发展, 2009, 46 (1): 15-22)
[54] Jiang Yuncheng, Wang Ju, Shi Zhongzhi, et al. Fixpoint Semantics and Reasoning of Terminological Cycles in Description Logic εLN. Journal of Software, 2009, 20(3): 477-490 (in Chinese)
(蒋运承,王 驹,史忠植,等.描述逻辑εLN 循环术语集的不动点语义及推理.软件学报, 2009, 20(3): 477-490)
[55] Jiang Yuncheng, Wang Ju, Tang Yong, et al. Semantics and Reasoning of Description Logic μALCQO. Journal of Software, 2009, 20(3): 491-504 (in Chinese)
(蒋运承,王 驹,汤 庸,等.描述逻辑μALCQO的语义及推理.软件学报, 2009, 20(3): 491-504) |
|
|
|
2010, Vol. 23 
