No coin nor oath required. For personal study only.
The complexity of reasoning is a fundamental issue in AI. In many cases, the fact that an intelligent system needs to perform reasoning on-line contributes to the difficulty of this reasoning. This paper considers the case in wllich an intelligent system computes whether a query is entailed by the system's knowledge base. It investigates how an initial phase of off-line preprocessing and design can improve the on-line complexity considerably. The notion of an eficient basis for a query language is presented, and it is shown that off-line preprocessing can 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 @cienr disjunctive basis for a knowledge base is introduced, and it is shown that off-line preprocessing is worthwhile for knowledge bases that have an efficient disjunctive basis.
๐ SIMILAR VOLUMES