Efficient Decision Procedures for RNmatrix Semantics
For logicians and automated reasoning researchers, this provides the first efficient implementations for the entire C_n hierarchy and competitive general-purpose provers for intuitionistic and modal logics.
The paper introduces efficient decision procedures for RNmatrix semantics by encoding them as SMT problems, enabling automated theorem provers that outperform state-of-the-art for paraconsistent logics and achieve competitive performance for intuitionistic and modal logics.
Restricted non-deterministic matrices (RNmatrices) impose constraints on the rows of non-deterministic matrices (Nmatrices), filtering out ``unsound" rows and retaining only ``valid" ones. This yields a more expressive framework than standard Nmatrices. Although this approach enables sound and complete semantics for a broad class of logics, \eg, paraconsistent logics, propositional intuitionistic logic, and the fifteen normal modal logics of the modal cube, no {\em efficient} decision procedures based on these semantics have been proposed. In this paper, we implement the RNmatrix framework to develop a new suite of automated theorem provers for these logics. By encoding RNmatrices and their elimination criteria as Satisfiability Modulo Theories (SMT) problems, we leverage SMT solvers to decide formula validity and construct countermodels. We illustrate the method for paraconsistent logics, where our prover outperforms the current state-of-the-art and provides the first implementation for the entire $C_n$ hierarchy, as well as for intuitionistic and modal logics, where our general-purpose prover achieves competitive performance.