Proceedings of the AAAI Conference on Artificial Intelligence, 5
One severe problem in frame-based description languages is that computing subsumption in computationally intractable for languages of reasonable expressive power. Several partial solutions to this problem are used in knowledge representation systems that incorporate such languages, but none of these solutions are satisfactory if the system is to be of general use in representing knowledge. A new solution to this problem is to use a weaker, four-valued semantics for frame-based description languages, thus legitimizing a smaller set of subsumption relationships. In this way a computationally tractable but expressively powerful knowledge representation system incorporating a frame-based description language can be built.