On the tractability of terminological logics with numerical restrictions

A number of results relative to the complexity of terminologicallogics have recently appeared in the literature. Unfortunately, most of these results are ``negative",as they show that, in the logics they refer to, deciding{\em subsumption} is intractable. In this paper weshow that computing subsumption is $O(n^{2})$ in ${\calBrachman84}^{{\cal N}-}$, a logic obtained by adding the twooperators {\bf atleast} and {\bf atmost}, which allowthe specification of number restrictions, to Brachmanand Levesque's ${\cal Brachman84}^{-}$ logic.