ML Anthology

Query-Based Entailment and Inseparability for ALC Ontologies

Elena Botoeva, Carsten Lutz, Vladislav Ryzhikov, Frank Wolter, Michael Zakharyaschev
IJCAI 2016 pp. 1001-1007
/ijcai/2016/botoeva2016ijcai-query/

Abstract

We investigate the problem whether two ALC knowledge bases are indistinguishable by queries over a given vocabulary. We give model-theoretic criteria and prove that this problem is undecidable for conjunctive queries (CQs) but decidable in 2EXPTIME for unions of rooted CQs. We also consider the problem whether two ALC TBoxes give the same answers to any query in a given vocabulary over all ABoxes, and show that for CQs this problem is undecidable, too, but becomes decidable and 2EXPTIME-complete in Horn-ALC, and even EXPTIME-complete in Horn-ALC when restricted to (unions of) rooted CQs. PDF

PDF IJCAI Semantic Scholar

Cite

Text

Botoeva et al. "Query-Based Entailment and Inseparability for ALC Ontologies." International Joint Conference on Artificial Intelligence, 2016.

Markdown

[Botoeva et al. "Query-Based Entailment and Inseparability for ALC Ontologies." International Joint Conference on Artificial Intelligence, 2016.](https://mlanthology.org/ijcai/2016/botoeva2016ijcai-query/)

BibTeX

@inproceedings{botoeva2016ijcai-query,
  title     = {{Query-Based Entailment and Inseparability for ALC Ontologies}},
  author    = {Botoeva, Elena and Lutz, Carsten and Ryzhikov, Vladislav and Wolter, Frank and Zakharyaschev, Michael},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2016},
  pages     = {1001-1007},
  url       = {https://mlanthology.org/ijcai/2016/botoeva2016ijcai-query/}
}