Undecidability of subsumption in NIKL

✍ Scribed by Peter F. Patel-Schneider

• Book ID: 102637991
• Publisher: Elsevier Science
• Year: 1989
• Tongue: English
• Weight: 364 KB
• Volume: 39
• Category: Article
• ISSN: 0004-3702
• DOI: 10.1016/0004-3702(89)90030-1

✦ Synopsis

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.

* Much of the research reported in this note was performed at Schlumberger Palo Alto Research. tin the earlier systems, this formal semantics was devised after the system was built, but nowadays the semantics precedes the system.