ML Anthology

Query Conservative Extensions in Horn Description Logics with Inverse Roles

Jean Christoph Jung, Carsten Lutz, Mauricio Martel, Thomas Schneider
IJCAI 2017 pp. 1116-1122
doi:10.24963/IJCAI.2017/155 /ijcai/2017/jung2017ijcai-query/

Abstract

We investigate the decidability and computational complexity of query conservative extensions in Horn description logics (DLs) with inverse roles. This is more challenging than without inverse roles because characterizations in terms of unbounded homomorphisms between universal models fail, blocking the standard approach to establishing decidability. We resort to a combination of automata and mosaic techniques, proving that the problem is 2EXPTIME-complete in Horn-ALCHIF (and also in Horn-ALC and in ELI). We obtain the same upper bound for deductive conservative extensions, for which we also prove a coNEXPTIME lower bound.

PDF IJCAI Semantic Scholar

Cite

Text

Jung et al. "Query Conservative Extensions in Horn Description Logics with Inverse Roles." International Joint Conference on Artificial Intelligence, 2017. doi:10.24963/IJCAI.2017/155

Markdown

[Jung et al. "Query Conservative Extensions in Horn Description Logics with Inverse Roles." International Joint Conference on Artificial Intelligence, 2017.](https://mlanthology.org/ijcai/2017/jung2017ijcai-query/) doi:10.24963/IJCAI.2017/155

BibTeX

@inproceedings{jung2017ijcai-query,
  title     = {{Query Conservative Extensions in Horn Description Logics with Inverse Roles}},
  author    = {Jung, Jean Christoph and Lutz, Carsten and Martel, Mauricio and Schneider, Thomas},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2017},
  pages     = {1116-1122},
  doi       = {10.24963/IJCAI.2017/155},
  url       = {https://mlanthology.org/ijcai/2017/jung2017ijcai-query/}
}