Query-Based Entailment and Inseparability for ALC Ontologies

Botoeva, Elena; Lutz, Carsten; Ryzhikov, Vladislav; Wolter, Frank; Zakharyaschev, Michael

Query-Based Entailment and Inseparability for ALC Ontologies

Elena Botoeva, Carsten Lutz, Vladislav Ryzhikov, Frank Wolter, Michael Zakharyaschev

Download BibTeX Cite

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 1001-1006.

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.

Elena Botoeva, Carsten Lutz, Vladislav Ryzhikov, Frank Wolter, and Michael Zakharyaschev. 2016. Query-Based Entailment and Inseparability for ALC Ontologies. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16. IJCAI, 1001–1006. https://ijcai.org/proceedings/2016/146

@inproceedings{ijcai2016p146,
  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 = {Proceedings of the Twenty-Fifth International Joint Conference on
               Artificial Intelligence, {IJCAI-16}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Subbarao Kambhampati},
  pages     = {1001--1006},
  year      = {2016},
  month     = {7},
  url       = {https://ijcai.org/proceedings/2016/146},
}

TY  - CPAPER
TI  - Query-Based Entailment and Inseparability for ALC Ontologies
AU  - Botoeva, Elena
AU  - Lutz, Carsten
AU  - Ryzhikov, Vladislav
AU  - Wolter, Frank
AU  - Zakharyaschev, Michael
T2  - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2016
SP  - 1001
EP  - 1006
UR  - https://ijcai.org/proceedings/2016/146
ER  -