The complexity of existential quantification in concept languages
1992
Abstract Much of the research on concept languages, which also are 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 jy - with constructs containing some form of logical disjunction leads to co-NP-hard subsumption problems. Secondly, adding negation to jy - makes subsumption PSPACE-complete. The main result of this paper is that extending jy - with unrestricted existential quantification makes subsumption NP-complete. This is the first proof of intractability for a concept language containing, whether explicitly or implicitly, no construct expressing disjunction. Unrestricted existential quantification is therefore, alongside disjunction, a source of computational complexity in concept languages.
Keywords:
- Computational complexity theory
- Negation
- Logical disjunction
- First-order logic
- Mathematics
- Natural language processing
- Conceptualization
- Knowledge representation and reasoning
- Existential quantification
- Expert system
- Algorithm
- Artificial intelligence
- Discrete mathematics
- Theoretical computer science
- Knowledge base
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
14
References
91
Citations
NaN
KQI