💻 computer science

Computation and Size of Interpolants for Hybrid Modal Logics

This paper introduces a new hypermosaic elimination technique to prove that Craig interpolants in standard hybrid modal logics can be computed in fourfold exponential time, while simultaneously demonstrating that the existence of uniform interpolants in these logics is undecidable.

Original authors: Jean Christoph Jung, Jędrzej Kołodziejski, Frank Wolter

Published 2026-05-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jean Christoph Jung, Jędrzej Kołodziejski, Frank Wolter

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

The Big Picture: The "Translator" Problem

Imagine you have two people, Alice and Bob, speaking different languages.

Alice says: "The red key opens the door to the garden."
Bob says: "The garden is safe only if the door is locked."
Together, they imply: "The red key implies the door is locked."

A Craig Interpolant is like a translator who creates a new sentence that:

Uses only words both Alice and Bob understand (the "shared vocabulary").
Is something Alice would agree is true.
Is something Bob would agree follows from that truth.

In this example, the translator might say: "The red key leads to a locked door." This sentence bridges the gap without using Alice's specific word "garden" or Bob's specific word "safe."

The Problem: When Translation Fails

In many logical systems (like standard math or computer logic), you can always find a translator (an interpolant) if the logic holds together. This is called the Craig Interpolation Property (CIP).

However, this paper focuses on a specific, tricky family of logics called Hybrid Modal Logics. Think of these as languages that have "pointers" or "names" for specific locations (like saying "Here is the red key" pointing to a specific spot).

The Bad News: In these specific logics, a perfect translator doesn't always exist. Sometimes, Alice and Bob's statements are compatible, but there is no single sentence using only their shared words that bridges the gap.
The Catch: You can't just "fix" the language by making it more powerful (adding more words), because that would break the computer's ability to decide if things are true or false (decidability).

The Paper's Main Achievement: Building the Translator (When Possible)

The authors ask: "If a translator does exist for these tricky logics, how hard is it to build one, and how long will the translation be?"

1. The "Four-Story Exponential" Tower
The paper proves that if a translator exists, we can definitely build one. However, the translation might be enormously long.

The Analogy: Imagine you are trying to describe a maze.
- A normal maze might take a paragraph to describe.
- A "double exponential" maze might take a book.
- A "triple exponential" maze might take a library.
- The authors found that for these hybrid logics, the translation can be four times exponential.
- What does that mean? If the input is small (like a sentence of 10 words), the output translation might be so long that it would take more atoms in the universe to write it down. It is computable (we can do it), but it is practically impossible for large inputs.

2. The "Hypermosaic" Method
How did they build this translator? They used a new technique called Hypermosaic Elimination.

The Analogy: Imagine you are trying to prove two puzzle pieces fit together.
- Old Method (Mosaics): You look at two pieces at a time. If they don't fit, you throw them away.
- New Method (Hypermosaics): Sometimes, two pieces look like they fit, but they actually clash with a third piece hidden in the background. The authors realized they had to look at groups of pieces (mosaics) and then groups of groups of pieces (hypermosaics) to see the whole picture.
- They systematically eliminate "impossible" groups until they find the ones that work, and then they construct the translation based on what was eliminated.

The Bad News: Uniform Translators are Impossible

The paper also looks at Uniform Interpolants.

The Analogy: A standard translator (Craig) translates a specific conversation between Alice and Bob. A Uniform translator is like a dictionary that translates any sentence Alice says into a language Bob understands, regardless of what Bob says.
The Result: The authors prove that for these hybrid logics, deciding if a "Universal Dictionary" exists is impossible.
Why it matters: In other logics (like standard modal logic), you can always build this universal dictionary. In these hybrid logics, the computer will run forever trying to figure out if such a dictionary is even possible. It is an undecidable problem.

Summary of Findings

We can build translators: If a "bridge" sentence exists between two statements in these hybrid logics, we can construct it.
It's huge: The bridge might be astronomically large (fourfold exponential size).
We can't build a universal dictionary: We cannot decide if a "one-size-fits-all" translator exists for these logics.
The Method: They used a new "Hypermosaic" technique, which is like checking groups of puzzle pieces rather than just pairs, to find the solution.

Why This Matters (According to the Paper)

The paper mentions that in the real world, these logics are used in Knowledge Bases (like the "brain" of a smart system or a database of facts).

Separators: These translators can act as "separators" to tell the difference between good data and bad data.
Definitions: They can help define what a specific concept means without relying on external, hidden details.

The authors emphasize that while we now know how to build these translators and how big they get, the size is so massive that it highlights a fundamental limit in how efficiently we can reason about these specific types of logical systems.

Technical Summary: Computation and Size of Interpolants for Hybrid Modal Logics

Problem Statement
The paper addresses the computational complexity and construction of Craig interpolants in hybrid modal logics (specifically $H$ , $H@$ , $H@,U$ , and their graded extensions $GHL$). While recent research has established the complexity of deciding the existence of interpolants in logics lacking the Craig Interpolation Property (CIP), the construction of such interpolants remains an open challenge. Existing decision procedures are non-constructive, relying on compactness arguments (e.g., Robinson's joint consistency) rather than providing explicit formulas. Consequently, no meaningful upper bounds on the size of interpolants are known for these logics.

This problem is particularly acute for hybrid modal logics (and description logics with nominals) because:

CIP cannot be restored by adding logical connectives without sacrificing decidability.
Interpolants in these logics have critical applications in knowledge representation, such as explaining modularity violations, separating positive and negative data examples, and providing definite descriptions.

Methodology
The authors introduce a new constructive technique called hypermosaic elimination. This method extends the standard "type elimination" procedure used for satisfiability in modal logics and the "mosaic" approach used for deciding interpolant existence in non-CIP logics.

From Types to Mosaics to Hypermosaics:
- Standard type elimination works with pairs of types.
- Mosaic elimination (used for decision procedures) works with pairs of sets of types to handle non-shared nominals.
- The authors argue that mosaic elimination is too local to compute interpolants because it cannot capture global interactions between different "nominal cases" (scenarios regarding how nominals are interpreted).
- To overcome this, they define hypermosaics: sets of mosaics that must be realized simultaneously in bisimilar models. This structure allows the algorithm to track global constraints across different nominal interpretations.
Elimination Procedure:
- The procedure starts with a set of all $\sigma$ -consistent and nominal-clean hypermosaics.
- It iteratively eliminates hypermosaics that lack a "witness." A witness for a hypermosaic $H$ is an extending hypermosaic $H'$ that satisfies specific coherence conditions (e.g., for graded logics, quantitative constraints on successors must be met via counting functions).
- The procedure stabilizes at a set $Z^*$ of realizable hypermosaics. If the initial hypermosaic containing the input formulas is eliminated, the formulas are not jointly consistent, and an interpolant exists.
Constructive Separator Construction:
- The paper constructs hyperseparators inductively alongside the elimination process.
- A hyperseparator consists of a "case distinction" (exhaustive scenarios for nominal types) and functions mapping types to formulas.
- In each elimination round, the case distinction is refined to capture the "star-types" (local neighborhoods) of the eliminated hypermosaics.
- This construction transforms the non-constructive existence proof into an explicit algorithm that generates the interpolant (or separator).

Key Contributions and Results

Upper Bounds on Size and Complexity:
The primary result (Theorem 1) establishes that for any logic $L \in HL \cup GHL$ , if a Craig interpolant exists for $\phi \to \psi$ , it can be constructed in fourfold exponential time, and the resulting interpolant has a size of fourfold exponential in the size of the input formulas.
- Note: The proof relies on the fact that while there are triply exponentially many hypermosaics, the elimination procedure stabilizes after at most doubly exponentially many rounds due to the monotonicity of witnesses.
Lower Bounds:
The paper provides a triply exponential lower bound on the size of Craig interpolants (and doubly exponential for DAG-size) for logics with the universal modality ( $H@,U$ and $G@,U$ ). This demonstrates that interpolants in hybrid logics are inherently larger than in standard modal logic (where they are typically exponential).
Undecidability of Uniform Interpolants:
In a stark contrast to standard modal and intuitionistic logics (where uniform interpolants always exist and are often constructible), the paper proves (Theorem 3) that the existence of uniform interpolants is undecidable for any logic containing $H$ and contained in First-Order Logic (FO). This is shown via a reduction from the undecidability of defining finite linear orders of even length in FO.
Graded Extensions:
The methodology is successfully extended to graded hybrid logics ($GHL$), which include qualified number restrictions. The authors adapt the witness definition to include counting functions and show that the fourfold exponential upper bound holds for these logics as well.

Significance and Claims
The authors claim to provide the first elementary upper bounds for constructing Craig interpolants in a family of decidable logics where CIP fails and cannot be easily repaired.

Constructive vs. Non-Constructive: The work bridges the gap between knowing that an interpolant exists (decidability) and how to compute it. Previous methods were non-constructive; this paper provides an explicit algorithm.
Robustness: The construction method is shown to be robust under language restrictions (e.g., computing interpolants in a weaker sub-language) and can be adapted to handle standard constraints like transitivity and reflexivity.
Limitations: The paper acknowledges that the exact complexity gap between the fourfold exponential upper bound and the triple exponential lower bound remains open. Furthermore, the extension to inverse relations or the hybrid $\mu$ -calculus remains an open question, as the existence of interpolants in those specific extensions may be undecidable or require non-elementary bounds.

In summary, the paper establishes that while interpolants in hybrid modal logics are computationally expensive (fourfold exponential), they are effectively computable, offering a constructive foundation for applications in knowledge representation that previously relied on non-constructive existence proofs.