Tractable Concept Languages

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

Tractable Concept Languages

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

Download BibTeX Cite

Proceedings of the Twelfth International Joint Conference on Artificial Intelligence. Knowledge Representation. 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.

Francesco M. Donini, Maurizio Lenzerini, Daniele Nardi, and Werner Nutt. 1991. Tractable Concept Languages. In Proceedings of the Twelfth International Joint Conference on Artificial Intelligence, IJCAI-91. IJCAI, 458–464. https://ijcai.org/proceedings/1991/69

@inproceedings{ijcai1991p69,
  title     = {Tractable Concept Languages},
  author    = {Donini, Francesco M. and Lenzerini, Maurizio and Nardi, Daniele and Nutt, Werner},
  booktitle = {Proceedings of the Twelfth International Joint Conference on
               Artificial Intelligence, {IJCAI-91}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {John Mylopoulos and Ray Reiter},
  pages     = {458--464},
  year      = {1991},
  month     = {8},
  note      = {Knowledge Representation},
  url       = {https://ijcai.org/proceedings/1991/69},
}

TY  - CPAPER
TI  - Tractable Concept Languages
AU  - Donini, Francesco M.
AU  - Lenzerini, Maurizio
AU  - Nardi, Daniele
AU  - Nutt, Werner
T2  - Proceedings of the Twelfth International Joint Conference on Artificial Intelligence, IJCAI-91
PB  - International Joint Conferences on Artificial Intelligence
PY  - 1991
SP  - 458
EP  - 464
UR  - https://ijcai.org/proceedings/1991/69
ER  -