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
Technical Report, Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology, volume LTCS-05-08, 2005. LTCS-Report

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.
Bemerkung: Note: See http://lat.inf.tu-dresden.de/research/reports.html.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@techreport{ BaaderEtAll-LTCS-05-08,
  address = {Germany},
  author = {Franz {Baader} and Carsten {Lutz} and Eldar {Karabaev} and Manfred {Thei{\ss}en}},
  institution = {Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology},
  note = {See http://lat.inf.tu-dresden.de/research/reports.html.},
  number = {LTCS-05-08},
  title = {A New $n$-ary Existential Quantifier in Description Logics},
  type = {LTCS-Report},
  year = {2005},
}