DFKI Research Report-91-02



Language: English

by Francesco Donini, Bernhard Hollunder, Maurizio Lenzerini, Alberto Marchetti Spaccamela, Daniele Nardi, Werner Nutt

The Complexity of Existential Quantification in Concept Languages

22 Pages


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.

This document is available as PDF-File(16,7MB).

The next abstract is here, and the previous abstract is here.

DFKI-Bibliothek (bib@dfki.uni-kl.de)

Note: This page was written to look best with CSS stylesheet support Level 1 or higher. Since you can see this, your browser obviously doesn't support CSS, or you have turned it off. We highly recommend you use a browser that supports and uses CSS, and review this page once you do. However, don't fear, we've tried to write this page to still work and be readable without CSS.