8 papers
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…
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…
Deciding the Existence of Interpolants and Definitions in First-Order Modal Logic
Agi Kurucz, Frank Wolter, Michael Zakharyaschev
None of the first-order modal logics between and under the constant domain semantics enjoys Craig interpolation or projective Beth definability, even in…
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…
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…