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.