CS Paper Radar

A decision procedure for intuitionistic modal logic IS4 (and IK4)

Marianna Girlando, Roman Kuznets, Sonia Marin, Lutz Straßburger

cs.LO ·submitted 2026-09-21 17:18 UTC · v2

Abstract

In this paper, we show that the two intuitionistic modal logics IS4 and IK4 are decidable. We provide a constructive decision procedure, that, given a formula, produces either a proof showing the formula to be valid or a finite countermodel falsifying the formula, thus also proving the finite model property for both logics. The main ingredient of our strategy is the introduction of (possibly unsound) loop rules, which encode repeating behaviour in proof search. This paper fixes a previous mistake in our LICS'23 contribution.

Comment
corrections of minor technical issues in v1

Closest papers

Nearest neighbours by meaning across the whole index.

Fine Selection for Intuitionistic Modal Logic

cs.LO math.LO ·2026-09-22 ·David Fernández-Duque
similarity 0.75
Abstract · This version corrects various typos and inaccuracies which, while minor, affected legibility. Notably, the definition of $Σ$-trees was missi…

We extend Fine's selection method to the setting of intuitionistic modal logic and use it to provide a model-theoretic proof that Fischer Servi-style intuitionistic $\sf K4$ has the finite model property.

0.23

A Kruskal Decision Procedure for Intuitionistic Modal Logic IK4

cs.LO ·2026-08-10 ·Mario Piazza
theory similarity 0.71
Abstract · 24

We prove decidability of Simpson's intuitionistic modal logic IK$ by working directly with cut-free nested proofs. Once the end formula is fixed, only finitely many combinations of input and output formulae can occur at a node, although the modal tree itself remains unbounded. We order these nested sequents by rooted homeomorphic embedding: weakening may add input formulae, while transitivity allows a modal edge to be stretched into a non-empty path. Kruskal's theorem makes rooted homeomorphic embedding a well-quasi-order, but does not by itself make backward application of the rules effective: an inference may still occur inside an arbitrarily large context. The finite-support lemma shows that a minimal predecessor need retain only the positions used by the inference, the images of the chosen basis elements, and the branch points joining them. Together with an effective enumeration of bounded rule instances, this bound makes the minimal predecessors computable. Backward closure from the initial sequents gives an increasing sequence of finitely based upward-closed sets. The sequence eventually stabilises, and its stable value is the set of provable nested sequents. At that point, finitely many cut-free proofs suffice: every other provable nested sequent is obtained from one of them by weakening along an embedding. Their maximum height gives a uniform proof-height bound.

0.33

New Proofs of Weak Normalization for Propositional Logic

cs.LO ·2026-09-13 ·S P Suresh
similarity 0.66
Abstract

We present new proofs of weak normalization for intuitionistic and classical propositional logics (with the full set of operators -- falsum, implication, conjunction and disjunction). These proofs work with cuts rather than cut segments, and they provide explicit ``local'' rules for determining whether to contract a whole proof or reduce one of its subproofs, and in the latter case, which subproof to reduce. Interestingly, much of the complication in the case of intuitionistic logic is due to the disjunction elimination rule, while our version of the same rule for classical logic has falsum as conclusion always, and so is much easier to handle. All the complication in the case of classical logic shifts to cuts involving the reductio ad absurdum rule. We also discuss a formalization of the entire proof in Lean, and present a deterministic algorithm for weak normalization.

0.20

Canonical Proof Nets for Intuitionistic Multiplicative Linear Logic

cs.LO ·2026-11-18 ·Matteo Acclavio, Willem Heijltjes, Dominic J. D. Hughes
similarity 0.63
Abstract

We study the problem of finding canonical representations of proofs in the multiplicative fragment of intuitionistic linear logic with units. We show that, contrary to the classical case, it is possible to define a notion of proof nets for this fragment which is provided with a polynomial-time sequentialization procedure and is both canonical and efficient. In particular, we show that sequent calculus derivations differing only by a permutation of independent rule applications are translated to the same proof net, and that the translations between sequent calculus and proof nets are inverse to each other.

0.32

A generalised and modular proof-theoretic semantics for sequent systems

cs.LO math.LO ·2026-10-16 ·Victor Barroso-Nascimento, Arghya Chakrabarty, Elaine Pimentel
similarity 0.63
Abstract

Base-extension semantics explains logical consequence via derivability in atomic systems. Extending this approach across logics requires careful control of structural principles and contexts. We present a modular sequent-based framework in which support is indexed by multisets of atomic resources and the semantic clauses for connectives are guided by their left introduction rules. The framework separates additive from multiplicative behaviour and makes explicit the contributions of structural rules and restrictions on sequents. We establish soundness and completeness for classical and intuitionistic propositional logic and for multiplicative-additive fragments of classical and intuitionistic linear logic. We then investigate axiomatic extensions of intuitionistic logic through Jankov logic. Two classes of atomic bases yield sound and complete semantics. Completeness is proven using two novel and modular methods using simulation bases, one of which is constructive. These results provide a common semantic treatment of several logical systems while identifying the additional conditions needed to extend the framework beyond structural variations.

0.16

Restricted Peirce's Law and Natural Deduction

cs.LO ·2026-10-29 ·Satoru Niki
publishedtheoryhot direction similarity 0.60
Abstract · In Proceedings NCL'26, arXiv:2610.34489

The constructive logic JP' is known to be the weakest logic between intuitionistic and minimal logic that satisfies Glivenko's theorem. In spite of this natural and desirable formal property, the motivation for its notion of negation remains rather elusive: it can be characterised by a restriction of Peirce's law or by the double negation of ex falso quodlibet, neither of which is very intuitive. In order to have an alternative perspective on this negation, we study in this paper a couple of natural deduction systems for JP'. We first present a system that is normalisable and satisfies a restricted form of the subformula property. Then a modification of this system is introduced, whose rules satisfy the separation of connectives and the full subformula property. Afterwards we turn our attention to a typed lambda-calculus, with respect to which our natural deduction enjoys the Curry-Howard correspondence, followed by a concluding discussion.

0.40

A minimal intuitionistic public announcement logic

cs.LO ·2026-11-10 ·Philippe Balbiani, Hans van Ditmarsch, Cigdem Gencer, Clara Lerouvillois
similarity 0.60
Abstract

We introduce intuitionistic public announcement logics Lmin and Lequ determined by classes of birelational frames where the intuitionistic preorder and the modal accessibility relation do not need to satisfy the confluence conditions traditionally considered within the framework of IPAL. Our logics can be seen as generalisations of IPAL seeing that their language is based on a binary epistemic modality of "relativised knowledge" that allows us to define valid reduction axioms. Our main results are the soundness and completeness of Lmin with respect to the class of all birelational frames and the soundness and completeness of Lequ with respect to the class of all birelational frames where the modal accessibility relation is an equivalence relation.

0.24

Towards Finite Satisfiability of PDL with Loops

cs.LO ·2026-10-11 ·Bartosz Jan Bednarczyk, Mikołaj Swoboda
theory similarity 0.60
Abstract · 52 pages, 8 figures, 2 tables. Under submission. This is a part of our ongoing work in progress: we are close to settling the finite satisfi…

Propositional Dynamic Logic (PDL) is a well-established modal logic of programs. Among its many extensions, the loop operator stands out for capturing the cyclic behaviour of programs: a world satisfies loop(pi) precisely when it can return to itself along a path matching the regular expression pi. While the satisfiability problem for the resulting logic LPDL was settled already in the 1980s, the decidability of its finite satisfiability problem has remained open ever since. The core difficulty is inherent to the finite setting: requiring and forbidding cycles at once is easily reconciled over arbitrary models, but over finite ones it defeats the existing finite-model-theoretic techniques. We make the first substantial progress towards closing this gap. We prove that finite satisfiability is ExpTime-complete for LPDL formulae (also in the presence of the converse operator) in negation normal form, under the restriction that every negated non-atomic loop has the form loop(pi^+) for some arbitrarily complex program pi -- a generalised form of self-reachability; positive occurrences of loops remain unrestricted. At the heart of our approach lies a novel way of representing intended finite models as their infinite, cactus-like unravellings: these are recognisable by two-way tree automata and satisfy a tailored omega-regular foldability condition that lets us finitise the accepted structures.

0.36