The Satisfiability Reasoning Of Terminological Cycles In Description Logic εLQ

Description logic is a form of knowledge representation. But in the knowledge representation, We’ll generally assume that, a knowledge system can answer the user’s query within a reasonable period of time. So the people who research on description logic are interested in the reasoning process, that is the process of the decision. Whether the answer is yes or no, it is to end this process. Therefore, the calculation of a description logic reasoning problem complexity is very important. And it is the inference problem about the uncertainty and complexity of description logic is used, depends on the ability of expression. The expression ability of description logic restricts the reasoning in the complexity of the problem. The stronger expression ability of description logic system, it can become more complex of the reasoning problems. It’s necessary to research the expression ability of DL and it’s complexity of reasoning. Cyclic definitions can strengthen the expression of DL, and it Can’t be avoided in many practical application.In addition. Cyclic definitions can also establish a description logic knowledge base for the users. And make the knowledge represented or axiomin in line with people’s intuition. If there is no cyclic definitions. With a non cyclic definitions to describe, will make the knowledge base becomes very complicated, and the Users are difficult to understand.No matter in the theory, or from the practical application, research on the cyclic definition of description logic is of great value.Terminological cycles have been a very hard problem in description logics for a long time, and their essential problems are semantics and reasoning problem, have not been solved reasonably. Current research progress and the existing problems of Terminological cycles in description logics are analyzed in this paper. Based on the work of Baader, a new direction in Terminological cycles is put forward. Aiming at more expressive description logic, the semantics and reasoning mechanism of Terminological cycles. Jiang Yuncheng added the number restriction to description logic εL, and the description logic εLN is presented. The semantics (greatest fixpoint semantics least fixpoint semantics and descriptive semantics) of ELN are given. And according to the Badder, the satisfiability and subsumption reasoning algorithms of Terminological cycles in description logics εLN with respect to fixpoint semantics are presented with simulation between description graphs. It is proved that the satisfiability and subsumption reasoning algorithms of Terminological cycles in εLN are polynomial.The εLN system leads to the thinking, mainly for the εL, the number restriction within a certain range are added to description logic EL, and the description logic εLQ are given. The difference between εLN and εLQ is that, The former is just the number restriction, and the latter is the number restriction within a certain range. To meet the requirement of εLQ, the description graphs(syntax description graph and semantics description graph) are redefined. This paper is mainly to study the satisfiability of ELQ with respect to descriptive semantics.From the Predecessors’work we found the condition GT～GJ in the conclusion of Badder is so abstract and harsh. In this paper we want to give it up and try to find a more simple method from the simulation condition, to study the relationship between these two graphs, that is the matching relationship between the route map. Using the method of path matching to judge the satisfiability. Thus turn the abstract results into concrete, easy to understand for the people.The main work of this paper:(1)Introducing the basic content of the description logic and its research value. tgraphs (syntax description graph and semantics description graph) are redefined.(2)Studying the syntax description graph and semantics description graph of εLQ, use the simulated conditions of Badder to study the relationship between them. By this conclusion, we can verify the new method which we are Introducting, which is the method of path matching.(3)The definition of path matching is given, we can find that if the two graphs are matching, then each node on the semantic description graph is the solution of the concepts which are defined. The purpose of doing so, is to let a person standing in another perspective to look at the solution, that is the definitions of satisfiability, and is more intuitive and easy to understand it. As long as we see the semantic description graph, we can immediately judge whether it has nontrivial solutions.