| ¡¡ | Chinese Journal of Computers Full Text |
| Title | Semantics and Reasoning of Terminological Cycles in Description Logic FL- |
| Authors | JIANG Yun-Cheng1),2) WANG Ju1) DENG Pei-Min3) TANG Yong2) |
| Address | 1)(College of Computer Science and Information Engineering, Guangxi Normal University, Guilin, Guangxi 541004) 2)(Department of Computer Science, Sun Yat-Sen University, Guangzhou 510275) 3)(College of Mathematics, Guangxi Normal University, Guilin, Guangxi541004) |
| Year | 2008 |
| Issue | No.2(185¡ª195) |
| Abstract & Background | Abstract Terminological cycles have been a difficult spot in the study of description logics for quite a few years. The basic problems, such as their semantics and reasoning mechanisms, have not been reasonably well settled. The current research progresses and the existing problems of terminological cycles in description logics are analyzed in this paper. Based on the work of Baader F, the semantics and reasoning of terminological cycles in description logic FL- are further studied. The syntax, semantics, and construction method of fixpoint models of terminololgical cycles in FL- are given. Aiming at the requirement of terminololgical cycles in FL-, a kind of new finite automata is presented, and the satisfiability and subsumption reasoning algorithms of terminological cycles in FL- w.r.t. fixpoint semantics and descriptive semantics are presented using finite automata. The correctness of reasoning algorithms is proved, and the complexity property of reasoning algorithms is given. keywords description logic; terminological cycles; fixpoint semantics; descriptive semantics; finite automata background Description logics are a logical reconstruction of the frame-based knowledge representation languages, with the aim of providing a simple well-established declarative semantics to capture the meaning of structured representation of knowledge. Terminological cycles (or cyclic definitions) have been a difficult spot in the study of description logics for quite a few years. The basic problems, such as their semantics and reasoning mechanisms, have not been reasonably well settled. However, terminological cycles may greatly extend the expressive capability of the language. In some applications, terminological cycles are indispensable. Also, by using terminological cycles, one can establish a description logic knowledge base more conveniently because it would give the people an intuitive understanding of the axioms, sentences of the knowledge base. If we do not accept terminological cycles in the knowledge base, when a cyclic concept occurs in the application, it would make the system specification overly complex and hard to understand by a user. For these reasons, it is significant to study the semantics and the algorithmic nature of terminological cycles. Based on the work of Baader F, the semantics and reasoning of terminological cycles in description logic FL- are further studied in this paper. The syntax, semantics, and construction method of fixpoint models of terminololgical cycles in FL- are given. Aiming at the requirement of terminololgical cycles in FL-, a kind of new finite automata is presented, and the satisfiability and subsumption reasoning algorithms of terminological cycles in FL- w.r.t. fixpoint semantics and descriptive semantics are presented using finite automata. Theoretical foundation for the application of terminological cycles in description logics is provided. The work is supported by the National Natural Science Foundation of China under grant Nos.60663001, 60673135, 60373081, and 60573010, the Natural Science Key Foundation of Guangdong Province of China under grant No.04105503, and the Youth Science Foundation of Guangxi Province of China under grant No.0640030. |