SciDok

Eingang zum Volltext in SciDok

Lizenz

Report (Bericht) zugänglich unter
URN: urn:nbn:de:bsz:291-scidok-35868
URL: http://scidok.sulb.uni-saarland.de/volltexte/2011/3586/


The complexity of existential quantification in concept languages

Donini, Francesco M. ; Hollunder, Bernhard ; Lenzerini, Maurizio ; Spaccamela, Alberto Marchetti ; Nard, Daniele ; Nutt, Werner

Quelle: (1991) Kaiserslautern ; Saarbrücken : DFKI, 1991
pdf-Format:
Dokument 1.pdf (10.976 KB)

Bookmark bei Connotea Bookmark bei del.icio.us
SWD-Schlagwörter: Künstliche Intelligenz , Natürliche Sprache , Computerlinguistik
Institut: DFKI Deutsches Forschungszentrum für Künstliche Intelligenz
DDC-Sachgruppe: Informatik
Dokumentart: Report (Bericht)
Schriftenreihe: Research report / Deutsches Forschungszentrum für Künstliche Intelligenz [ISSN 0946-008x]
Bandnummer: 91-02
Sprache: Englisch
Erstellungsjahr: 1991
Publikationsdatum: 18.05.2011
Kurzfassung auf Englisch: 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.
Lizenz: Standard-Veröffentlichungsvertrag

Home | Impressum | Über SciDok | Policy | Kontakt | Datenschutzerklärung | English