A New n-ary Existential Quantifier in Description Logics

Franz BaaderFranz Baader, Carsten LutzCarsten Lutz, Eldar KarabaevEldar Karabaev, Manfred TheißenManfred Theißen

Download

Franz Baader, Carsten Lutz, Eldar Karabaev, Manfred Theißen
A New n-ary Existential Quantifier in Description Logics
Proceedings of the 28th Annual German Conference on Artificial Intelligence, KI 2005, volume 3698 of Lecture Notes in Artificial Intelligence, 18-33, 2005. Springer

Details
Bibtex

KurzfassungAbstract
Motivated by a chemical process engineering application, we introduce a new concept constructor in Description Logics (DLs), an n-ary variant of the existential restriction constructor, which generalizes both the usual existential restrictions and so-called qualified number restrictions. We show that the new constructor can be expressed in ALCQ, the extension of the basic DL ALC by qualified number restrictions. However, this representation results in an exponential blow-up. By giving direct algorithms for ALC extended with the new constructor, we can show that the complexity of reasoning in this new DL is actually not harder than the one of reasoning in ALCQ. Moreover, in our chemical process engineering application, a restricted DL that provides only the new constructor together with conjunction, and satisfies an additional restriction on the occurrence of roles names, is sufficient. For this DL, the subsumption problem is polynomial.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

The final publication is available at Springer.

@inproceedings{ BaaderEtAlKI05,
  author = {Franz {Baader} and Carsten {Lutz} and Eldar {Karabaev} and Manfred {Thei{\ss}en}},
  booktitle = {Proceedings of the 28th Annual German Conference on Artificial Intelligence, {KI 2005}},
  pages = {18--33},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Artificial Intelligence},
  title = {A New $n$-ary Existential Quantifier in Description Logics},
  volume = {3698},
  year = {2005},
}