In [De 95] complexity results for various DLs are obtained by sophisticated polynomial reduction to a propositional dynamic logic. The author establishes many complexity results, one of which is of special interest for our purposes.

The DL studied by the author is a strict extension of ; TBoxes in his thesis correspond to what we call in this paper. Unary coding of numbers is assumed 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.

Together with Theorem 4.5, this solves the open problem concerning the lower bound for the complexity of with cardinality restrictions; moreover, it shows that the -algorithm presented in [BBH96] is not optimal with respect to worst case complexity.

May 02 2000