The complexity of concept languages.

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

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

Concept languages provide a means for expressing knowledge about hierarchies of concepts, i.e. classes of objects with common properties. The basic reasoning tasks to be performed on concepts are satisfiability checking and subsumption checking. Although concept languages have been widely used in \(AI\)-systems, only in rare case complete algorithms have been known. The few complexity results that have been obtained gave mostly lower bounds and were not related to each other. We consider a family of languages, called \({\mathcal {AL}}\)-languages, which covers most of the concept languages considered in the literature.

First, we develop a general technique for checking satisfiability and subsumption of \({\mathcal {AL}}\)-concepts, which is based on the tableau calculus for predicate logic.

Second, we use this algorithmic technique to give precise upper and lower bounds for the \({\mathcal {AL}}\)-languages, thus providing a complete analysis of the computational complexity of the satisfiability and the subsumption problem for concept languages.

Concept languages provide a means for expressing knowledge about hierarchies of concepts, i.e. classes of objects with common properties. The basic reasoning tasks to be performed on concepts are satisfiability checking and subsumption checking. Although concept languages have been widely used in \(AI\)-systems, only in rare case complete algorithms have been known. The few complexity results that have been obtained gave mostly lower bounds and were not related to each other. We consider a family of languages, called \({\mathcal {AL}}\)-languages, which covers most of the concept languages considered in the literature.

First, we develop a general technique for checking satisfiability and subsumption of \({\mathcal {AL}}\)-concepts, which is based on the tableau calculus for predicate logic.

Second, we use this algorithmic technique to give precise upper and lower bounds for the \({\mathcal {AL}}\)-languages, thus providing a complete analysis of the computational complexity of the satisfiability and the subsumption problem for concept languages.

##### MSC:

68T30 | Knowledge representation |

68Q25 | Analysis of algorithms and problem complexity |

68T99 | Artificial intelligence |