Proc. of the 12th Int. Joint. Conf. on Artificial Intelligence (IJCAI'91)
We present two concept languages, called P L 1 and P L 2 , which are extensions of F L - . We prove that the subsumption problem in these languages can be solved in polynomial time. Both languages include a construct for expressing inverse roles, which has not been considered up to now in tractable languages. In addition, P L 1 includes number restrictions and negation of primitive concepts, while P L 2 includes role conjunction and role chaining. By exploiting recent complexity results, we show that none of the constructs usually considered in concept languages can be added to P L 1 and P L 2 without losing tractability. Therefore, on the assumption that languages are characterized by the set of constructs they provide, the two languages presented in this paper provide a solution to the problem of singling out an optimal trade-off between expressive power and computational complexity.
@inproceedings{DLNN-91-b,
title = "Tractable Concept Languages",
year = "1991",
author = "Donini, Francesco M. and Lenzerini, Maurizio and Nardi,
Daniele and Nutt, Werner",
booktitle = "Proc. of the 12th Int. Joint. Conf. on Artificial Intelligence
(IJCAI'91)",
pages = "458-463",
note = "Best Paper Award.",
}