The Q* Algorithm - A Search Strategy for a Deductive Question-Answering System

Abstract

An approach for bringing semantic, as well as syntactic, inforrration to bear on the problem of thoorem- proving search for Question-Answering (0\) Systems is described. The approach is embodied in a search algorithm, the Q* search algorithm, developed to control derluctive searches in an experimental svstem. Tre Q* algorithm is part of a system, termed the Hazylarrl Refutation Proof Procedure System (MRPPS), which incorpJrates both the Q* algorithm, which performs the search required to answer a query, and an inferential catp;)nent, which performs the logical manipulations necessary to deduce a clause from one or two other clauses. The inferential comp:ment includes many refinements of resolution. The Q* algorithm generates nodes in the search space, applying semantic and syntactic information to direct the search. The use of semantics permits paths to be terminated and fruitful paths to be explored . Tre paper is restricted to a description of the use of syntactic and semantic information in the Q* algorithm.