Off-line reasoning for on-line efficiency, knowledge bases

Yoram Moses

doi:10.1016/0004-3702(95)00015-1

1996-06-01

Yoram Moses *

Moshe Tennenholtz

DOI：10.1016/0004-3702(95)00015-1

原文链接

查看原文

摘要

En 中文

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 which 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 efficient 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 efficient 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.