Lics

ACM/IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

Forty-First Annual Symposium on

Logic in Computer Science (LICS 2026)

Paper: Computation and Size of Interpolants for Hybrid Modal Logics (at LICS 2026)

Authors: Jean Christoph Jung Jędrzej Kołodziejski Frank Wolter

Open access: https://doi.org/10.4230/LIPIcs.LICS.2026.60

Abstract

Recent research has established complexity results for the problem of deciding the existence of interpolants in logics lacking the Craig interpolation property (CIP). The proof techniques developed so far are non-constructive, and no meaningful bounds on the size of interpolants are known. Hybrid modal logics (or modal logics with nominals) are a particularly interesting class of logics without CIP: in their case, CIP cannot be restored without sacrificing decidability and, in applications, interpolants in these logics can serve as definite descriptions and separators between positive and negative data examples in description logic knowledge bases. In this contribution we show, using a new hypermosaic elimination technique, that in many standard hybrid modal logics Craig interpolants can be computed in fourfold exponential time, if they exist. On the other hand, we show that the existence of uniform interpolants is undecidable, which is in stark contrast to modal or intuitionistic logic where uniform interpolants always exist.

BibTeX

  @InProceedings{JungKolodziejskiWol-ComputationandSizeo,
    author = 	 {Jean Christoph Jung and Jędrzej Kołodziejski and Frank Wolter},
    title = 	 {Computation and Size of Interpolants for Hybrid Modal Logics},
    booktitle =  {Proceedings of the Forty-First Annual Symposium on Logic in Computer Science (LICS 2026)},
    year =	 {2026},
    month =	 {July}, 
    pages =      {60:1--60:27},
    location =   {Lisbon, Portugal}, 
    publisher =	 {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
    doi =        {10.4230/LIPIcs.LICS.2026.60}
  }
   

Last modified: 2026-09-2114:25
Sam Staton