The Complexity of Reasoning with Cardinality Restrictions and Nominals in Expressive Description Logics

Stephan TobiesStephan Tobies

Datei:Tobies-JAIR-2000.ps.gz

Download

Stephan Tobies
The Complexity of Reasoning with Cardinality Restrictions and Nominals in Expressive Description Logics
Journal of Artificial Intelligence Research, 12:199-217, May 2000

Details
Bibtex

KurzfassungAbstract
We study the complexity of the combination of the Description Logics ALCQ and ALCQI with a terminological formalism based on cardinality restrictions on concepts. These combinations can naturally be embedded into C^2, the two variable fragment of predicate logic with counting quantifiers, which yields decidability in NExpTime. We show that this approach leads to an optimal solution for ALCQI, as ALCQI with cardinality restrictions has the same complexity as C^2 (NExpTime-complete). In contrast, we show that for ALCQ, the problem can be solved in ExpTime. This result is obtained by a reduction of reasoning with cardinality restrictions to reasoning with the (in general weaker) terminological formalism of general axioms in the presence of nominals in the language. Using the same reduction, we show that for the extension of ALCQI with nominals reasoning with general axioms is a NExpTime-complete problem. Finally, we sharpen this result and show that already concept satisfiabiliy for ALCQI with nominals is NExpTime-complete. Without nominals, this problem is known to be PSPACE-complete.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@article{ Tobies-JAIR-2000,
  author = {Stephan {Tobies}},
  journal = {Journal of Artificial Intelligence Research},
  month = {May},
  pages = {199--217},
  title = {The Complexity of Reasoning with Cardinality Restrictions and Nominals in Expressive Description Logics},
  volume = {12},
  year = {2000},
}