Experiments with a Natural Language Problem-Solving System

Introduction

During the past few years, several research projects have been devoted to the development of computerized natural-language question-answering systems. These endeavors may be roughly divided (a Ia Bobrow[1) and Simmons [7)) into two categories : data-based and text-based. The former classifica­ tion refers to those systems which initially contain well-structured sets of data representing potential answers (or parts of answers) to questions in some given subset of knowledge . Solutions may utlllze sophisticated intormation retrieval methods, theorem­ proving techniques, or other inference schema in performing the deduction from question to answer. The data base is usually large and essentially static. A keyword (semantic) scan of the input question often suffices to provide the extra information required to deduce the desired answer . Some systems also em­ ploy structural (syntactic) analysis of the input to determine relationships among semantic objects, and then search the data base for similar relation., ships among stored objects (cf. Simmons [7)).

Text-based question-answering systems, which we shall refer to as problem-solving systems, uni­ formly contain small initial data bases. New data is added to the data base from the input text prior to attempting solution, but this information is normally discarded immediately after a solution is generated. Some, such as Raphael's Sffi [6] and Lindsay's SAD SAM[5], continuously augment their data bases with information gleaned from the input, and utilize both kinds of data for future solutions; the new data is discarded at the end of a problem-solving session, however. Usually, some form of syntax analysis of the problem text is required so that the relationships among semantical objects may be uncovered and.data base entries created . Bobrow's STUDENT (1] appli­ ed a simple transformational grammar to the input problem text, and demonstrated that such a grammar was sufficient to produce the equational representa­ tions of high-school level algebra word-story prob­ lems . Charniak [2] went on to show how a slightly more sophisticated parser, when applied to calculus rate problems by his CARPS system, could be used to determine the cross-dependency structures pre­ sent in that class of problems.

In the research reported herein, we set out to design and implement a system for the solution of probability problems phrased in English, such as might be found at the end of the initial chapters of a college-level probability text . Since the input lan­ guage was reasonably complex, sophisticated tech­ niques for syntactic and semantic analyses were postulated; in reality, the judicious application of heuristics enabled us to produce a simplified analysis which was still comprehensive enough to handle all but the most pathological cases. In addition, solu­ tions were produced symbolically and in a piecemeal fashion, with an eye toward the possible didactic app­ lications of that method. Only at the final stage of solution were numbers actually displayed.

The system, dubbed HAPPINESS (for ~euristic ~alysis of Erobability _rroblems !P aJ:Iatural-langu­ age _!:nvironment with §ymbolic §:elutions) has been programmed in LISP 1. 5 and is running interactively under ffiM's TSS/ 67.

The HAPPINESS Srstem

The system is divided into two main, indepen­ dent subsections: a language analyzer, and a solu­ tion generator. There is also a control section, called DRIVER, whose job it is to communicate with the user, pass pertinent information from the lan­ guage analyzer to the solution generator, and gener­ ally, to drive the system (see Fig. 1). Each of the two subsections performs its own error checking and / or correction; unrecoverable errors are currently conveyed to the user via the driver, and a new prob­ lem requested . The timing information displayed by DRIVER refers to actual CPU time since the last dis­ play, and includes garbage collection and paging times. Although, for the purpose of this experiment, solution times were not considered important, the de­ lays incurred were reasonably minimal .

The Language Analrzer

The purpose of the language analyzer is to create a descriptor-list (or, desclist) representation of the input problem. This list is a compact tree­ like representation of those semantic objects in the problem statement essential to effect a solution. The nodes of the tree are categorically prespecified; the tips of the tree refer to the semantic objects . For example, the analysis of the problem:

(WHAT IS THE PROBABILITY OF GETTING TWO OR! MORE HEADS OR EXACTLY 3 TAILS WHEN FOl.JR

COINS ARE TOSSED ONCE?)

would ultimately result in a desclist represented by

the tree in Fig. 2.

Examination of elementary textbook probability problems indicated that they overwhelmingly appear in one of two forms . The first is a one-sentence question containing the description of the probability outcome space, combined with an indication of which of those outcomes are to be considered favorable;

this is the case with our sample problem . . The se­ cond form consists of one or more sentences descri­ bing the outcome space, followed by a question sen­ tence specifying the desirable outcomes . The goal of the language analyzer is to reduce both forms to a common form via transformations, and then apply se­ mantic and syntactic analysis to provide a desclist equivalent of the problem . This goal is accomplished in three or four steps, as outlined below.

In the first pass over the input text , "number" words are replaced by their equivalent digits, phras­ es and synonyms are replaced by more meaningful forms, and phrase-modified numbers are so indica­ ted . At the conclusion of this first transformational pass, the above problem becomes

(WHAT IS THE PROBABILITY OF GETTING (GE 2) HEADS OR 3 TAILS WHEN 4 COINS ARE

TOSSED 1 TIMES ?)

A secondary transformational pass is then per­ formed. The purpose of this analysis is to break the problem do\\11 further into a series of simple senten­ ces, followed by a question sentence. It will subse ­ quently be assumed that the simple sentences contain a complete outcome space specification, while the question sentence contains a description of the fa\"­ orable events. Examples of the kind of rearranging transformations performed are

~ \\"H EI\ J? ? _. J? . A ? ~ FRO l\1 J? \\'HICH verb £ .. J? verb f . ~ . A THAT , IF J? , f . _. J? . ~ THAT £ .

where ~ J? , and £ are clauses or phrases. The simple sentences thus produced are each then fur­ ther rearranged, via the application of a simple con­ text-free grammar, into a form consisting of a verb and its voice, a subject (possibly compount), and a predicate . The verb may not be the same as the one specified in the input, but one which is synonymous and representative of a class of like verbs . Aside from singling it out, no further action is taken with respect to the question sentence . In our example, the simple sentences would be represented as

((TOSS / PASSI\'E) (4 COINS) (1 TI:'IIES))

and the question sentence reduced to

(WHAT IS THE PROBABILITY OF �ETT~�(�E2)HEADS OR 3

TAILS?)

At this point, a third pass over the question sentence alone ma.v occur, depending on its form . In our example, no further action would be taken .

If, however, the question sentence had read

(WHAT IS THE PROBABILITY THAT 2 OR MORE HEADS, OR 3 TAILS APPEAR ?)

it would be reduced exactly to the previous (gerun­ dive) form. This global reduction simplifies the grammar for the parser in the next pass by restrict­ ing the allowable sentential forms.

The final step in the language analysis consists of a keyword scan over the simple sentences com­ bined with a syntax analysis of the question sentence. The keyword scan attempts to classify the problem oy looking tor those words with highest semantic con­ tent; in the type of probability problems under con­ sideration, these words are those referring to dice, coins, or cards . If such a classification is possible, a search for modifiers of those words and related words is instituted; for the types of problems exam­ ined, this was sufficient to determine the outcome space exactly . If a classification of this nature is not possible, the verbs of the simple sentences are examined for semantic content. For example, verbs such as "distribute" and "place" would indicate ar­ rangement-type problems, whereas "contain" and "draw" would indicate sampling . The voice of the verb determines which of the subject or predicate are to be examined for the objects being acted upon. In these cases, more information is extracted in the form of numbers and the modifiers and/ or nouns they specify . This type of heuristic analysis was again adequate in determining the outcome space .

The syntax analysis of the question sentence is performed utilizing an LL (1) grammar for the Eng­ lish language subset on a simulated one-state push­ down machine (cf. Lewis et al [4]). The language subset is restricted to include just those grammatical constructs which normally appear in basic probabi­ lity problems; excessive wordage was regarded as typical of more advanced texts . The actual words appearing can be arbitrary: the top-down, predic­ tive analysis assumes word classifications if no se­ mantics are present . Context sensitivities, such as antecedent references, are processed by associating "properties" with particular sentential forms and passing them through the analysis by combining them with affected productions (cf. Stearns and Lewis [8]). This permits the analyzer to make assumptions about relations between input words despite the lack of se­ mantic information about them . The result of the syntax analysis is a symbolic description of the sim­ ple probability events described in the problem, to­ gether with a specification of the combination of these events required to solve the problem. This informa­ tion, combined with the results of the semantic scan, constitute the desclist for a given problem . For our example, the desclist is pictured in Fig. 2. A more complete description of the analysis may be found in Gelb [3).

The Solution Generator

Solutions are generated in four steps using the information contained in the desclist. The first three stages produce symbolic results in a tutorial progres­ sion; the final stage produces a numerical result.

The first stage examines the compound event structure (i.e . , the combination of simple events) in the desclist and performs a symbolic expansion ac­ cording to the addition rule of probability:

This is a straightforward combinatorial problem, and, in our example, would result in a LISP equivalent of

Using this expansion, the second solution stage examines each multiple event term to determine if the component events are mutually exclusive or inde­ pendent . In the latter case, the joint probability is replaced by the (symbolic) product of the component probabilities; in the former case, the term is just discarded . The criteria for mutually exclusive or independent events are a collection of heuristics established for each problem type; if there is doubt, the terms are not replaced. The sample problem would be recognized as consisting of two mutually exclusive events, and would be reduced to a form representing

In the third stage of solution, each symbolic probability term is examined and replaced by a com­ binatorial form representing its value. These new forms constitute the most explicit symbolic repre­ sentation of the probabilities, containing combinations, permutations, fractions, and arithmetic operations. Producing these terms involves dissecting the events and combining indicated formulas and/ or probability distributions; in certain cases, it is necessary to gen­ erate and examine the outcome space explicitly (this is particularly true of joint events) . Much of this pro­ cedure is algorithmic; heuristics are applied when the desclist information is insufficient or incomplete. In our example, the result of the third stage would be the LISP equivalent of The fourth stage applies the indicated opera­ tions to achieve a numerical result; both a fraction and its decimal equivalent are displayed. The frac­ tional result is presented in lowest terms as a con­ sequence of expressing numerator and denominator as the products of their prime factors, and removing common factors . For the sample problem, this would result in the final solution

15/16 (or . 9375)

The Driver

The driver requests a problem from the user, and passes it on to the language analyzer without em­ bellishment. Part of the driver is resident in the language analyzer, controlling the flow from pass to pass, and reflecting errors back to the user. The actual construction of the desclist is performed by the driver, which then passes control to the solution generator . Each stage of the solution generation is returned to the driver for display, the driver then returns fue result to the solution generator for fur­ ther analysis. At the conclusion of the fourth solution stage, the driver re-initializes itself and requests a new problem. STOP terminates the problem-solving session.

Limitations and Extensions

HAPPINESS is currently limited to the solution of very basic probability problems. However, the system is extendable along several dimensions:

1. The language complexity may be fairly easily increased by augmenting the current LL(1) grammar and specifying the new productions
2. The problem types may be expanded by specifying the new keywords and adding the solution routines
3. Interactive error recovery is readily im­ plementable on a language level thanks to the power of predictive parsing techniques
4. The words and phrases in the data base may be modified dynamically, thus permitting the system to learn (an artificial belief sys­ tem would be helpful here)
5. The addition of a theorem-prover to HAPP­ NESS would permit the solution of many basic probability problems of a theoretical nature

As HAPPINESS was constructed, areas (1) and (2) above were modified in a straightforward manner to provide increased solving capability. The power of LISP greatly enhances the ability to provide system extensions.

Discussion

The difficulties inherent in the computer solu­ tion of natural language probability problems were myriad and required the development of more sophi­ sticated and general techniques to overcome than were utilized by the earlier STUDENT and CARPS systems. Aside from the challenging problems of linguistic ana­ lysis, the determination of the pertinent symbolic re­ sult formulas leading ultimately to a numerical solu­ tion was a formidable task.

Probability questions, including those of a basic nature intended for solution by HAPPINESS, encom­ pass an extremely diverse class of problems which do not readily lend themselves to a generalized tres.tment. They each tend to require the creation of a single, specially tailored solution function as opposed to mere substitution into a universal form and, because of lim­ ited applicability, the developed formula is normally discarded after use. To maintain a certain degree of flexibility, then, it became necessary to develop a collection of very powerful, primitive functions with multiple applications. This approach may be contra­ sted with the limited formulations available to STU­ DENT (simultaneous equations) and CARPS (differen­ tiated system of equations).

The production of the solution formulation itself involved a great deal more than the identification of admissible problem variables and constants. Analy­ tic treatment of the semantics of these elements was indicated at various stages in the formula generation process so as to eliminate the subsequent creation of unnecessary and incorrect solution components. Moreover, since the objects in the system were prob­ abilistic events with potentially multiple semantic constraints (as opposed to variables with unique spe­ cifications), considerable circumspection of the in­ terrelationships among events constituting joint prob­ abilities was required.

Because of the design intention to permit "unre­ stricted" language input (or, perhaps, limiting to em­ pirically determined common forms), HAPPINESS was able to circumvent somewhat a common com­ plaint in earlier systems. The utilization of heuris­ tics in this regard, coupled with the judicious appli­ cation of powerful syntactic analysis techniques adap­ ted from recent compiler advances, allowed for greater scope and versatility in communicating prob­ lems to the system.

The order of magnitude increase in complexity of the problems attacked by HAPPINESS, combined with the required greater depth of solution capability with­ in the system, has resulted in a successful and effec­ tive problem solving tool.

Conclusions

Many of the techniques utilized by this system appear to wear well; they can be applied equally well to problem-solving systems unconnected to probabi­ lity. The predictive parsing algorithm utilizing LL(k) property grammars with heuristic decision-making procedures, permits a flexible analysis of the input language while maintaining necessary semantic con­ straints . Keyword analysis using heuristics also seems to allow reasonable ability to recognize prob­ lem elements containing semantic information. Sym­ bolic solutions provide a tutorial capability, as well as guiding interactive error recovery.

Combining the above techniques with more power­ ful deduction schema may provide a method with which to construct general problem-solving systems . Such systems, operating with small, extendable data bases, could be readily tailored to meet specific processing needs .

Figures

Examples

(PLV.SE INPU'I' PRO&~)

(A pair of dice are toaaed twice ·. What ia the probability of qetting 7 pointa on th· firat tOll and 11 points on the aecond ?)

(A PAIR OF DICE ARE TOSSED TWICE · IIHAT IS THE PROBABILITY OF GETTING 7 POINTS ON THE FIRST TOSS AND 11 POINTS ON THE SECOND ?)

IELI\PSED TIME NOW 0 . 08099997 SECONDS )

(1\P"TER PRIMARY (IDIOMI\TIC) TAANSFORMI\TIOt: , PROBLE~ BECC>t-IESI

(2 DICE ARE TOSSED 2 THIES · IIHA"l" IS THF. PROBA~ILITY OF GETTING 7 POINTS ON THE ( 11 TOSS AND 1 1 POINTS Oil THF ( 2) ? I

(ELAPSED TIME NOW 0.329 SECONDS)

(1\P"TER SECONDARY (REARRANGING) TAANSPOPIIATIOt: : )

(THE SIMPLE SENTENCES ARE) ((TOSS I PASSIVE) (2 DICE) (2 TIMES))

(THE QUESTION SENTENCE IS) (IIHAT IS THE PROBABILITY OF GE'I'TING POINTS ON TRE ( 1) Tr.SS AND 11 POINTS ON THE ( 2) 1)

(ELI\PSED T:UU: NOW 0.132 SECONDS!

(1\P"TER SYNTAX ANALYSIS OF QUESTION SENTENC"E 1)

(DESCLIST POR THIS PROBLEI< CONTAINS :)

PROBLEMTYPE· DICE POPULATION· 2 OBJECTS SAMPLESIZEITRIALS· 2 SIMPLE EVENTS· ( G12'80 G12l79) C1208lr· ((11 POitrrl NIL (1) t:IL !21 NIL) G12l79· ( (7 POINT) NIL (1) 1/IL ( 1) NIL) COMPOUND EVE~"T STRUCTURE· (Al!D (OR C12·791 (OR C12·8 0 ))

REPLACE:MrNT _INVOLVED? NO

(ELI\PSEO TIME NOW 0. 6 56 SECONDS I

(FIRST LrvEL SOLUTION TO PROBLE~ IS I

(PLUSF (PROB (QUOTE ( G12079 G12080))) I

(TIME POR EVALUATION WAS 0.032 SECONDS)

(SECOND LrvEL SOLUTION TO PR08LP-"' IS)

(PLUSFN (TIMESP'N (PR (QUOTE G12l79)) IPR (OUOTE C12080))))

(TIME POR EVALUATION WAS 0 · 0 S SECONDS I

(STATUS or rv!:NTS NASI

( ( ( G12l79 G12410) (INDEPENDENT NOTM\."I"UALLYEXCLU~IVE)))

(THIRD LI!:Vr:L SOLUTION TO PROBLEII IS)

(PLUSPMC (TlMESPMC (TIMESPIU\C (FRACTION (NOC0>'8INS 1 1 I 1 I (POIII'!RrRAC (1 6) 1) (,.OW!:RrRAC 15 E) 0)) (TIMESPMC (PRACTIO!i (NOCOMBINS 1 1) 1) (POifERPIU\C ( 1 181 1) (POIII'!RPIU\C ( 17 11) 0)) ))

(TIME POlO I!:VAl.UATION WAS 0. U 3 SECONDS)

(FOURTH LI!:V"£L SOLUTION TO PROBLEII IS)

11108 (OR 0 . 009259257)

(ELI\PSED TIME NOW 0,065 SECONDS)

(TOTAL TIME FOR PROBLEM SOLUTION WAS 1.500 SECO~"DS I

(PLV.SE INPUT PROBLEM)

(A box containa aixteen good and four defective fuaea are drawn ·, what 1· the probability that they are defective ?) It 2

(A BOX CONTAINS SIXTEEN GOOD AND POUR DErF.CTIVI' FC~ES · IT 2 ARE DRAWN , NllAT IS THE PROBABILITY TH.O.T Tl!rY ARF DErECTIVE ? )

!ELAPSED TIME NOW 0.01200002 SECONDS)

(APTER PRIMI\RY (IDIOMATIC) TRANSrORMATiot: , PROBLP-"' BECO,ES I

(1 BOX CONTAINS 16 GOOD ANt> 4 DUECTIVI' FUSES · Ir 2 ARr DRAWN , IIHAT IS THE PROBABILITY THAT THEY ARE DEFECTIVE ? I

(ELI\PSED TIME NOW 0.3 SECONDS)

(1\P"TER SECONOAJIY (REAJUIANCINC) TRANSFORMATION :I

(THE SIMPLE SEIITENCES ARE) ( (CONTAW I ACTIVE) ( 1 BOX) (16 GOOD AND 4 DEFECT I".'!: FVSES )) ((DRAW I PASSIVE) 12) NIL)

(TRE OUESTION SENTENCE IS) (WHAT IS THE PROBABILITY THAT THEY ARE DErECTIVI' 'I

(ELI\PSED T:UU: NOW 0. 199 SECONDS)

(1\P"TER TERTIARY (CASE-REDUCING) TRANSFOIU'.ATION , THE QVES~ION SENTENCE BECOMES : I

(WHAT IS THE PROBABILITY or GETTING ALL DEPFCTIVE ? I

(ELI\PSED TIME NOt! 0.06100002 SECONDS!

(NO RECOC!IIZABLE JtEYNORDS POUND IN PROBLE:H . ASSUIIED SAIIPLING PROI~. ) (1\P"TER SYNTAX AJIAL\'S IS OF OUESTION SP:IITENCE : I

(ASSUMING THAT · 16 GOOD · MEANS · 16 COOn FV~ES ·) (ASSUMING THAT · 2 ° MEANS · 2 FUSES ·)

(DI:SCLIST POR THIS PROBLEM CONTAINS :)

PROBLEMTYP!· SAMPLING

POPULATION- ( ( 0 DEFECTIVE FCSES ) ( 16 GOOD Ft;SES ) ) AS OBJECTS

SAIIPLESIZE/TIIIAl.S· 2 SIMPU EVENTS· ( G12 .. 5)

GUO I!· ((FUSE) I DEFECTIVE) 12) NIL NIL NIL) COMPOUND EVENT STRUCTUU· (OR G12 .. 5) REPLACEM!IIT _ IN\ft>LVE07 NO

(ELAPSED TIME NOW 0. 069 SECONDS)

(FIRST LEVEL SOL~"TION TO PROBLEM IS)

(PLUSF (PROB (QUOTE ( G1 2085) )) )

IT IME FOR EVALUATION WAS 0.028 SECONDS)

(SECOND LEVEL SOLt:TIOII TO PROBLD~ IS)

IPLUSFN IPR (QUOTE G12085)))

ITIME FOR EVALUATION W'-S 0 . 026 SECONDS)

!THIRD LEVEL SOLl."TION TO PROBLEM IS)

IPLt:SFRAC ISIMPLIFYFRAC I LIST ICOMBINL Q 2) ICOMBit:L 16 0)) (COMBINL 20 2) ) )

(TIME FOR EVALUATION WAS 0. 07099999 SECONDS)

(FOURTH LEV!:L SOLUTION TO PROBLEM IS)

3/ 95 lOR 0 . 03157895)

I ELAPSED TIME NOW 0. 108 SECONDS)

(TOTAL TIME FOR PROBI.EM SOLUTION WAS 1. 37 SECOI!OS)

((CONTAIN / ACTIVE) (1 IOJICH) (0 rEI!D AND l BIIAJai:T AND

5 CliiJtTQUS! WI!IIFELS)) ((DRAW I PASSIVE) (3) NIL)

(Till! QUESTION SEN'I'ENCE IS)

!WNAT IS THE PJIOIABILITT THAT 2 AU CHARTiti!USE AND 1 IIIAJOrf 7)

(ELAPSID TIKI - 0.227 SECONDS)

(ArTER T!!RTIAJIY (CASE-IIEOUCING) TRAIISFOP.MATION TilE QUESTION SENTENCE IECOI'T.S : )

(WHAT IS THE PROBABILITY OF GETTING 2 CHARTREUSE AND 1 BRA~l<Y 7)

(ELAPSED TIME NOW 0.108 SECONDS)

(NO JU:COGNIZABLE 1\EYWORDS FOUND Ill PROBLEM. ASSUMED SAMPLING PROBLEM.)

(ArTER SYNTAX ANALYSIS OF QUESTION S~l!"l'EIIC£ 1 )

(ASSUMING THAT · BRA~J(Y · MEANS · 3 IRA~l<Y I<ERFnS ") (ASSUMING THAT 0 · FERlJ · M!:ANS · 0 FERO WERFFLS ") (ASSUMING THAT 0 3 · MEANS · 3 WERFELS ·)

(OESCLIST FOR THIS PnQBLDI CONTAINS : )

PROBLEM"l'YPE· SAMPLING

POPI.!LATIOII· ( ( 5 CHARTREUSE WERTELS ) ( 3 BRAJ<rt WEP.nLS (4 FERO IIEJIFELS ) ) AS OBJECTS

SAIIPLES IZE/TRIAI.S· 3

SIMPLE EVENTS· ( G12503 G12502) G1250!· ((WERTEL) (BRAJ<I<Y) (1) NIL NIL NIL )

G12502· ((WERTEL) (CHARTJU:t:SE) (2) IIIL NIL NIL)

COMPOl.'NO EVENT STRUCTt:RI!· (AND (OR G12502) (OR G12503))

REPLACEM!NT _INVOLVED? 110

(ELAPSED TIKI NOW 0. 715 SECONDS)

(PLEASE INPUT PROBLEM)

(F'roll\ a Iorch containinq · terd and 3 brakky and 5 chartreuae wertela 1 , l are drawn ·. What ia the probability that 2 are c hartreuae and t.he other brakky ?)

IFROM A ZORCR CONTAINING 0 FERlJ AND 3 BRAnT AND CKARTR£t:SE WERTELS · 3 AJU: OJIAWN · W!<AT IS THF PROBABILITY THAT 2 ARE CHARTREUSE AIID THE OTII!R BRUI<Y 1)

(ELAPSED TIME NOW 0. 09299999 SECONDS)

(ArTER PRIKARY (IDIOMATIC) TRANSFORMATION , PROBLD< BECOMES)

!FROM 1 ZORCR CONTAINING 0 FERlJ AND 3 BJIAJO(Y AND 5 CKARTRrt'SE WERTELS , 3 AU DJIAWN · WHAT IS THE PROBABILITY TRAT 2 ARE CKIJtTRI!USE AHil 1 BRAJO(T 7)

(ELAPSED TIME NOW 0.310 SECONDS)

I ArTER SECONDARY (JIEAIIIIANGING) TIIAIISFOIIMATION :)

(TH~ SIMPLE SENTENCES ARE )

I FIRST l.EVEL SOLUTION TO PROBLD< IS )

(PLUSF (PROB (QUOTE ( G12502 G12503))))

(TIME FOR EVALUATION WAS 0.032 SECONDS)

(SECOND LEVEL SOLUTION TO PROBLEM IS)

(PLUSFN IPR (QUOTE ( G12502 G12503))))

(TIME FOR EVALUATION WAS 0. 0 30 SECONDS )

(THIRD LEVEL SOLUTION TO PROBLEI' IS)

(PLUSFRAC ISIMI'LIFYFRAC (LIST (COMB IN!. 2) (COMBIIIL 3 1) (COMBIIIL 0 0)) (COMIIIIL 12 3)))

(TIME FOR EVALUATION WAS 0 . U SECONDS)

(FOURTH l.EIIEL SOLUTION TO PROBLEM IS)

3/22 (OR 0.1363636)

IE LAPS EO TIME NOW 0. 1 30 SECONDS)

(TOTAL TIME FOR PROBLEM SOLUTION WAS 1 . 182 SECONDS )

Bibl iograph\·

• [1) Bobrow, D. G. "Natural Language Input for a Computer Problem Solving System," Ph . D. Thesis, Department of Mathematics, MIT, Cambridge, Mass .; 1964 .
• (J) Charniak, E. "Computer Solution of Calculus Word Problems," Proc . Inti. Joint Conf.., Artif . Intell . , Washington, D. C.; May , 1969.
• Gelb, J.P. "The Computer Solution of English Probability Problems" , Ph . D. Thesis, Compu­ ter Science Program, RPI, Troy , New York; 1971.
• Lewis, P . M. et al. Theory of Compiler Design, in preparation .
• Lindsay, R . K. "Inferential Memor y as the Basis of Machines Which Understand Natural Language. " In Feigenbaum, E.A. and Feldman, J . (eds . ), Computers and Thought, McGraw-Hill, New York; 1963 .
• Raphael, B. "SIR: A computer Program for Semantic Information Retrieval. " In Minsky , M. (ed . ), Semantic Information Retrieval, The MIT Press, Cambridge, Mass. ; 1968.
• (7] Simmons, R. F . "Answering English Questions by Computer : A survey , " Comm . ACM, vol. 8, no . 1; January , 1965 .
• Stearns, R . E . , and Lewis, P . M. "Property Grammars and Table Mac hines," Information and Control, vol. 14, no . 6; June, 1969.