Conservative Extensions in Horn Description Logics with Inverse Roles
Authors: Jean Christoph Jung, Carsten Lutz, Mauricio Martel, Thomas Schneider
JAIR 2020 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 that the answers to all conjunctive queries are left unchanged, and deductive conservative extensions, which require that the entailed concept inclusions, role inclusions, and functionality assertions do not change. Upper bounds for query conservative extensions are particularly challenging because characterizations in terms of unbounded homomorphisms between universal models, which are the foundation of the standard approach to establishing decidability, fail in the presence of inverse roles. We resort to a characterization that carefully mixes unbounded and bounded homomorphisms and enables a decision procedure that combines tree automata and a mosaic technique. Our main results are that query conservative extensions are 2Exp Time-complete in all DLs between ELI and Horn-ALCHIF and between Horn-ALC and Horn-ALCHIF, and that deductive conservative extensions are 2Exp Time-complete in all DLs between ELI and ELHIF . The same results hold for inseparability and entailment. |
| Researcher Affiliation | Academia | Jean Christoph Jung EMAIL Carsten Lutz EMAIL Mauricio Martel EMAIL Thomas Schneider EMAIL Fachbereich 3 Mathematik/Informatik Universität Bremen Postfach 330 440, 28334 Bremen, Germany |
| Pseudocode | No | The paper describes theoretical results, characterizations, and decision procedures using mathematical notation and logical formalism. It does not include any explicitly labeled pseudocode or algorithm blocks with structured steps formatted like code. |
| Open Source Code | No | The paper does not contain any statement about releasing source code, nor does it provide links to a code repository. The research is theoretical, focusing on decidability and complexity. |
| Open Datasets | No | The paper is theoretical and focuses on description logics and query entailment. It mentions 'ontology-mediated querying' and 'data integration context' in a conceptual sense, but does not use or refer to any specific datasets for experimental evaluation. |
| Dataset Splits | No | The paper does not describe any experiments or empirical studies that would involve datasets, and therefore no dataset splits are mentioned. |
| Hardware Specification | No | The paper presents theoretical work on decidability and computational complexity in description logics. It does not describe any experimental evaluations requiring specific hardware. |
| Software Dependencies | No | The paper focuses on theoretical computer science, specifically on decidability and computational complexity. It does not describe an implementation or experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical, dealing with logical formalisms, decidability, and complexity. It does not describe any experiments or their setup, including hyperparameters or training configurations. |