257 citations · 486 across the 35 of their papers we have counts for
38 papers
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…
On Deciding the Data Complexity of Answering Linear Monadic Datalog Queries with LTL Operators(Extended Version)
Alessandro Artale, Anton Gnatenko, Vladislav Ryzhikov +1
Our concern is the data complexity of answering linear monadic datalog queries whose atoms in the rule bodies can be prefixed by operators of linear temporal logic LTL. We first ob…
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…