A Net Structure Based Relational Question Answerer: Description and Examples

1 · Introduction

Our main research interest has been in the organization of data structures for question an­ swering systems, systems that retrieve facts and have deductive and inductive capabilities to derive new information fz:om the facts explicitly given them. Our two main aims have been to maintain as much generality as possible so that no additional programming be needed regardless of the domain of knowledge for which the sys­ tem is used and to put as much question an­ swering power as possible into the memory structure itself rather than in the executive routines. This latter aim supports the first in that it would allow special instructions for par­ ticular domains to be entered into the memory in the same way as any other information. SAMENLAQ II, the system described in this paper represents progress toward reaching these aims. Further progress is being made in a later system (see Section 5).

SEMANLAQ II is based upon binary relations. This was a natural starting point because of the generality of binary relations, and the fact that system. The final section describes a later sys­ tem which is being developed to satisfy more com­ pletely the goals discussed above.

2. Implementation and Operation

SAMENLAQ II is a revision of SAMENLAQ, "A Semantic Association MEmory Net that Learns and ~nswers Questions" 1 o:- Both programs -are written in SNOBOL3 as interactive question an­ swering systems, but SAMENLAQ II, unlike SAMENLAQ which was run in batch mode with simulated interaction on a CDC 3600, is fully interactive and is currently running under the University of Wisconsin B5500 time sharing sys­ tem. SAMENLAQ II differs from SAMENLAQ in that it provides aids to the user, who inputs data directly via a teletype, allows for storage of input files and memories in disk files, and, most importantly, allows for recursive defini­ tions of relations and allows the user to control in real time how much effort the system should spend searching its memory to discover more information for use in answering a question.

Figures 2a and 2b depict the overall flow of control in SAMENLAQ II. Figure 1 demonstrates its operation. At the top level of operation, three types of input are allowable: statements, questions and requests to the system executive. [B1, 2a]* Representative examples are given in fig. 1 by lines "a," "f," and "b" respectively. Notice that user inputs are indicated by terminal left arrows whereas unterminated lines indicate SAMENLAQ II responses. Simple statements such as line "c" result in the construction of a net substructure containing the nodes "BOSTON", "EAST .OF", "EAST .OF(CNV)", and "WORCESTER" in which "BOSTON" and "WORCESTER" are tied to­ gether via the "EAST .OF" node and "WORCESTER" and "BOSTON" are tied together via the "EAST. OF(CNV)" node. This structure is considered in more detail in the next section. More compli­ cated statements such as line "a" are inter­ preted by the system as a series of simple statements.

The system provides the user with various types of feedback, some of which may be turned off by appropriate requests to the execu­ tive.[B7,2a] Lines prior to "f" demonstrate in­ put in the full and limited response modes. Line "b" requests that the full response mode be turned off. Requests are identified by a terminating " @". Other request options are in­ dicated in fig. 2. [B2, 2a]

Several relation words are built into the system. "MEMBER" allows a particular net search to be limited to a subclass of all the relations represented in the net. Subclass definition may take place at any point during a conversation and is determined solely by the user. Line "d" represents the introduction of the subclass "COMPASS. RELS". Such classes are useful for handling questions involving paths in the net which connect prescribed nodes.

*Bracketed references refer to the flow charts in fig. 2, E.g. "[B1,2a]" refers to Box 1 in fig. 2a.

"IMPLBY" allows a given relation to be de­ fined in terms of other relations. It is one of the most important features of SAMENLAQ II. The system has the ability to utilize "IMPLBY" information about a relation during the question answering process by using it as a generalized substitution rule.

Line "e" demonstrates the use of IMPLBY to introduce NORTH.OF(CNV) as an acceptable re­ placement for SOUTH .OF. The line also results in SOUTH .OF(CNV) IMPLBY NORTH .OF being in­ corporated in memory.

To enhance readibility, the system allows the user to introduce his own interrogatives by means of the form "x IS QUESTION".

Questions are terminated by "*". There are four possible types -- one . verification type (x R y *) and three fill in the blank types (x R _ *}, (_ R y *) and (x _ y *).[B3,2a]. Line "f" illustrates the x R _ * type, line "j" the X _ Y* type and line "k" the _ R Y* type. Notice that non-simple relations can be handled by the system. There are three types of rela­ tions used in SAMENLAQ II, simple, compound and complex. A simple relation is of the form R or R(CNV) where the character string R is not meaningfully decomposable and Y R (CNV) X if and only if X R Y. A compound relation is a simple relation or a relative product of simple relations and is of the form Rl/R2/R3, (or some­ times, as a stylistic variant, Rl/R2/R3/).

X Rl/R2/R3 Y holds if and only if there exists some z and w such that X R1 z, z R2 w and w R3 Y. A complex relation is a compound re­ lation or a compound relation with node restric­ tions. A node restriction is of the form (R-,0) where R is a simple relation and ,0 is a string of names, each one followed by a comma. Node restrictions are used to restrict the domain or range of a simple relation which forms part of the complex relation. For example, (R-,0)R1 is the relation R1 with a restricted domain, and Rl (R-,0) is R1 with a restricted range.

A name ,x, satisfies the node restriction (R-,0) if for all y in the string ,0 xRy is explicitly stored in memory. Thus the relational statement above holds if x satisfies (R1-,01) and (R2-,02), y satisfies (R7-,05) and there exists some z such

• a ALBANY,BUFFAW,NEW.YORK,POUGHKEEPSIE IN NEW.YORK.STATESTATEMENT - ALBANY,BUFFALO ,NEW. YORK,POUGHKEEPSIE IN NEW. YORK.STATE OK? ··· YES-

WAIT ···

READY

BOSTON, WORCESTER IN MASSACHUSETTS-

STATEMENT - BOSTON ,WORCESTER IN MASSACHUSETTS OK? ··· YES-

WAIT ···

READY

• b FLAG ECHO OFF@- REQUEST - FLAG ECHO OFF

READY

c BOSTON EAST .OF WORCESTER­

READY

WORCESTER EAST .OF ALBANY­

READY

ALBANY EAST .OF BUFFAW­

READY

ALBANY NORTH.OF POUGHKEEPSIE­

READY

POUGHKEEPSIE NORTH .OF NEW. YORK­ READY

IN MEMBER WCATION .RELS­ READY

• d NORTH .OF, EAST .OF MEMBER COMPASS .RELS­ READY

e SOUTH.OF IMPLBY NORTH.OF(CNV)­ READY

WEST .OF IMPLBY EAST .OF(CNV)­ READY

WHAT,HAS.WHAT.RELATIONSHIP.TO IS QUESTION­ READY

• I WILL USE THE FOLLOWING RELATIONS:
• f BOSTON EAST .OF WHAT*- EAST.OF/

I FIGURE BOSTON EAST.OF/ WORCESTER IF THIS IS SUFFICIENT, RESPOND - OK OTHERWISE TYPE AN INTEGER FOR FUTHER SEARCH OR - UST TROUBLES OR AN INPUT STATEMENT OR - EXAMPLES

• g I-
• I WILL USE THE FOlLOWING RELATIONS: NO FURTHER RELATIONS FOUND.

I FIGURE BOSTON EAST .OF/ WORCESTER

IF THIS IS SUFFICIENT, RESPOND - OK

OTHERWISE TYPE AN INTEGER FOR FUTHER SEARCH

OR - LIST TROUBLES OR AN INPUT STATEMENT OR - EXAMPLES

• h EAST .OF IMPLBY EAST .OF/EAST .OF-

STATEMENT - EAST .OF IMPLBY EAST .OF /EAST .OF OK? ··· YES-

WAIT

ENTER ANY OF THE ABOVE OPTIONS.

• I WILL USE THE FOLLOWING RELATIONS: EAST.OF/EAST.OF/

AND EAST .OF /EAST .OF /EAST .OF/

I FIGURE BOSTON EAST .OF/WORCESTER AND ALBANY AND BUFFALO IF THIS IS SUFFICIENT, RESPOND - OK

Fig. 1 A Conversation With SAMENLAQ II.

OTHERWISE TYPE AN INTEGER FOR PUTHER SEARCH OR - LIST TROUBLES OR AN INPUT STATEMENT OR - EXAMPLES OKWAIT ··· ANSWER - WORCESTER [Answer to Question posed at line "f".] AND ALBANY AND BUFFAW READY BUFFAW HAS. WHAT ,RELATIONSHIP. TO NEW. YORK*ZENTER COMMA LIST OF RELATION CLASSES TO BE USED OR - " ANY " ANYBUFFAW IN NEW, YORK.STATE IN(CNV) NEW. YORK ENTER - OK - OR AN INTEGER INDICATING NUMBER OF ADDITIONAL PATH LINKS, WAIT ··· BUFFAW EAST,OF(CNV) ALBANY NORTH,OF POUGHKEEPSIE NORTH.OF NEW,YORK ENTER - OK - OR AN INTEGER INDICATING NUMBER OF ADDITIONAL PATH LINKS. OKREADY FLAG ASK OFF@­ READY FLAG TRACE OFF @­ READY k WHAT (IN-NEW.YORK,STATE 1 )SOUTHWEST,OF BOSTON*- ! FIGURE BOSTON SOUTHWEST,OF(CNV)/(IN-NEW,YORK.STATE 1 ) UNKNOWN WHAT NOW? LIST TROUBLESAT THE FOLLOWING NAMES COULD NOT APPLY THE LISTED RELATIONS. BOSTON - SOUTHWEST .OF(CNV) WHAT NOW? SOUTHWEST ,OF IMPLBY SOUTH .OF /WEST .OF 1 WEST .OF /SOUTH ,OFSTATEMENT - SOUTHWEST ,OF IMPLBY SOUTH ,OF /WEST ,OF 1 WEST ,OF / SOUTH ,OF OK? ··· YESWAIT ··· WHAT NOW? 31 FIGURE BOSTON SOUTHWEST .OF(CNV)/ (IN-NEW. YORK,STATE 1 ) POUGHKEEPSIE WHAT NOW? SOUTH,OF IMPLBY SOUTH,OF/ SOUTH,OFSTATEMENT - SOUTH,OF IMPLBY SOUTH.OF/SOUTH.OF OK? ··· YESWAIT ·· , WHAT NOW? 31 FIGUJU; BOSTON SOUTHWEST.OF(CNV)/ (IN-NEW.YORK,STATE 1 ) POUGHKEEPSIE AND NEW. YORK WHAT NOW? OKANSWER - POUGHKEEPSIE [Answer to question posed at line "k".] AND NEW. YORK READY

Fig. 1 (cont.) A Conversation With SAMENLAQ II

*See figure 2b.

*This routine is used at [B4,2a], [B5,2a] and [B6,2a].

that z satisfies (R4-,0'3) and (RS-,0'4) , xR3z, and zR6y.

A complex relation may also consist solely of node restrictions, in which case it is an identity relation on a restricted domain (viz. the set of all names which satisfy all the node restrictions) and is the statement of a conjunc­ tive concept. The executive routines have built into them the ability to deal with converse rela­ tions and with compound and complex relations. When a relation serves to label an edge of the net, i.e. in its appearance in the value of a name, it is treated as a simple relation. Com­ pound and complex relations are used when de­ fining other relations and may themselves have definitions. Lines beginning at "k" illustrate these ideas.

Line "f" represents one of the four question types. To answer it, SAMENLAQ II attempts to apply "EAST .OF" to "BOSTON". Since the sys­ tem has the statement "BOSTON EAST .OF WORCESTER" represented explicitely in its mem­ ory, EAST .OF can be successfully applied - yielding "WORCESTER". Since the system does not know explicitly that "BOSTON EAST .OF ALBANY" or that EAST .OF is a transitive rela­ tion, it is incapable of finding further nodes satisfying "BOSTON EAST.OF X". This is illus­ trated in line "g" where "1" indicates that SAMENLAQ II is to execute one substitution cycle - i.e. substitute for each relation it is currently attempting to apply to a node, all acceptable replacements contained on the rela­ tions IMPLBY list.[Bl,2b) (The IMPLBY list for a relation R is a list of all relations, x, such that R IMPLBY X.) In line "h" the system is informed that EAST .OF is transitive. Two addi­ tional IMPLBY substitution cycles are then re­ quested by typing in "2".

Figure 3 illustrates an application of SAMENLAQ to rudimentary conjunctive concept formation. The statements presented in Fig. 3a supply the system with a small data base con­ cerning the relations of various objects in. a room. Note, in line "a" two of these are grouped into the class "SPLREL" · In Fig. 3b SAMENLAQ is asked to answer a question con­ cerning a relation it has never seen before. Failing to apply this relation, it is given a series of examples whose relationship to one another is arbitrarily designated CONCEPTI. Restricting its search to the relation class SPLREL, the system obtains all paths of length 2 or less connecting the example pairs. The properties common to each class of nodes at the same level along the path are also calculated. For example (CONSTRUCTION -ELECTRICAL,), (CONSTRUCTION-WOOD,) and (HAS.PART-ELE­ VATED.HORIZONTAL.SUPPORTING SURFACE,) are node properties common to the first, second, and third levels respectively. The path connecting the example pairs is "ON. TOP/ELEMENT". This relation is then placed upon the IMPLBY list for CONCEPTI. Finally CONCEPTI is used to de­ fine the original concept IS.AN.ELECTRICAL. COMMUNICATION. DEVICE. THAT .IS.ON. TOP .OF. A. PIECE. OF. WOODEN. The system then has sufficient information to answer the question and res ponds with the correct answer.

3. SAMENLAQ II Description

Statements entered into the memory are of the form "NAME! RELATION NAME2" where NAME! and NAME2 are non-decomposable names and RELATION is a simple relation. Information contained in such statements is stored on paren lists associated with NAME! and NAME2. Thus, the above statement produces the following paren list for "NAME! : "(RELATION-/I)" where the contents of the slash ~ "/1" is the ~ list "NAME2,". In the example below, the paren pair (WEST .OF-/3) on the paren list for ' WORCESTER indicates that Worcester is West of each of the elements found on the comma list named /3. Note that the value of a slash name is a comma list, similarly the value of a name is its paren list.

BOSTON

/1

WORCESTER

/2

/3

EAST .OF

/4

/5

(EAST.OF-/1)

= WORCESTER,ALBANY, BUFFAW,

(EAST .OF-/2)(WEST .OF-/3)

= ALBANY,BUFFAW,

BOSTON

= (IMPLBY-/4)(MEMBER-/5)

= EAST.OF/EAST.OF/,

COMPASS.RELS,.

Although the paren list looks like a conven­ tional attribute - value list it differs in that both the relations (attributes) and the names on the comma lists (values) are themselves names of paren lists and these various paren lists mutually occur as elements of each other. The memory may be thought of as a directed graph whose nodes are the names (BOSTON, WORCESTER, . etc.) and whose edges are labeled by the rela­ tions. Since, however, the relations are also names and thus should be thought of as nodes in the graph, we should, perhaps, think of the edges as being labeled by passing through a node, and all edges bearing the same label as passing through the same node.

The statement NAME! RELATION NAME2 is not only stored as such on NAMEl's paren list, but its converse, NAME2 RELATION(CNV) NAME! is stored on NAME2' s paren list. This is done so that the information contained in the state­ ment is recoverable from either name. Although this involves duplicate storage of information,

CHAIR,SHELF, TABLE HAS. fl.l\Wf ELEVATED,HOR,JZONTAL,SUPPORTING,SURFACE­ READY

DRESSER, BENCH HAS. PART ELEVATED, HORIZONTAL, SUPPORTING, SURFACE­

READY

SHELF HAS, PART BRACKET. SUPPORTS­

READY

CHAIR, TABLE,DRESSER,BENCH HAS,PART LEGS­

READY

DRESSER HAS. PART DRAWERS­

READY

BENCH,CHAIR,SHELF, TABLE,DRESSER ELEMENT FURNITURE­

READY

TVl, TTYl, TELl, TEL3,PENl,SIGNAL.UGHTl,RADIOl USED. FOR COMMUNICATION­

READY

TVl, TTYl, TEL3, TELl, TEL2, SIGNAL. LIGHT!, RADIO! CONSTRUCTION ELECTRICAL-­ READY

PENl CONSTRUCTION MECHANICAL­

READY

CHAIR!, CHAIR2 ELEMENT CHAIR­

READY

SHELF 1, SHELF2, SHELF 3 ELEMENT SHELF­

READY

TABLE!, TABLE2 ELEMENT TABLE­

READY

DRESSER! ELEMENT DRESSER-

READY

CHAIR!, CHAIR2, SHELF2 CONSTRUCTION METAL­

READY

BENCH!, SHELF!, TABLE!, TABLE2, DRESSER! CONSTRUCTION WOOD­ READY

RADIOl,PENl ON,TOP DRESSERl­

READY

SIGNAL.UGHTl,PICTUREl ON.TOP SHELFl­

READY

TVl ON. TOP TABLE2-

READY

TTYl ON. TOP BENCH I­

READY

BENCH! ELEMENT BENCH-

READY

PICTURE3, TEL3 ATTACHED, TO WALLl­

READY

TELl ON. TOP TABLE I­

READY

WHAT IS QUESTION­

READY

a ON. TOP ,ELEMENT MEMBER SPLREL­ READY

Fig. 3a A Conjunctive Concept Formation Example: Data Base Input.

a WHAT IS ,AN ,ELECTRICAL,COMMUNICATION. DEVICE. THAT .IS.ON. TOP .OF .A. PIECE, OF WOODEN FURNITURE*- ! FIGURE FURNITURE IS.AN ,ELECTRICAL, COMMUNICATION ,DEVICE, THAT .IS.ON ,TOP.OF ,A,PIECE,OF .WOO DEN(CNV )/ UNKNOWN WHAT NOW? EXAMPLESRELATION WHOSE DEFINITION IS TO BE FOUND ·· ,CONCEPTI­ RELATION CLASS CONCEPTI IS A MEMBER OF ··· SPLREL­ DEPTH OF ALTERNATE DEFINITIONS ·· , 2TYPE PAIRS X Y SUCH THAT X CONCEPTI Y. WHEN FINISHED, TYPE - END. TELl TABLERADIO 1 DRESSERSIGNAL,LIGHTl SHELFENDOK? ... YES­ THANK YOU, WAIT: ·· FROM THE EXAMPLES YOU HAVE GIVEN ME,! WOULD GUESS THAT CONCEPTI/ IS THE SAME AS (CONSTRUCTION-ELECTRICAL, )(USED.FOR-COMMUNICATION I )ON. TOP/(CONSTRUCTIO N-WOOD I )ELEMENT/(HAS. p ART-ELEVATED.HORIZONTAL.SUPPORTING,SURFACE,) WHAT NOW? IS .AN ,ELECTRICAL. COMMUNICATION ,DEVICE, THAT .IS.ON. TOP .OF .A.PIECE,OF · WOODEN IMPLBY CONCEPTI/ELEMENTSTATEMENT - IS ,AN ,ELECTRICAL. COMMUNICATION. DEVICE, THAT ,IS ,ON. TOP,OF ,A. PIECE,OF. WOO DEN IMPLBY CONCEPTI/ELEMENT OK? ··· YESWAIT ··· WHAT NOW? 2I FIGURE FURNITURE IS,AN .ELECTRICAL, COMMUNICATION .DEVICE, THAT .IS.ON. TOP .OF .A. PIECE,OF. WOO DEN(CNV)/ TTYl AND SIGNAL.LIGHTl AND TELl AND TVl AND RADIO! WHAT NOW? OKWAIT ··· ANSWER - TTYl AND SIGNAL.LIGHTl AND TELl AND TVl AND RADIO! READY [Answer to Question posed at line "a".]

changing the statement to its converse form for storage under the second argument allows all statements about a name to be stored in the same place (the name's value) regardless of whether the name was the first or second argu­ ment in the original statements. This contrasts with the methods for retrieving a relational statement from either argument used by the Relational Data File 4 (RDF) and by DEACON 1 ' 6 · In RDF, statements are stored in only one direction, but in different files, ordered on dif­ ferent parts of the statement. Thus to get all information about a single name, either one file must be searched exaustively or the name must be looked up in all files. In DEACON, the statements are stored in the form of closed "connecting rings" through the three parts of the statement. Thus the statement is reachable from any part of it without recourse to several files, but it is impossible to tell from a connecting ring where the statement should begin, i.e. whether the ring through x, R, and y represents the statement xRy, Ryx, or yxR.

The generality of SAMENLAQ derives largely from the ability to introduce new relations at any time, to introduce definitions of new rela­ tions or relations that had previously been un­ defined and to extend the definition of a rela­ tion. Definitions may also be added at any time and are stored in the memory net structure just like any other data. Definitions are not given in terms of relation properties that have been built into the system, but in terms of other relations. Nevertheless, various standard relation properties can be dealt with, for exam­ ple:

1. Entering the statement, "Rl IMPLBY Rl/Rl causes Rl to be transitive.
2. Entering "Rl IMPLBY Rl (CNV)" causes Rl to be symmetric.
3. It was previously pointed out (section 2) that the complex relation consisting only of a node restriction (R-,0') serves as an iden­ tity relation for all names x such that for every name y in the string %, xRy is ex­ plicitly in memory. If % were the string consisting only of the delimiter ",", (R-,0') would be the identity relation for all x such that for any y, xRy were explicitly stored. If this were true for all x in mem­ ory, (R-,) would be the universal identy relation. In that case entering,the state­ ment "Rl IMPLBY (R-,)" would cause Rl to be reflexive.

Thus, Rl might be defined to be an equiv­ alence relation by entering "Rl IMPLBY (MEMBER-,), Rl (CNV), Rl/Rl/". In addition to these forms of definition, a relation may be de­ fined a) by using only other relations, and b) by combining other relations along with the relation being defined thus forming a general re­ cursive definition. A wide range of relations may thus be used without programming them into the executive routines as it is done in Raphael's SIR 8 · This method of defining relations also contrasts with that used by Elliotf in "GRAIS". In "GRAIS" relational properties are built into the executive routines. In fact, this is done in such a way as to provide specific routines for 32 classes of relations. The user introduces a new relation by specifying which of the 32 classes it belongs in and this determines how it will be handled. This does not allow a user to uce a relation whose properties he either does not know completely or does not wish to make specific initially. A user may also define a relation in terms of a Boolean function of previ­ ously introduced relations. However, these re­ lations may not be stored in the data structure, only used for question answering.

It is interesting to note that the user builds his own logic system into SAMENLAQ II when he specifies IMPLBY information (used as the rules of inference) and other statements (the axioms). The only logical structure ·imposed on the user is the metatheoretic substitution rule embodied in the procedures which apply IMPLBY and the limits on the form of a rule of inference im­ posed by the syntax of complex relations. If the user specifies a strange or even self-con­ tradictory "logic" SAMENLAQ II will produce de­ ductions that are equally strange or contradic­ tory; interpretation is in the mind of the user. (For example, in section 4, deductions arising from the relation "IS. PART .OF" only make sense if the interpretation of "x IS. PART .OF y" moti­ vating the rule of inference "IS.PART.OF IMPLBY IS. PART .OF /IS(CNV)" is that every member of y has a part which is a member of x and the in­ terpretation of "IS" is "is subset of.")

It would be possible to append an executive to SAMENLAQ II which would constrain the type of logical system to one with certain prescribed properties.

4. Some Varied Applications of SAMENLAQ II

The following sample conversations demon­ strate SAMENLAQ II's ability to deal with rela­ tions arising from a variety of problem areas.

The first conversation (Figure 4a, b, c) in­ volves a subdialogue from SIR 8 · It demon­ strates SAMENLAQ's ability to handle relations such as part, subset, owns and element and the interdependence between such relations. Al­ though specific relations and relational proper­ ties are not built into the system, SAMENLAQ can utilize the information (x) (Y) (Z) (x IS. PART. OF Y & ZcY- x IS.PART .OF Z) via the IMPLBY statement IS.PART.OF IMPLBY IS.PART.OF/IS (CNV). (See comments at the end of section 3.)

IS. PART .OF IMPLBY IS ,PART ,OF/ IS, PART ,OF ,IS.PART .OF /IS(CNV)­ READY

SOMETIMES IMPLBY IS(CNV)­

READY

IS IMPLBY IS/ IS­

READY

NOSE IS ,PART .OF PERSON­

READY

NOSTRIL IS, PART .OF NOSE­

READY

PROFESSOR IS TEACHER­

READY

TEACHER IS PERSON­

READY

NOSTRIL IS.PART,OF PROFESSOR*!-

! FIGURE NOSTRIL IS. PART . OF/ NOSE AND PERSON WHAT NOW?

1-

I FIGURE NOSTRIL IS, PART . OF/ NOSE AND PERSON AND TEACHER

WHAT NOW?

1-

I FIGURE NOSTRIL IS,PART ,OF/ NOSE AND PERSON AND TEACHER AND PROFESSOR WHAT NOW?

OK-

WAIT ···

ANSWER - TRUE

READY

PERSON IS UVING CREATURE­ BAD INPUT. TRY AGAIN,

READY

PERSON IS UVING,CREATURE­

READY

HAS,AS,PART IMPLBY IS,PART.OF(CNV)­

READY

UVING.CREATURE SOMETIMES/ HAS.AS,PART NOSTRIL*3I FIGURE UVING,CREATURE SOMETIMES/ HAS,AS,PART/ NOSTRIL WHAT NOW?

OK-

ANSWER - TRUE

READY

CRT IS DISPLAY,DEVICE­

READY

CRT IS,PART,OF B550o--­

READY

BRUTUS IS B550o--­

READY

a SCREEN IS. PART ,OF DISPLAY. DEVICE-

READY

SCREEN IS,PART,OF BRUTUS* l-

I FIGURE SCREEN IS.PART.OF/ DISPLAY.DEVICE AND CRT

WHAT NOW?

1-

I FIGURE SCREEN IS.PART.OF/ DISPLAY,DEVICE AND CRT AND B5500 WHAT NOW?

I FIGURE SCREEN IS,PART.OF/ DISPLAY,DEVICE AND CRT AND B5500 AND BRUTUS

WHAT NOW?

Fig. 4a Learning and Deduction Using Several Relations From SIR

OK-

WAIT,,,

ANSWER - TRUE

READY

OWNS IMPLBY IS/OWNS-

READY

FIREMAN OWNS PAIR.OF ,RED, SUSPENDERS­

READY

DOCTOR OWNS PAIR,OF .RED,SUSPENDERS*1-

I FIGURE DOCTOR OWNS/ UNKNOWN

WHAT NOW?

OK-

WAIT ···

ANSWER - UNKNOWN

READY

FIRECHIEF IS FIREMAN-

READY

FIRECHIEF OWNS PAIR. OF ,RED,SUSPENDERS*1-

I FIGURE FIRECHIEF OWNS/ PAIR,OF ,RED, SUSPENDERS

WHAT NOW?

OK-

WAIT ···

ANSWER - TRUE

READY

a EXAMPLE,OF IMPLBY EXAMPLE,OF/IS­

READY

A IMPLBY EXAMPLE,OF­

READY

STU OWNS WG,WG,DECITRIG1-

READY

WG,WG, DECITRIG1 EXAMPLE,OF WG,WG,DECITRIG­

READY

WG,WG,DECITRIG IS SUDE,RULE­

READY

STU OWNS/A SUDE RULE*1-

I FIGURE STU OWNS/A/ WG.LOG,DECITRIG

WHAT NOW?

1-

I FIGURE STU OWNS/A/ LOG.WG,DECITRIG AND SUDE.RULE

WHAT NOW?

OK-

ANSWER - TRUE

READY

ENGINEERING,STUDENT OWNS SUDE,RULE­

READY

GEORGE EXAMPLE,OF TECH.MAN­

READY

TECH,MAN IS ENGINEERING,STUDENT­ READY

GEORGE OWNS/A SLIDE,RULE*1-

I FIGURE GEORGE OWNS/A/ UNKNOWN WHAT NOW?

1-

I FIGURE GEORGE OWNS/A/ UNKNOWN WHAT NOW?

OK-

ANSWER - UNKNOWN

READY

[Answer to question posed at line "a" Fig. 4a .]

Fig. 4b Learning and Deduction Using Several Relations From SIR

• c ENGINEERING.STUDENT EXAMPLE.OF(CNV)/ OWNS/ EXAMPLE.OF WG.WG.DECITRIG*l­ I FIGURE ENGINEERING.STUDENT EXAMPLE.OF(CNV)/ OWNS/ EXAMPLE.OF/ UNKNOWN WHAT NOW?
• b STU EXAMPLE.OF TECH.MAN[Provide additional information necessary to answer question.] STATEMENT - STU EXAMPLE.OF TECH.MAN

OK? ··· YES-

WAIT ···

WHAT NOW?

• I FIGURE ENGINEERING. STUDENT EXAMPLE .OF(CNV)/OWNS/EXAMPLE .OF/ LOG.WG.DECITRIG AND SLIDE.RULE

WHAT NOW?

OK-

ANSWER- TRUE

[Answer to question posed at line "c".]

READY

Fig. 4c Learning and Deduction Using Several Relations From SIR

NEW, YORK,LOS,ANGELES,SANTA.BARBARA,ORLANDO IS CITY­ READY NEW,YORK HAS,POPULATION 7781984-­ READY LOS,ANGELES HAS,POPULATION 2479015READY ORLANDO HAS,POPULATION 88135READY SANTA,BARBARA HAS.POPULATION 58768READY 7781984,24 79015 IS, GREATER. THAN 100000READY 88135,58768 IS.LESS.THAN 100000READY BOEING.707,BOEING.727,DC8 IS JET.PLANE­ READY CONVAIR. 240 IS PROP. PLANE­ READY JET. PLANE, PROP. PLANE SUBSET AIRPLANE­ READY IS IMPLBY IS/SUBSET­ READY BOEING,707,DC.8 CARRIES !50READY BOEING, 727 CARRIES 120READY CONVAIR,240 CARRIES 50READY 150 IS, GREATER. THAN 12 a­ READY 50 IS, LESS, THAN 12 a­ READY a IS.LARGE IMPLBY (IS-CITY, )HAS .POPULATION/ (IS.GREATER. THAN-100000,) HAS. POPULATION(CNV)/ISREADY . b IS.LARGE IMPLBY (IS-AIRPLANE, )CARRIES/ (IS.GREATER. THAN-120, )CARRIES (CNV)/ISREADY WHAT IS QUESTION­ WHAT IS AIRPLANE*!- ! FIGURE AIRPLANE IS(CNV)/ BOEING. 707 AND BOEING. 727 AND DC,8 AND CONVAIR.240 WHAT NOW? OKWAIT ··· ANSWER - BOEING. 707 AND BOEING. 727 AND DC.8 AND CONVAIR.240 READY c DC,8 IS,LARGE WHAT*lI FIGURE DC. 8 IS, LARGE/ JET. PLANE AND AIRPLANE WHAT NOW? OKWAIT ··· ANSWER - JET. PLANE AND AIRPLANE READY

Fig. Sa Application to census, airplane and airline flight data with an ambiguous relation.

WHAT IS.LARGE CITY*lI FIGURE CITY IS.LARGE(CNV)/ NEW. YORK AND LOS,ANGELES WHAT NOW?

OK-

WAIT ···

ANSWER - NEW. YORK

AND WS,ANGELES

READY

! FIGURE SANTA,BARBARA,ORLANDO HAS,POPULATION/ 58768 AND 88135

SANTA.BARBARA,ORLANDO HAS.POPULATION WHAT*- WHAT NOW?

OK-

WAIT ···

ANSWER - 58768

AND 88135

READY

FLT. 2 07 FLIES. FROM NEW. YORK­

READY

FLT.207 FLIES.TO WS.ANGELES­

READY

DC.8 USED.ON FLT.207-

READY

FLT ,207 DEPARTS.AT !O:OOAM­

READY

FLT.207 ARRIVES.AT !2:30PM­

READY

FLT.308 FLIES,FROM NEW.YORK­

READY

FLT. 308 FLIES. TO ORLANDO­

READY

BOEING. 727 USED.ON FLT.308-

READY

FLT ,45 FLIES,FROM WS.ANGELES­

READY

FLT ,45 FLIES. TO SANTA.BARBARA­

READY

CONVAIR.240 USED,ON FLT ,45READY

FLT ,45 DEPARTS.AT 1:30PM­

READY

FLT.45 ARRIVES,AT 2:15PM­

READY

1:30PM IS.LATER,THAN !2:30PM­

READY

CONNECTS. WITH IMPLBY ARRIVES .AT/IS .LATER. THAN(CNV)/DEPARTS ,AT(CNV)­ READY

WHAT (FLIES,FROM-NEW. YORK, )CONNECTS .WITH/FLIES. TO SANTA,BARBARA*lI FIGURE SANTA.BARBARA

FLIES. TO(CNV)/CONNECTS. WITH(CNV)/(FLIES,FROM-NEW. YORK,) FLT .207 WHAT NOW?

OK-

ANSWER - FLT ,207

READY

FLT ,207 USED.ON(CNV)/IS.LARGE AIRPLANE*-

! FIGURE FLT.207 USED.ON(CNV)/IS,LARGE/ JET.PLANE AND AIRPLANE

WHAT NOW?

OK-

ANSWER - TRUE

READY

Fig. 5b Application to census, airplane and airline flight data with an ambiguous relation.

a TRUE IMPLBY IMPLIES(CNV)/TRUE­

READY

FALSE IMPLBY IMPLIES/FALSE­

READY

A IMPLIES B­

READY

A TRUE PROPOSITION-

READY

B TRUE PROPOSITION*l-

I FIGURE B TRUE/ PROPOSITION

WHAT NOW?

OK-

WAIT ···

ANSWER - TRUE

READY

FOLLOWS,FROM IMPLBY IMPLIES(CNV)­

READY

b IMPLIES IMPLBY IMPLIES/IMPLIES­

READY

C IMPLIES D-

READY

D FALSE PROPOSITION­

READY

C FALSE PROPOSITION*l-

I FIGURE C FALSE/ PROPOSITION

WHAT NOW?

OK-

WAIT ···

ANSWER - TRUE

READY

FORGET PROPOSITION@­

FORGET - PROPOSITION

OK? ··· YES-

WAIT ···

READY

B IMPLIES C-

READY

D FALSE PROPOSITION­

READY

A FALSE PROPOSITION*l-

I FIGURE A FALSE/ UNKNOWN

WHAT NOW?

2-

I FIGURE A FALSE/ PROPOSITION

WHAT NOW?

OK-

WAIT ···

ANSWER - TRUE

Fig. 6a A Simple Problem in Logic Using Modus Ponens

READY ELEMENT IMPLBY ELEMENT/SUBSET­ READY SI SUBSET S2READY S2 SUBSET S3READY EI ELEMENT SI­ READY WHAT IS QUESTION­ READY EI ELEMENT WHAT*I1 FIGURE EI ELEMENT/ SI AND S2 WHAT NOW? II FIGURE EI ELEMENT/ SI AND S2 AND S3 WHAT NOW? OKWAIT ··· ANSWER - SI AND S2 AND S3 READY c D FOLLOWS.FROM A*2I FIGURE D FOLLOWS.FROM/ C AND B WHAT NOW? II FIGURE D FOLLOWS.FROM/ C AND B AND A WHAT NOW? OKWAIT ··· ANSWER - TRUE READY F IS AXIOMREADY [Answer to question posed at line "c ".] FIND.PROOF .FROM IS QUESTION­ READY A DERIVABLE.FROM F­ READY D FIND. PROOF .FROM AXIOM*6ENTER COMMA UST OF RELATION CLASSES TO BE USED OR - " ANY " ANYD FOLLOWS.FROM A DERIVABLE.FROM F IS AXIOM WHAT NOW? OKREADY

Fig. 6b Set Theory and Simple Theorem Proving

I PLUS.I.IS 2-

READY

2 PLUS.I.IS 3-

READY

3 PLUS.I.IS 4-

READY

PLUS.2 .IS IMPLBY PLUS.I.IS/ PLUS.I.IS­

READY

WHAT IS QUESTION­

READY

2 PLUS.2.IS WHAT*I-

I FIGURE 2 PLUS.2.IS/ 4

WHAT NOW?

OK-

WAIT ···

ANSWER - 4

READY

MINUS .2 .IS IMPLBY PLUS.2 .IS(CNV)­

READY

• a I DIVISIBLE.BY.2 FALSE­ READY
• b 2 DIVISIBLE. BY. 2 TRUE­ READY
• c DIVISIBLE. BY. 2 IMPLBY MINUS. 2. IS/DIVISIBLE. BY. 2READY

4 DIVISIBLE.BY.2 WHAT*2-

I FIGURE 4 DIVISIBLE.BY.2/ TRUE

WHAT NOW?

OK-

WAIT ···

ANSWER - TRUE

READY

3 DIVISIBLE.BY.2 WHAT*3-

I FIGURE 3 DIVISIBLE.BY.2/ FALSE

WHAT NOW?

OK-

WAIT ···

ANSWER - FALSE

READY

Fig. 7 Arithmetic and Handling Recursive Definitions

3M3CL lC OMlCR-

READY

3M3CL lMlC lMlCR-

READY

3M3CL 2C OM2CR-

READY

3M3CL lC OM2CR-

READY

3M2CL lM lMlCR-

READY

3M2CL 2C OM3CR-

READY

3MlCL lC OM3CR-

READY

3MlCL 2M 2M2CR-

READY

2M2CL lMlC 2MCR-

READY

2M2CL 2M 3MICR-

READY

IMICL lM 3M2CR-

READY

IMICL lMIC 3M3CR-

READY

OM3CL lC 3MICR-

READY

OM3CL 2C 3M2CR-

READY

OM2CL lC 3M2CR-

READY

OM2CL 2C 3M3CR-

READY

OMICL lC 3M3CR-

READY

GET.TO IS QUESTION-

READY

3M3CL GET. TO 3M3CR*II-

ENTER COMMA UST OF RELATION CLASSES TO BE USED OR - " ANY "

ANY-

[First solution follows:]

3M3CL 2C OM2CR IC(CNV) 3M2CL 2C OM3CR IC(CNV) 3MICL 2M 2M2CR lMlC(CNV) 2M2CL 2M 3MICR IC(CNV) OM3CL 2C 3M2CR IM(CNV) 1M1CL 1M 1 C 3M3CR [Second solution follows:]

3M3CL 2C OM2CR 1C(CNV) 3M2CL 2C OM3CR 1C(CNV) 3MlCL 2M 2M2CR 1M1C(CNV) 2M2CL 2M 3M1CR 1C(CNV) OM3CL 2C 3M2CR 1C(CNV) OM2CL 2C 3M3CR

WHAT NOW?

OK-

READY

Fig. 8 Solving the Missionary-Cannibal Problem

In attempting to answer a question, it may be necessary to supply further information to the system. Such a situation is illustrated by line "b" in the conversation starting at line "a".

Notice that ip the case of a "WHAT R Y" question, SAMENLAQ II proceeds by attempting to apply the R(CNV) relation to the node Y. [B4,2a]

Figure 5 shows an application of SAMENLAQ II to census, airplane and airline flight data. Note especially that even though the relation 'iS.LARGE" is defined ambiguously in lines "a" and "b" as to its application to cities or air­ planes, SAMENLAQ II can disambiguate it from context (lines "c" and "d").

In figure 6, SAMENLAQ II works with simple logic and set theory. The rule of inference Modus Ponens is entered in 6a line "a" , and with this and the transitivity of IMPUES given in line "b", simple "chain implication" prob­ lems can be solved. In 6b the relations SUB­ SET and ELEMENT are introduced along with the rule (x)(xEA &AcB-XEB). Then some set membership problems are solved, and finally, a simple proof is constructed.

Figure 7 shows SAMENIAQ II being taught its first lesson in arithmetic. Although neither numbers nor arithmetic functions have been built into the SAMENIAQ II structure or executive routines, SAMENIAQ II is capable of being taught arithmetic the way school children used to be taught: by first memorizing tables, and then being taught certain rules. Notice espe­ cially that divisibility by 2 was defined recur­ sively in lines "a", "b" and "c". Similarly, SAMENIAQ II could have been taught multiplica­ tion, division, the recursive definitions for less than and greater than as well as other arithme­ tic relations .

Figure 8 shows SAMENIAQ II solving the Missionary - Cannibal Problem, with three mis­ sionaries, three cannibals and a boat that holds a maximum of two people. The problem was described to SAMENIAQ II as a set of all the legal states in the problem with all the possible transitions between the states. For example, the first line represents the fact that if 3 mis­ sionaries and 3 cannibals are on the left bank with the boat on the left bank, then 1 cannibal can take the boat to the right bank , which will result in there being 0 missionaries and 1 can­ nibal on the right bank with the boat on the right bank. SAMENIAQ II solves the problem by showing how the boat should be used to get from the initial state, 3M3CL, to the final state, 3M3CR. Any problem solving task that can be represented as finding a path from an initial state to a final state through a state transition graph can in theory be solved similarly by SAMENLAQ II.*

5. Extension of the SAMENLAQ Structure

Work is now proceeding on the design and implementation of a memory net structure, MENS 9 , which goes further than SAMENLAQ II toward sat­ isfying goals discussed in the first section of this paper. The two major improvements needed in the SAMENLAQ structure are:

1. the ability to deal with a name which is itself a statement
2. the ability to store names which represent some unspecified other names, i.e. act as variables.

The first would facilitate the handling of n-ary relations and statements which serve to modify or give further information about other state­ ments. The second would allow generalizations to b3 stored, and would also permit the storage of statements of the predicate calculus directly in the memory structure. These statements could then be interpreted by the executive and used as rules of inference to direct the memory search routines in a mann~r similar to the way SAMENLAQ II deals with IMPLBY definitions. The currently extant implementation of MENS (which is programmed in Burroughs Extended ALGOL and uses ASLIP, a SUP like package of list processing routines) incorporates the first improvement, and work is progressing on the de­ sign of the implementation of the second im­ provement.

The main generalization involved in going from SAMENLAQ to MENS was to let xRy state­ ments _be nodes in the net along with arguments and relations. The basic element of the MENS structure is called an lli.!!l., which may be an unstructured unit or may be a structure consist­ ing of a pair or triple of items. Thus, items are similar to the "events" used by Simmons et al in Protos ynthex II u. As in SAMENLAQ, a major characteristic of the MENS structure is that there is no duplication of items or struc­ tures; the physically same item is used every­ where that the structure it represents is referred to in a containing structure. Several implica­ tions of this uniqueness of items are: (1) two structures which have a substructure in common actually overlap in the net, (2) if there is an item representing logical implication, all struc­ tures interpretable as rules of inference will be discoverable directly from that item since it will be a central substructure of all of them, ( 3) in

*Since SAMENLAQ II exhaustively searches the state transition graph, the threat of expo­ nential growth is ever present. Thus in certain interesting problems exhaustive search would be infeasible and heuristic search techniques would be necessary.

general statements involving a quantified varia­ ble, the separate occurrences of the variable will all be pointers to a single item, so that a substitution attached to that item will serve as a substitution for all occurrences of the varia­ ble.

Allowing a structure to be formed from a pair of substructures provides for the represen­ tation of unary relations such as negation and quantification. Allowing a structure to be formed from a triple of substructures provides for the representation of binary relation, and since any of the substructures may in fact be structures as well as unstructured items pro­ vides for the representation of n-ary relations. A more direct representation of n-ary relations is provided in another version of MENS being implemented*, which will allow any structure to consist of any number of substructures.

It is demonstrated in the examples given in Section 4 that SAMENLAQ II is capable of an­ swering questions in formal logic involving simple chains of inference and basic set theory. With its ability to store statements of the predicate calculus, the MENS structure should enable simple question answering routines to perform more complicated theorem proving. Although we should · perhaps not expect a high powered theorem prover to be developed in this way, the MENS extension of SAMENLAQ will provide an interesting contrast to systems, such as Green and Raphael's QA2 3 , which use theorem proving techniques to answer questions.