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 hdl:20.500.11880/24866 http://dx.doi.org/10.22028/D291-24810 |
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 | Size | Format | |
---|---|---|---|---|
RR_90_04.pdf | 15,47 MB | Adobe PDF | View/Open |
Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.