Abstract We establish a systematic correspondence between sequent and resolution calculi for a broad class of modal logics. Our main result is that soundness and completeness transfer from sequent to resolution calculi as long as cut and weakening are admissible. We first construct generative calculi that essentially import modal rules to a resolution setting, and then show how soundness and completeness transfer to absorptive calculi, where modal rules are translated into generalised resolution rules. We discuss resolution calculi that establish validity, and then introduce local clauses to generate calculi for inconsistency. Finally, for modal rules of a certain shape, we show how to construct layered resolution calculi, a technique that has so far only been established for the modal logic K. Our work directly yields new sound and complete resolution calculi, and layered resolution calculi, for a large number of modal logics.

Abstract We investigate the systematic development of refined tableau systems for a subset of the logics of confluence, which are modal logics comprising of instances of the Scott-Lemmon axioms. In particular, we look at rule refinements aiming to decrease branching, perform fewer inferences and reduce the application of rules which create new labels in the tableau. Propagation rules are common forms of refined rules, that construct smaller pre-models sufficient to determine satisfiability, without needing to construct full concrete models satisfying the correspondence properties which would require a lot more inference steps. These rules have already been developed for the confluence logics that are part of the modal logic cube, but are lacking for some instances outside the cube. Such instances can be awkward, as the nature of their correspondence properties makes the development of propagation rules particularly challenging. These are the logics K G0111, K G and K De for which we propose refined tableau systems. We also present refined tableau systems for the combined logics K alt1De, K BG0111 and K DDe. Soundness and completeness results for all the systems are established.

Abstract We present deterministic model construction algorithms for sets of modal clauses saturated with respect to three refinements of the modal-layered resolution calculus implemented in the prover "Image missing". The model construction algorithms are inspired by the Bachmair-Ganzinger method for constructing a model for a set of ground first-order clauses saturated with respect to ordered resolution with selection. The challenge is that the inference rules of the modal-layered resolution calculus for modal operators are more restrictive than an adaptation of ordered resolution with selection for these would be. While these model construction algorithms provide an alternative means to proving completeness of the calculus, our main interest is the provision of a ‘certificate’ for satisfiable modal formulae that can be independently checked to assure a user that the result of "Image missing" is correct. This complements the existing provision of proofs for unsatisfiable modal formulae.

Abstract Non-monotonic modal logics are typically interpreted over neighbourhood frames. For unary operators, this is just a set of worlds, together with an endofunction on predicates (subsets of worlds). It is known that all systems of not necessarily monotonic modal logics that are axiomatised by formulae of modal rank at most one (non-iterative modal logics) are Kripke-complete over neighbourhood semantics. In this paper, we give a uniform construction to obtain complete resolution calculi for all non-iterative logics. We show completeness for generative calculi (where new clauses with new literals are added to the clause set) by means of a canonical model construction. We then define absorptive calculi (where new clauses are generated by generalised resolution rules) and establish completeness by translating between generative and absorptive calculi. Instances of our construction re-prove completeness for already known calculi, but also give rise to a number of previously unknown complete calculi.

Abstract We are interested in widening the reasoning support for propositional modal logics in the so-called modal cube. The modal cube consists of extensions of the basic modal logic $$\textsf{K}_{}$$ K with an arbitrary combination of the modal axioms $$\textsf{B}$$ B , $$\textsf{D}$$ D , $$\textsf{T}$$ T , $$\textsf{4}$$ 4 and $$\textsf{5}$$ 5 . We revisit recently developed local reductions from all logics in the modal cube to a normal form comprising sets of clausal formulae with associated modal levels. We extend these reductions further to the basic modal logic $$\textsf{K}_{}$$ K , called definitional reductions. This enables any prover for $$\textsf{K}_{}$$ K to be used to solve the satisfiability problem for all logics in the modal cube. We also present alternative, axiomatic, reductions based on ideas originally proposed by Kracht, providing new theoretical results and improved bounds on the size of the reductions. We compare both sets of reductions combined with state-of-the-art provers for $$\textsf{K}_{}$$ K on a large set of parametric benchmarks for all logics in the modal cube. The results show that the provers perform better with reductions based on the clausal normal form than the axiomatic reductions.

Abstract We present resolution calculi for the cube of classical non-normal modal logics. The calculi are based on a simple clausal form that comprises both local and global clauses. Any formula can be efficiently transformed into a small set of clauses. The calculi contain uniform rules and provide a decision procedure for all logics. Their completeness is based on a new and crucial notion of inconsistency predicate, needed to ensure the usual closure properties of maximal consistent sets. As far as we know the calculi presented here are the first resolution calculi for this class of logics.

Abstract We present novel reductions of extensions of the basic modal logic $${\textsf {K} }$$ K with axioms $$\textsf {B} $$ B , $$\textsf {D} $$ D , $$\textsf {T} $$ T , $$\textsf {4} $$ 4 and $$\textsf {5} $$ 5 to Separated Normal Form with Sets of Modal Levels $$\textsf {SNF} _{sml}$$ SNF sml . The reductions typically result in smaller formulae than the reductions by Kracht. The reductions to $$\textsf {SNF} _{sml}$$ SNF sml combined with a reduction to $$\textsf {SNF} _{ml}$$ SNF ml allow us to use the local reasoning of the prover $${\text {K}_{\text {S}}}{\text {P}}$$ K S P to determine the satisfiability of modal formulae in the considered logics. We show experimentally that the combination of our reductions with the prover $${\text {K}_{\text {S}}}{\text {P}}$$ K S P performs well when compared with a specialised resolution calculus for these logics, the built-in reductions of the first-order prover SPASS, and the higher-order logic prover LEO-III.

Abstract We present novel reductions of the propositional modal logics "Image missing" , "Image missing" , "Image missing" , "Image missing" and "Image missing" to Separated Normal Form with Sets of Modal Levels. The reductions result in smaller formulae than the well-known reductions by Kracht and allow us to use the local reasoning of the prover "Image missing" to determine the satisfiability of modal formulae in these logics. We show experimentally that the combination of our reductions with the prover "Image missing" performs well when compared with a specialised resolution calculus for these logics and with the b̆uilt-in reductions of the first-order prover SPASS.

Petri Nets are a widely used formalism to deal with concurrent systems. Dynamic Logics (DLs) are a family of modal logics where each modality corresponds to a program. Petri-PDL is a logical language that combines these two approaches: it is a dynamic logic where programs are replaced by Petri Nets. In this work we present a clausal resolution-based calculus for Petri-PDL. Given a Petri-PDL formula, we show how to obtain its translation into a normal form to which a set of resolution-based inference rules are applied. We show that the resulting calculus is sound, complete, and terminating. Some examples of the application of the method are also given.

In this paper we describe the implementation of , a resolution-based prover for the basic multimodal logic $${\textsf {K}}_{n}^{}$$ Kn. The prover implements a resolution-based calculus for both local and global reasoning. The user can choose different normal forms, refinements of the basic resolution calculus, and strategies. We describe these options in detail and discuss their implications. We provide experiments comparing some of these options and comparing the prover with other provers for this logic.

Resolution-based provers for multimodal normal logics require pruning of the search space for a proof to ameliorate the inherent intractability of the satisfiability problem for such logics. We present a clausal modal-layered hyper-resolution calculus for the basic multimodal logic, which divides the clause set according to the modal level at which clauses occur to reduce the number of possible inferences. We show that the calculus is complete for the logics being considered. We also show that the calculus can be combined with other strategies. In particular, we discuss the completeness of combining modal layering with negative and ordered resolution and provide experimental results comparing the different refinements.

In this paper, we briefly describe an implementation of a hyper-resolution-based calculus for the propositional basic multimodal logic, Kn. The prover, KSP, is designed to support experimentation with different combinations of refinements for its basic calculus. The prover allows for both local and global reasoning. We present an experimental evaluation that compares KSP with a range of existing reasoners for Kn.

We present a resolution-based calculus for Coalition Logic CL, a non-normal modal logic used for reasoning about cooperative agency. We introduce a normal form and a set of inference rules to solve the satisfiability problem in CL. We also show that the calculus presented here is sound, complete, and terminating.

The paper describes tableaux based proof methods for temporal logics of knowledge allowing interaction axioms between the modal and temporal components. Such logics can be used to specify systems that involve the knowledge of processes or agents and which change over time, for example agent based systems or knowledge games. The interaction axioms allow the description of how knowledge evolves over time and makes reasoning in such logics theoretically more complex. Completeness arguments for the tableaux are discussed.