Horn-Rewritability vs PTime Query Evaluation in Ontology-Mediated Querying
Authors: Andre Hernich, Carsten Lutz, Fabio Papacchini, Frank Wolter
IJCAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we ask the converse question: Assume that a TBox T is formulated in an expressive DL L and admits PTIME query evaluation. Does it follow that T can be replaced by a TBox T formulated in the corresponding Horn-DL without affecting the answers to queries? Let us make this more precise. We concentrate on queries that are conjunctive queries (CQ) since these are widely used in ontology-mediated querying and require T and T to be CQ-inseparable, that is, to give exactly the same answers to any CQ on any ABox, see [Lutz and Wolter, 2010; Botoeva et al., 2016a; 2016b]. We say that an L TBox T is CQ-Horn-rewritable if there is a TBox T formulated in Horn-L that is CQ-inseparable from T . The main property of an expressive DL L that we are interested in is then whether CQ-Horn-rewritability captures PTIME query evaluation, that is, whether every L TBox that enjoys PTIME CQ-evaluation is CQ-Horn-rewritable. |
| Researcher Affiliation | Academia | 1 University of Liverpool, UK 2 University of Bremen, Germany {hernich,papacchf,wolter}@liverpool.ac.uk, clu@uni-bremen.de |
| Pseudocode | No | The paper does not contain structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not involve training models on datasets for experimental evaluation. |
| Dataset Splits | No | The paper is theoretical and does not involve dataset splits for validation. |
| Hardware Specification | No | The paper does not provide specific hardware details used for running experiments, as it is a theoretical paper. |
| Software Dependencies | No | The paper does not provide specific ancillary software details with version numbers, as it is a theoretical paper. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or training configurations. |