5 papers
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…
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…
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…