Infomation and Computation
A basic feature of Terminological Knowledge Representation Systems 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 taxonomy is built through a representation language called 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 systems. The main contributions of the paper are: (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.
@article{DLNN97,
title = "The Complexity of Concept Languages",
year = "1997",
author = "Francesco M. Donini and Maurizio Lenzerini and Daniele
Nardi and Werner Nutt",
journal = "Infomation and Computation",
pages = "1-58",
volume = "134",
}