7 papers
Computation and Size of Interpolants for Hybrid Modal Logics
Jean Christoph Jung, Jędrzej Kołodziejski, Frank Wolter
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 tec…
From Interpolating Formulas to Separating Languages and Back Again
Agi Kurucz, Frank Wolter, Michael Zakharyaschev
Traditionally, research on Craig interpolation is concerned with (a) establishing the Craig interpolation property (CIP) of a logic saying that every valid implication in the logic…
Separation and Definability in Fragments of Two-Variable First-Order Logic with Counting
Louwe Kuijer, Tony Tan, Frank Wolter +1
For fragments L of first-order logic (FO) with counting quantifiers, we consider the definability problem, which asks whether a given L-formula can be equivalently expressed by a f…
Extremal Separation Problems for Temporal Instance Queries
Jean Christoph Jung, Vladislav Ryzhikov, Frank Wolter +1
The separation problem for a class Q of database queries is to find a query in Q that distinguishes between a given set of `positive' and `negative' data examples. Separation provi…
Interpolant Existence is Undecidable for Two-Variable First-Order Logic with Two Equivalence Relations
Frank Wolter, Michael Zakharyaschev
The interpolant existence problem (IEP) for a logic L is to decide, given formulas P and Q, whether there exists a formula I, built from the shared symbols of P and Q, such that P…
The interpolant existence problem for weak K4 and difference logic
Agi Kurucz, Frank Wolter, Michael Zakharyaschev
As well known, weak K4 and the difference logic DL do not enjoy the Craig interpolation property. Our concern here is the problem of deciding whether any given implication does hav…
A non-uniform view of Craig interpolation in modal logics with linear frames
Agi Kurucz, Frank Wolter, Michael Zakharyaschev
Normal modal logics extending the logic K4.3 of linear transitive frames are known to lack the Craig interpolation property, except some logics of bounded depth such as S5. We turn…