The Complexity of Concept Languages

详细信息    查看全文

• 作者：Donini ; Francesco M. ; Lenzerini ; Maurizio ; Nardi ; Daniele ; Nutt ; Werner
• 刊名：Information and Computation
• 出版年：1997
• 出版时间：April 10, 1997
• 年：1997
• 卷：134
• 期：1
• 页码：1-58
• 全文大小：727 K

文摘

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 aconcept language(ordescription 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.