Qualifying number restrictions in concept languages.

*(English)*Zbl 0765.68190
Principles of knowledge representation and reasoning, Proc. 2nd Int. Conf., Cambridge/MA (USA) 1991, 335-346 (1991).

Summary: [For the entire collection see Zbl 0747.00023.]

We investigate the subsumption problem in logic-based knowledge representation languages of the KL-ONE family. The language presented provides the constructs for conjunction, disjunction, and negation of concepts, as welll as qualifying number restrictions. The latter ones generalize the well-known rule quantifications (such as value restrictions) and ordinary number restrictions, which are present in almost all KL-ONE based systems. Until now, only little attempts were made to integrate qualifying number restrictions into concepts languages. It turns out that all known subsumption algorithms which try to handle these constructs are incomplete, and thus detecting only few subsumption relations between concepts. We present a subsumption algorithm for our language which is sound and complete. Subsequently we discuss why the subsumption problem in this language is rather hard from a computational point of view. This leads to an idea of how to recognize concepts which cause tractable problems.

We investigate the subsumption problem in logic-based knowledge representation languages of the KL-ONE family. The language presented provides the constructs for conjunction, disjunction, and negation of concepts, as welll as qualifying number restrictions. The latter ones generalize the well-known rule quantifications (such as value restrictions) and ordinary number restrictions, which are present in almost all KL-ONE based systems. Until now, only little attempts were made to integrate qualifying number restrictions into concepts languages. It turns out that all known subsumption algorithms which try to handle these constructs are incomplete, and thus detecting only few subsumption relations between concepts. We present a subsumption algorithm for our language which is sound and complete. Subsequently we discuss why the subsumption problem in this language is rather hard from a computational point of view. This leads to an idea of how to recognize concepts which cause tractable problems.

PDF
BibTeX
XML
Cite

\textit{B. Hollunder} and \textit{F. Baader}, in: Principles of knowledge representation and reasoning. Proceedings of the 2nd international conference (KR' 91), Cambridge, MA, USA, April 22-25, 1991. San Mateo, CA: Morgan Kaufmann Publishers, Inc.. 335--346 (1991; Zbl 0765.68190)