CS Paper Radar

Propositional Dynamic Logic without tests does not have Craig Interpolation

Malvin Gattinger

cs.LO math.LO ·submitted 2026-11-12 13:08 UTC · v1

Abstract

It was shown recently by Borzechowski et al. (2026) that Propositional Dynamic Logic (PDL) has Craig Interpolation. Whether test-free PDL, i.e. PDL without the `?' operator, has interpolation remained open. Here we answer this question in the negative with a counterexample: a test-free PDL validity for which no test-free interpolant exists. The validity only uses one atomic program and the Kleene star, so it implies that the basic modal logic K extended with the reflexive transitive closure does not have interpolation, as previously shown by Studer (2009). The example was originally obtained using LLMs and Lean. We describe our methodology and provide links to all prompts, LLM output summaries as well as the Lean proof.

Closest papers

Nearest neighbours by meaning across the whole index.

Strong Lyndon Interpolation for Multi-Modal Logics with Converses: A Constructive Approach with Tree Sequents

cs.LO math.LO ·2026-11-12 ·Tim S. Lyon
similarity 0.67
Abstract · in review

Grammar logics with converses are multi-modal logics that generalize tense logics and whose frame conditions are determined by context-free production rules. We study the strong Lyndon interpolation property (strong LIP) for these logics, which requires interpolants to respect both the polarities of propositional atoms and the indices of modalities. We show that the strong LIP properly strengthens the Lyndon interpolation property over grammar logics, since it fails for certain grammar logics with bridge axioms, i.e., path axioms relating modalities with distinct indices. We then prove that every bridge-free grammar logic, possibly extended with seriality axioms, has the strong LIP. This class includes the multi-modal tense logics obtained by imposing any combination of seriality, reflexivity, transitivity, symmetry, and Euclideanity on each pair of converse modalities. Our proof is constructive and purely syntactic, and is based on tree sequent calculi. Because standard methods for computing interpolants with tree and nested sequents may introduce modalities whose indices are not common to both sides of an implication, we introduce a novel tripartite partition method. It sorts the labels of a proof into common labels and labels private to the left or right component, and only lets relational atoms pointing to common labels contribute modalities to interpolants. Given a proof of an implication, our method computes a strong Lyndon interpolant together with proofs of its correctness.

0.45

Proof-Relevant Interpolation for Circular Proofs in Linear Logic

cs.LO ·2026-11-18 ·Daniel Osorio-Valencia, Alexis Saurin
theory similarity 0.65
Abstract

First introduced for proving Craig's interpolation theorem, Maehara's method provides a constructive, proof-theoretic procedure for extracting interpolants in sequent calculus proofs. Building on this method, Saurin developed a ``proof-relevant'' interpolation theorem for first-order linear logic, in the sense that the interpolated proof is obtained by cut-introduction steps that can be reversed via cut-elimination. In this work, we extend Saurin's proof-relevant interpolation to linear logic proofs with cuts as well as to circular proofs in linear logic with fixed-points. We specifically show how Maehara's method can be extended in a proof-relevant way to work on non-cut-free and non-well-founded (but regular) proof objects, and guarantee that the interpolation procedure preserves strong validity. We also study conditions under which one can interpolate system L terms that are not necessarily in normal form.

0.33

The Density of Interpolants in Modal Logic: First Results

cs.LO ·2026-11-19 ·Roman Kontchakov, Louwe Kuijer, Frank Wolter
similarity 0.61
Abstract

We initiate a quantitative study of interpolation in propositional modal logic. Instead of asking only whether a logic has Craig or uniform interpolation, we measure the density of formulas, or pairs of formulas, admitting interpolants. For quasi-normal modal logics, formulas of bounded modal depth over finite signatures are counted modulo logical equivalence. We show that interpolation failure is local to cells determined by the retained signature, yielding product decompositions of both uniform and Craig interpolation densities. These decompositions allow us to analyse their asymptotic behaviour as either the retained or the forgotten signature grows. When the retained signature grows, we obtain general results for all quasi-normal modal logics; when the forgotten signature grows, the behaviour is subtler, particularly when formulas are counted after existential quantification over forgotten variables. For locally tabular logics, we introduce cell incompatibility graphs and use them for a fine-grained analysis covering tabular logics, the difference logic Diff, and bounded-depth extensions of Grz.

0.33

Propositional Dynamic Logic with Program Costs

cs.LO math.LO ·2026-11-02 ·Krishna Manoorkar, Wolfgang Poiger
similarity 0.60
Abstract

We introduce $\mathbb{N}\mathtt{PDL}$, a resource-aware variant of Propositional Dynamic Logic ($\mathtt{PDL}$) capable of accounting for program costs measured by natural numbers (such as time or space in the sense of computability theory). In this framework, programs correspond to transition systems weighted by extended natural numbers, and the syntax of our logic includes formulas expressing which properties are reachable by program executions within specific cost constraints. First, we explain how the standard program constructs of non-deterministic choice, sequential composition, iteration, and tests are interpreted in this weighted setting and establish the validity of their corresponding reduction axioms. Using an appropriate adaptation of the (Fischer-Ladner) filtration technique, we proceed to prove decidability and completeness for $\mathbb{N}\mathtt{PDL}$ as our main results. We furthermore provide upper and lower complexity bounds for this logic using translations between standard $\mathtt{PDL}$ and $\mathbb{N}\mathtt{PDL}$.

0.13

Towards Finite Satisfiability of PDL with Loops

cs.LO ·2026-10-11 ·Bartosz Jan Bednarczyk, Mikołaj Swoboda
theory similarity 0.58
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

Tracking relevance syntactically: A nested approach to weak relevant logic

cs.LO ·2026-11-12 ·Fabio De Martin Polo, Han Gao
theory similarity 0.54
Abstract

The variable-sharing property (VSP) is regarded as a key feature of relevant logics, while the Craig interpolation property (CIP), formulated with respect to relevant implication, implies the VSP in constant-free propositional languages. However, to the best of our knowledge, no constant-free distributive relevant logic has previously been shown to enjoy the CIP. This absence of positive results has contributed to a widespread impression among relevant logicians that relevance and Craig interpolation are incompatible. In this work, we address this tension by proving that the negation-free fragment of base relevant logic B, denoted B+, enjoys both properties. Our proof is purely syntactic and is based on a novel nested sequent calculus featuring binary relevant blocks as primitive structural constructs. Unlike conventional nested sequent calculi, where unary nesting reflects the binary accessibility relation of Kripke semantics, our calculus employs a binary nesting operator that directly reflects the ternary relational structure of Routley-Meyer semantics for relevant logics. After establishing soundness and cut-free completeness of the calculus, we prove several meta-logical properties for the logic. Most notably, we provide the first syntactic proof of the VSP (along with a variety of its stronger variants) and the first proof of the CIP for B+, both derived directly from the cut-free system using a structural notion internalized within nested sequents.

0.26

Proofs Without Nominals: Gödel's Ontological Argument, its Shallow Embedding, and the Open Questions of the Monatshefte Notes

cs.LO cs.AImath.LO ·2026-09-28 ·Christoph Benzmüller
theory similarity 0.52
Abstract · 51 pages. New in v5: the witness criterion and the whole-term condition come apart (a proof with the nominal in a context alone); three open…

The shallow embedding of higher-order modal logic in classical higher-order logic, used in Benzmüller and Scott's Notes on Gödel's and Scott's variants of the ontological argument, reaches beyond the modal object language: its quantifiers range over domains containing the nominals and satisfaction operators of hybrid logic. A proof using one proves a theorem of the embedding, not necessarily of the modal logic. Whether a result is one of the modal logic can be settled by replaying it in an explicit calculus, or, more cheaply and for all results at once, by analysing what the embedding's proofs substitute. Every statement the Notes prove has a proof in the embedding substituting nothing outside the object language, 294 of them explicit. The Notes' own proofs substitute none either; what it flags are terms a prover introduced. A soundness theorem over general models closed under the object language, and a sentence of that language the embedding proves but which fails in such a model, fix what the certificate says. The Notes' three open questions are settled too, without nominals, but by the empty instance of the conjunction axiom, too cheaply to convince. Generalised to Gödel's "any number of summands", the axiom covers the empty conjunction and the singleton. This article restricts it to at least two different conjuncts, a non-degenerate reading of Gödel's footnote, and settles them again without nominals. In effect only the empty conjunction is excluded; the singleton comes back with the other axioms. In one variant the restriction refutes the possible existence of a God-like being; the answers return, with no side condition, once the Notes' non-emptiness clause is confined to Gödel's essence. Every theorem here is verified in Isabelle/HOL and independently in Lean 4, the separating model in its propositional part; the countermodels are Nitpick's, checked by the build.

0.45

Symbolic Execution of Constrained Horn Clauses

cs.LO cs.PL ·2026-10-02 ·Johannes Weiser, Zafer Esen, Philipp Rümmer
similarity 0.51
Abstract · 34 pages, 8 figures

Constrained Horn clauses (CHCs) are a fragment of first-order logic widely used as an intermediate language for verification. We study constrained resolution as a calculus for reasoning about the satisfiability of sets of CHCs. Constrained resolution forms a simple alternative to model checking algorithms such as CEGAR and IC3 and is here shown to exhibit complementary features. We show that, when CHCs encode programs, forward symbolic execution corresponds to positive unit hyper-resolution, and backward symbolic execution to SLD resolution, which are special cases of constrained resolution. We formalize forward and backward reasoning for linear and non-linear CHCs and transition systems, prove refutational completeness under fair strategies, and develop subsumption criteria for pruning redundant derivations. We moreover show that backward resolution with subsumption generalizes $k$-induction to non-linear CHCs, and that forward constrained resolution is related to the problem of constructing proofs in incorrectness logic. Lastly, we provide an experimental evaluation in the Eldarica CHC solver on benchmarks from CHC-COMP.

0.19