257 citations · 486 across the 35 of their papers we have counts for
4 papers · 1 filter
Ontology-Mediated Queries: Combined Complexity and Succinctness of Rewritings via Circuit Complexity
Meghyn Bienvenu, Stanislav Kikot, Roman Kontchakov +2
We give solutions to two fundamental computational problems in ontology-based data access with the W3C standard ontology language OWL 2 QL: the succinctness problem for first-order…
Theoretically Optimal Datalog Rewritings for OWL 2 QL Ontology-Mediated Queries
Meghyn Bienvenu, Stanislav Kikot, Roman Kontchakov +2
We show that, for OWL 2 QL ontology-mediated queries with (i) ontologies of bounded depth and conjunctive queries of bounded treewidth, (ii) ontologies of bounded depth and bounded…
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…