Knowledge compilation in multimodal logic

Abstract

Knowledge representation and knowledge retrieval are the integral parts of artificialintelligence. However, both the representation of knowledge using a logicalformalism and the retrieval of information from the knowledge base, arehighly demanding from computational point of view. The three main approachesproposed to deal with the computational intractability of query answering problemsare restriction on the representation language, approximation of the knowledgebase and knowledge compilation. However, the first approach leads to reducedexpressibility and the second one lacks the equivalence-preserving property.Knowledge compilation divides the task of query answering into two phasesnamely, off-line and on-line phase. In off-line phase, the knowledge base is compiledand its output is then used to answer the actual queries in the on-line phase.In this thesis, we are mainly concerned with the logical compilations in multimodalknowledge bases. We consider computation of theory prime implicates asour off-line phase of knowledge compilation. The algorithm to compute theoryprime implicates in modal logic has been proposed in [10]. In this thesis, we haveextended that algorithm to compute theory prime implicates of a knowledge baseX with respect to another knowledge base ^ts=1 sY in multimodal logic Ks andproved its correctness. We have also extended the query answering algorithmfrom [10] and given the complexity for the same.