throughout his thesis.  Although a unique name assumption is made, it is not inherent to the utilised reduction since is explicitly enforced. It is thus possible to eliminate the propositions that require a unique interpretation of individuals from the reduction. Hence, together with Lemma 4.2, we get the following corollary.

## Corollary 4.7

Consistency of ACCO-T 1 Boxes is E XP T IME -complete if unary coding of number is assumed.

Together with Theorem 4.5, this solves the open problem concerning the lower bound for the complexity of ALCQ with cardinality restrictions; moreover, it shows that the NEXP-
TIME-algorithm presented in (Baader et al., 1996) is not optimal with respect to worst case complexity.

Corollary 4.8 Consistency of ACCQ-T c Boxes is E XP T IME -complete, if unary coding of numbers in cardinlity and number restrictions is used.

## 4.2.2 Alcolo

Conversely, using Theorem 4.5 enables us to transfer the NEXPTIME-completeness result from Theorem 3.8 to ALCQIO.

## Corollary 4.9

Consistency of ALCQIO -T 1 Boxes or T C Boxes is NEXP T IME -complete. Proof.  For T t Boxes, this is an immediate corollary of Theorem 4.5 and Theorem 3.8.

Reasoning with T C Boxes is as hard as for T t Boxes in the presences of nominals.

This results explains a gap in (De Giacomo, 1995). There the author establishes the complexity of satisfiability of knowledge bases consisting of T i Boxes and ABoxes both for CNO , which allows for qualifying number restrictions, and for CIO , which allows for inverse roles, by reduction to an EXPTIME-complete PDL. No results are given for the combination CINO, which is a strict extension of ACCOIO.  Corollary 4.8 shows that, assuming EXPTIME ̸= NEXPTIME, there cannot be a polynomial reduction from the satisfiability problem of CINO knowledge bases to an EXPTIME-complete PDL. Again, a possible explantion for this leap in complexity is the loss of the tree model property. While for CIO and CNO , consistency is decided by searching for a tree-like pseudo-models even in the presence of nominals, this seems no longer to be possible in the case of knowledge bases for CINO. Unique Name Assumption It should be noted that our definition of nominals is nonstandard for Description Logics in the sense that we do not impose the unique name assumption that is widely made, i.e., for any two individual names o 1 , o 2 E N 1 , o 7 F o 7 is required. Even without a unique name assumption, it is possible to enforce distinct interpretation of nominals by adding axioms of the form o 1 nme assumption in the presence of inverse roles and number restriction leads to peculiar effects. Consider the following T 1 Box:

$$T\,=\,\{o\,\sqsubseteq(\leqslant\,k\;R\,\top),\;\;\top\,\sqsubseteq\exists R^{-}\,.o\}$$
