On the Tractability of Terminological Logics with Numerical Restrictions
Fabrizio Sebastiani, Umberto Straccia, S. Maria · 1992
A number of results relative to the complexity of terminological logics have recently appeared in the literature. Unfortunately, most of these results are egative, as they show that, in the logics they refer to, deciding subsumption is intractable. In this paper we show that computing subsumption is O(n 2 ) inBrachman84 N , a logic obtained by adding the two operators atleast and atmost, which allow the specication of number restrictions, to Brachman and Levesque’s Brachman84 logic.