Computation and Size of Interpolants for Hybrid Modal Logics
Jean Christoph Jung, Jędrzej Kołodziejski, Frank Wolter · 2026
Read Computation and Size of Interpolants for Hybrid Modal Logics by Jean Christoph Jung, Jędrzej Kołodziejski, Frank Wolter (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-15821.txt.
Description
Jung and colleagues study interpolants for hybrid modal logics, modal logics with nominals. Recent research has established cost results for deciding whether they exist in logics lacking the Craig Interpolation Property. Proof techniques so far are non-constructive, with no meaningful bounds on their size known. Hybrid modal logics are a prime class without that property. In their case, the property cannot be regained without losing decidability. In uses, they can serve as exact descriptions and splits between positive and negative examples.
Using a new hypermosaic removal method, the authors show that in many usual hybrid modal logics, Craig interpolants can be computed in fourfold exponential time, if they exist. Existence of uniform interpolants, by contrast, is undecidable. That clashes hard with modal or intuitionistic logic, where uniform ones always exist. The paper thus gives the first built bounds for a long non-constructive area, plus that result.
Catalog record
| CREATOR | Jean Christoph Jung, Jędrzej Kołodziejski, Frank Wolter |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 161 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-15821