Terminological Logics are knowledge representation formalisms of enor- mous applicative interest, as they are specifically oriented to the vast class of application domains that are describable by means of taxo- nomic organizations of complex objects. A number of results rela- tive to the computational complexity of terminological logics have re- cently appeared in the literature. Unfortunately, most of these results are "negative" in nature, as they show that, in the logics they refer to, deciding subsumption (i.e. the metalinguistic relation which corre- sponds to validity in standard logics) is computationally intractable. In this paper, after briefly introducing the fundamental concepts un- derlying terminological logics, we show that computing subsumption is O(n log n) in the ALN logic, an extension of Brachman and Levesque's FL − logic. ALN is obtained by endowing FL − with the two oper- ators atleast and atmost, which allow the specification of number restrictions, and the operator a-not, which introduces a limited form of negation. The result we present is of theoretical significance, in that
['Fabrizio Sebastiani', 'Umberto Straccia', 'S. Maria']
A Computationally Tractable Terminological Logic