An Algorithm for Computing Prime Implicates in Modal Logic Using Resolution

Abstract

In this paper we have proposed an algorithm for computing prime implicates of a modal formula in $\mathbf{K}$ using resolution method suggested in \cite{Enjalbert}. The algorithm suggested in this paper takes polynomial times exponential time ,i.e, $O(n^{2k}\times 2^n)$ to compute prime implicates whereas Binevenu's algorithm \cite{Bienvenu} takes doubly exponential time to compute prime implicates. We have also proved its correctness.