THE COMPLEXITY OF CONCEPT LANGUAGES

A basic feature of Terminological Knowledge Representation Systems is to represent knowledge by means of taxonomies, here called terminologi es, and to provide a specialized reasoning engine to do inferences on these structures, The taxonomy is built through a representation langu age called a concept language (or description logic), which is given a well-defined set-theoretic semantics. The efficiency of reasoning has often been advocated as a primary motivation for the use of such syst ems. The main contributions of the paper are: (1) a complexity analysi s of concept satisfiability and subsumption for a wide class of concep t languages; (2) algorithms for these inferences that comply with the worst-case complexity of the reasoning task they perform. (C) 1997 Aca demic Press.