A New n-ary Existential Quantifier in Description Logics

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche

Toggle side column

A New n-ary Existential Quantifier in Description Logics

Franz BaaderFranz Baader,  Carsten LutzCarsten Lutz,  Eldar KarabaevEldar Karabaev,  Manfred TheißenManfred Theißen
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
  • 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},
}