RIA: Tractable Reasoning in Knowledge Representation Systems

9410117 Dalal A general-purpose knowledge representation (KR) system allows explicit representation of and reasoning with various kinds of information. A critical problem in present-day KR systems is caused by the tradeoff between the expressiveness of the representation language and the computational complexity of reasoning with it -- deductive reasoning with sufficiently expressive languages is inherently intractable. In preliminary work in addressing this problem, the PI has developed a technique for generating tractable approximate reasoners, and a parameter, called intricacy, whose finite value for a representation language indicates that reasoning with it is tractable. The preliminary approach has some serious limitations. First, although there are many approximate reasoners that can be obtained using the technique for any given application, the PI has not provided any systematic way for among them. Second, although he has shown that many known tractable cases of reasoning have finite intricacy, he has not used this parameter for obtaining new non-trivial tractability results. The proposed research addresses these limitations. The PI proposes to evaluate various approximate reasoners by implementing and testing them on KR systems used in some real-world applications; this evaluation will be used to develop guidelines for choosing appropriate reasoner for a given application. The PI also proposes to use intricacy for obtaining new non-trivial tractable cases that are characterized by efficiently-identifiable syntactic features.