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.