Please use this identifier to cite or link to this item: doi:10.22028/D291-40192
Title: Subsumption in KL-One is Undecidable
Author(s): Schmidt-Schauß, Manfred
Language: English
Year of Publication: 1988
Place of publication: Kaiserslautern
Free key words: Knowledge representation
DDC notations: 004 Computer science, internet
Publikation type: Report
Abstract: It is shown that in the frame-based language KL-ONE it is undecidable, whether one concept is subsumed by another concept. The concept forming operators which are sufficient for this result are: conjunction, value restriction, role restriction, the operator ‘SOME’, and role value maps using only ‘=’. In particular, number restrictions are not used. This shows that there is a basic difference between feature terms and KL-ONE, since the complexity of subsumption switches from co-NP-complete to undecidable, if the restriction is dropped that roles are functional.
Link to this record: urn:nbn:de:bsz:291--ds-401927
Series name: SEKI-Report / Deutsches Forschungszentrum für Künstliche Intelligenz, DFKI [ISSN 1437-4447]
Series volume: 88,14
Date of registration: 11-Aug-2023
Notes: In der GND existiert kein Normdatensatz für die Person, die sie eindeutig als solche identifiziert. Alternative oder damit in Verbindung stehende Schreibweise(n): Schmidt-Schauss, Manfred.
Faculty: SE - Sonstige Einrichtungen
Department: SE - DFKI Deutsches Forschungszentrum für Künstliche Intelligenz
Professorship: SE - Sonstige
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
SEKI-Report-SR-88-14_Schmidt=Schauß_Subsumption-in-KL=One-is-Undecidablepdf.pdf941,52 kBAdobe PDFView/Open

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