The Tractability of Subsumption in Frame-Based Description Languages

A knowledge representation system provides an important ser-vice to the rest of a knowledge-based system: it computes au-tomatically a set of inferences over the beliefs encoded within it. Given that the knowledge-based system relies on these infer-ences in the midst of its operation (i.e., its diagnosis, planning, or whatever), their computational tractability is an important concern. Here we present evidence as to how the cost of comput-ing one kind of inference is directly related to the expressiveness of the representation language. As it turns out, this cost is per-ilously sensitive to small changes in the representation language. Even a seemingly simple frame-based description language can pose intractable computational obstacles. 1