Please use this identifier to cite or link to this item: doi:10.22028/D291-24836
Title: The complexity of existential quantification in concept languages
Author(s): Donini, Francesco M.
Hollunder, Bernhard
Lenzerini, Maurizio
Spaccamela, Alberto Marchetti
Nard, Daniele
Nutt, Werner
Language: English
Year of Publication: 1991
OPUS Source: Kaiserslautern ; Saarbrücken : DFKI, 1991
SWD key words: Künstliche Intelligenz
Natürliche Sprache
DDC notations: 004 Computer science, internet
Publikation type: Report
Abstract: 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 to this record: urn:nbn:de:bsz:291-scidok-35868
Series name: Research report / Deutsches Forschungszentrum für Künstliche Intelligenz [ISSN 0946-008x]
Series volume: 91-02
Date of registration: 18-May-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_91_02.pdf10,98 MBAdobe PDFView/Open

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