Abstract Sebastiani et Straccia.

On the tractability of terminological logics with numerical restrictions.

Associazione italiana per l'intelligenza artificiale, 5(2), 1992.

Abstract:
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*n) in FLN-, a logic obtained by adding the two operators atleast and atmost, which allow the specification of number restrictions, to Brachman and Levesque's FL- logic.