Concept Implicate Tree for Description Logics

ABSTRACT

Description logics is a class of knowledge representation languages with high expressive power, and the computational complexities of the queries of these expressive description logics are defined as PSPACE-complete. Moreover, knowledge compilation can be regarded as a new direction of research for dealing with the computational intractable reasoning problems. In fact, knowledge compilation based on description logic has been investigated in recent years. However, when the compiled knowledge base is exponential as compared to original knowledge base, the queries are not. Therefore, we proposed a new knowledge compilation method for description logic to solve the queries in linear time depending on the size of the query. In this paper, we first introduced the concept implicate tree for the ALC concept. Then, we present an algorithm, which can transform an ALC concept into an equivalent concept implicate tree, and proved that each branch of the tree is an implicate of this concept. Finally, we proved that the queries are computable in linear time. The proposed method has an important property that no matter how large the concept implicate tree is, any query can be resolved in linear time depending on the size of the query.

Keywords: