27 citations · 58 across the 16 of their papers we have counts for
18 papers
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…
Reverse Engineering of Temporal Queries Mediated by LTL Ontologies
Marie Fortin, Boris Konev, Vladislav Ryzhikov +3
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 explan…
Deciding FO-rewritability of regular languages and ontology-mediated queries in Linear Temporal Logic
Agi Kurucz, Vladislav Ryzhikov, Yury Savateev +1
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…
Unique Characterisability and Learnability of Temporal Instance Queries
Marie Fortin, Boris Konev, Vladislav Ryzhikov +3
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 considerin…
First-Order Rewritability and Complexity of Two-Dimensional Temporal Ontology-Mediated Queries
Alessandro Artale, Roman Kontchakov, Alisa Kovtunova +3
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 l…
Deciding FO-definability of regular languages
Agi Kurucz, Vladislav Ryzhikov, Yury Savateev +1
We prove that, similarly to known PSpace-completeness of recognising FO(<)-definability of the language L(A) of a DFA A, deciding both FO(<,C)- and FO(<,MOD)-definability are PSpac…
First-Order Rewritability of Ontology-Mediated Queries in Linear Temporal Logic
Alessandro Artale, Roman Kontchakov, Alisa Kovtunova +3
We investigate ontology-based data access to temporal data. We consider temporal ontologies given in linear temporal logic LTL interpreted over discrete time (Z,<). Queries are giv…
Data Complexity and Rewritability of Ontology-Mediated Queries in Metric Temporal Logic under the Event-Based Semantics (Full Version)
Vladislav Ryzhikov, Przemyslaw Andrzej Walega, Michael Zakharyaschev
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 w…
Query Inseparability for ALC Ontologies
Elena Botoeva, Carsten Lutz, Vladislav Ryzhikov +2
We investigate the problem whether two ALC ontologies are indistinguishable (or inseparable) by means of queries in a given signature, which is fundamental for ontology engineering…
Inseparability and Conservative Extensions of Description Logic Ontologies: A Survey
Elena Botoeva, Boris Konev, Carsten Lutz +3
The question whether an ontology can safely be replaced by another, possibly simpler, one is fundamental for many ontology engineering and maintenance tasks. It underpins, for exam…
Querying Log Data with Metric Temporal Logic (Technical Report)
Sebastian Brandt, Elem Güzel Kalaycı, Vladislav Ryzhikov +2
We propose a novel framework for ontology-based access to temporal log data using a datalog extension datalogMTL of a Horn fragment of the metric temporal logic MTL. We show that d…
The Complexity of Ontology-Based Data Access with OWL 2 QL and Bounded Treewidth Queries
Meghyn Bienvenu, Stanislav Kikot, Roman Kontchakov +3
Our concern is the overhead of answering OWL 2 QL ontology-mediated queries (OMQs) in ontology-based data access compared to evaluating their underlying tree-shaped and bounded tre…
Metric Temporal Logic for Ontology-Based Data Access over Log Data
Diego Calvanese, Elem Güzel Kalaycı, Vladislav Ryzhikov +2
We present a new metric temporal logic HornMTL over dense time and its datalog extension datalogMTL. The use of datalogMTL is demonstrated in the context of ontology-based data acc…
Query-Based Entailment and Inseparability for ALC Ontologies (Full Version)
Elena Botoeva, Carsten Lutz, Vladislav Ryzhikov +2
We investigate the problem whether two ALC knowledge bases are indistinguishable by queries over a given vocabulary. We give model-theoretic criteria in terms of (partial) homomorp…
Horn Fragments of the Halpern-Shoham Interval Temporal Logic (Technical Report)
Davide Bresolin, Agi Kurucz, Emilio Muñoz-Velasco +3
We investigate the satisfiability problem for Horn fragments of the Halpern-Shoham interval temporal logic depending on the type (box or diamond) of the interval modal operators, t…
The Complexity of Clausal Fragments of LTL
A. Artale, R. Kontchakov, V. Ryzhikov +1
We introduce and investigate a number of fragments of propo- sitional temporal logic LTL over the flow of time (Z, <). The fragments are defined in terms of the available temporal…
A Cookbook for Temporal Conceptual Data Modelling with Description Logics
Alessandro Artale, Roman Kontchakov, Vladislav Ryzhikov +1
We design temporal description logics suitable for reasoning about temporal conceptual data models and investigate their computational complexity. Our formalisms are based on DL-Li…