On the tractability of terminological logics with numerical restrictions

A number of results relative to the complexity of terminological logics 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 we show that computing subsumption is $O(n^{2})$ in ${\cal Brachman84}^{{\cal N}-}$, a logic obtained by adding the two operators {\bf atleast} and {\bf atmost}, which allow the specification of number restrictions, to Brachman and Levesque's ${\cal Brachman84}^{-}$ logic.