Please use this identifier to cite or link to this item: doi:10.22028/D291-24961
Title: The complexity of concept languages
Author(s): Donini, Francesco M.
Lenzerini, Maurizio
Nardi, Daniele
Nutt, Werner
Language: English
Year of Publication: 1995
OPUS Source: Kaiserslautern ; Saarbrücken : DFKI, 1995
SWD key words: Künstliche Intelligenz
DDC notations: 004 Computer science, internet
Publikation type: Report
Abstract: The 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 well-defined set-theoretic semantics. The efficiency of reasoning has often been advocated as a primary motivation for the use of such systems. Deduction methods and computational properties of reasoning problems in concept languages are the subject of this paper. The main contributions of the paper are: (1) a complexity analysis of concept satisfiability and subsumption for a wide class of concept languages; (2) the algorithms for these inferences that comply with the worst-case complexity of the reasoning task they perform.
Link to this record: urn:nbn:de:bsz:291-scidok-37463
Series name: Research report / Deutsches Forschungszentrum für Künstliche Intelligenz [ISSN 0946-008x]
Series volume: 95-07
Date of registration: 30-Jun-2011
Faculty: SE - Sonstige Einrichtungen
Department: SE - DFKI Deutsches Forschungszentrum für Künstliche Intelligenz
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
RR_95_07.pdf504,01 kBAdobe PDFView/Open

Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.