Carsten Lutz

Conservative Extensions in Horn Description Logics with Inverse Roles

2020 · arXiv (Cornell University)

We investigate the decidability and computational complexity of conservative extensions and the related notions of inseparability and entailment in Horn description logics (DLs) with inverse roles. We consider both query conservative extensions, defined by requiring …

A Complete Classification of the Complexity and Rewritability of Ontology-Mediated Queries based on the Description Logic EL

2019 · arXiv (Cornell University)

We provide an ultimately fine-grained analysis of the data complexity and rewritability of ontology-mediated queries (OMQs) based on an EL ontology and a conjunctive query (CQ). Our main results are that every such OMQ is …