In this paper we establish a number of new complexity results for DLs with cardinality restrictions or nominals. Figure 1 summarises the new complexity bounds established in this paper. All problems are complete for their respective complexity class. This paper is organised as follows.

After giving some basic definitions in Section 2, we show that consistency of TBoxes with cardinality restrictions for ALCQI is a NEXP TIME-complete problem (Section 3).  Membership in NEXPTIME is shown by a translation to the satisfiability problem of C 2 (Pacholski et al., 1997) 1 , the two variable fragment of first order predicate logic augmented with counting quantifiers. The matching lower bound is established by a reduction from a N EXP TIME-complete  bounded domino  problem.

In Section 4, we show that reasoning with cardinality restrictions can be reduced to reasoning with the (weaker) formalism of general axioms in the presence of nominals. This yields interesting complexity results both for reasoning with cardinality restrictions and with nominals. Using a result from (De Giacomo, 1995), the reduction shows that consistency of TBoxes with cardinality restrictions for ALLQ is in EXPTIME. This improves the result from (Baader et al., 1996), where it was shown that the problem can be solved in NEXPTIME. Moreover, we show that for a DL with number restrictions, inverse roles, and nominals reasoning problems become NEXPTIME-hard, which solves an open problem from (De Giacomo, 1995). This combination is of particular interest for the application of DLs in the area of reasoning with database schemata (Calvanese et al., 1998a, 1998b).

## 2. The Logic Accql

Definition 2.1 Let N c ; be a set of atomic concept names and N R be a set of atomic role nmes.  Concepts in ALCOI are built inductively from these using the following rules:  all A E Nc; are concepts, and, if C, C1, and C2 are concepts, then also

$\mathbf{L}_{\mathcal{D}}^{\dagger}$
¬C 1 C 1 C 2 1 and ( ≥ n S C ),
are concepts, where n E N and S = R or S = R-1 for some R E N R .

A cardinality restriction of ALCQI is an expression of the form ( > n C ) or ( < n C )
where C is a concept and n E N; an ALCQI-TCBox 2 is a finite set of cardinality restrictions.

The semantics of concepts is defined relative to an interpretation I = ( Δ T, T ), which consists of a domain ∆ ⋆ and a valuation ( ⋆ ) that maps each concept name A to a subset A I of Δ I and each role name R to a subset R I of Δ I × Δ I . This valuation is inductively extended to arbitrary concepts using the following rules, where HM denotes the cardinality of a set M :

$$(\neg C)^{\mathcal{I}}:=\Delta^{\mathcal{I}}\setminus C^{\mathcal{I}},$$ $$(C_{1}\cap C_{2})^{\mathcal{I}}:=C_{1}^{\mathcal{I}}\cap C_{2}^{\mathcal{I}},$$ $$(\geqslant n\ R\ C)^{\mathcal{I}}:=\{a\in\Delta^{\mathcal{I}}\ |\ \sharp\{b\in\Delta^{\mathcal{I}}\ |\ (a,b)\in R^{\mathcal{I}}\wedge b\in C^{\mathcal{I}}\}\geq n\,\},$$ $$(\geqslant n\ R^{-1}\ C)^{\mathcal{I}}:=\{a\in\Delta^{\mathcal{I}}\ |\ \sharp\{b\in\Delta^{\mathcal{I}}\ |\ (b,a)\in R^{\mathcal{I}}\wedge b\in C^{\mathcal{I}}\}\geq n\,\}.$$
