TY  - RPRT
T1  - The complexity of existential quantification in concept languages 
T3  - Kaiserslautern ; Saarbrücken : DFKI, 1991
A1  - Donini,Francesco M.
A1  - Hollunder,Bernhard
A1  - Lenzerini,Maurizio
A1  - Spaccamela,Alberto Marchetti
A1  - Nard,Daniele
A1  - Nutt,Werner
Y1  - 2011/05/18
N2  - 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. 
KW  - Künstliche Intelligenz
KW  - Natürliche Sprache
KW  - Computerlinguistik
CY  - Saarbrücken
PB  - Universitäts- und Landesbibliothek
AD  - Postfach 151141, 66041 Saarbrücken
UR  - http://scidok.sulb.uni-saarland.de/volltexte/2011/3586
ER  -