Undecidability of subsumption in NIKL

摘要

Subsumption—determining whether one concept is more general than another—is known to be NP-hard for all reasonably expressive terminological logics, but, up to now, the decidability of subsumption for terminological logics used in current knowledge representation systems such as NIKL remained unknown. This paper shows that subsumption in the terminological logic of NIKL is undecidable and thus that there are no complete algorithms for subsumption or classification in NIKL.