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

✍ Scribed by Yoram Moses; Moshe Tennenholtz

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 901 KB
• Volume: 83
• Category: Article
• ISSN: 0004-3702
• DOI: 10.1016/0004-3702(95)00015-1

✦ Synopsis

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 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 eficient 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.