Browse Prior Art Database

A Question-answering System Based on the Kay Parsing Algorithm

IP.com Disclosure Number: IPCOM000128329D
Original Publication Date: 1973-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 12 page(s) / 38K

Publishing Venue

Software Patent Institute

Related People

John Seely Brown: AUTHOR [+3]

Abstract

wanted to explore some of -the obvious parallels between parsing and theorem proving and likewise between grammars and inference rules. Second, we wanted to investigate if the Ray Parsing Algorithm could be useful for inference making. We were intrigued by the way this algorithm so efficiently encoded partial parses. Could some of these same techniques be used to circumvent the large amount of back-up inherent in many approaches to inference making by efficiently carrying along parallel "sub-proofs" even when such sub-proofs might never yield a complete proof? (Examples of related capabilities in both top-down and bottom-up parsers are also exemplified in Woods' well-formed substring feature [3) and in Kaplan's GSP [41.)

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 11% of the total text.

Page 1 of 12

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A Question-answering System Based on the Kay Parsing Algorithm

John Seely Brown

TECHNICAL REPORT #28 - June 1973

This paper is a revised version of a working paper written in February, 1972, titled "Old Fashioned Question Answering Revisited." Page .2

wanted to explore some of -the obvious parallels between parsing and theorem proving and likewise between grammars and inference rules. Second, we wanted to investigate if the Ray Parsing Algorithm could be useful for inference making. We were intrigued by the way this algorithm so efficiently encoded partial parses. Could some of these same techniques be used to circumvent the large amount of back-up inherent in many approaches to inference making by efficiently carrying along parallel "sub-proofs" even when such sub-proofs might never yield a complete proof? (Examples of related capabilities in both top-down and bottom-up parsers are also exemplified in Woods' well-formed substring feature [3) and in Kaplan's GSP [41.)

Before delving any deeper into our system, a short description of the Kay Algorithm is in order. We will refer interchangeably to the Kay Algorithm and the Chart Parser wherein the modelling structure underlying Kay's algorithm will be cailed a "chart". We will describe only the simplest context free aspect of the Parsing Algorithm and refer the interested reader to Kay [21 and Kaplan [4].

Let us consider the following utterance:

"The cherry blossoms in the Spring

which is syntactically ambiguous yielding two obvious reading:

(Equation Omitted)

Superimposing these two parses one notes that some parts of the structural description are the same and other parts are different. The Kay parser provides a mechanism for circumventing the need to reparse any well formed substring that is shared between any two parses. This feat is primarily accomplished by using a special modelling structure to represent the parsings. For the above sentence an initial chart is constructed as follows:

(Equation Omitted)

where the words of the utterance act as labels on the arcs. Arcs are then added covering these initial arcs according to what syntactic categories each word may be, i.e. Page 4

(Equation Omitted)

Assuming for the moment that our grammar is context free, then a single sweep from right to left is made applying all the reduction rules wherever possible! For each reduction a new arc is added which dominates the sub-arcs that it reduces. (A broken line denotes explicitely which

University of California, Irvine Page 1 Dec 31, 1973

Page 2 of 12

A Question-answering System Based on the Kay Parsing Algorithm

sub-arcs a new arc dominates.) The final chart resulting from the application of all possible rules for this utterance would look like:

*We caution ' the reader that this is a most superficial indication of the parsing scheme and recommend Kay [11 (2] for a thorough description of the chart parser as it applies to tran...