A computationally tractable terminological logic.

In Proceedings of SCAI-91, 3rd Scandinavian Conference on Artificial Intelligence, pages 307--315, Roskilde, Denmark, 1991.


Abstract:
Terminological Logics are knowledge representation formalisms of enormous applicative interest, as they are specifically oriented to the vast class of application domains that are describable by means of taxonomic organizations of complex objects. A number of results relative to the computational complexity of terminological logics have recently 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 corresponds to validity in standard logics) is computationally intractable. In this paper, after briefly introducing the fundamental concepts underlying 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 operators 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 ALN is one of the few terminological logics that have been shown tractable. ALN is also a pragmatically significant extension of FL-, as it results from the addition of operators of considerable applicative interest.