---
title: "Tractable Concept Languages"
authors:
  - "Francesco M. Donini"
  - "Maurizio Lenzerini"
  - "Daniele Nardi"
  - "Werner Nutt"
doi: ""
url: "https://ijcai.org/proceedings/1991/69"
pdf: "https://ijcai.org/proceedings/1991/0069.pdf"
venue: "Proceedings of the Twelfth International Joint Conference on Artificial Intelligence"
year: 1991
pages: "458-464"
track: "Knowledge Representation"
keywords:
---

# Tractable Concept Languages

Francesco M. Donini, Maurizio Lenzerini, Daniele Nardi, Werner Nutt

*Proceedings of the Twelfth International Joint Conference on Artificial Intelligence*, pages 458-464.

## Abstract

We present two concept languages, called PC1 and PC2, which are extensions of :Fe-. 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 C1 includes number restrictions and negation of primitive concepts, while P C2 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 add ed toP C 1 and P C2 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.