💻 computer science

Interpolation via Generalized Splitting

This paper introduces a novel proof-theoretic method based on generalized splitting in deep inference to establish Lyndon interpolation as a decomposition of derivations, offering a strengthened and generalized alternative to standard sequent calculus approaches that is successfully applied to linear, classical, and various modal logics.

Original authors: Lutz Straßburger

Published 2026-07-28

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Lutz Straßburger

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery, but instead of fingerprints or DNA, your clues are logical statements. You have a starting point (a premise) and an ending point (a conclusion), and you know they are connected. But what if you wanted to know exactly what information is shared between the two? Is there a secret "middle ground" formula that explains how you got from A to B, without revealing any secrets that only A knows or only B knows? This is the heart of a famous problem in computer science and mathematics called interpolation.

To understand this, think of logic like a game of building with LEGO bricks. Each brick is a piece of information. If you build a tower (a proof) that starts with a red base and ends with a blue top, interpolation asks: "Is there a middle section made only of bricks that appear in both the red base and the blue top?" A stricter version, called Lyndon interpolation, adds a rule: not only must the bricks be the same color, but they must also be facing the same way (upright or upside down). For decades, mathematicians have used a specific set of tools called sequent calculus to prove that this middle section always exists. However, these tools can be clunky, like trying to build a complex model with a hammer instead of a screwdriver. They often require rebuilding the entire tower from scratch if you change just one tiny rule.

Enter Lutz Straßburger's paper, which introduces a brand new way to solve this puzzle using a technique called deep inference. Instead of building the tower layer by layer from the outside in, deep inference lets you reach inside the structure and rearrange the bricks wherever they are, even deep in the middle. The paper proves that by using a clever "splitting" trick, you can always separate any logical proof into an "up" part and a "down" part, with a perfect middle section (the interpolant) sitting right between them. This isn't just a new way to prove the old rules; it's a more flexible, modular approach that works for many different types of logic, including the complex rules used in computer verification and artificial intelligence. The author shows that this method is so powerful that it can handle linear logic, classical logic, and even several types of modal logic (logic about possibility and necessity) with a single, unified strategy.

The Story of the Split

Imagine you have a long, winding tunnel that connects a cave entrance (your starting idea) to a treasure room (your final conclusion). For a long time, explorers thought the only way to prove the tunnel existed was to walk the whole way through, step by step, checking every turn. But Straßburger discovered a magical map that lets you split the tunnel right in the middle.

The paper proposes a new method called Interpolation via Generalized Splitting. The core idea is that any logical proof can be broken down into two distinct halves: an up-fragment and a down-fragment. Think of the up-fragment as the "construction phase" where you are building things up, and the down-fragment as the "deconstruction phase" where you are breaking things down to reach your goal. The magic happens in the middle: the point where these two phases meet is the interpolant. This is the secret formula that contains only the information shared by the start and the end, acting as a perfect bridge.

Why is this a big deal? In the old way of doing things (using sequent calculus), if you wanted to find this bridge, you had to carefully dissect the entire proof, looking for specific patterns. It was like trying to find a specific grain of sand in a beach by sifting through the whole thing. If you changed the rules of the game slightly, you often had to start the whole sifting process over again. Straßburger's method is like having a laser cutter. It uses a "generalized splitting lemma" to slice the proof cleanly. Because the rules of the "up" part and the "down" part are so different (one creates new variables, the other doesn't), the paper proves that the middle slice must be the perfect interpolant. It's a mathematical guarantee that the bridge exists and is made of the right materials.

The Magic of "Flipping"

One of the coolest tricks in the paper is something the author calls the flipping lemma. Imagine you have a proof that goes from Point A to Point B. The flipping lemma says you can take that proof, turn it inside out, and it still works, but now it connects Point B to Point A in a mirrored way. It's like taking a glove, turning it inside out, and realizing it still fits your hand, just with the seams on the outside.

This "flipping" is crucial because it allows the author to prove that the "up" and "down" fragments can be separated without losing any information. The paper demonstrates that this works for Linear Logic (a logic where resources matter, like having one cookie that disappears if you eat it), Classical Logic (the standard logic of true and false), and even Modal Logics (logics that deal with concepts like "possibly" and "necessarily").

For the modal logics, the author had to build some new tools from scratch. It turns out that the existing tools for deep inference in modal logic were a bit like using a bicycle to drive a car; they just didn't have the right gears. Straßburger designed new, cut-free proof systems specifically for these logics, allowing the splitting method to work smoothly. This is a significant step forward because deep inference for modal logic was previously underdeveloped, and now we have a clear, modular way to handle them.

Why This Matters

The beauty of this approach is its modularity. In the past, proving interpolation for a new logic was like building a new house from the ground up every time you wanted to add a room. If you changed a brick, you might have to rebuild the whole foundation. With this new method, the "core" of the logic (the essential rules) is separated from the "non-core" parts (the specific details). You can change the non-core parts without having to redo the entire proof. It's like having a LEGO set where the base plate is universal, and you can snap on different wings or towers without worrying about the foundation collapsing.

The paper doesn't just suggest this might work; it provides a rigorous, mathematical proof that it does work for the specific logics mentioned. It shows that interpolation is not just a lucky accident in some logics, but a fundamental property that can be revealed by looking at proofs through the lens of deep inference. By separating the "up" and "down" movements of a proof, the paper reveals a hidden structure that makes finding the interpolant almost automatic.

In the end, this paper offers a new pair of glasses for mathematicians and computer scientists. Instead of staring at a messy, tangled proof and trying to untangle it, they can now use this generalized splitting technique to see the clean, modular structure underneath. It proves that for a wide range of logical systems, there is always a "middle ground" formula, and we now have a much better, more flexible way to find it. This could eventually help in building better software, verifying that computer programs are safe, and understanding how knowledge is represented in artificial intelligence, all by making the underlying logic more transparent and easier to manipulate.

Technical Summary: Interpolation via Generalized Splitting

Problem Statement

The paper addresses the proof-theoretic proof of the Lyndon interpolation theorem. While interpolation has been established for various logics (classical, intuitionistic, modal, linear) using model-theoretic, automata-theoretic, or syntactic methods, the most common proof-theoretic approach relies on Maehara's method. This method surgically extracts an interpolant from a cut-free sequent proof. However, Maehara's approach and its modern variations often lack modularity; minor changes to a proof system (e.g., adding new rules) frequently necessitate redoing the entire interpolation proof from scratch. Furthermore, traditional sequent calculus mixes "core" logical rules with structural rules (like weakening and contraction), making it difficult to separate the logical essence of a derivation from its resource management aspects.

The author proposes a new method that avoids the sequent calculus entirely, utilizing deep inference techniques. The goal is to formulate interpolation not merely as the existence of a formula, but as a structural decomposition of a derivation, thereby achieving a more modular and generalizable proof technique.

Methodology

The proposed methodology is grounded in deep inference, a proof-theoretic framework where inference rules can be applied at any depth within a formula, rather than only at the root. The core of the approach involves three main technical components:

Generalized Splitting Lemma:
The standard splitting lemma in deep inference states that if a formula $(A \otimes B) \parr K$ is provable, the context $K$ can be split into $K_A$ and $K_B$ such that $A \parr K_A$ and $B \parr K_B$ are provable. The author generalizes this to derivations with an arbitrary premise $J$ (rather than just the unit $1$). Specifically, if $J \vdash (A \otimes B) \parr K$ , the derivation can be decomposed into an "up-fragment" (deriving a split context from $J$ ) and a "down-fragment" (deriving $K$ from the split context), while simultaneously isolating the sub-derivations for $A$ and $B$ . Crucially, this generalization requires specific rules (denoted $p'_{\downarrow}, d'_{\downarrow}, d'_{0\downarrow}$ ) that are not strictly necessary for completeness but are essential for the decomposition.
Core/Non-Core Separation:
The proof systems are decomposed into a core fragment (containing logical rules and specific structural rules like $p'_{\downarrow}$ ) and a non-core fragment (containing standard structural rules like weakening, contraction, and promotion). A key lemma demonstrates that any derivation in the full system can be permuted into a form where the core fragment is applied first, followed by the non-core fragment, preserving the multiplicative structure of the conclusion. This separation allows the interpolation proof to be modular: the core handles the logical splitting, while the non-core handles resource management.
Flipping Lemma:
Building on the generalized splitting, the author introduces a "flipping" mechanism. This lemma allows the transformation of a derivation where an "up-fragment" (analogous to cut introduction) sits above a "down-fragment" (analogous to cut elimination) into a new derivation where the roles are reversed or restructured. Specifically, a derivation from $H$ to $F \parr K$ via an up-fragment and a down-fragment can be transformed into a derivation from $F^\perp \otimes H$ to $K$ via a flipped up-fragment and down-fragment, introducing an intermediate formula $I$ .

Key Contributions

A New Proof-Theoretic Method for Interpolation:
The paper presents a proof of the Lyndon interpolation theorem that does not rely on the sequent calculus. Instead, it uses the generalized splitting lemma and the flipping lemma within deep inference systems. This approach views interpolation as a decomposition of a derivation into an up-fragment and a down-fragment separated by an interpolant $I$ .
Theorem 1 (Decomposition Theorem):
The central result states that every derivation $A \vdash_X B$ can be decomposed into:
$A \xrightarrow{\delta_1} I \xrightarrow{\delta_2} B$
where $\delta_1$ uses only rules from the up-fragment ( $X^\uparrow$ ) and $\delta_2$ uses only rules from the down-fragment ( $X^\downarrow$ ). The formula $I$ serves as the Lyndon interpolant. This theorem is presented as both a strengthening of the standard interpolation theorem (providing explicit proofs for $A \vdash I$ and $I \vdash B$ ) and a generalization of the cut elimination theorem.
Novel Proof Systems for Modal Logics:
The author introduces new cut-free deep inference proof systems for the modal logics K, KT, K4, and S4. Existing deep inference systems for modal logic were deemed insufficient for the proposed method (specifically lacking the necessary core/non-core separation or cut elimination properties). These new systems allow the interpolation results to be extended from linear and classical logic to these modal logics.
Modularity of Proof:
The methodology establishes a modular structure for interpolation proofs. Because the core fragment satisfies the generalized splitting lemma independently of the non-core fragment, minor changes to the proof system (e.g., adding new modalities or structural rules) do not require a complete re-derivation of the interpolation theorem, provided the core/non-core separation is maintained.

Results

The paper successfully demonstrates the flexibility of the approach by applying it to:

Linear Logic: Proving interpolation for systems including multiplicative, additive, and exponential fragments (MELL).
Classical Logic: Showing that the results for linear logic imply results for classical logic via a translation, and providing a direct proof for the system SKS.
Modal Logics: Establishing interpolation for K, KT, K4, and S4 using the newly designed proof systems.

In all cases, the method yields a Lyndon interpolant (preserving the polarity of propositional symbols) and constructs explicit derivations for the interpolant's implications. The paper also notes that the decomposition into up- and down-fragments entails cut elimination in two ways: directly (if the premise is the unit) and via a "flipping" operation that constructs a cut-free derivation of the implication.

Significance and Claims

The paper claims that its primary significance lies in modularity. Citing Girard's observation that the lack of modularity is a major limitation in current proof theory, the author argues that traditional methods (like Maehara's) force a "redo from scratch" whenever a proof system is modified. In contrast, the deep inference approach presented here isolates the logical core from structural rules, allowing interpolation proofs to be robust against system variations.

The author also highlights that the method reveals a deeper connection between interpolation and cut elimination. The decomposition theorem suggests that interpolation is a particular case of an "inverse cut elimination," where the interpolant acts as a bridge between the up-fragment (cut introduction) and the down-fragment (cut elimination).

Finally, the paper positions this work as a step toward understanding interpolation in logics where no sequent calculus exists, suggesting that the core/non-core separation might be a general criterion for the existence of interpolation in other logical systems. The author modestly notes that while the method is powerful, it currently relies on specific design choices in the inference rules (such as the inclusion of $p'_{\downarrow}$ ) to achieve the necessary decomposition, and further work is needed to extend these results to first-order logic and other modal logics.