OFF-LINE REASONING FOR ONLINE EFFICIENCY, KNOWLEDGE BASES

The complexity of reasoning is a fundamental issue in AI. In many case s, the fact that an intelligent system needs to perform reasoning on-l ine contributes to the difficulty of this reasoning. This paper consid ers the case in which an intelligent system computes whether a query i s entailed by the system's knowledge base. It investigates how an init ial phase of off-line preprocessing and design can improve the on-line complexity considerably. The notion of an efficient basis for a query language is presented, and it is shown that off-line preprocessing ca n be very effective for query languages that have an efficient: basis. The usefulness of this notion is illustrated by showing that a fairly expressive language has an efficient basis. A dual notion of an effic ient disjunctive basis for a knowledge base is introduced, and it is s hown that off-line preprocessing is worthwhile for knowledge bases tha t have an efficient disjunctive basis.