Please use this identifier to cite or link to this item: doi:10.22028/D291-24810
Title: Subsumption algorithms for concept languages
Author(s): Hollunder, Bernhard
Nutt, Werner
Language: English
Year of Publication: 1990
OPUS Source: Kaiserslautern ; Saarbrücken : DFKI, 1990
SWD key words: Künstliche Intelligenz
Terminologische Sprache
DDC notations: 004 Computer science, internet
Publikation type: Report
Abstract: We investigate the subsumption problem in logic-based knowledge representation languages of the KL-ONE family and give decision procedures. All our languages contain as a kernel the logical connectives conjunction, disjunction, and negation for concepts, as well as role quantification. The algorithms are rule-based and can be understood as variants of tableaux calculus with a special control strategy. In the first part of the paper, we add number restrictions and conjunction of roles to the kernel language. We show that subsumption in this language is decidable, and we investigate sublanguages for which the problem of deciding subsumption is PSPACE-complete. In the second part, we amalgamate the kernel language with feature descriptions as used in computational linguistics. We show that feature descriptions do not increase the complexity of the subsumption problem.
Link to this record: urn:nbn:de:bsz:291-scidok-35566
Series name: Research report / Deutsches Forschungszentrum für Künstliche Intelligenz [ISSN 0946-008x]
Series volume: 90-04
Date of registration: 7-Apr-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_90_04.pdf15,47 MBAdobe PDFView/Open

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