Foundations for Uniform Interpolation and Forgetting in Expressive Description Logics

Lutz, Carsten; Wolter, Frank

doi:10.5591/978-1-57735-516-8/IJCAI11-170

Foundations for Uniform Interpolation and Forgetting in Expressive Description Logics

Carsten Lutz, Frank Wolter

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 989-994.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-170

Abstract

We study uniform interpolation and forgetting in the description logic ALC. Our main results are model-theoretic characterizations of uniform interpolants and their existence in terms of bisimulations, tight complexity bounds for deciding the existence of uniform interpolants, an approach to computing interpolants when they exist, and tight bounds on their size. We use a mix of model-theoretic and automata-theoretic methods that, as a by-product, also provides charachterizations of, and decision procedures for, conservative extensions.

Carsten Lutz, and Frank Wolter. 2011. Foundations for Uniform Interpolation and Forgetting in Expressive Description Logics. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 989–994. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-170

@inproceedings{ijcai2011p170,
  title     = {Foundations for Uniform Interpolation and Forgetting in Expressive Description Logics},
  author    = {Lutz, Carsten and Wolter, Frank},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {989--994},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-170},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-170},
}

TY  - CPAPER
TI  - Foundations for Uniform Interpolation and Forgetting in Expressive Description Logics
AU  - Lutz, Carsten
AU  - Wolter, Frank
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 989
EP  - 994
DO  - 10.5591/978-1-57735-516-8/IJCAI11-170
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-170
ER  -