Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-24836
Titel: The complexity of existential quantification in concept languages
Verfasser: Donini, Francesco M.
Hollunder, Bernhard
Lenzerini, Maurizio
Spaccamela, Alberto Marchetti
Nard, Daniele
Nutt, Werner
Sprache: Englisch
Erscheinungsjahr: 1991
Quelle: Kaiserslautern ; Saarbrücken : DFKI, 1991
SWD-Schlagwörter: Künstliche Intelligenz
Natürliche Sprache
Computerlinguistik
DDC-Sachgruppe: 004 Informatik
Dokumentart : Report (Bericht)
Kurzfassung: Much of the research on concept languages, also called terminological languages, has focused on the computational complexity of subsumption. The intractability results can be divided into two groups. First, it has been shown that extending the basic language FL- with constructs containing some form of logical disjunction leads to co-NP-hard subsumption problems. Second, adding negation to FL- makes subsumption PSPACE-complete. The main result of this paper is that extending FL- with unrestricted existential quantification makes subsumption NP-complete. This is the first proof of intractability for a concept language containing no construct expressing disjunction--whether explicitly or implicitly. Unrestricted existential quantification is therefore, alongside disjunction, a source of computational complexity in concept languages.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-35868
hdl:20.500.11880/24892
http://dx.doi.org/10.22028/D291-24836
Schriftenreihe: Research report / Deutsches Forschungszentrum für Künstliche Intelligenz [ISSN 0946-008x]
Band: 91-02
SciDok-Publikation: 18-Mai-2011
Fakultät: Sonstige Einrichtungen
Fachrichtung: SE - DFKI Deutsches Forschungszentrum für Künstliche Intelligenz
Fakultät / Institution:SE - Sonstige Einrichtungen

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
RR_91_02.pdf10,98 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.