V

ISR-8
December 1964

V. AUTOMATIC PBMSE MATCHING
G. Salton

1.

Introduction
In 1957, Luhn suggested a fully automatic procedure for theprocessing of written texts, based on the frequency of occurrence of1

words within the texts/" Specifically, use of high-frequency words
was advocated for purposes of content identification, and document
retrieval was to be effected by manipulation of the corresponding word
frequency lists*

The suggested, procedure, while admittedly imperfect,is still used, as a basis for many automatic text processing programs.
More recently, the original statistical, methods have been
modified in various ways:

by using word stems rather than theoriginal, word forms to identify document content; by introducing
synonym dictionaries to lessen the effects of vocabulary variations;and, most importantly, by identifying relations between certain words
to be used as content identifiers in conjunction with the surroundingwords.
As a result, many of the word matching systems are now being
replaced by phrase processing systems, in which the basic units being
manipulated are sets of normalized words together with specified relations between them.
In the present report, a variety of methods are described forthe automatic generation and manipulation of phrases*

The phraseV-2
matching procedures used in the SMART document retrieval system to match
semantically similar but syntactically quite distinct structures aredescribed in detail, as a specific example of present capabilities.

2.

The Content Analysis Problem
In information processing, the structure of written data isof particular importance, because a large part of the information ofinterest is represented by combinations of words in the natural language.
If it is desired to use written data directly as part of an information
system, it becomes necessary to define transformations designed to reduce
the original input in the natural language into some predetermined standardform.

In particular, it would be useful if a text were reducible auto-

matically into a set of controlled terms complemented by a set of welldefined relational indicators.
Before determining the extent to which the known structure of
the natural language can help in this endeavor, it may be well to list
some of the known difficulties which stand in the way of an automatic
content analysis:(a) the synonym and homograph problem for individual text
words (many words can be used to represent the same
concept; some words can represent many different
concepts)j(b) the problem of semantically equivalent, but syntacticallydistinct, constructions (a large number of different
constructions can be used in the natural language toexpress the same thought; e.g. "the children broke theV-3
window," "the children used rocks to break thewindow," "rocks were thrown by the children, andf
as a result the window was broken," etc.);(c) the problem of indirect reference, including the useof pronouns and other referents to describe information
not specifically stated but presumed known from thecontext (the dependent structures often straddle
sentence boundaries in such cases, as in the example:"Someone opened the door*

It was our father.");(d) the problem of existing relations which are unstated,but may nevertheless be deduced from relationships
actually available (in the Syntol system, for example,"associative" relations between a first element and anaction, and. between the same action and a second element,
automatically generate a "consecutive" relation between
elements one and two); ^'^jO(e) the grouping problem which arises because constructions
may refer to a variable number of unspecified items, orto a set of items defined elsewhere (e»g. "all words
starting with ! x ! are of foreign origin").
It is clear that any one of these difficulties would by itself
be sufficient to prevent, in almost all cases, an analysis of written texts
into simple components. The presence of homographs and synonyms effectively
guarantees that the words used in a texf. will have to be properly standardized before being used, and the multiplicity of semantically equivalent
A large number of examples of this type are included in Refs» 2 and 3*
k solution to this problem is sometimes sought in the construction of
automatic deductive systems•'^,8

V-4
structures indicates that the isolation of word groupings together
with normalized relations between them is likely to be an operationof great difficulty.
The normalization of the vocabulary may be attempted byusing a variety of synonym dictionaries and thesauri. Word groupings
and relations between words, on the other hand, must be determined inpart by utilizing the known structure of the language. This problem is
examined in more detail in the next few paragraphs.

3.

Language Structure
It is well-known that at least some of the structure ofsentences in the natural language is based on syntax, and that thisstructure is revealed by syntactic analysis. A variety of programs
exist to perform automatic syntactic analyses, and these programs are
generally based on a form of grammar, known as a context-free phrase
structure (type 2) grammar.

Such grammars are characterized, by thefact that the bracketting used to represent the sentence structure
includes both juxtaposed bracket sets as well as nests of brackets,
but that interleaving between different bracket pairs is not possible.
For example, a structure such as[{(A.B) • C] • |U)-E) • F • [G • (H*I)}]],
where the letters may stand for text words and the bracketting denotes
phrase structure, could have been produced by a type 2 grammar. On

V-5
the other hand, the structureA • {(B-C) • DJ
is not producible by such a grammar, because of the interleaving between
different bracket pairs•
The syntactic structure of a sample sentence is shown as an
example in Fig. 1 in various stages of the analysis. In order to exhibit
explicitly the syntactic dependency relations between the words (therelations between governor and dependent words), a dependency model isused, together with the corresponding dependency tree.

In Fig. 1, aword A appearing below another word B to which it is attached by a branch
is syntactically dependent on itj furthermore the bracketting structure
is given directly by the subtree arrangement in the dependency tree (orin the corresponding phrase structure tree)«Phrase structure analyses are of particular interest in thepresent context not only because a variety of machine programs exist
1.1
which can perform such analyses automatically, '" out also because phrase
structure, as the name indicates, accounts for the most important word
groupings, including noun phrases, prepositional phrases, adverbial
phrases, and in most cases for the basic subject-verb-object grouping.
These groups are also those which make up the basic components to be
included in a useful information graph, as seen for example in Fig. 2,
illustrating the (manual) construction of a Syntol graph.
'Dependency grammars have been shown to be (weakly) equivalent to phrase
structure grammars: the two models can be used interchangeably forpresent purposes.-^V-6

Type of

1 2

Dependency

0

0

3 4

5

0

0

0

6

7
0

0

8

9

10

0

0

O

Connection

The very tall man sleeps in his bed all night

Formation of

1

adv. - ad j•

o

3

4

5

o

o

o

0

10

and
adj • ~ noun
connections

The (very tall) man sleeps in (his bed) (all night)

Formation of

5
o

10

noun-phrases
andprepositional
phrases

I

i

i

i

(Tiie (very t a l l ) man) sleeps (in (his bed)) ( a l l night)
10

Formation ofsubject-verbobject
connections[((The (very tall) man) sleeps (in (his beci))) (all night)

Connections ofadverbial andother auxiliaryphrases(((Tile (veryman) sleeps (in (his bed))) (all night))

Formation of Dependency Connections for a Sample Sentence
Figure 1

V-7

English Correspondent

Tree or Graph Formo(s)falteration of the EEG

EEG(partial information)(A)cralterationiC Alt e rat i on("XT

alcohol alters something(partial, information)

alcoholp(s)Alcohol, affects the EEG

y * EEG(partial information)(E)Oalcohol

Alteration of the EEG( A ) Q Alteration

due to alcohol(complete information item)/ T? Y"^

tfe*S~ f P

alcoholEEGi2

associative relation

3

Consecutive relationaactionE

EntityS

StateConstruction of a Typical information Graph
Figure 2V-8
Some phrases or word groups whose component words do not occur
in adjacent word positions within a sentence are difficult to generateby an unmodified phrase structure grammar. This is the case notablyof phrases with the so-called discontinuous constituents (e.g. "call up,!
in H call him up n ).

In order to accommodate discontinuous constituents,

the normal type 2 production rules must be extended, thus tending to
produce a relatively complicated grammar. 'Some important linguistic phenomena do not fit into a phrase
structure model, even if extended to handle special cases such as
discontinuous constituents*

There is no way in a phrase structure model

to relate, for example, two semantically identical sentences of which one
is in the passive and the other in the active voice*

It Is often suggested,

therefore, that in order to produce correct word groupings for a variety oftransformed structures, a transformational grammar be added to the phrase
structure model. Such a move could, be expected to produce not only agrammar more nearly representative of natural language structure as itexists, but would also result in a simpler, more economical, phrase
structure component.
k possible procedure advocated for an automatic sentence analysis,
and for the generation of basic word groups, or kernels, consists in thealternate application of phrase structure rules and inverse transformations.
Specifically, phrase structure rules are applied first to produce a standard
phrase structure analysis of an input string; the analyzed string is thensubjected to all applicable inverse transformations. The transformed

V-9
strings are then analyzed once more* and so on, until no further change"LL

13

is produced in the output•
This procedure may be expected to produce a much larger numberof correct word groupings than can be obtained from a phrase structure
analysis alone*

On the other hand, the apparatus required to use atransformational grammar as part of an automatic system may be expected
to be much more complex than the simple pushdown store analysis, or listtracing procedures, needed to use a simple phrase structure grammar.
Whether the combined phrase structure and transformational procedureturns out to be effective in the generation of word groups needed forcontent description remains to be seen. In any case., experimental
kernelizing programs are presently under study by several research
3,15,16
groups. "4»

The Processing of Unrestricted Text
a number of text processing systems have be^n designed to processcompletely unrestricted natural language input*

among these are at least

two systems designed to answer questions rather than to furnish references,
the Protosynthex and the l!lLEl systems*' 'In order to be able better to assess the problems raised bysystems such as the two previously mentioned, it is convenient to consider
some of the text processing methods included in a fully automatic document,
rather than fact, retrieval system.

19 20
The SMaRT system" 'takes both

documents and search requests in unrestricted. English, performs aV-10
complete content analysis automatically, and retrieves those documents
which most nearly match the given search request, k large variety ofprocedures are available for the generation of the content identifiers
attached to both search requests and stored, documents, and documents may
therefore be retrieved in accordance with many different criteria.
The system can be controlled by the user in that a search request is first processed in a*standard mode; the user is then asked toanalyze the output obtained, and depending on his further requirements,
the original search request can be reprocessed using a new processing
method.

The new output is then again examined and the process can be

iterated until such time as the right kind and amount of information
are retrieved*

The various processing modes correspond to different

automatic methods of analyzing information, and the iterative procedure
represents an attempt to approximate, with natural language input, thetype of analysis (in terms of controlled concepts together with controlled relations between them) previously illustrated by the manual
process of Fig. 2. Before exhibiting the differences between thetheoretically desirable and the actually achievable reduction, some of
the basis SM&RT operations are outlined, briefly.
The first operation consists generally in a stem-suffix cut-off
operation, which replaces each text word occurring in a document or ina search request by the corresponding word stem. High-frequency function
words, such as conjunctions, prepositions, and the like may then be
temporarily discarded, and a document (or a search request) can be
identified by the set of remaining word stems, together with a frequency

V-ll

indicator for each stem, at this point, the word stems used to represent item properties are not as yet normalized•
In order to reduce synonymous word stems to a single nconcept,"
and to provide a variety of different concept identifications for the
many stem homographs which may arise in the natural, language, it isnecessary to perform a thesaurus look-up operation. This processeffectively replaces each word stem by one or more so-called concept
numbers.

The replacement of word stems by concept numbers is illus-

trated in Fig, 3 for a typical document abstract included in SMART.
Use of the thesaurus insures that a given document is identified bya set of controlled terms.
Generic relations between properties may be provided by consulting a hierarchical arrangement of concept numbers as shown in Fig. 4.
Specifically, given any concept obtained from the thesaurus, it is now
possible to obtain related concepts by using the tree structures.
More general concepts may be located by going "up" in the tree, more
specific ones by going "down," and various related concepts may be
picked up by locating the "brothers" (nodes in the same filial set) ofa given concept. Figure U illustrates, for example, the expansion ofconcept 258 (punctuation) into concept 188 (syntax), and. of 58 (pattern)
into 59 (representation).
Relations between concepts may be added by grouping the concepts
instead of using them one at a time. The identification of so-calledstatistical phrases is illustrated in Fig. 5 for the document abstract
previously shown in Fig. 3. Statistical phrases are groups of concepts

12

O102

LANGUAGE

L2e

CODE, NOTATIONTERMINOLOGYr

INFLECTSTRESSPHRASESENTENCE
WORD

PUNCTUATEDISPLAY, S T A T E
REPRESENTATION

59O

CHART
DIAGRAMX58

AMOUNT, DEGREEDIMENSIONy\PATTERN

c

212

105

77

BULK
CAPACITY

xsOND
CONNECT

SPACE

TI E

FILE
LIST
STORE

hierarchy Excerpt Showing Expansion
Figure 4

V-14

which co-occur within the sentences of the documents with a frequency
exceeding some pre-established threshold.

If such a group of concepts

is detected, the individual concept numbers may be replaced by a groupconcept number attached to the statistical phrase; such a phrase concept may then be given a higher weight than the individual word concepts
when it is used as part of a document identification.
In the abstract of Fig. 5, co-occurrence in the same sentenceof concepts 11 (analysis) and 102 (language) is recognized as a phrasewith concept number 305 (language analysis); similarly for concepts 102(language) and 149 (program), which are transformed into 178 (programming
language)•

The exact type of relation which obtains between a concept

pair included in a given statistical phrase cannot in general be
determined, since the formation of such phrases depends strictly on
concept co-occurrence characteristics. Thus, the use of statisticalphrases does not completely fill the requirements of the graph model ofFig* 2, where relations are identified completely.
An attempt to identify at least some relations between concepts
may be made by using the syntax of the language. Specifically, statistical phrases may be replaced by syntactic phrases in which the included
concepts exhibit some specified syntactic relationship•

In order to beable to include syntactic relationships as part of the content identification process, it is necessary to perform an automatic syntactic analysis.
Such a step is included in the SM&RT system, and procedures are provided
for eliminating statistical phrases which do not qualify as proper syntacticphrases. In the abstract of Fig. 5, for example, the statistical phrase

co

UJ
CO

co
UJ
CO
<

<r
en

If)

<r
o

/o \

co

ho
<

CO

CO

• 00

CO°^ \-g<_J

m A p- / COCn/"~l /fi\£

3—}\

NH/OD 2<U J \ vz\

YNT

TATI

< m 1 ~z.

^

CD

h-

I 1\

X
CL

_J

O
"~" \ >

/

cr

i

cr
! h

1 0X= 0") \ "
>'X
< / o
** 1\

CVJ

o

\3^r UJ
2*
2

2

*

„
00

CO

zr
cr

1

»•

<•—>

>~

t

UJC0 COo
UJ I h-^
cr
\<

LU
>

i °-

2
3

J
o
>

#*

"Z.

o

o

1UJ
-

Q

1-

cr

<
Z)00

UJ

00

§

in

cr 1 \— ""> cr
—*

2

rO|

^
0_

C\J
OJ

H

cr
H
co
DO
<

-D

_J
h<
CO

CO
3

<

3

o

UJ

o

5

2

O

h-

CD

<
X

UJ

CD

x
U—

>CD

OJ
i

a.
GL

\

o°

o

p

rO

h-

*

t 5i±;3I

CM <T

CD cr fbco
— \- x zCDoo+ ^ox <c
o<r
^ cr
H

o p -J
- z <
+ co
—
>- 2!
<

.

X

UJ
^ CO

w<
> 3

CD

^•z
00 _
T ^ S S 2
OJ C D < <OZQ:^T -JCD^t^o^.
™
> cr <
CO Q_ - 1

^

t

^ o

CD Q
O

<

<

<

<

S tr

^r o O CD+- h- h- O
CD 3 3 cr
_I

CL

V-16

corresponding to concept 178 (programming language) is not a syntacticphrase, since an admissible syntactic relation does not exist between
the included concepts 102 (language) and 149 (program)*
Identification of syntactic relationships between concepts included in a phrase does furnish some relational indications in accordancewith the requirements of the model of Fig. 2. However, in order togenerate a completely defined graph structure, both concepts and relations must be properly normalized.

That is, different syntactic

structures must be transformed into the same phrase if there exists
semantic equivalence. To what extent this can be done automatically isfurther described in the next few paragraphs*
The complete content analysis process is summarized in Fig. 6
for the document abstract previously shown in Figs. 3 and 5»

5«

Syntactic Phrase Matching
The identification of information items by concept numbers andphrases of various kinds is of use only if the corresponding identifiers
are, in fact, properly normalized.

This is achieved in the SMART system

by replacing words by concept numbers, by performing a syntactic analysisof the sentences occurring in documents and search requests so as todetermine syntactic dependency relations between concepts, and finallyby looking up the resulting dependency tree structures (see Fig. 1) in adictionary of criterion trees.
Criterion trees consist of prestored frames including concept
numbers, syntactic indicators, and the syntactic dependency relations

V-17

Method ofGeneration

IdentifiersConcept
Numbers

English Examples(weights)

1.1

Analysis, Synthesis

(4,8)

53

Diagram, Picture

(2/4)

59
93

amount, Extent(12)Translation

(12)

102

Language

(12)

119

Automatic, Machine

(24)

149

Program, Routine

(12)

170

Phrase, Word, Sentence

(12)

258

Punctuation(4.8)

57 (53,59)

Display, Represent(36)

112 (119)

Manipulate, Operate(24)

188 (170,258)

Grammar, Syntax(60)

Statistical

178 (149,102)

SYMLNG (program, language)Phrases305 (11,1.70)

SYNTAX (analysis, word)

Syntactic

303 (119,98)

MCHTRA (machine translation)

Phrases305 (11,102)

SYNTAX (analysis of language)U

AUTC0D (automatic prograjn)

Thesaurus
Look-up

Hierarchy
Expansion(119,H9)

Identification of Abstract #223
Figure 6

V-18
which obtain between the included concepts*

There exist four mainclasses of criterion trees as shown in Fig* 7, corresponding to nounphrases, subject-verb relations, verb-object relations, and subjectobject relations. The syntactic structure of criterion trees isconveniently specified by syntactic dependency trees as seen in thecenter section of Fig* 7. The top-most tree in Fig. 7 corresponds,
for example, to an English phrase consisting of an adjective (A), or
noun (N), (tree node 2) which is syntactically dependent upon anothernoun specified by tree node 1.
The operations of the criterion tree dictionary may be
explained by considering the example of Fig. 8. The tree, termed
SYNTAX, is defined at the top of the figure. Node 1 of the tree mustcorrespond to either concepts 11 or 158, and node 2 to concepts 102,
188, or 170. Furthermore, four different syntactic frames are allowed
for the tree, as indicated by the format numbers which follow the fisign (fourteen different formats are used at present in the criterion
tree dictionary). a few typical word stems corresponding to the concepts included in the SYNTAX tree specification are also shown in
Fig. 8, as are examples of English phrases and sentences which will
match the given tree.
Obviously, the multiplicity of concepts attached to a given nodeof a criterion tree, and the variety of permissible syntactic formats
guarantees that a given criterion tree specification corresponds tohundreds of different English constructions. Furthermore, both documents
and search requests use the same criterion tree dictionary, so that aV-19

Tree Type

Dependency Trees

English Examples
Syntactic analysis

Noun Phrases
\

or

/

(2)

V

Prepositional

(£

(g)

Phrases

A,N

A,N

(1)

Analysis of phrases
(1)

(2)

This machine translates*••
Subject-verb

(1)

®
S

(2)

&) <g> (S)the translation appears.••

j

0,G

J

S

0,C

(2)

(1)

! We translate texts
Verb-object(1)

Verb-complement(2)

by machine(3)@

Subject-object
Subject-

03s

9 j
HN

data are available for(2)(f) s d)complement(i)machines perform translation(1)oindirect connections

Vprocessing

direct connections (not shown)

Basic Criterion Tree Glasses
Figure 7

(2)

j

V-20

PHRASE SPECIFICATIONSSYNTAX (11,158)/(102,188,170), & 1 , 3 , 4 , 1 3Vv

CONCEPTNODE 1NODE 1
1.1

ANAL

/ v

CONCEPTNODE 2102

INTERLINGULANGUAGESYNTHESv— ^FORMATS1/®N 0

SAMPLE PHRASES
1£^

ANALYSIS OF SENTENCES
3

PHRASECLASS••'SYNTHESIZE A SYNTAXSUBJECT

CORRESPOND

WORD

GROUP
INDEPEND
RELATEWE CAN ANALYZE THE
LANGUAGESENTENCE
158

SYNTACTIC ANALYSISPHRASE RELATIONS

1 (4 h3

170/

FORMATSNODE 2SYNTHESISSYNTHET

Jv

188

GRAMMARucf
1 U s ^© 0J
13

XT

SYNTAXU

THE GRAMMAR I S NOWAVAILABLE FOR ANALYSIS

13

THIS ANALYSIS I SAPPLICABLE TO
RUSSIAN GRAMMARSYNTACTICC r i t e r i o n Phrase S p e c i f i c a t i o n s
Figure 8V-21

flexible matching process ensues. The comparison of concept numbers
and of syntactic indicators is done in the SMART system by table lookup, and the dependency structures of input sentences and criterion trees
21 22
are compared by an efficient graph-matching process. 'The Kuno-

Oettinger multiple path syntactic analyzer is used to perform theautomatic syntactic analysis of the input documents.
In order to evaluate to what extent the automatic criterion tree
procedures can approximate the manual analysis specified by the modelof Fig. 2, it is of interest to examine in more detail the variety ofdifferent structures which can be matched. The flexibility of theprocedure arises from four principal characteristics of the criterion
trees:(a) word stems rather than complete words are used during
the thesaurus look-up;(b)concept numbers rather than words or word stems areattached to the criterion tree nodes;(c)each criterion tree is assigned several possible
syntactic frames, or equivalently, a variety ofsyntactic relations are normally allowed between
concepts; and(d) the dependency connection between two specified
concept numbers is an indirect connection, ignoring
occurrences of extraneous concepts, or of function
It is obvious that if the syntactic analysis procedure furnishes
an incorrect or a doubtful analysis, the phrase matching process
may be affected adversely.

V-22

words which may be part of the syntactic context(thus, the preposition "of11 in the phrase "retrievalof information5' is ignored when the dependency trees
are matched)•'As a result of this type of criterion tree specification, it
is in general possible to match semantically equivalent phrases orsentences, provided that the same basic order between major sentenceparts (subject, verb, object) is present*

Differences due to addition

or deletion of auxiliary particles and phrases, shifts from noun toverb constructions or vice-versa, use of synonyms and of multiple
subjects, verbs, or objects do not in general interfere with thematching procedure*

Examples of various syntactic constructions which

can be properly recognized by the criterion tree procedure are given
in Fig. 9»'Within each group, the sample phrases match the same basic

criterion tree*
Since function words, including prepositions, adverbs, and conjunctions, are not normally included in a criterion tree specification,a variety of structures which are not completely synonymous are nevertheless assumed to be identical by the criterion tree routine*

Typicalexamples of the nonrecognition of semantic differences, as well as someexamples of the nonrecognition of semantic similarities are shown in
Fig. 10. Figure 10 may in fact be considered to be a repertoire of the_'This feature is also incorporated in a somewhat different form in a
number of other text processing systemsv^
rSome of the examples included in Figs. 15 and 16 were suggested instudies dealing with the construction of transformational grammars.2^ 26

V-23

Transformations

Examples ofCorrectly Identified
1. declarative vs. interrogative(word order between principal
sentence parts is maintained)

Matching Structures
the man bats the balldoes the man bat the ballthe boy asks whether the manbats the ball

2. identification of multiple

the large, grey, empty hall...
the large hall* o.
the grey hall...

subjects, verbs, objects

11
3- "there is or "it is"the car is in the garage
there is a car in the garage

constructionsA-

this is the information that you
wantedthis is the information you wanteddeletions of certain pronouns

5. permutations within noun andpattern analysis...
'.. the analysis of patterns...

prepositional phrases

6. some negative constructions________„_________. _ _ _ — .

children do not like teachers
no children like teachers______—— —7. identification of synonymous

the grammar of this coding system...
the syntax of this notation...

constructions
—

—

—

—

—

—

—

8. identification of stem similarities

analyzer...
analysis..•9. verb-noun shifts

he dances; he is a dancer
he looks; he gives a look

10. addition of subject or object
clauses

L i _i . certain eo uivalent constructionsx

the boy works
the father demands that the boy
should work
how much.••j what..•which time...; at what time...
for more than...; for longer than**.

Correctly Identified Phrase and Sentence Transformations
Figure 91

V~24[matching^
Examples

Type of D e f i c i e n c y^ not matching ^/ the man hits the ball

.1 . active-passive changes not/

immediately identified (due tothe ball is hit by the manchange in basic structure)(uman eats dog,11 "dog eats man"are, however, distinguished)

no distinction between depth ofanalysis of English patterns

dependency connection

analysis of English[analysis of patterns

no recognition of negative-[the sun shines

positive transformation

I the sun does not shine

no recognition of some relative/ I saw the man

clauses causing word order changes
no recognition of dependencies,

It is he whom I saw/ Mr« X is tall.

across sentence boundaries

He is our teacher, /Mr. X is our teacher*no recognition of unstated/ This poodle is bigclassifications

This poodle is a big dog/ They are 1000 feet apart
The distance between them is 1000feet.

no recognition of distinct verb
forms

The data are retrieved\ The data were retrieved_The data have not been retrieved{ nonrecognition of semantic differences
nonrecognition of semantic similarities

Deficiencies in Phrase Matching Process
Figure 10V-25

deficiencies of the SMRT phrase matching process. The nonrecognitionof the semantic differences illustrated in examples 2, 3> and 7 ofFig. 10 is generally of no consequence for document retrieval, and may
also be of trivial importance in question-answering systems based on
the given phrase matching process. On the other hand, the nonrecognitionof some of the semantic similarities, notably those illustrated byexamples 1 and 5* may be expected to be serious, at least for automaticquestion-answering•
To summarize, the criterion tree matching routine can be usedin automatic text processing systems to furnish groupings between
specified concepts and to identify a limited number of syntactic dependency
relations. While the resulting structures do not completely obey the
specifications of the graph model of Fig. 2, the identification obtained
is sufficiently detailed to handle satisfactorily the great majority ofthe problems arising in automatic document retrieval. Additional work
remains, however, to be done, including the construction of workable
kernelizing routines, before fully automatic, unrestricted questionanswering systems become feasible.

V-26
REFERENCES

1.

Luhn, H. P., "A Statistical Approach to Mechanized Encoding and
Searching of Literary Information," IBM Journal of Research andDevelopment, Vol. 1, No, 4 (October 1957).

2.

Robinson, J. J., "Preliminary Codes and Rules for the Automatic
Parsing of English," Rand Memorandum RM-3339-PR? Rand Corporation(December 1963) •3. Robinson, J. J., "Automatic Parsing and Fact Retrievals

A Comment

on Grammar, Paraphrase, and Meaning," Rand Memorandum RM~4-005~PR(February 1964) •4»

Gardin, J. C , and Levy, F., "Le Syntol - Syntagmatic Organization
Language," Proceedings IFIP Congress-62, North Holland Publishing
Company (1962).

5. Gardin, J. C , et al., "Final Report on a General System for theTreatment of Documentary Data (Theoretical. Applications of Syntol Part I, Programming of Syntol - Part II)," Association Marc Bloch(October 1963)*
6.

Coyaud, 1VL, "Analyse Automatique Syntol," presented at the NATO
Advanced Study Institute on Automatic Documentation, Venice(July 1963).

7*Black, F., "A Deductive Question-Answering System," Doctoral
Thesis, Harvard University (June 1964.) •8.

Cooper, W* S., "Fact Retrieval and. Deductive Quest ion-Answering
Information Retrieval Systems," Journal of the ACM, Vol. 11,
No. 2 (April 1964)*

9.

Chomsky, N,, Syntactic Structures, Mouton and Co*, s'Gravenhage(1957).

10.

Hays, D. G-, "Dependency Theory: A Formalism and Some Observations,"
Report RM-4QB7-PR, The Rand Corporation (July 1964.) .

V
11.

Bobrow, D. G., "Syntactic Analysis of English by Computer A Survey/' Proceedings AFIPS Fall Joint Computer Conference,Vol. 2U, Las Vegas (1963).

12.

Yngve, V. H., "Computer Programs for Translation," Scientific
American (June 1962).

13-

Petrick, S« R. , "On Transformational Grammar Recognition
Procedures," unpublished manuscript.

ill. Herzberger, H. G., "Some Aspects of Kernelization," Western
Reserve University (November 1963).
V;j. CarmoGy, B. T., and Jones, P. E., Jr., "Automatic Derivation ofConstituent Sentences," 196!.; Annual Meeting of the Association
for Machine Translation and Computational Linguistics, Indiana
University (1961|).
16.

Bobrow-, D. G., "Natural Language Input for a Computer Problem
Solving System," MIT Report MAC-TR-1 (September 196)4).

17.

Simmons, R. F., Klein, S., and McConlogue, K., "Indexing and
Dependency Logic for Answering English Questions," American
Documentation, Vol. 15, No. 3 (July I96I4.).

18.

Thome, J. P., "Automatic Language Analysis," Final Technical
Report to RADC under contract AF 30 (602) - 216$, Indiana
University (December 1962).

19.

Salton, G., et al., Information Storage and Retrieval, Report
No. ISR-7 to the National Science Foundation, Computation
Laboratory of Harvard University (June I96I4.).

20.

Salton, G. , "A Document Retrieval System for Man-machineInteraction," Proceedings of the ACM 19th National Conference,
Philadelphia (19610.

21.

Su s s e nguth, E. I I., Jr., "S tru cture Mat ch i n g in Inf0 rma tio n
Processing," Doctoral Thesis, Information Storage and Retrieval,
Report No, ISR-6 to the National Science Foundation, Computation
Laboratory of Harvard University (April 19610-

V-28

22*

Salton, G*, and Sussenguth, E. Hv> Jr.-, "Some Flexible Information
Retrieval Systems Using Structure Matching Procedures/5
Proceedings of the AFIPS Spring Joint Computer Conference>
Washington (April 1964).

23*

Kuno3 S.j and Oettinger, &* G., "Multiple-Path Syntactic Analyzer/8
Proceedings of the IFIP Congress-62, North Holland Publishing
Company (1962.) •24*

Klein, S., and Simmons, R. F., "Syntactic Dependency and theComputer Generation of Coherent Discourse," Mechanical Translationt
Vol. 7, No. 2 (August 1963).

2$.

Harris* Z. S., English Transformation List, Transform and Discourse
Analysis Project, Paper No a 30, University of Pennsylvania (1964).

26-

Hall* B., "Notes on Transformational Grammars," unpublishedmanuscript.