Explanipedia

Deciding the Existence of Interpolants and Definitions in First-Order Modal Logic Open

Agi Kurucz, Frank Wolter, Michael Zakharyaschev · 2025

None of the first-order modal logics between $\mathsf{K}$ and $\mathsf{S5}$ under the constant domain semantics enjoys Craig interpolation or projective Beth definability, even in the language restricted to a single individual variable. It…

From Interpolating Formulas to Separating Languages and Back Again Open

Agi Kurucz, Frank Wolter, Michael Zakharyaschev · 2025

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 has a Craig interpolant and (b) designing algorithms that …

On Deciding the Data Complexity of Answering Linear Monadic Datalog Queries with LTL Operators Open

Alessandro Artale, Anton Gnatenko, Vladislav Ryzhikov, Michael Zakharyaschev · 2025

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 observe that, for data complexity, answering any connected qu…

Interpolant Existence is Undecidable for Two-Variable First-Order Logic with Two Equivalence Relations Open

Frank Wolter, Michael Zakharyaschev · 2024

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 entails I and I entails Q in L. If L enjoys the Craig inter…

The interpolant existence problem for weak K4 and difference logic Open

Agi Kurucz, Frank Wolter, Michael Zakharyaschev · 2024

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 have an interpolant in these logics. We show that the nonexist…

A non-uniform view of Craig interpolation in modal logics with linear frames Open

Agi Kurucz, Frank Wolter, Michael Zakharyaschev · 2023

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 this `negative' fact into a research question and pursue a…

Reverse Engineering of Temporal Queries Mediated by LTL Ontologies Open

Marie Fortin, Boris Konev, Vladislav Ryzhikov, Yury Savateev, Frank Wolter , et al. · 2023

In reverse engineering of database queries, we aim to construct a query from a given set of answers and non-answers; it can then be used to explore the data further or as an explanation of the answers and non-answers. We investigate this q…

Definitions and (Uniform) Interpolants in First-Order Modal Logic Open

Agi Kurucz, Frank Wolter, Michael Zakharyaschev · 2023

We first consider two decidable fragments of quantified modal logic S5: the one-variable fragment and its extension S5ALC that combines S5 and the description logic ALC with the universal role. As neither of them enjoys Craig interpolation…

Unique Characterisability and Learnability of Temporal Queries Mediated by an Ontology Open

Jean Christoph Jung, Vladislav Ryzhikov, Frank Wolter, Michael Zakharyaschev · 2023

Algorithms for learning database queries from examples and unique characterisations of queries by examples are prominent starting points for developing automated support for query construction and explanation. We investigate how far recent…

Reverse Engineering of Temporal Queries Mediated by LTL Ontologies Open

Marie Fontin, Boris Konev, Vladislav Ryzhikov, Yury Savateev, Frank Wolter , et al. · 2023

In reverse engineering of database queries, we aim to construct a query from a given set of answers and non-answers; it can then be used to explore the data further or as an explanation of the answers and non-answers. We investigate this q…

Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic Open

Agi Kurucz, Vladislav Ryzhikov, Yury Savateev, Michael Zakharyaschev · 2023

Our concern is the problem of determining the data complexity of answering an ontology-mediated query (OMQ) formulated in linear temporal logic LTL over (Z,<) and deciding whether it is rewritable to an FO(<)-query, possibly with some extr…

Deciding the Existence of Interpolants and Definitions in First-Order Modal Logic Open

Agi Kurucz, Frank Wolter, Michael Zakharyaschev · 2023

None of the first-order modal logics between $\mathsf{K}$ and $\mathsf{S5}$ under the constant domain semantics enjoys Craig interpolation or projective Beth definability, even in the language restricted to a single individual variable. It…

First-Order Rewritability and Complexity of Two-Dimensional Temporal Ontology-Mediated Queries Open

Alessandro Artale, Roman Kontchakov, Alisa Kovtunova, Vladislav Ryzhikov, Frank Wolter , et al. · 2022

Aiming at ontology-based data access to temporal data, we design two-dimensional temporal ontology and query languages by combining logics from the (extended) DL-Lite family with linear temporal logic LTL over discrete time (Z,<). Our main…

Deciding FO-rewritability of regular languages and ontology-mediated queries in Linear Temporal Logic Open

Agi Kurucz, Vladislav Ryzhikov, Yury Savateev, Michael Zakharyaschev · 2022

Our concern is the problem of determining the data complexity of answering an ontology-mediated query (OMQ) formulated in linear temporal logic LTL over (Z,<) and deciding whether it is rewritable to an FO(<)-query, possibly with some extr…

Unique Characterisability and Learnability of Temporal Instance Queries Open

Marie Fortin, Boris Konev, Vladislav Ryzhikov, Yury Savateev, Frank Wolter , et al. · 2022

We aim to determine which temporal instance queries can be uniquely characterised by a (polynomial-size) set of positive and negative temporal data examples. We start by considering queries formulated in fragments of propositional linear t…

On the First-Order Rewritability of Ontology-Mediated Queries in Linear Temporal Logic (Extended Abstract) Open

Alessandro Artale, Roman Kontchakov, Alisa Kovtunova, Vladislav Ryzhikov, Frank Wolter , et al. · 2022

We argue that linear temporal logic LTL in tandem with monadic first-order logic can be used as a ba- sic language for ontology-based access to tempo- ral data and obtain a classification of the resulting ontology-mediated queries accordin…

A tetrachotomy of ontology-mediated queries with a covering axiom Open

Olga Gerasimova, Stanislav Kikot, Agi Kurucz, Vladimir V. Podolskii, Michael Zakharyaschev · 2022

Our concern is the problem of efficiently determining the data complexity of answering queries mediated by description logic ontologies and constructing their optimal rewritings to standard database queries. Originated in ontology-based da…

Unique Characterisability and Learnability of Temporal Instance Queries Open

Marie Fortin, Boris Konev, Vladislav Ryzhikov, Yury Savateev, Frank Wolter , et al. · 2022

We aim to determine which temporal instance queries can be uniquely characterised by a (polynomial-size) set of positive and negative temporal data examples. We start by considering queries formulated in fragments of propositional linear t…

First-Order Rewritability and Complexity of Two-Dimensional Temporal\n Ontology-Mediated Queries Open

Alessandro Artale, Roman Kontchakov, Alisa Kovtunova, Vladislav Ryzhikov, Frank Wolter , et al. · 2021

Aiming at ontology-based data access to temporal data, we design\ntwo-dimensional temporal ontology and query languages by combining logics from\nthe (extended) DL-Lite family with linear temporal logic LTL over discrete time\n(Z,<). Our m…

First-Order Rewritability and Complexity of Two-Dimensional Temporal Ontology-Mediated Queries Open

Alessandro Artale, Roman Kontchakov, Alisa Kovtunova, Vladislav Ryzhikov, Frank Wolter , et al. · 2021

Aiming at ontology-based data access to temporal data, we design two-dimensional temporal ontology and query languages by combining logics from the (extended) DL-Lite family with linear temporal logic LTL over discrete time (Z,<). Our main…

First-order rewritability of ontology-mediated queries in linear temporal logic Open

Alessandro Artale, Roman Kontchakov, Alisa Kovtunova, Vladislav Ryzhikov, Frank Wolter , et al. · 2021

Deciding FO-Rewritability of Ontology-Mediated Queries in Linear Temporal Logic Open

Vladislav Ryzhikov, Yury Savateev, Michael Zakharyaschev · 2021

Our concern is the problem of determining the data complexity of answering an ontology-mediated query (OMQ) given in linear temporal logic LTL over (ℤ, <) and deciding whether it is rewritable to an FO(<)-query, possibly with extra predica…

Deciding FO-definability of Regular Languages Open

Agi Kurucz, Vladislav Ryzhikov, Yury Savateev, Michael Zakharyaschev · 2021

A Data Complexity and Rewritability Tetrachotomy of Ontology-Mediated Queries with a Covering Axiom Open

Olga Gerasimova, Stanislav Kikot, Agi Kurucz, Vladimir V. Podolskii, Michael Zakharyaschev · 2020

Aiming to understand the data complexity of answering conjunctive queries mediated by an axiom stating that a class is covered by the union of two other classes, we show that deciding their first-order rewritability is PSPACE-hard and obta…

Boolean Role Inclusions in DL-Lite With and Without Time Open

Roman Kontchakov, Vladislav Ryzhikov, Frank Wolter, Michael Zakharyaschev · 2020

Traditionally, description logic has focused on representing and reasoning about classes rather than relations (roles), which has been justified by the deterioration of the computational properties if expressive role inclusions are added. …

A tetrachotomy of ontology-mediated queries with a covering axiom Open

Olga Gerasimova, Stanislav Kikot, Agi Kurucz, Vladimir V. Podolskii, Michael Zakharyaschev · 2020

Our concern is the problem of efficiently determining the data complexity of answering queries mediated by description logic ontologies and constructing their optimal rewritings to standard database queries. Originated in ontology-based da…

Data Complexity and Rewritability of Ontology-Mediated Queries in Metric Temporal Logic under the Event-Based Semantics Open

Vladislav Ryzhikov, Przemysław Andrzej Wałęga, Michael Zakharyaschev · 2019

We investigate the data complexity of answering queries mediated by metric temporal logic ontologies under the event-based semantics assuming that data instances are finite timed words timestamped with binary fractions. We identify classes…

Model Comparison Games for Horn Description Logics Open

Jean Christoph Jung, Fabio Papacchini, Frank Wolter, Michael Zakharyaschev · 2019

Horn description logics are syntactically defined fragments of standard description logics that fall within the Horn fragment of first-order logic and for which ontology-mediated query answering is in PTime for data complexity. They were i…

Data Complexity and Rewritability of Ontology-Mediated Queries in Metric Temporal Logic under the Event-Based Semantics (Full Version) Open

Vladislav Ryzhikov, Przemysław Andrzej Wałęga, Michael Zakharyaschev · 2019

We investigate the data complexity of answering queries mediated by metric temporal logic ontologies under the event-based semantics assuming that data instances are finite timed words timestamped with binary fractions. We identify classes…

Ontology–based access to temporal data with Ontop: A framework proposal Open

Elem Güzel Kalaycı, Sebastian Brandt, Diego Calvanese, Vladislav Ryzhikov, Guohui Xiao , et al. · 2019

Predictive analysis gradually gains importance in industry. For instance, service engineers at Siemens diagnostic centres unveil hidden knowledge in huge amounts of historical sensor data and use it to improve the predictive systems analys…

Michael Zakharyaschev YOU? Author Swipe