
| ACQ                    | AC 20       | ACCL        | ACCOTO            |                     |
|------------------------|-------------|-------------|-------------------|---------------------|
| Concept Satisfiability | PSPACE-C    | open        | PSPACE-C.         | N E XP T I ME - C . |
| GCIs                   | EXP TIME-C. | EXP TIME-C. | E XP T IME - C .  | N E XP T I ME - C . |
| Cardinality Restr.     | EXP TIME-C. | EXP TIME-C. | N E XP T I ME-C . | N E XP T I ME - C . |

## 5. Conclusion

Combining the results from (De Giacomo, 1995) and (Tobies, 2000) with the results from this paper, we obtain the classification of the complexity of concept satisfiability and TBoxconsistency for various DLs and for TBoxes consisting either of cardinality restrictions or of general concept inclusion axioms shown in Figure 4, where we assume unary coding of numbers.

The result for ACCOIO shows that the current efforts of extending very expressive DLs as the logic SHIQ (Horrocks et al., 1999) and DLR (Calvanese et al., 1998c) or propositional dynamic logics as CPDL q (De Giacomo & Lenzerini, 1996) with nominals are difficult tasks, if one wants to obtain a practical decision procedure, since already concept satisfiability for these logics is a NEXPTIME-hard problem.

We have shown that, while having the same complexity as C 2 , ALCQI does not reach its expressive power (Tobies, 1999). Cardinality restrictions, although interesting for knowledge representation, are inherently hard to handle algorithmically. The same applies to nominals in the presence of inverse roles and number restrictions. As an explanation for this we offer the lack of a tree model property, which was identified by Vardi (1997) as an explanation for good algorithmic behaviour of many modal logics.

At a first glance, our results make ALCQL with cardinality restrictions on concepts or ALCOIO with general axioms obsolete for knowledge representation because C 2 delivers more expressive power at the same computational price. Yet, is is likely that a dedicated algorithm for ALCQI may have better average complexity than the C 2 algorithm; such an algorithm has yet to be developed. This is highly desirable as it would also be applicable to reasoning problems for expressive DLs with nominals, which have applications in the area of reasoning with database schemata (Calvanese et al., 1998a, 1998b).

An interesting question lies in the coding of numbers: If we allow binary coding of numbers, the translation approach together with the result from (Pacholski et al., 1997) leads to a 2-NEXPTIME algorithm. As for C 2 , it is an open question whether this additional exponential blow-up is necessary. A positive answer would settle the same question for C 2 while a proof of the negative answer might give hints how the result for C 2 might be improved. For AXQ with cardinality restrictions, we have partially solved this problem:
with unary coding, the problem is EXPTIME-complete whereas, for binary coding, it is N E XP T IME-hard.