An Algorithm for Computing Prime Implicates in Modal Logic Using\n Resolution

2018/11/12 by Manoj K. Raut, Raut, Manoj K.
Computer Science · #Advanced Algebra and Logic #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Logic, programming, and type systems

paper · pdf · doi:10.48550/arxiv.1811.04566

openalex publication_date 2018/11/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper we have proposed an algorithm for computing prime implicates of\na modal formula in \K using resolution method suggested in\n citeEnjalbert. The algorithm suggested in this paper takes polynomial times\nexponential time ,i.e, O(n^2k\× 2ⁿ) to compute prime implicates\nwhereas Binevenu's algorithm citeBienvenu takes doubly exponential time to\ncompute prime implicates. We have also proved its correctness.\n

Related

• Computing Theory Prime Implicates in Modal Logic
• An algorithm for finding square root modulo p
• On the Inversion Modulo a Power of an Integer
• A method for determining the mod-p^k behaviour of recursive sequences
• Decomposition of an integer as the sum of two cubes to a fixed modulus