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

CREATORJean Christoph Jung, Jędrzej Kołodziejski, Frank Wolter
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE161 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-15821

Browse the full library · About the Tower of Babel