The complexity of existential quantification in concept languages

摘要

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.