Semantics and Reasoning of Hybrid Terminological Cycles in Description Logic εL with RVM
JIANG YunCheng1,2, WANG Ju1, ZHOU ShengMing1, TANG Yong2
1.College of Computer Science and Information Engineering, Guangxi Normal University,Guilin 5410042. Department of Computer Science, Sun Yatsen University, Guangzhou 510275
Abstract：The current research progresses and problems of terminological cycles in description logics are analyzed in this paper. Based on the research of Baader F and Brandt S, the semantics and reasoning of hybrid terminological cycles in description logic εL with RVM is further studied. The syntax and semantics of hybrid terminological cycles in description logic εL with RVM are given. Aiming at the requirement of subsumption reasoning of hybrid terminological cycles in description logic εL with RVM, TBoxcompletion is presented and the description graph is redefined. The subsumption reasoning algorithms of hybrid terminological cycles in description logic εL with RVM w.r.t. greatest fixpoint semantics and descriptive semantics are presented using TBoxcompletion and description graph. The correctness of reasoning algorithms has been proved. And it is also proved that the subsumption reasoning w.r.t. greatest fixpoint semantics and descriptive semantics can be computed in polynomial time.
[1] Giacomo G, Lenzerini M. A Uniform Framework for Concept Definitions in Description Logics. Journal of Artificial Intelligence Research, 1997, 6(1): 87110 [2] Buchheit M, Donini F M, Nutt W, et al. A Refined Architecture for Terminological Systems: Terminology = Schema + Views. Artificial Intelligence, 1998, 99(2): 209260 [3] Baader F. Using Automata Theory for Characterizing the Semantics of Terminological Cycles. Annals of Mathematics and Artificial Intelligence, 1996, 18(2/3/4): 175219 [4] Nebel B. Terminological Cycles: Semantics and Computational Properties // Sowa J F, ed. Principles of Semantic Networks. San Mateo, USA: Morgan Kaufmann Publishers, 1991: 331361 [5] Nebel B. Reasoning and Revision in Hybrid Representation Systems. Berlin, Germany: SpringerVerlag, 1990 [6] Baader F. Terminological Cycles in a Description Logic with Existential Restrictions // Proc of the 18th International Joint Conference on Artificial Intelligence. Acapulco, Mexico, 2003: 325330 [7] SchmidtSchaubβ M. Subsumption in KLONE is Undecidable // Proc of the 1st International Conference on Principles of Knowledge Representation and Reasoning. San Francisco, USA, 1989: 301311 [8] Horrocks I, Sattler U. Decidability of SHIQ with Complex Role Inclusion Axioms. Artificial Intelligence, 2004, 160(1/2): 79104 [9] Baader F. Restricted RoleValueMaps in a Description Logic with Existential Restrictions and Terminological Cycles // Proc of the International Workshop on Description Logics. Aachen, Germany, 2003: 113122 [10] Brandt S, Model J. Subsumption in εL w.r.t. Hybrid TBoxes // Proc of the 28th Annual German Conference on Artificial Intelligence. Koblenz, Germany, 2005: 3448 [11] 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: 319324 [12] Tarski A. A Lattice Theoretical Fixpoint Theorem and Its Applications. Pacific Journal of Mathematics, 1955, 5(2): 285309 [13] Henzinger M R, Henzinger T A, Kopke P W. Computing Simulations on Finite and Infinite Graphs // Proc of the 36th Annual Symposium on Foundations of Computer Science. Milwaukee, USA, 1995: 453462
2008, Vol. 21 
