The Complexity of Reasoning with Cardinality Restrictions and Nominals
  in Expressive Description Logics
  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 for ALCQ extended with
nominals. 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 pure concept satisfiability for
ALCQI with nominals is NExpTime-complete. Without nominals, this problem is
known to be PSpace-complete.
