Interpolation via Generalized Splitting
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: I'm Tom.
Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.
Tom: We're looking at the paper: "Interpolation via Generalized Splitting".
Jane: Here's the gist of the paper. Interpolation via Generalized Splitting proposes a new proof theoretical method for proving Lyndon interpolation based on a generalization of the splitting lemma in deep inference The main theorem states that every derivation can be decomposed into an up-fragment and a down-fragment, which is then used to show that the interpolant must be a Lyndon interpolant Core Method for Interpolation The authors formulate the interpolation theorem as a decomposition of a derivation into an up-fragment and a down-fragment, which is seen as both a strengthening of the standard formulation and a generalization of the cut elimination theorem The key ingredient is a generalization of the so-called splitting lemma, which allows transforming one derivation into another via currying, preserving the decomposition under this operation This leads to a flipping lemma that allows investigation of how currying influences the interpolant System Construction and Scope The approach is demonstrated across linear logic, classical logic, and several modal logics K, KT, K4, and S4 Novel cut-free deep inference proof systems are introduced for these modal logics because existing ones are underdeveloped or lack clear cut elimination properties For linear logic, specific proof systems like SLS'c are defined with core and non-core fragments, which allows for a modular structure in the proof of interpolation Decomposition and Flipping Lemmas The paper introduces Lemma 13 (Decomposition), which states that any derivation in LS'c can be decomposed into a core-part and a non-core part, preserving the O-structure of the conclusion Lemma 12 (Core Flipping) uses this decomposition to show that if a derivation exists, there is an interpolant formula Theorem 15 then shows that for any derivation in SLS'↑, there is an equivalent cut-free derivation with the interpolant Results for Classical and Modal Logics The method is extended to classical logic (SKS) and modal logics K, KT, K4, S4 For classical logic, the separation into core and non-core coincides with the separation in combinatorial proofs For modal logics Y ∈ Y is shown to have interpolation via Theorem 31, which follows from Lemma 12 and Lemma 30 The results for all four modal logics are summarized in Proposition 43 The modularity achieved through the core/non-core separation makes the proof of interpolation modular, unlike traditional methods where minor changes force a complete re-proof The work suggests that this method can be applied to other modal logics lacking sequent calculi and opens avenues for investigating the interpolant existence problem in logics like K4.
Paper summary: Jane: So how do they formulate this interpolation theorem? It seems like it boils down to decomposing any derivation into an up-fragment and a down-fragment. Tom Exactly, that’s the core idea. They see this decomposition as both making the standard interpolation theorem stronger and generalizing the cut elimination theorem.
Lu: The key ingredient they use is a generalization of what they call the splitting lemma in deep inference. This lemma allows them to transform one derivation into another through something called currying, and it keeps that decomposition intact during that transformation. Meng Wait, so this isn't just a neat trick for one specific logic? Lu No, they show how this works across linear logic, classical logic, and several modal logics like K4 and S4.
Jane: That’s a broad scope then. They introduce novel cut-free proof systems for those modal logics because the existing ones are underdeveloped or don't have clear cut elimination properties. Tom Right, so they build these new tools specifically to make this interpolation work cleanly in those areas.
Lalam: I see how it’s set up modularly with this core and non-core separation. They introduce a lemma that says any derivation can be split into a core part and a non-core part, which preserves the structure of the conclusion. Meng That sounds useful for production systems because it means you only have to worry about the non-core part when you modify things.
Tom: And then they use this decomposition to show that if a derivation exists, there must be an interpolant formula. Their theorem shows that for any derivation in a specific system, there's an equivalent cut-free derivation with that interpolant. Jane That’s the main payoff right there, showing how the splitting works for them.
Lu: The paper then extends this method to classical logic and those four modal logics by showing how their tools allow results from linear logic to translate almost trivially into classical and modal settings. Meng So it’s like they found a central piece of machinery that lets them solve interpolation problems across different logical frameworks without reinventing the wheel for each one?
Jane: That’s a good way to put it. They prove the results for all four modal logics using something called Theorem thirty-one which follows from Lemma twelve and Lemma thirty. Tom So they’re showing that this one generalized splitting lemma is versatile enough for this whole family of logics.
Conclusion: Tom: So, "Interpolation via Generalized Splitting" by Lutz Straßburger et al. They propose a new proof theoretic method for proving Lyndon interpolation that relies on a generalization of the splitting lemma in deep inference. Jane What does this actually mean for the broader field? Tom It gives us a modular structure because you can separate derivations into core and non-core parts, so minor changes to the proof system don't force you to redo everything from scratch.
Lu: The modularity is key here. They designed the proof systems in such a way that results for classical and modal logic follow almost trivially from their work on linear logic. Meng I wonder what that means when we think about actually running these proofs on a production system? Lu It means the underlying representation learning tools they're building can handle complexity across these different logical settings without needing entirely separate, massive proof engines for each one.
Jane: The paper shows flexibility by applying this technique to linear logic, classical logic, and modal logics K, KT, K4, and S4. Tom It suggests that we can apply this kind of decomposition idea to other modal logics that currently lack sequent calculi. Meng That sounds promising if we want to investigate interpolation in those systems more seriously.
Lalam: My analysis confirms what the authors claim about the modular structure; it makes the proof of interpolation very flexible. Jane So, for someone who only listens to this show, how should I summarize this? Tom Think of it as finding a universal way to break down a complex derivation into manageable pieces, which lets you prove that an interpolant exists in various logical settings using one core set of tools.
inria · Ecole Polytechnique · IP Paris
cs.LO
Submitted: 2026-07-26
Updated: 2026-11-16
Comments: v1: submitted version, v2: final author version for the CSL 2027 paper, with appendices (page layout might be different from the official Dagstuhl version, but theorem numbering is the same)
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 96/100
The gist: Interpolation via Generalized Splitting proposes a new proof theoretical method for proving Lyndon interpolation based on a generalization of the splitting lemma in deep inference The main theorem…
Key concepts
- Generalized Splitting Lemma
- This is a key ingredient that allows transforming one logical derivation into another through an operation called currying. Crucially, this lemma ensures that the decomposition of the derivation into fragments remains valid after this transformation, which is essential for proving interpolation.
- Up-fragment and Down-fragment Decomposition
- The main theorem states that any complex derivation can be split into two parts: an up-fragment and a down-fragment. This structural decomposition is used to show that the resulting interpolant formula must necessarily be a Lyndon interpolant, providing a systematic way to find it.
- Core and Non-core Fragments
- In specific proof systems like SLS'c for linear logic, derivations are separated into core and non-core parts. This modular separation helps manage the complexity of the proof of interpolation, allowing researchers to prove results by focusing on these distinct structural components.
- Flipping Lemma
- This lemma investigates how the currying operation affects the interpolant formula. It is used in conjunction with the decomposition to demonstrate that if a derivation exists, an equivalent cut-free derivation containing the interpolant can be constructed.
Terminology
Summary
Interpolation via Generalized Splitting proposes a new proof theoretical method for proving Lyndon interpolation based on a generalization of the splitting lemma in deep inference The main theorem states that every derivation can be decomposed into an up-fragment and a down-fragment, which is then used to show that the interpolant must be a Lyndon interpolant
Core Method for Interpolation
The authors formulate the interpolation theorem as a decomposition of a derivation into an up-fragment and a down-fragment, which is seen as both a strengthening of the standard formulation and a generalization of the cut elimination theorem The key ingredient is a generalization of the so-called splitting lemma, which allows transforming one derivation into another via currying, preserving the decomposition under this operation This leads to a flipping lemma that allows investigation of how currying influences the interpolant
System Construction and Scope
The approach is demonstrated across linear logic, classical logic, and several modal logics K, KT, K4, and S4 Novel cut-free deep inference proof systems are introduced for these modal logics because existing ones are underdeveloped or lack clear cut elimination properties For linear logic, specific proof systems like SLS'c are defined with core and non-core fragments, which allows for a modular structure in the proof of interpolation
Decomposition and Flipping Lemmas
The paper introduces Lemma 13 (Decomposition), which states that any derivation in LS'c can be decomposed into a core-part and a non-core part, preserving the O-structure of the conclusion Lemma 12 (Core Flipping) uses this decomposition to show that if a derivation exists, there is an interpolant formula Theorem 15 then shows that for any derivation in SLS'↑, there is an equivalent cut-free derivation with the interpolant
Results for Classical and Modal Logics
The method is extended to classical logic (SKS) and modal logics K, KT, K4, S4 For classical logic, the separation into core and non-core coincides with the separation in combinatorial proofs For modal logics Y ∈ Y is shown to have interpolation via Theorem 31, which follows from Lemma 12 and Lemma 30 The results for all four modal logics are summarized in Proposition 43
Conclusion and Future Directions
The modularity achieved through the core/non-core separation makes the proof of interpolation modular, unlike traditional methods where minor changes force a complete re-proof The work suggests that this method can be applied to other modal logics lacking sequent calculi and opens avenues for investigating the interpolant existence problem in logics like K4.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Modular interpolation proof systems can be designed by separating them into core and non-core fragments, which allows minor changes in system rules to not force a complete re-proof of interpolation.
-
The improved AI system can prove Lyndon interpolation for linear logic, classical logic, and several modal logics K, KT, K4 and S4 using novel cut-free deep inference proof systems.
-
The system can be extended to first-order logic by investigating existing deep inference systems to find a separation between core and non-core fragments that might apply there.
-
The AI system can determine the existence of an interpolant for a given derivation by decomposing it into an up-fragment and a down-fragment, which is seen as
a strengthening of the standard formulation of the interpolation theorem.
-
The AI can perform cut elimination within deep inference systems by leveraging Theorem 8, which follows from Proposition 7.5 and Theorem 4, allowing translations from sequent calculus proofs to deep inference proofs.
Abstract
We propose a new proof theoretical method for proving Lyndon interpolation. Our proof does not use the sequent calculus but is based on a generalization of the splitting lemma in deep inference. We then formulate the interpolation theorem as a decomposition of a derivation into an up-fragment and a down-fragment. This can be seen as (i) a strengthening of the standard formulation of the interpolation theorem, and (ii) a generalization of the cut elimination theorem. We demonstrate the flexibility of our approach by applying it to linear logic, classical logic, and modal logics. For this, we also introduce novel cut-free proof systems for several modal logics in deep inference.
Sources
- Proof Identity and Categorical Models of BV
- Interpolation and Query Rewriting
- Six Proofs of Interpolation for the Modal Logic K
- Interpolation in Knowledge Representation
- From Interpolating Formulas to Separating Languages and Back Again
- Craig Interpolation in Program Verification
- Interpolation in Proof Theory
Related papers
- A Non-Dichotomy for CSPs of Stable omega-Categorical Structures
- A Deeper Look at Depth: Stable Generation Accounting for Quantifier Reasoning
- Formalizing Hyperspaces and Operations on Subsets of Polish Spaces over Abstract Exact Real Numbers
- A Diagrammatic Basis for Computer Programming
- Staying Productive Under the Palm Trees: On Graded Coeffect Typing in the Tropical Semiring
- Tree algebras and bisimulation-invariant MSO on finite graphs