A SERIES OF RESULTS FOR THE COMPLEXITY OF REASONING IN SOME DESCRIPTION LOGICS LANGUAGES TOGETHER WITH THEIR PROOF
A SERIES OF RESULTS FOR THE COMPLEXITY OF REASONING IN SOME DESCRIPTION LOGICS LANGUAGES TOGETHER WITH THEIR PROOF

Summary/Abstract: This article represents the next step of our research in Description Logics domain which we began some time ago. Here we will continue the study that we left in the last paper, that about inference and reasoning problems and services from logical knowledge bases, and this time tackle the complexity of reasoning for these problems as they had been found in some of the most important Description Logics (DL) languages. We will interpret those limits as coming from various sources of complexities which we will isolate particularly. Will be analyzed reasoning in respect with both simple concept descriptions and a TBox, and will be discussed the complexities of instance checking in the ABox. Will be shown the inner workings of a Tableaux algorithm for deciding the satisfiability of a concrete DL language relying on transformation rules to expand concept descriptions, it will be analyzed the complexity of its computations, then subsequently propose a solution for it in order to reduce this complexity from exponential time to polynomial. Next this algorithm will be applied also for other, more complex, reasoning tasks, like consistency if an ABox, and again make a series of discussions about the complexity of computations. In the concluding section we will present a list with results of complexity in some of the most important DL languages, as they were found by the domain scholars, and we will interpret, analyze and compare these results for the respective languages with regard to their capabilities that they provide, mostly in terms of constructors for concepts and roles by means of which can be captured the information from the real world.

• Details
• Contents