Reference: Levy, A. Y. & Sagiv, Y. Exploiting Irrelevance-reasoning to Guide Problem Solving. Knowledge Systems Laboratory, 1993.
Abstract: Identifying that parts of the knowledge base are irrelevant to a specific problem solving goal is a powerful method of controlling search in problem solving. However, the problem of finding methods of such {\em irrelevance reasoning} and analyzing their utility is open. We present a framework based on a proof-theoretic analysis of irrelevance that enables us to address these problems. Within the framework, we focus on a class of {\em strong-irrelevance} claims and show that they have several desirable properties. For example, in the context of Horn-rule theories, we show that strong- irrelevance claims can be efficiently derived either by examining the knowledge base or as logical consequences of other strong-irrelevance claims. An important aspect of our algorithms is that we consider only a small part of the knowledge base for our reasoning. Consequently, the reasoning is efficient and the irrelevance-claims are independent of changes to other parts of the knowledge-base.
Notes: Revised April 1993.
Full paper available as ps.