Anumber of results relative to the complexity of terminologicallogics 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 weshow that computing subsumption is $O(n^{2})$ in ${\calBrachman84}^{{\cal N}-}$, a logic obtained by adding the twooperators {\bf atleast} and {\bf atmost}, which allowthe specification of number restrictions, to Brachmanand Levesque's ${\cal Brachman84}^{-}$ logic.
On the tractability of terminological logics with numerical restrictions
Sebastiani F.;Straccia U.
1992
Abstract
Anumber of results relative to the complexity of terminologicallogics 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 weshow that computing subsumption is $O(n^{2})$ in ${\calBrachman84}^{{\cal N}-}$, a logic obtained by adding the twooperators {\bf atleast} and {\bf atmost}, which allowthe specification of number restrictions, to Brachmanand Levesque's ${\cal Brachman84}^{-}$ logic.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
