The complexity of concept languages (Q1363785)

This paper is dedicated to a formidable problem of artificial intelligence. The main concern of this paper is terminological knowledge representation systems (TKRSs), whose basic feature is to represent knowledge by means of taxonomies, here called terminologies, and to provide a specialized reasoning engine to do inferences on these structures. The communication between the KRS and the rest of the knowledge based systems is realized via queries and answers to queries. The type of language used to represent knowledge, and the inferences drawn from it characterize the KRS. Here are the main contributions of the paper: (1) a complexity analysis of concept satisfiability and subsumption for a wide class of concept languages; (2) algorithms for these inferences that comply with the worst-case complexity of the reasoning task they perform [\textit{F. M. Donini}, \textit{B. Hollunder}, \textit{M. Lenzerini}, \textit{A. M. Spaccamela}, \textit{D. Nardi} and \textit{W. Nutt}, The complexity of existential quantification in concept languages, Artificial Intell. 2-3, 309-327 (1992)].