Description logics are a class of knowledge representation languages with high expressive power, and the com- putational complexities of the queries of these expressive description logics are PSPACE-complete. Moreover, knowledge compilation can be regarded as a new direction of research for dealing with the computational intractable reasoning prob- lems. In fact, knowledge compilation based on description logic has been investigated in recent years. However, when the compiled knowledge base is exponential in the size of original knowledge base, the queries are not fast enough. Therefore, we propose a new knowledge compilation method for description logic so that the queries can be done in linear time in the size of the query. In this paper, we first introduce concept implicate tree for ALC concept. Then, we present an algorithm, which can transform an ALC concept into an equivalent concept implicate tree, and prove that each branch of the tree is an implicate of this concept. Finally, we prove that the queries are computable in linear time. Our method has an im- portant property that no matter how large the concept implicate tree is, any query can be done in linear time in the size of the query.
Paper
Full text
Concept Implicate Tree for Description Logics
Semantic Scholar · Computer Science · 2015
Abstract
Description logics are a class of knowledge representation languages with high expressive power, and the com- putational complexities of the queries of these expressive description logics are PSPACE-complete. Moreover, knowledge compilation can be regarded as a new direction of research for dealing with the computational intractable reasoning prob- lems. In fact, knowledge compilation based on description logic has been investigated in recent years. However, when the compiled knowledge base is exponential in the size of original knowledge base, the queries are not fast enough. Therefore, we propose a new knowledge compilation method for description logic so that the queries can be done in linear time in the size of the query. In this paper, we first introduce concept implicate tree for ALC concept. Then, we present an algorithm, which can transform an ALC concept into an equivalent concept implicate tree, and prove that each branch of the tree is an implicate of this concept. Finally, we prove that the queries are computable in linear time. Our method has an im- portant property that no matter how large the concept implicate tree is, any query can be done in linear time in the size of the query.