Ame6~tU1 Journal of Computationd Lu~gUitti~ 
Hi ~icr~fi che 32 
PROCEEDlNGS 
13TH ANNUAL MEETING 
ASSOCIATION FOR COMPUTATIONK LINGUI ST1 CS 
Timothy C. Diller, Editor 
Sperry-Univac 
S-t. Paul, Minnesota 56101 
Copyright @ 1975 by the Association for romputational Lf nguf $tic@ 
PREFACE 
The 13th annual ACL meeting was held at Boston. Massa- 
chusetts, October 30 - November 1, 1975, in conjunction with 
the 38th meeting of the American Society for Information 
Science. The ACL thanks the ASIS for its assistance in pub- 
licizing the conference and in handling registration. 
This and the fallowing four microfiehe8 contain 27 of 
the 30 papers presented at the meeting. The breadth of the 
oonference is evident in (a) the modes of communication in- 
vestFgated (speech, sign language, and written text), (b) the 
styles of communication (monologues, dialogues, and note 
making) , and (c) the uses envisioned for @he processing of 
language data (e.g., theoretical modeling, data collection and 
retrieval, game playing, story generation, idiolect charac- 
terization, and automatic indexing). 
Topics considered include the development of language 
understanding systems, the integration and utilization of 
specific components of language, specifically syntax and 
semantics, the representation and use of discourse structure 
and general world knowledge, and the construction of text 
processing eystems. 
The program committee was solely responsible for select- 
ing the talks to be given, and hence the papers to be pub- 
lished hereln. (Reg~etfully, nearly half of those submitted 
could not be accepted for lack of program time .) Members of 
the program committee were Jonathan Allen, Joyce Friedman, 
.. 
Bonnie Nash-Webber, and Chuck Rieger. A special word of ap- 
preciation is due Jonathan Allen, who also served as Local 
Arrangements Chairman. Working with him were Betty Brociner 
and Skip McAfee of the MIS. Aravind Joshi, president of 
ACL, provided guidance in all areas of preparation. 
The AJCL kindly provided advance publication of the 
accepted abstracts and now makes possible the publication of 
the entire proceedings. David Hays, editor of AJCL, provided 
guidance in publication format and each author provided final 
copy in accordance with requested specifications. The Center 
for Applied Ltnguistics (in particular, David Hoffman and 
Nancy J~kovich with guidance from Hood Roberts) contributed 
in a variety of ways, most notably in the preparation of 
meeting handbooks. 
Tkis microfiche contains the papers as submitted by 
their authors for ffve of the six talkb touching on Language 
Understanding Systems. The paper detailing "Conceptua1 
Grammartt by William Mattin was too long for inclusion in 
&baa microfiche and will appear elsewhere. My thanks to 
Yorick Wilks for chairing the session. 
--Timothy C. Diller 
Program Committee Chairman 
TABLE Of, CONTENTS 
Program Schedule 
PEDAGLDT and Unlderstanding Natural Language Processing 
...................... William Fa.bens 9 
A General System for Semantic Analysis of English and 
ilta Use in Drawing Maps from Directions ~erry,~. HQ~S . 21 
Arl Adaptive Natural Language Parser Parry L. Miller . , . 42 
Conceptual Gramar (abstract only) William A. Martin . , 57 
Semantic-based Parsing and a Natural-language Interface 
for Iaterac tive Data Management Ja'm F, Burger, Antonio 
Leal, and Arie Shoshani ................. 58 
PHLIQA 1: Multilevel Semantics in Question Answering 
P. Medema, W, J. Bromenberg, H. C. Bunt, S. P. J, Landsbergen, 
R. J. HI ScM, W. J. Schoenmakers, and El P. C. van Utteren ... 72 
THIRTEENTH ANNUAL MEETING 
THE AS$OCIATtON FOR COMPUTATIONAL UNGUISTICS 
Sheraton Boston Hotel 
Boston, Massachusef ts 
October $0-November 1, 1975 
Thursday, October 30, 197.5 
S&SSION 1: i,AhrCUAGE C/IVn ERSTAArDlllFG SYSTElhf S 
Session Chairman: Yorick Wdks - hrverslty of Edtnburgh 
990 A.M. Greetings and Irrtroductory Rernarks 
9: 15 A.M. PE'DfiGI,OT and Underrl art ding Natural 1,nnguagr Procr t sing 
Willtarn Fabens - Rutgers University 
9:40 AM 
A Syrtcm /or Gencral Scmankc Analysis And lt,q Use 
In Drawirt g Al apa from Dircctiotts 
Jerry R. t.lobbs - The C~ty College of CUNY 
tO:OS A.M 
An Adaprivo Nutural Lartguago Parser 
Ferry t. M~ller - M I T. 
1030 AM. COFFEE & DONUS 
t 1 :30 A.M. Semantic-Based Parsing Arzd A Natural-Langun /ar, Irttr,r farr, 
Far Intcrraciittc! Data Af artngctnrrlt 
John F. Burger, Antonio Leal, and Ar~e Shoshanl - 
System Development Carporation 
L2a0 NOaN PliLlQA I: Mulrilrucl Srrmaniic~ in Qrrrlrtiort Ancu:crina 
P. hkderna, st. a1 - Phil~ps Research Laboratorres, 
The Netheviand$ 
1290 P.M. LUNCHEON BREAK 
SESSION 2: LANGUAGE GENERATION SYSTEhIS 
Sess~on Chairman: Martin Kay - Xerox Corporation 
2:OO P.M. A Framework for Writiftg Ga~~eratiotr Crurnrnnrs 
for Intstactivc Cornputr?t Progrnrnn 
Dav~d McDonald - M I T. 
2:30 P.M. 
3:OO P.M, 
3:30 P.M. 
4:OO P.M. 
4:30 P.M. 
5:30 P.M. 
8:00 P.M. 
Incrarn~ntnl Sonlenco Proc~s~i~tg 
Rodger Knaus - Bureau of the Census 
A IJoricnl Proces~ Model of IVomit~crl Compounding 
In English 
J.R. Rhyne - University of Houston 
COFFEE & OONUTS 
Gsneratin~r ns Parsing horn A Natzrtork irtto a 
Idheat String 
Stuart C Shap~ro - Indiana University 
Speech Gcnrrntior~ frdm Scmnr~i ir Nctr 
Jonathan Slocum - Stanford Research lnst i lute 
Using Plnrming Structurra to C~rzcratc Stories 
Jim Meehan - Yale University 
DINNER BREAK 
WINE, CHEESE & COMPUTER DEMONSTRATIONS 
SESSION 3: PARSING, SYNTAX, flND SEhl ANTICS 
Session Chairman: Joyce Friedrnan - Stanford Research Institute 
9:00 AM. Synrucric Procanrirta in tho BRN Spcaclr Urtdcrstnrtdi~tjy 
System 
Madeline Bates- Bolt, Beranek & Newman, lnc 
9:30 A.M. Sygtnrn latonration and Coi~iml for $prcr h Uttdrrrrnrzdin/r 
Wllimrn H, Paxtoln and Ann E. Robinson 
Stanford Research I~stitute 
10a0 A.M. A Tuneahlo Porfarrnancc Grnrnmnr 
Jane J'. P~binson - Stanford Rosearch Institute 
10:30 A.M. COFFEE & DONUTS 
lla0 A.M. Scmdrriic Processing f~r Speech Underxianding 
Gary G Hendrix - Stanford Research institute 
11:30 A.M.. 
SPS: A Fortnalim for* Scmaniic Itrterlrrr~ation artd 
Its Use irr Processing Prcpssition~ that Rcj'rrettcc Spacc 
Norman K Sondhetrner - Ohro State University 
12:OO  NOON Tho Nature and Computational Use of n filcnning 
Reproscrrlntion Tor Pard Conccprz 
Nick Cercone - University of Alberta 
1 2:30 P.M LUNCHEON BREAK 
SESSION 4: MODELING DISCOURSB AM EBOR1,D KN111171,1CIIGE I 
Session Chairman: Carl Hew~tt - MIT 
2a0 P.M. Ertabliahirrg Conrcxt irt Task-Oricnicd Dinlogs 
Barbara G, Oeutsch - Stanford Research Institute 
290 P.M. Dircoursc Modclx and Language Cotnpr~lzerl cion 
Bertram C Bruce - Bolt, Bersnek & Newman, Inc 
300 P.M. Judging ihc Coherertcy o/ Disrourse (and Some 
Observations About Frtzrnc?s/Scrip t s) 
Brian Ph~il~ps - University of Illinois at 
Chicago Circle 
3:30 P.M. COFFEE & DONUTS 
4fi0 P.M. Art Approach to r hc Orgariizatiort of Murtdnrtc 117orZd 
Krto~led~a: tho Carterarioir and fifariaacrrterrt of Scripts 
R.E. Cuflingford - Yale University 
490 P.M. Tho &ncaptuaZ II~h;cTi~t ion of P hysicnl Arli.tiiti~s 
Norman Badler - University of Pennsylvan~a 
5:OO P.M. fi Frarno Artalysit 01 Arn~rican Sign l,nr~gunae 
hdy Keg1 (MIT) and Nancy Ch~nchor (U. of Mass ) 
5:30 P.M. 
ACL BUSINESS MEETING AND ELECTION OF OFFICERS 
DlNNER: ACL BANQUET 
Saturday, November 1, 1975 
SESSION $A: AIOl)Ef,liVG DISCOURSE & WORI,D KNOlVI,ItIIGlI: /I 
Session Chairman: Georgette Silva - System Development Corporation 
9:00 A.M. Cross-Sct~t~tztinE R~fir~nrc Rr~olutiorz 
David Klappholz and Abe Lockman - Colutnbia Uhiversity 
9:30 A.M. 
Ilaia Doc$ a Systcrn Knou~ TVhclz to Stop l~tf~rcr~ring? 
Stan Rosensche~n - University of Pennsylvahla 
10:00 A.M. COFFEE Rt DONUTS 
SESSION 5i?: TI5XT AiYflLYSIS 
1 1 :00 A.M. 
1 1 :30 A.M. 
D;c?ucZoping n Cornputcr Syatrm for Ilanrlling Iltizcrclrttly 
Vtzrinhlc I,ii~~uis~ic Data 
Dav~d 8eckles, Lawrence Carrrngton, and 
Gemma Warner - The unrversity of the West lndies 
A Nururul I1a~tguagc Proecs.sirtg Pnckrcgc, 
David Brill and Beairlee T Oshika - 
Speech Communications Reseatch Laboratory 
On the Kolc of Words and Phrases irt Autornntir Tert 
Analy,& and Cornru~niiort 
Gerard Salton - Cornell University 
12:OQ NOON Crnmrnnlicul Comprrssiolz in Not~s and Rcrards: 
A~talysib and Cornl~v tntiolt 
Barbara Anderson (University of New Brunswick), 
Irwin Bross (Roswell Park Memorial Institute), 
a~d Naomi Sager (New 'fork University) 
American Journal of Computational Linguistics Hicrofiche 32 : 9 
CGmputer Scf ence Department 
Rutgers Uni versi ty 
Few Brmick, New Jersey 08903 
ABSTRACT 
PEDAGLOT is a programmable parser, a 'meta-parser.' To program it, one 
describes not just syntax and some semantics, but also--independently--its 
modes of behavior. The PEDAGLOT formulation of such modes of behavior follows 
a categorization of parsing processes into attention-control, discovery, pre- 
diction and construction. Within these overall types of -activities, control 
can be specifled covering a number of syntax-processing and semantics-process- 
ing operations. While it is not the only possible way of programing a meta- 
parser, the PEDAGLOT mode-specification technique is suggestive in itself of 
various new approaches to modeling and understanding same language processing 
activities besides parsing, such as generation and inference, 
7% is wotk was sponsored by through NIH Grant #RR643. 
It is well known that to process natural language, one needs both a 
syntactic description of possible sentences, blended in some way with a semantic 
description bf a certain domain of discourse, and a rather detailed description 
of the actual processes used in hearing or producing sentences. 
An augmented transition network (Woods, 1970) is qn example of the blending 
of syntactic and quasi-semantic descriptions, Here registers would be reposi- 
tories of, or pointers to, semantics. When used in conjunction with a semantic 
nqtwork, an ATN can be used 60 parse or to generate (Simmons and Slocum, 1912) 
sentences. The issue of changing the des'cription of the actual processes used 
in such systems has been touched on by Woods (in using a 'generation modet), to 
some extent by Gimmons and Slo~um (usi~g decision functions to control style of 
generation), and to a larger extent by Kaplari (19751, in his General Syntactic 
Procdssor, GSP. GSP indeed is one example of a system in which syntax, semantics 
and to some extent processes can each be usefully defined. 
If we look at syntax, semantics and processes as three describable components, 
these systems just mentioned illustrate how thoroughly intertwined they can become-- 
to the extent that theorists from time to time deny the existence or at least the 
importance of some one of them. Ignoring that dispute, I would- like to concentrate 
on the question of being able to comprehensively describe one's theory of language 
in terms of its syntax, semantics and processes in a way that allows for their 
necessary and extensive intertwining connections, but at the sane time allows one 
to describe them independently. 
I came ta the need for doing this while designing a Trelaxation parser,' a 
parser which can make grammatical relaxations if it is given an Ill-formed string, 
so as to arrive at a klosestt possible parse for the' string. This probl-em involved 
describing a korrectt grammar and then (in some way) describing a space of deviations 
az 
that night be allowed by the paxser. 
Thus the syntax would be fixed and the way 
the parser uses it would separately have to be described. 
It was soon noticed 
that efficiency could be greatly enhanced if some rudimentary notion of semantic 
plausibility could also be used. It would have to be described in a way related 
to the cbrrect syntax but still be usable by the parser. 
Thus, for my purposes, 
the descriptions had to be independent of one another. 
One feature of a relaxation parser is that it can 'fill in the gaps' of a 
string that is missing various words. 
If one could, which my relaxation parser 
did not, specify the semantic context of a sentence, the generated sentence might 
be semantically rather plausible. In any case, the relaxation parser operates in 
various respects like an actual parser or like a generator, and it was this rela- 
tionship between parsing and generating that became of interest, 
Out of the design of the relaxation parser, the notation (independent of syn- 
tax) which to some extent describes various processes and choices of alternate ways 
of processing was developed. Thus, one may take a set of syntax and semantic de- 
scriptions and then through describing the processing 'modest involved, define a 
processor which uses the particular algorithm that the individual processes together 
define, One may call the parser that is programmabLe in its processes a meta-parser, 
of which various existing qarsers and generators appear to be special cases, 
A closer examination of the parser I have developed (called PEDAGLOT*) may show 
some such aspects of meta-parsing, especially as regards the relationship between 
parsing and generating. I will describe the syntactic and semantic parts of the 
parser first: by noting its resemblances to the parser of J. Earley (1970) and the 
ATN system of Woods. Then I will describe the process-type specifications that are 
available, and the use of meta-parsers as a basis for defining general language be- 
haviors. Purther detail can be found in the PEDAGMT manual (Fabens, 1972 and 1973). 
*for pe&~ogic polyglot 
1. The Core of the Parqer 
-1 
The fundamental operation of the parser is very similar to the operation 
of Earleyvs parser, with augmentations for recording the results of parses 
(e,g,, their tre structure, and various of their attributes, which I call 
ftags'). It is given a grammar as a set of context-free rules with various 
extensions, most imp~rtant of which are that LISP functions may be used as 
predicates instead of terminals, and thay each rule may be followed by opera- 
tions that are defined in tbnns of the syntactic elements af the rule in question, 
An example of this notation is as follows: 
S -+ NP VP 
=> [AGREE [REF NP] [VB VP] ] 
[SUM = [REF NP] ] [OW = [REF VP] [VB = [VB VP] ] 
S -* NP [BE] [VPASS] BY NP 
=> [AGREE [REF NP] [VB [BE] ]I 
[SUM = [REF NP I] ] [OBJ = REF NP] ] [VB = [VB [VPASS] ] ] 
NP -+ [DET] [N] 
=> [REF = [N]] 
W + [VINP 
=> [VB = [V]] [REF = [REF NP]] 
Here, each bracketed symbol is the name of a recognition predicate (e .g., 
IN] recognizes nouns, [BE] recognizes fons of hto be1), Following the => are 
the post -recognit ion functions. For instance [AGREE [REF NP] [VB VP] ] specifies 
a call to the AGREE function which is given, as arguments, the REF attribute (tag) 
of the sub-parse involved in that rule and the VB attribute of the VP part of 
the rule. 
Following is a parse tree for 'The Man Bites theDogl and values of tags 
after the parse. 
The Dog 
The general flow of the parser is from top-down, and as the lowest compo- 
nents (symbols in the string) are found, the post-recognition functions that are 
associated with the rule that recognized them 
are applied. Tags become associated 
with sub-parses when the post-recognition operation uses the form [x = y] (in which 
the value referenced by y is stored as the x tag of the sub-parse). 
In the example, 
[DET] and [N] recognize 'The Manf and 'Manf is used as the REF attribute ofi the 
first NP. In the second S rule, the operation of [SUM = [REF NP']] would be to 
retrieve the REF tag of the second NP (thus the prime), and to store that as the 
SUM tag of the final pane. 
As in most top-down parses, this parser begins with S and its two rules, 
since S is non-terminal. S is expanded into the two sequences of matches it should 
perform. This expansion results in various (in this case, two) predictisns of what 
to find next, When the initial symbol in some rule is a terminal or a predicate, 
a discovery is called for (in which a match is pexformed, possibly involving the 
known values of the tags). When some complete sequence of elements is found (here, 
for instance, when NP -+ [DET] IN] has matched the [N] ) . 
Construction invokes the 
post-reoognit ion operat ions and then usual lyt completes some earlier part of a rule 
(here, the 'NPi ~f S + NP VP) So further predictions 
(involving VP) or discoveries 
are then specified. 
1 have broken up the parsing process into t\he$e three parts so as to simi4arly 
catalpg the 'parsing modes,' turning this parser into a meta-parser. Before doing 
so, f should note tbat this parser stores each zesult under construction in a 
'chart' as is done by Kaplan in his GSP, so that, for instance, the NP 'testt 
will only have to be evaluated once for each place one is wanted in the string. 
[Nl [;I 1 [Nl 
5 
The 
T 
Man Bites The 
$ 
Dog 
I1 lustrat ion of PEDAGLOT ' s Parsing Chart 
Simple Arrows indicate 'Predictions.' 
Double Head Arrows indicate iDiscoveries, 
Dotted Arrows indicate tlConstruction. 
Also, for various well known reasons of efficiency, Earley's concept of 
independent processing of syntactic events is used (combined conceptually with 
the chart), SO that a main controller can evaluate the individual syntactic 'tests1 
in almost any order, and not just in a backtracking sense (cf. Woods, 1975). Thb 
efficiency is realized here since many 'partial parses (partially recognized forns) 
15 
are effectively abandoned if other results can complete the parse, or a sub- 
parse, first . 
2. Meta-Parsing Modes 
One can see that, except for the notational inefficiencies of the context, 
free formalism (as opposed to the augmented transition network form), this parser 
is very much like other standard parsers (especially ATN s) . 
It differs in that 
there is a waytof specifying how to proceed. Currently, this system has approxi- 
mately a dozen toodesr and I will present some of them here. Each mode specifies 
how to handle a certain part of the parsing process. 
They can be classified into 
four categories: attention control, prediction, discovery and construction. 
a, Attention Control Wes: 
Since the parser operates on a chart of independent events ('parsing 
questions1), one must give the parser a method of sequencing through them. 
Thus, one may specify 'breadth-first1 or 'depth-first1 and the appropriate 
~echanism will be invoked {this merely involves the way the processor stacks 
its jobs). A 'best-first ' option is -under development, which, when given an 
evaluation function to be applied to the set of currently active partial 
parses, allows the system to operate on the 'best1 problem next, Experi- 
Bents with this mode have so far been inconclusive. 
One also can specify when to stop (i.e., at the first complete parse, 
or to wait until all other ambiguous parses have been discovered). 
The dis- 
it~gbiguation routine (which is described as a part of the construction modes) 
defines which parse is %estl, Further, one may specify a left-to-right or 
right-to-left mode of how to progress along the string. 
b. Discovery Modes: 
The starting point of building a relaxation parser 
is to specify what 
to do when an exact match is not made. 
If the parser is expecting one word 
and finds another it can look arowd the indicated place in the string to find 
what- it is looking for, or it can in certain other circumstances simply 
insert the expected word into t'he string. Thus, under discovery.modes, 
there are vaxious options: either the parser is allowed to attempt matches 
in out-of-sequence parts of the string, or nat, And if not, or if no such 
match is found, the parser may or may not be allowed to make an insertion. 
So in PEDAGLOT, there is an INSERT mode (and various restricted versions 
of ft) and a 'where to look1 mode which is used to control the degree to which 
the parser can try to find out-of-place matches, There are tags associated 
with-these two specifications, the INSERT tag and the OMIT tag, which are 
associated with the parses involving insertions and omissions tbat contain 
the number of insertions made and the number of input symbols omitted in 
building the parse. 
There is also a rearrangenient mode. mus, given certain constraints, 
the parser could be givep 'The Bites Man Dogt and produce a parse for *The 
Man Bites the Dogt since it would have found 'Man,' by temporarily omitting 
'Bites,' but then it looks for and finds 'Bitest and finally, finding no se- 
cond lthe,fthe,l inserts one [or some other determiner because of the [DET] func- 
tion]) and finds 'Dog. In a similar way it would try to produce a passive 
form [i.e., the Man Is Bitten By the Dog) but since this involves more inser- 
tions, etc. it would not be chosen. 
These heuristics are controlled by recording numerical summary tags 
with each sub-parse that participate in, and are judged1 by the disambiguatic;~~ 
routines. Similar ideas are used by Lyon (1974). 
c. Prediction Modes: 
As Woods (1975) has pointed out, the extent to which a parser's prediction 
increases efficiency varies with the quality of the expected input. This fact 
affects greatly our discavBry procedures, since, if insertions are to be made, 
one aught to be rather sum of one's p~edictions, or risk a combinatorial ex- 
plosion. 
In PEDAGLOT, there is a programmable 
choice ' function that- con- 
trols predlctions. 
Specifically, when the parser encounters a non-terminal 
symbol, that symbol is the left-hand side of various rules. An uncontrolled 
pkediction (used by a canonical top-down parser) is to select each such rule 
as the expansion. 
Intuitively, however, people do not seem to do this. 
In- 
stead, as in an A'I??, they try one and only if that fails, go Into the next. 
In PEDAGLOT, the choice of which rule to try can be defined as the result of 
the call to a 'choosef function (or it can be left uncontrolled] , We have 
des&ned various approaches to such predictions (e.g., a limited key-word 
scan of the incoming string, and the use of 'language statistics such as the 
set of rules which can generate the next symbol in the string as their left 
most symbol). 
The prediction is currently made once for any given choice point; its 
outcomes are expected to be an ordered set of rules to try next. 
d . Construct ion Modes : 
The phase of parsing in which the parts of the parse tree and associated 
tag values are formed, is a place where most of the non-syntactic information 
(tags] about the string being parsed can come into play. 
In the first place, new tags can be formed as functions of lower level 
parse tags tbough a process called melding, Thus, 'nonsense1 can be discovered 
d pronoun references can sometimes be tied down, In the second place, it is 
a result of construction that ambiguity is discovered and dealt with, 
Since these features of parsing deal primarily with semantics (and since, 
if anyrcthere, sttsntantic representations of the string reside in the tags), most 
of tb PEDAGLOT construction modes involve tags. 
One play explicitly meld tag values by using post-recognition operators, or 
one nay define an 'implicit' melding routine that is associated with the tag 
names themselves instead of with individual rules. In our example we use 
this device to implicitly form a simple list of the two REF tags that be- 
come associated with the S rule. This implicit melding operation can also 
include a blocking function, or some reference to a data base. The tags 
that contain INSERT and OMIT information are used in this way to keep running 
totals of, and to minimize the munber of such heuristics in the relaxation 
parsing modes. One may also associate a LIFT function which, when the par- 
tial parse becomes complete, specifies a transformation of that tag to be 
used as The tag of the next higher level parse. 
Ambiguity is discovered when two parses from the same symbol, cbvering 
the same string segment axe found. For this case, an AMBIG function is asso- 
ciated with tag names, and it makes a 'value judgement1 of which tag is 'better, 
hence which interpretation to use. (Other types of criteria can also come into 
play here such as user interaction, (cf. Kay, 1973). 
3. The Uses of Meta-Parsers 
I ha-re just catalogued some of the parsing modes available in PEDAGLOT. Others, 
such as Bottom-Up (instead of Top-Down) or Inside-Out (instead of Left-to-Right, etc.), 
are envisionedlbut not implemented. Since PEDAGLOT is an interactive program, the 
user can change modes at will, just as he can change syntax or introduce new tags, 
Thus, the obvious first use af meta-parsers is that one may use them to desisn 
language processors without having to tie oneself down from the start to say, a 
depth-first parser, 
Meta-parsers also have a certain amount of tractibility that parsers that 
blend all .activities into one huge network may not. Ono may sea at a rather high level 
what is going to be happening (i.e,, all tags of a certain name will meld together 
in a certain way, unless the grammar specifies otherwise), If one, however, wants 
certain foms of local behavior, one may use predicates or functions on individuaQ 
rules. Further, if one wants to change the order in which predictions are evaluated, 
one can program a tchoosel function which will make that global change. To a 
large extent, the language designer may specify mch of the processor in broad 
ternas and still be able to control local events where necessary. 
In a more general sense, a meta-parser allows one to understand and build 
higher order theories about how people might represent and process language. 
For instance, while it may be true that generating is the inverse of parsing, 
there is more than one way to do such inverting. One could start from a senantic 
network, using the choose function along with the INSERT mode to restrict means of 
expression consistent with the intendea message, and using AMBIG functions to weed 
out all but reasonable messages from mng the many the parser may produce or one 
might simply take from the semantic network a simple string of meaningful words, 
and then we a less tightly programmed 'relaxation parser' to rearrange these words 
to be syntactically correct. We are now considering using a crude 'backwardsT mode 
which begins with the operati~n part of a rule and, by using predicates (e.g., AGREE) 
to yield inverses, specifies what the context-free pattern must produce. Thus there 
are many variations of how to generate using a meta-parser. 
In the area of language inference, to take another example of language processing, 
PEDAGLOT suggests various differing ways of approaching the problem. First, ofie may 
use it a5 a 'relaxation-parser, the 'parse tree1 can be pattern-matched against 
the new sentence, and hypotheses can be famed. Or, one could place a more rudimentary 
inference systw on the 'prediction' part of the processor itself, and using other 
controls, the predictions that are successful could be rewritten as a new gramar. 
These two learning paradigms could each be strengthened by way of the use of tags 
to contain (in a sense) the meaning of the sentelzces to be learned, Each of these 
paradips can be modeled using a meta-parser like PEDAGLM. Thus, a meta-parser can 
raise [and be prepared to answer) a nlrmbor of interesting questions. 
American Journal of Compatationd Linguistics 
Microfiche 32 : 21 
Department of Computer Science 
The City College of the 
City University of New York 
Convent Avenue at 140th Street 
Hew York, New York 10031 
ABSTRACT 
We describe a semantic processor we are constructing which is 
intended to be of general applicability. It is designed around 
semantic operations which work on a structured data base of world 
knowledge to draw the appropriate inferences and to identify the 
same entities in different parts of the text. The semantic oper- 
ations capitalize on the high degree of redundancy exhibited by 
all texts. Described are the operations for interpreting higher 
predicates, for detecting some intersententialqrelations, and in 
particular detail, for finding the antece6ents of definite noun 
phrases. The processor is applied to the problem of drawing maps 
from directions. We describe a lattice-like representation 
intermediate between the linguistic representation of directions 
and the visual representation of maps. 
OVERVIEW 
1,2 
We are trying to construct a semantic processor of some 
7 
A 
This research was supported by the Research Foundation of the 
City University of New York under Faculty Grant No. 11233. 
The author would like to express his indebtedness to Harry Elam 
for many insights into the problems discussed here. 
22 
generality. We are using as our data base a set of facts involv- 
ing spatial terms in English. To test the processor and to study 
the interfacing of semantic and task components, we are building 
a system which takes as input directions in English of how to get 
from one place to another and outputs a map, a map such as one 
might sketch for an unfamiliar region, hearing the directions 
over the phone. 
A typical input might be the text 
"Upon leaving thi,s building, turn right and follow 
Washington Street three blocks. Make a left, The 
library is an the right side of the street before 
the next coxner." 
The output would be the map 
I 
Library 
I 
To bypass syntactic problems, we are using as our input the 
output of the Linguistic String Project's transformational pro- 
A 
I 
Washington Street 
gram (Grishman et al. 1973, Hobbs & Grishman), which is very 
. 
close to a predicate-like natation. The semantic component is 
. 1 
This Building 
designed around general semantic operations which work on a 
r 
structured data base of world knowledge to draw the appropriate 
N 
inferences and to identify phrases in different parts of the text 
which refer to the same eptity. The text, augmented and inter- 
related in this way, is then passed over to the task component, 
which makes arbitrary decisions when the map requires information 
not given by the directions and produces the map. 
ORGANIZATION OF TEXT AND WORLD KNOWLEDGE 
The kwp problems of semantic analysis are to find, out of a 
potentially enormous collection of inferences, 
the appropriate 
inferences, and to find them quickly. Our solution to the first 
is in our semantic operations described below. Our approach to 
the second problem is in the organization of the data base. 
The data in the semantic coptponent is of two sorts: 
1. The Text: the information which is explicitly in the 
text, In the course of semantic processing this is augmented by 
information which is only implicit in the text. The text con- 
sists of the set of entities X1,X2, ..., explicitly and implicitly 
referred to in the text, and structures of $he form p (X1,X2) rep- 
resenting the statements m#de or implied about these entities,e.g. 
walk (XI) = X1 walks, 
building (XZ) = X is a building, 
2 
door (X3, X2) = X is a &or of X2. 
3 
2. The World Knowledge or the Lexicon: the system's knowl- 
edge of words and the world. Words are the boundary between the 
Text and the LexPcon. A word is viewed as a key indexing a large 
body of facts (Holzman, 1971). 
Associated with each word are a number of facts or inferences 
which can be drawn from the occurrknce of p(X1, ..., X,) in the 
Text. The facts are expressed in terms of p's set of parameters 
Ylf 
,Ykt and a set of other lexical variables 
zl,.. ,,z 
m' 
stanaing for entities whose existence is also implied. A fact 
consists of enabling conditions and conclusions. When p(X1, ... X,) 
occurs in the Text and the semantic operations determine a 
24 
particular inference appropriate, its enabling conditions are 
checked. If they hold, the conclusions are instantiated by 
creating a copy of them in the Text with the lexical variables 
replaced by Text entities. 
Clusters. One way td state the "frames" problem (Minsky 
1974) is "How should the data base be organized to guide, confine, 
and make efficient the searches which the semantic operations 
require?" We approach this by dividing the sets of inferences 
into clusters according to topic and salience in the particular 
application. In the searches, the clusters are probed in order 
of their salience. In our application, the top-level cluster 
concerns the one-dimensional aspects of objects and actions. For 
example, the fact about a block that it is the distance between 
two intersections is in the cluster. If "around the block" is 
encountered, less salient clusters will have to be accessed to 
find informatio,~ about the two-dimensional nature of blocks, The 
mast important fact about an apartment building is that it is a 
building, to be represented by a square on the map. But if the 
directions take us inside the building, up the elevator, and 
along the hallway, the cluster of facts about the interiors of 
buildings must be accessed, 
A self-organizing list (Knath 1973) of the clusters is main- 
tained--when a fact in a cluster is used, it becqmes the top- 
level cluster--on the ,assumption that the text will continue to 
talk about the same thing. 
The ''<Truth Status" of Inferences. In natural language, 
unlike mathematics, one is not always free to draw certain 
inferehces. We tag our inferences always, normally, or sometimes. 
These notions are defined operationally. 
An always inference is 
one we are always free to draw, such as that a street is a path 
through space. A normally inference is one we can draw if it is 
not explicitly contradicted elsewhere, such as that buildings 
have windows. A sometimes inference may be drawn if reinforced 
elsewhere, such as the fact used below that a building is by a 
street. This classification of inferencescuts across the cluster 
structure of the Lexicon. 
Lattices. A large number of statements in any natural lan- 
guage text, especially the texts this system analyzes, involve a 
transitive relation, or equivalently, say something about an 
underlying scale. For example, the word "walk" indicates a 
change of location along a path through space, or a distance 
scale; "turn" indicates a change along a scale of angular orie,n-- 
tation. 
In any particular type of text there are scales or transitive 
relations which are important enough to deserve a more economical 
repredentation than predicate notation. In this particulak task, 
the important scales are a distance scale, a subscale of thbis 
indicating the path "you" $ill travel, and a scale representing 
angular orientation. This is the principal information used in 
constructing the map. For these scales we translate into a 
directed graph or lattice-like representation (Hobbs 1974). 
Some of the things which can be said about the structure of 
a scale are mat some point is on the scale, that of two points 
- 
on the scale one is closer to the positive end tHan the other, 
26 
and that a scale is a part of another scale. If a point B is 
closer to the positive end of the scale than point A, this *fact 
is represented by 
A-B 
If point C lies in the interval from A to B the representation is 
The diagram 
mean& the scale from C to D is part of the scale from A to B, It 
is possible to represent incompleteness of information. For exam- 
ple, if it is known that points A and B both lie in a region R 
of a scale but their relative positions are not known and if it 
is known about C only thati,tprecedes B this is represented by 
The lattice for the distance scale for text (1) is as follows: 
Washington St. The Second St. 
the 
cross 
st. 
Library 
The lattices are intermediate between the linguistic repre- 
sentation of the directions and the visual representation of the 
maps. They are used at several points in the semantic and task 
27 
processes. They can be constructed for any transitive relation, 
and could be very useful, for example, in representing causal and 
enabling relations in a system translating descriptions of algo- 
rithms into flowcharts OE programs. 
SEMANTIC OPERATIONS 
Basic Principle of Semantic Analysis. We bedieve the key to 
t=he first problem of semantic analysis, that of finding which 
inferences are appropriate, is Joos' Semantic Axiom Number One 
(Joos 1972), or what I will call the Principle of knitting. 
Restated, this is, "The important facts in a text will be repeat- 
ed, explicitly or implicity." That is, we capitalize on the very 
high degree of redundancy that characterizes a11 texts. Consiifer, 
for example, the simple sentenced "Walk out the door of this 
building." "Walk" implies motion from one pLace to another. 
"Out" implies motion from inside something to the outside. "Door" 
is something which permits motion from inside something to the 
outside or from the outside to the inside, or if closed, prevents 
this motion. "Building" is something whose, purpose is for people 
to be in. Thus, all four content words of the sentence repeated- 
ly key the same facts. Those inferences which should be drawn 
are those which are keyed by more than one element in the text. 
This principle is used both formally and informally by the 
semantic operations. It is used formally in the interpretation. 
of higher predicates and in finding antecedents. It is used more 
informally for deciding among competing plausible antecedents, 
resolving ambiguities, detecting intersentential relations, and 
knitting the text together in some minimal way. Here it isd 
primarily the formal uses that will be described. 
Xnterpretation.of Higher Predicates. In "walk out", "walk 
slwoly", and "pleasant walk", the higher predicates "out", "slow" 
and ''pleasant" a11 apply to "walk", but they narrow in on differ- 
ent aspects of walking. That is, each demands that a different 
inference be drawn from the statement that "X walks". "Out" and 
"slow" demand their arguments be motion from one place to 
another., forcing us to infe'r from "X walks'' that "X goes from A 
to B". "Out" then adds information about the locations sf A and 
B, while "slow" says something about the speed of this motion. 
"Pleasant", on the other hand, requires its argument to be an 
awareness, so we must infer from "X walks" that "X engages in a 
bodily activity he is aware of". 
Stored in the Lexicon with each higher predicate is the 
inference which must be drawn from its argument and the informa- 
11 
tion it adds to this inference. For example, go(zl,z2,z3)" must 
be inferred from the argument of "out". When the statement 
"out(waDk(X1))" is encountered in the Text, the higher predicate 
operation makes efforts to find a proof of 11go(zl,~1,~3) I1 from 
"walk(XL)". The search for this inference is similar td the 
search procedure described below for finding antecefienes. The 
facts in the resulting chain of inference are instantiated 
together with the information added by the higher predicate, and 
they are subsequently treated as though part of- the explicit Text. 
It is usual for them to be useful in further processing, unless 
the modifier is simply gratuitous information. 
Note that this operation allows considerable compression in 
29 
the number of senses that must be stored for each word* It 
ellows us, for example, to define "slow" as something like "Find 
the most salient associated motion. Find the most specific speed 
Scale for the object X of this motion. X's speed is on the lower 
end of this scale". This definition is adequate for such phrases 
as "walk slowlyn (the most salient motion is the forward motion 
of the walking), "slow race" [the forward motion of the competi- 
tors), "slow horsew (its running at full speed, usually in a 
race), and "slow personw. This last case is highly dependent on 
context, and could mean the person's physical acts in general, 
his mental processes, or the act he is engaged in at the moment. 
This operation has a default feature, If a proof of the 
required inference can't be found, it is assumed anyway. This 
allows a text to be understood even if all the words aren't 
known. Suppose, for example, "veer rightw is encountered, and 
the word "veern isn't known, i.e. no inferences can be drawn from 
it. Since "rightn requires a change in angular orientation as 
its argument, it is assumed this is what "veer" means. Only the 
information that the change is small is lost. 
FIND ANTECEDENTS OF DEFINITE NOUN PHRASES 
~ntities referred to in a text may be arranged in a hierarchy 
according to their degree of specification: 
1. proper names, including "you" and "I" 
2. other noun phrases, including those with definite, 
indefinite, and demofistrative articles 
3. khird person pronouns 
4. 
zeroed arguments am5 implied entities. 
30 
So far our work has concerned primarily definite noun phrases, 
but it is expected that many features of the definite noun phrase 
algorithm will carry over to other cases, 
The definite noun phrase algorithm consists of four steps. 
First, "uniquent2~s conditionsn are checked to determine whether 
an antecedent is required. If so, the Text and Lexicon are 
searched for plausible anteceaents. Third, consistency checks 
are made on these. Finally if more than one plausible antecedent 
remains the Principle of Knitting is applied to decide between 
them. 
Vniqueness Conditions, In the phrase "the end of the block", 
we know we must look back in the text for an explicitly or impli- 
citly mentioned "block" (the search case), but we do fiat neqes- 
sarily look for a previously meptioned "end" (the no-search case) . 
Given a definite noun phrase the algorithm first tries to deter- 
mine whether it belongstothe search or no-search case. This is 
done by checking two broad criteria. (These criteria were moti- 
vated by a large number of examples not only from sets of direc- 
tions but also from technical and news articles,) 
These criteria are checked by searching the Lexicon for 
certain features. However these searches are generally very 
shallow, in contrast to the potentially much deeper searches in 
the riext step of the algorithm. Sincs by far the majority of 
definite noun phrases are in the no-search case, checking unique- 
ness conditions can result in great savings. 
A caveat is in order. We state the criteria at a very high 
level of abstraction, We feel in fact that the algorithm can 
work at that level of abstraction if the   ex icon is properly 
constructed. But how to construct a large  exi icon properly is 
a problem we have not yet tackled in detail. In any event, we 
give examples for each case, and the examples themselves form a 
reasonably exhaustive classification. 
1. A definite entity is in the no-search case if it can be 
located precisely with respect to some framework. n his includes 
me following conditions. 
a. Objects which are located with respect to some identi- 
fied point in space: "the building on the corner". 
b, Plurals and mass nouns which are restricted to some 
identified region sf space: "the trees in the park", "the water 
in the swimming pool". Here "the" indicates all such objects or 
substance. 
c.. Points and intervals in time khich are fixed with 
respect to some identified event: "the minute you arrive", "the 
hour since you left". 
d. Events in which at least some of the participants are 
identified and which can be recognized as occurring at a specific 
time: nthe ride you took through the park yesterday1'; 
e, Points or intervqls on more abstract scales: "the end 
of the block", "the size of the building". The end is a specific 
point on the distance scale defined by the block. The size of 
the building is a specific point on the general size scale for 
objects , i . e. the volume scale. 
f. Superlatives, ordinals, and related terms: "the largest 
house on the block", "the second house on the block", "the only 
house on the block". If the set of comparison is identified, 
the superlative or ordinal indicates the scale oE comparison and 
the place on that scale of the entity it describes. This is a 
subcase of (e) . 
All of these conditions can be checked in one operation if 
the facts in the Lexicon are expressed in terms of suitably 
abstract operators relating entities to scales. We simply ask if 
the definite entity is on or part of a scale or at a point on or 
- - 
along an +interval of a scale, where the scale can be identified. 
However this requires that we take very seriously my suggestion 
in Hobbs (1974) that the lexicon for the entire language be built, 
insofar as possible, along the lines of a spatial metaphor. We 
have not yet had to face these problems since our only scales are 
physical -- our "at" and "on" are the locative "at" and "on". 
Also checking this criterion presupposes a very sophisticated 
syntactic and semantic analysis. For example, [d) assumes that 
the times of events mentioned in tenseless constructions can be 
recovered. 
2. A definite entity is in the no-search case if it is the 
dominant entity of that description. This divides into two sub- 
criteria: 
a, Those entities which are unique or dominant by virtue 
of the properties which describe them: "the sun1', "the wind". If 
the properties p1 (X) ,pZ (X), ..., are known about the definite 
entity X, the definitions of p1,p2, ..., are probed for the fact 
that the entity does not normally occur in the plural. Included 
under this heading are proper names beginning with "the", like 
"the Empire State Buildingff, and appositives, like "the city of 
Bos tonr' . 
b. Those entities which are unique by virtue of the prop- 
erties of an entity with which they are grammatically related: 
"the door of the building", "the Hudson River valley". 
"The door 
of the buildingn is represented in the Text as "xl 1  door'(^^,^^ 1 
building{X2))' i.e. "the Xl such that XI is the door of X2 which 
is a building". The uniqueness or dominance of XI is not a prop- 
erty of "door" but of "building". Stored with "building" is the 
fact that a building has in its front surface a main door which 
does not normally occur in the plural. "The door of the buildingr' 
is interpreted as this dominant dosr. 
If the tvliqueness conditions succeed, a pointer is set from 
the dominant lexical variable to the corresponding entity. If 
subsequently the same definite noun phrase occurs, the uniqueness 
check will discover this pointer and correctly identify the ante- 
cedent. Thus, we can handle the example 
"Walk up to the door of the building. Go through 
the door of the building." 
Here the uniqueness check gives us a shortcut around the next 
step in the algorithm. 
The Search for Plausible Antecedents. To illustrate the 
search for an antecedent, consider 
"Walk out the door of this buil8ing. Turn right. 
Walk to the end of the block. " 
What block? From "block" We follow a back pointerto the fact 
stored with "streetn *that "streets consist of blocks", and from 
34 
"street1' the fact with "buildingt' that "Buildings are by streets" 
Since a building is mentioned, we assume it is "the block of the 
street the building is on". The facts in the chain of inference 
leading to this are instantiated, An entity is introduced into 
the text for the "street" and the Text is augmented by the state- 
ments that "the building is on the street" and "the block is part 
of the street". This information turns out to be required for 
the map. Note that the Eact that a building is on a street is a 
sometimes fact and that we are free to d'raw it only because "the 
blockn occurs* 
To conduct the search of the Lexicon, ideally we would like 
to send out a pulse from the word "block" which travels faster 
over more salient paths, and look for the first entity which the 
ptXlse reaches. The saliency is simulated by the cluster 
structure descrihea above, The parallel process of the spreading 
signal is simulated by interleafing deeper pfobes from salient 
clusters with shallower probes from less salient clusters. For 
example, if "streets consist of blocks" is a cluster 1 fact, then 
we might probe for a cluster 1 fact involving syreets and a 
cluster 2 Eact involving blocks at roughly the same time, After 
one plausible antecedent is found in this way, the search is 
continued for possible antecedents which are nearly as plausible. 
If after a time no plausible antecedents are found, the search 
is discontinued. 
Searches for antecedents are conducted not only for entities 
but also for definite noun phrases that the nominalization trans- 
formations of the syntactic component have turned into statements 
35 
--e.g. "The walk was tiring". Here we look back for a statement 
whose predicate is "walk" or from which a statement involving 
"walkn can be inferred. There are cases in which the required 
inference is in fact a summary of an entire paragraph--e.g. 
"These actions surprised. , . "--although of course we cannot 
handle these cases. 
Consistencv. Each of the plausible antecedents is checked 
for consistency. Suppose X1 is the definite entity which prompt- 
ed the search and its properties are 
and X2 is the proposed antecedent with properties 
We must cycle through the q's and the r's to ensure they are con- 
sistent properties. Of course, to prove two properties q(X) and 
r(X) inconsistent can be an indefinitely long process with no 
assurance of termination. One admittedly ad hoc way we get 
around this is by placing into a special cluster those facts we 
feel are likely to lead quickly to a contradiction. The second 
tool we use for deriving inconsistencies may turn out to be 
quite significant. 
In the course of processing, the lattice described abave is 
constructed for several predicates. They contain information 
which can be useful in deriving an inconsistency. Suppose we 
have a text in which "the block" occurs explicitly several times. 
Toward the end of it, we encounter 
"Turn right onto Adarnii Street. The library 
fs at the end of the block". 
The search algorithm looks first for explicit mentions of "blockl" 
and finds them. Yet none of these entities is the one we want. 
Intuitively, the reason we know this is our almost visual feeling 
that we are already beyond those points. 
The lattice consistency check corresponds precisely to this 
feeling. If a definite entity X1 is a point or interval in a 
lattice or at a point or along an interval, we ask if the propos- 
ed antecedent X2 is or can be related to a portion of the lattice. 
If so, then since the lattice represents a transitive relation, 
we need only ask if there is a path in the lattice from X2 to XI. 
If there is, they cannot be the same entity. 
Many cases which pass for applications of the supposed 
recency principle--"Pick the most recent plausible antecedentn-- 
are in reality examples of this consistency check. The earlier 
plausible antecedent is rejected because of lattice considera- 
tions. 
As the text is processed, the whole structure of the 
discourse is built up. When a definite noun phrase is encounter- 
ed, this discourse structure is known and it is this knowledge 
that is used to determine the antecedent rather than the linear 
ordering of the words on the page. 
Competition among Remaining Plausible Antecedents. Even 
after the consistency checks, several plausible antecedents may 
remain, forcing us to decide among them on less certain criteria. 
To do this, we appeal to the Principle of Knitting again and make 
the choice that will maximize the redundancy in the simplest 
possible way. 
A probe is sent out from the definite entity and from each 
plausible antecedent. 
Each plausible antecedent is searched for 
properties it has in comon with the definite entity. 
Common 
properties Count most if they are already in the Text, an8 with- 
in the Lexicon, comon properties count more if they are within 
more salient clusters or they result from shorter chains of 
inference. 
Default. Like the higher predicate algorithm, the definite 
noun phrase algorithm has a default feature. If the uniqueness 
conditions fail and the search turns up no antecedent, we simply 
introduce a new entity. In fact, in the directians texts there 
are a disproportionately large number of default cases, for "the 
object" may simply be the object you will see when you reach 
that point in following the directions. 
Other Anaphora. We have not yet implemented routines for 
handling other anaphora. However, we believe they are very 
similar to the definite noun phrase routine, with certain differ- 
ences. For entities tagged with demonstrative articles, we do 
not check uniqueness conditions, and the search will be narrower 
since the antecedent must be an entity or statement actually 
occurring in the text. For pronouns also, no uniqueness condi- 
tions are checked. The search will turn up more consistent 
plausible antecedents, and a correspondingly greater burden will 
be placed on the competition routine. 
INTERSENTENTIAL CONNECTIVES 
We detect unstated inter-sentence connectives by matching two 
successive sentences 
S1 S2 with a small number of common 
38 
patterns. In the directions texts the patterns are usually few 
and simple. The most common are 
1. S1 asserts a change whose final state is asserted or 
presupposed by S2. 
2. 
S1 asserts or presupposes a state which is the initial 
state of a change asserted by S2. 
(These are likely very common patterns in all narratives,) For 
example, in the text 
"Walk out the door of this building. Turn right. 
Walk to the end of the black", 
pattern(1) joins the first two sentences, where the state is 
"You at X", Pattern(2') joins the last two sentences, where 
again the state is "You at X-". Note moreover that the sentences 
axe interlocked by n second application of the two patterns: The 
first sentence assumes an angular orientation which is the 
initial state of the change asserted in the second sentence. 
The final state of this change is assumed by the third sentence. 
In addition to providing the discourse with structure, this 
operation is one of the-princlipal means by which implied entities 
in one sentence, like X above, are identified with those in 
another. 
When pqttern (2) is applied, we delete the independent occur- 
rence of the state in the Text, so that subsequently it exists 
only as one intermediate state ih a larger event. Changes across 
time are handled in this way. 
TASK PERF-ORMANCE COMPONENT 
Arbitrary Decisians, The semantic operations are quite 
39 
general and can be used for any application. The augmented and 
interrelated Text is then handed aver to the task performance 
component, which of course is specific to the application. 
Our task component first makes arbitrary decisions required 
by the map but not given in the text. Both natural language 
directions and sketched maps allow information to be incomplete 
and imprecise, but in different ways. Far example, in 
nTurn right at the third street or the second stoplight". 
we must decide whether to put the first stoplight at the first 
or second street, 
The lattice representing the path "your' take must be complete 
in the sense that it is continuous, begins at the initial loca- 
tion, and ends at the desired goal, and that the relative loca- 
tions of all points on the path are known. The lattide is 
complete if and only if there is a directed path passing through 
every point in the lattice at least once. If it is not complete, 
it is completed by supplying the fewest possible new links. 
Gsometr-izing the Lattices. The second task operation is to 
convert the topological lattice representation into the geometric 
representation required by the maps. First we assign directions 
to all the points in the angular orientation lattice. In the 
simplest case we may have something like 
where "a - b" means direction b results from a clockwise 
rotation of direction a. If no explicit directional information 
4 (0 
is present, we simply assume a, c, and e are the same direction, 
and b and d are the same, and then assume the two directions are 
at right angles, Then in the distance lattice, contiguous or 
overlapping paths which share the same orientation are assumed 
to be parts of the same path and are mapped into a straight line. 
Information about names is accessed and assigned to the streets 
and buildings and the map is drawn, 
Specific Systems with a General Semantic Component. We are 
aiming not so much at the construction of a general natural 
language processing system, which still seems reasonably far off 
but at an easier way of constructing specific systems. The case 
of syntax is instructive. It would be foolish for one who is 
building a natural language processing system to build his 
syntactic component from scratch. Large general grammars and 
parsers for them exist (e.g. Grishman et al. 1973, Sager & 
Grishrnan 1975). It is easier by several orders of magnitude to 
begin with a general grammar and specialize it, by weeding out 
the rules for constructions that don't occur in the texts one is 
dealing with, and by adding a few rules for constructions and 
constraints peculiar to orre's application. 
We are trying to make a similar facility available for the 
most common kinds of semantic processing. Specializing the 
general semantic component would consist of several relatively 
easy steps. First the Lexicon would be organized into a 
cluster structure appropriate to the task. At worst, this would 
mean specifying the necessary knowledge in a fairly simple format. 
If a very large Lexicon were available, this could mean no more 
than designating for each fact the cluster it should appear in. 
Certain inferences could be made obligatory while others which 
are irrelevant to the task could be left out of the special Lexi- 
con altogether. Second a Task Component would be built which 
would take, as ours does, the semantically processed Text, and 
use it to perform the task. We are demonstrating the usefulness 
of this approach in performing a task involving a visual repre- 
sentation. It is likely to be useful in other sorts of tasks also. 
PERRY t. MILLER 
Massachusetts Institute of Technology 
Cambridge, Massachusetts 02139 
ABSTRACT 
\Jheh a user interacts with a natural language system, he may well 
use words and expressions which were not anticipated by the system 
designers. This paper describes a system which can play TIC-TAC-TOE, and 
discuss the game while it is in progress. If the system encounters new 
words, new expressions, or inadvertent ungrammaticalities, it attempts to 
understand what was meant, through contextual inference, and by asking 
ihteliigent clarifying questions of the user. The system then records 
the meaning of any ne9 words or expressions, thus augmenting its 
1inguist;lic knowledge in the course of user interaction, 
A number of systems tire being developed which communicate with 
users in a natural language such as English. The ultimate purpose of 
such systems is to provide easy computer access to a technically 
Onsophisticated pepon. When such a person interacts with a natural 
language systemr, however, he is quite likely to use words and expressions 
which were not anticipated. To provide truly natural interaction, the 
system should be able to respond intelligently when this happens. 
Most current systems, such as those of Winograd [lo] and Woods 
Ill], are not designed to ;ope with such "liiguistic input uncertainty." 
Their parsers fail completely if an input sentence does not use a 
specific, built-in syntax and vocabulary. At the other extreme, systems 
like ELIZB [93 and PARRY [Z] allow the user to type anything, but make no 
attempt to fully understand the sentence. The present work explores the 
tnlddle ground between these extremes: developing a sys.t;em which has a 
great deal of knowledge about a particular subject area, and which can 
use this knowledge to make language interaction a flexible, adaptive, 
learning medium. 
In pursuing this goal, the present work is most closely related 
to work being dona in the various speech recognition efforts [5, 7, 8, 
121 which ara studying how linguistic and semantic constraints can help 
deal with the ACOUSTIC error and uncertainty of speech. The adaptive 
system, however, is designed to deal with a much mors LINGUISTIC type of 
uncertainty. 
When people use unfamiliar words or expressions in conversation, 
we can usually deduce from context what is meant, and if not, we can at 
least ask intelligent clarifying qu~stions. To allow the machine to do 
the same, there must be a very flexible interaction of syntax and 
$emantics in the parsing/understanding process, There must be a 
different parser organization, and a more flexible use oP linguistic and 
semantic constraints, than is pfesen t in current natural language 
sys tern . 
The adaptive system is a step towards this goal Tha current 
implementation is a prototype, design'ed to illustrate many of these 
ideas, and to tie them together in a restricted system that is complete 
but not too complex. The system's domain of discourse is TIC-TAC-TOE: it. 
plays a game and discusses the game in progress. It has a (currently 
limited) set of semantic concepts, and attempts to interpret the user's 
sentences ih terms of these. The set of semantic concepts is FIXED. The 
system does not attempt to learn new concepts, merely new ways of 
describing concepts that are already familiar. 
When the system encounters a new word or a new phrasing, it uses 
contextual information to detername the possible meaning, and to ask 
clarifying questions which are as intelligent as possible. It then 
remembers the meaning of the new e&pressfon, and will use it itselF *en 
it talks. 
2. SAHPLE SESSION 
The best way to introduce the system is to show it in operatian. 
In the sample session that follows, user input is pteced~rd by 'U:", 
machine output by and comments added by the author arg in small 
type, enclosed in brackets, 
(HACHINE: I PLACE AM X IN TClE TOP LEFT SQUARE) 
[The machine makes its opening move. ] 
(USER: PLAY A ZERO IN THE CENTER WARE) 
(H: 1s ZERO A NOW HEANING 0) 
(U: YES) 
(H: OK) 
[The new word *zeroa is added to the machine's vocabu1ary.l 
(R: I PLACE AN X IN THE BOTTOM RIGHT WARE) 
(O: SLAP Ab4 0 IN THE BOTTOV! LEFT CORNER) 
(PI: IS (TO SLAP SOMETHING SOREWHERE) A WAY OF SAYING (70 PLACE SOMEmING 
SOMEWHERE)) 
(U: YES) 
(19: OK) 
[A new surface framer (as described in section 4) Is added to the set sf 
surface braes which express the concept of making a move.] 
(m: 1 SLAP AN X IN TWE TOP RIGHT SQUARE) 
f n this sample sassion, the machine uses its newly acquired vocabulary 
at every opportunity.) 
HOU CORE YOU PLACED AN X IN THE TOP RIGHT SQUARE) 
(H: IS (HOW CQHE MMEONE DOES SOHETHING) AN EXPRESSION ISEANIMG ( l!lOES 
SOMEONE 00 SQMETHING)) 
(U: YES) 
(M: OR) 
(H: TO-BEAT YOU) 
[A new surface frme is added to those sxpssssing the concept ' I 
Syntactic featuras are associated with each such frauge indicating such 
things as Wether subject-verb invsrsion is ds be DerBomed.1 
(U: CAN YOU CURRENTLY BEAT ME) 
m: 1s 
CURRENTLY AN ADVERB REFERRING TO THE TInE OF A RWE) 
[These are the only adverbs the system knows about. In fact, at present, 
the system ignores adverbs in its sewantic processing. I% asks the 
question because it wants to account for all the words in the sentence. 
(U: YES) 
'(M: OK) 
(11: YES) 
( M : r s WEST AN ADJECTIVE ~EANING 
EITHER 
(1: CORNER) 
(2: LEFT) 
(U: 2) 
(n:  or;^ 
(H: NO) 
[Notice that two top squares contain an x. However, only the left onel 
was played while the bottom right square was Free. Therefore the systcszn 
concluded that the top left square was being described. This example 
illustrates how contextual information can be used to ask as intelligent 
a cBarifying question as passibla.] 
(U: *yOW COME YOU PLACED AJ4 X IN THE TOP EAST SQUARE) 
(!I: IS EAST AN l@JECTLVE NEAWXNG) 
EITHER 
(1: RIGHT) 
(2: WEST) 
(0: lp 
(U: on) 

M IS (TO LAY SONETHING SOHEWHERE) A WAY OF SAYING (TO SLAP SOflETHING 
S0UEWERE) ) 
(U: YES) 
(M: OK) 
(H: IS (TO POLISH SOMEONE OFF) A WAY OF SAYING) 
E I THER 
( 1 : ( TO BEAT SOMEONE) ) 
(2: (TO LOSE TO SOMEONE)) 
(3: (TO TIE SOMEONE)) 
(U: I) 
(?'¶: OK) 
(R: BY LAYING AN X ON WE TOP CENTER CELL) 
[If this same session were subsequently repeated, sf course, the system 
would not need to ask any questions of the ushJr. 1 
2.1 Comments on Current Lirnitatians 
There are a number of limrtations to the adaptive system as it 
now stands. Some of these may be apparent in the smple session, bud an 
introductian to the system is not complete without discussing them 
explicitly. 
(1) The number of concepts available to the system at present is very 
small. This, in fact, is why the system's first guess is usually the 
correct one. If the sentence is at all within the systea's 
comprehension, the options as to its meaning are currently quite limited. 
(2) The range of expressive devices presently recognized is quits 
limited as well. For instance, the system does not recognaze relative 
clauses, con junctions, or pronouns (except for 1 and you). 
(3) The system currently deals only with TOTALLY UNFMILIAR words and 
expressions in this adaptive fashion, It will not correctly handle 
familiar words which are used in new ways (such as a noun used eas a varb, 
as in wzero the center squaren). 
(4) The system tries to map the meaning of new wards and expressiuns 
into its specified set of underlying concepts. It then displays its 
hypotheses to the user, giving him only the option of saying yas or nu. 
The user cann-ot say "no, not quite, it meahs . . .". (Thus concepts like 
Vhe 'northeast1 square" or "the 'topmost' squarew would ba confusing and 
not correctly understood.) 
The present simple system has been developed with two goals in 
mind: (1) to explore the techniques required to achieve adaptive 
behavior, and (2) to help fornulate the issues which will have to be 
faced when incorporating these techniques into a much broader natural 
language system. 
3. OVERVIEW 
Fig. 1 shows ths various stages that the Adaptive System gees 
through in understanding a sentence. In this sectian, we shall watch 
while the system processes the sentence "Mow came you placed an x in the 
top right ~quare.~ 
( 1) Local Syntactic Processing: 
In this first stage, the system scans the entire sentence looking for 
local constituents. These include Hsimplem noun phrases (NPs) and 
prepositional phrases (PPs), ("simplen meaning 'up to the head noun but 
not including any modifying clauses or phrases"), and verb groups (VGs) 
consisting of verbs together with any adjoining rnodals, auxilliaries, and 
adverbs. In this instance, the system Finds the two NPs, "youe and "an 
xm, the PP "in the top right squarem, and the VG nplacedw. 
(2) Semantic Clustering: 
At this stage, the clause-level processing starts. Unlike most systems, 
this clause-level processing is driven by SEMANTIC rslationshigs, rath-er 
than by syntactic form. It uses a semantics-first kclustssinsg*, with a 
sscondary use of syntax for cormnents and confirmation+ In this example, 
all the local constituents found can be clustered into s description of e 
single concept: that of making a nave, Section 4 describes the mechanics 
of this stage in more detail. 
(3) Cluster Expansion and Connection: 
During this stage an attempt Is mada to account Psr each word in the 
sentence by expanding the concept clusters, and if there is more thaw 
one, by joining them together to form an entire multicXausa1 sentence- 
In this case, ths concept cluster rnlght bs axpanded In two ways. 
a) One possiblllty night be that It is a "MOW" type question, and that 
wcornc.tn is some sort of adverb, However this possibility violatsf a 
semantic constraiet, since the system is not set up to answer haw a move 
is made; only how to win, how to prevent sorneons From winning, etc. 
Therefore this possibility is ignored. 
b) The other possibility f r; that "how come" is a new way of describing 
soma other clause funetton. 
(4) Contextual Inference; Clarification; and Response: 
During this final staga, any contextual inf~rrnatfsn available is brought 
to bear on araas of uncertainty, any necessary clarifying questions are 
asked, and the system responds to the sentencs. In this example, the 
only uncertainty is the meaning of "how comew. Since this is the main 
sentence 
1 
Xocal constituents 
concept 
clusters 
complete 
sentence 
hypothesf s 
system responds 
to sentence 
Fig. 1: Adaptive System Overview 
clause of the sentence, the possibility of its being an Wn or *aftsra 
clause are discarded. The remaining possibilities are nimperativsw, 
"hown, m~hyn, and "canw. The system does not answer %own and "canw 
quest ions in relation to making moves. Similarly, "imperativen does not 
make sense since the action described is a previously made move. 
Therefore the system asks if "How come someone does somethingw means Vhy 
does someone do somethingn. The user answers "yesn, so the system stores 
this new way of asking "whyn, and proceeds to answer the question. 
4. SEMANTICS-FIRST CLAUSE-LEVEL PROCESSING 
One of the major differences between this approach to parsing and 
that of a top-down, syntax-driven system (such as Moods' or Winograd's) 
is the order in which syntactic and semantic processing is done at the 
clause level. 
In a top-dom system, a sentence must exactly match the built-in 
syntax before semantics can even be called and given the various 
constituents of a clause, This IS clearly undesirable when one is 
dealing with input uncertainty, since one cannot be sure exactly how the 
user will phrase his sentence. One would prefer to Bet semantics opera%@ 
First on any local consituents present, so that it can make a reasonable 
grgss as to what is being discussed. 
As semantically-rslated clusters of local constf tuents are found, 
syntax can be consulted and asked to comment. on the rslative 
grmmaticality of the various clusters. If there are two competing 
semantlc inte~pretations of one part of a sentence, and syntax likes one 
much better than the other, then the "syntactically pleasing" 
interpretation can be pursued first. Later, if this does not pan out, 
the syntactically irregular possibility can be looked at as wsP1. In 
this way, syntax can help guide the system, but is not placed in a 
totally controlling position. 
A by-product advantage of this semantics-first approach is that 
the system can handle mildly ungrammatical input without any extra work, 
In addition, the semantics-first clustaring approach lends itself quite 
naturally to handling sentence fragments. 
In the remainder of thks section, we describe how the adaptive 
system organizes ids linguistic knowledge to implement this semantics- 
first approach. As we shall see, there are three componeflts of this 
knowledge. 
(a) Ths local racognizars which initially find local constituents. 
recognizers are represented tn Augmented Transition Network [ Ill fom, 
are quits simple, and are not described further in this paper. 
(b) Clause-level knowledge sf how actions and clause-functions are 
described. This knowledge is expressed in a descriptiva fashion which 
makes it msily manipulabla, and easy to add to. 
(c) Clause-level syntactic knowladge which is sxprssred ira a domain- 
indebpendent fom. 
4.1 Knowledge of how Actions are Described 
Figure 2 illustrates how the system stores its knowledge sf how 
actions (or events) are described. This knowledge is stored at two 
levels : the conceptual level, and the surface (or expressive) level 
As shown in Fig. 2, the concept PLACE represents the act of 
making a TIC-TAC-TOE wove. 
(a) On the CONCEPTUAL level, there are three "conceptual slots' 
indicating the actors which are involved in the actlon: a player, a @ark, 
and a square. 
(b) On the SURFACE, or expressive, level there is a list sf surface 
frames each indicating one possible way that the concept can be 
expressed. Each surface frame conslsts of a verb plus a set of syntactis 
case frames to be filled by the actors. 
(Notice that neither the conceptual slots nar the surface frames indicate 
explicitly the order in which the varlous constituents are to appear Fw a 
sentence.) 
When the system processes a sentence, it fills the concsptual 
shots with local constituents found rn the sentence If it has found a 
fmiliar verb, then it also gets any surface e(s) associated with 
that verb. At this point it calls syntax, asking for csments. 
For instance, if the input sentence is "1 place an x in the 
corner", then all the conceptual slots of #PLACE would be filled, and the 
system would pass the following string to syntax wagen% verb obj ppw . As 
a result, clause-level syntax does not see the actual constituents of the 
sentence, only the labels specifled In the surface case frame, plus 
information indicating number, tense, etc . 
An interesting aspect of this approach is that the clause-level 
syntax is entirely domain-independent. It knows no thing about TIC-TAC- 
TOE, or even about the words used to talk about TIC-TAC-TOE. Tke surface 
frames allow semantics to talk to syntax purely in terms of syntactic 
labels. As a result, one could write a single syntactic module, and than 
insert it unchanged into many domains. 
4.1.1 Using this Information 
In this section, we describe in more detail how this knowledge 
can be used when processing a sentence. 
(1) If the verb and constituents are familiar: 
If there is no uncertainty in a clause, then each constituent can 
be put into one of Ghe conceptual slots, and any surface frames 
associated with the verb can be examined The frame ~ndicates the csse 
(agent, object, etc. ) associated with each constituent whon that verb is 
used. The frame is used ta create a string of case labels that are sent 
to syntax for coments. 
For instance, iF the sentence is "1 place an x in the center 
CONCEPT: PLACE 
CONCEPTUAL SLOTS: 
P: player 
H: mark 
S: square 
SURFACE FRAMES: 
VERB: place (as in: 
AGENT: P mI place an x in the centera) 
OW: PI 
in: S 
VERB: play (as in: 
AGENT: P 
sf play an x in the centers) 
ow: H 
In: S 
VERB: play (as in: 
AGENT: P wX play the center") 
00J: S 
FLg . 2 : Linguistic KnowleMge about Actions 
square", the string passed to syntax is "agent verb obj pp". 
Syntax 
replies that the sentence follows normal order. 
Had the string been 
"verb obj pp" syntax would reply that the subject had been deleted. 
If 
the string was @'do agent verb obj ppn, syntax would reply that subject- 
verb inversion had taken place. 
Given "gent obj verb ppn, syntax would 
reply that the object was out of position. 
Thus syntax is set up to notice both g~irnmcatical and 
ungrmatf cal permutations in constituent order, and to comment 
appropriately. The system must then decide how to interpret these 
comments. 
For instance, if syntax replies that the object is out of 
position in the clause, or that there is incorrect agreement in number 
between subject and verb, the system may decide that the user has made a 
minor grammatical error, and allow the sentence to be processed anyway, 
especially if there is no better interpretation of the sentence. 
In this 
way, clause-level syntax plays an assisting role rather than a 
castrolling role in the analysis of a sentence. 
(2) If a constituent is unknown: 
If an unknown constituent is present, then both the frame and 
slot information can be used to help resolve its meaning. For instance, 
suppose the sentence is "I place a cross in the canter squarew, and the, 
word ~crossu is unfamiliar, 
Here, during the semantic clustering, the conceptual slots for a 
player and a square can bs filled by "Iu and "in the center square", but 
the slot for a mark is unfilled. In additiq, there is the unknown 
constituent "a crossg. 
A natural hypothesis, therefore, is that the unknown constituent 
refers to a type of mark. Since the verb is familia~, a surface frme is 
avaflable. Next, assumtag the unknown constituent is a mark, the string 
"agent verb obj ppw can be passed to syntax. Men syntax approves, this 
offers additional confirmation that the hypothesis is probably right. 
Subsequent evaluation of this hypothesis indicates that the 
sentence makes sense only if the mark referred to is Etn x, so the system 
asks if "crossu is a noun meaning 
(3) If the verb is unknown: 
If an unfamiliar verb is used, then there is no surface fsme 
availabls to help guide the analysis. Instead, syntax must ba used in a 
different mode to propose what the surface frame should be. 
Suppose the sentence is "I plunk an x in the center squareM. 
Here, all the constituants can be clustered into the concept #PLACE, but 
tbre is an unknown word, and no verb. Ths loglcrrl hypothasis is that 
the new word is a verb. A special syntactic module is therefore passad 
the followfag string "NP(P) verb(p1unk) NP(M) PP(in,S)# This module 
examines the string and produces tn new Frame: 
VERB: plunk 
AGENT: P 
OW: R 
in: 8 
The system can then ask if "to plunk something somewherew means 
"to place something somewheren, and upon getting an affirmative reply, 
can add the new frame to those associated with the concept 
PLACE. 
Since the system uses the surface frames to generate its om 
replies, it can now-use this new frame itself when it talks. When the 
system wants to generate a clause, it passes a selected frame, the 
constituents, and a list of syntactic features to a clause generator 
which outputs the specified form. (Thus, clauss-level syntax can be used 
by the system in three different modes: (1) to comment on the 
grmaticality of a string of case markers, (2) to constrbct a new 
surface frame, and (3) to generate clauscas when tha system itself 
replies. ) 
4.2 Knowledge of' how Clause-Functions are Described 
As illustrated in Fig. 3, knowledge of how clause-function 
concepts are described is also expressed as two Lexals. 
CONCEPT: #WHY 
CONCEPTUAL SLOTS: 
ACTION: #PLACE 
SURFACE F 
Why ACTIQN(SV1NV) (as in: 
*Why does someone do somsthkng") 
flow come ACTION() (as in: 
"Now come someone does something") 
Fig. 3 : Linguistic howl edge about Clause Functions 
Each clause function has a conceptual slot indicating what types 
of action can be used with that clause type (in this case, the action 
#PLACE), and a list of surface frames indicating different ways in which 
the cancspt can be expressed. 
A clause-type frame currently includes any special words which 
introduce the clause (ie. "whyn or "how comen), together with a list sf 
syntactic proparties which should be present in the clauss. This list of 
syntactic properties might include SVIMV, nsubjec$-verb inversionw (as in 
"why does someone do something"), ar 9ub ject deletionH, 'ING fomm, and 
"use of a particular preposition* (as in "from doing somethingw). 
These syntactic features, however, need not bs inflexible rules. 
Sentence understanding can still psocaed wen if tha syntactic features 
found by syntax do not exactly match those specified by the clause- 
function frame. Thus, an inadvertent ungrammaticality cam readily be 
recognized as such, and processing can continue. 
4.2.1 Using the Clause Function Knowledge 
In this section we examine how this clause function knowledge can 
be used. 
(1) With no uncertainty: 
If the input sentence is "Why dld you place an x in the center 
squarew, then during the semantic clustering the string Rdo agent verb 
obj ppu is passed to syntax, which replies that subject-verb inversion 
has taken place. 
When exarninlng the whole clause, the system sees that it exactly 
matches one of the surface frames for a #WHY-type question, since it 
starts with the word n~hyVind contams subject-verb inverslbon, 
Suppose, however, the sentence had been "Why you place an x IR 
the center squaren, or "How come did you place an x in the center 
square*. Each of these sentences matches a surface frame for a MY-type 
question, except that in both cases subject-verb inversion is incorrect. 
In such a case, the system can, if it chooses, decide that the user has 
made a minor error, and allow the sentence to be processed anway. The 
locally-driven semantics-first approach Lets this happen in a natural 
way. 
(2) A new surface frame: 
Another problem arises when a new clause introducer is 
encountered, as in: "Wherefore did you place an x in the center squareM. 
Here, as described in section 3, the system hypothesizes that this may be 
a new way of asking a #WHY-type question. Since syntax reports that 
subject-verb inversion has taken place, the system can therefore create a 
new surface frame: 
Wherefore ACTIOM(SV1NV) 
to be added to the frames associated with #WHY. 
B 
In summary, the adaptive -5ys tern stores its linguistic knowledge 
in a very accessible form. It is not embedded in the parsing logic. 
howledge of how actions and clause-functions are described is 
represented in a descriptive, manipulable format. Syntax is domain 
independent, and is used only to make cornants, with semantics playing 
the guiding role. This organization allows the parsinglunderstanding 
process to proceed kn a flexible fashion, 
5. CONCLUSION 
Language communication is an inherently adaptive medium. One 
sees this clearly ~f one takes a problem to a lawyer and spends time 
trying to assimilate the related "legalesen. One also sees it in any 
conversation where a persron is trying to convey a complicated idea, 
expressed in his own mental terms, to someone else. The listener must 
try to relate the words he Rears to his own set of concepts. Language 
has, presumably, evolved to facilitate this sort of interaction. 
Therefore it is reasonable to expect that a good deal of the structure of 
language is in some sense set up to assist in this adaptive process. By 
the same token, studying language from an adaptive standpoint should 
provide a fresh perspective on how the various levsls of linguistic 
structure interact. 
1575 ACL Mcetlng 
CONCEPTUAL GRAMMAR 
WILLIAM A, MARTIN 
Kassachusetts Insti tute of Tech~ology 
In OWL, an implementation of conceptual grammar, the two 
types of data items are symbols and concepts and the two basic 
data composition operations are specialization and restriction. 
A symbol is an alphanumeric string headed by ". 
Symbols 
correspond to words, suffixes, prefixes, and word stens in 
Znglish and the programer can introduce them at willm 
OWL concepts correspond to the meanings of EEglish words 
and phrases. 
They are constructed using the specialization ope- 
ration, comparable to CONS in LISP* 
(A B) is the specialization 
of A, a concept, by B, a concept or symbol. 
OWL form a branch- 
ing tree under specialization, with SOMETHING at the top. 
Concepts are given properties by restriction, which puts a 
concept on the reference list of another concept (compare property 
lists and S-expressions in LISP). A/B is the restriction of A 
by B. 
The categories in the specialization tree are semantic, but 
we use them also for the purposes usually assigned to syntactic 
dategories. 
A predication is a double specification of 2 model such as 
present tense or can. Examples are 
The pool is full of water. ((PRES-TNS (BE (FULL 94TER)) J POOL/THE) 
The cookie can be in the jaf. ((CAN (BE (IN JAR/TIIE))) COOKIE/THE) 
aob is the father of Sam. ( (PRES -TKS (BE (FATHE: SAM) ITHE) ) BOB) 
3ob hits the ball. ((PRES-TNS (HIT BALLITHE)) Boa) 
Bob is hitting the ball. ((PRES-TNS (BE (-ING (HIT BALL/THE))))BOB) 
Starting from this base we will discuss a number of issues 
buch as n~minalization incorporation, and deep vs surface cases. 
American Journal of Computational Linguistics ~icroffche 32 : 58 
JOHN F. BURGER, ANTONIO LEAL, AND ARIE SHOSHANI 
System Development Corporation 
Santa Monica, California 90406 
mcT 
We describe a natural-language recognition system having both applied and 
theoretical relevance. At the applications level, the prwram will give a 
natural ccmmunications interface facility to users of existing interactive 
data management systems. At the theoretical level, our work shows that the 
useful infoxmation in a natural-language expression (its "meaning") can be 
obtained by an algorithm that uses no formal description of synt-. The 
construction of the parsing tree is controlled primarily by semantics in the 
form of an abstraction of the nmicxo-world" of the DMS's functional capabil- 
ities and the organizat~on and semantic relations of the data base content 
material. A prototype is currently implemented in LTSP 1.5 on tho IBM 
370/145 computsr at System Development Corporation. 
In a recent article in Scientific, American, Dr. Alphonse Chapanis says, "Tf 
truly interactive computer (;ystm are ever to be created, they will ~omehow 
have to cope with the... errors and violations of format that are the rule 
rather than the exception in normal human ccmmunication" [1] . An example 
dialogue produced by twa persons interacting with each other by teletype- 
writer to solve a problem as~igned to them by experimenters showed that :not 
one grernaaatfcally correct sentence appears in the entire protocol. 
tl 
Many existing language pmcessors (woods, Kellogg , Thcmpson , etc. ) [ 2,3,4) 
are limited to what Chapanis calls "Irmnaculate prose," that is, "the sen- 
tences that are fed into the computer are parsed in one way or another so 
that the meaning of the ensemble can be inferred frm conventional rules of 
syntax," which are a £0- description of the language. 
In effect, users 
are required to interact with these system in sme formal language, 
or at 
least in a language that has a formal representation in the computer system 
that a user's expression must conform to (we are thinking, in the latter 
instance, of Vhampsonls REL, which has an extensible formal representation 
facility). In addition, most natural-language question-answering systems, 
including all referenced above, require that a user's data be restruct-wedl 
and reorganized acwraing to the particular data base requirements of the 
natural-language system to be used. 
At the level of artificial intelligence research [ti ,6 ,?'I , Mere is same 
interest in systems that recognize meaning in natural-language expressions 
by methods that dd not mire compiler-like syntactic analysi~ of an 
expression prior to asmantic interpretation. We believe it is possible, 
practical, and feasible, using new lingufstic processing strategies, to 
design a natural-language interface system that will permit flexible, intu- 
itive coaansmicatiba with information management systems and other computer 
programs already in existence. This interface is open-ended in that it has 
no prejudice about the user's system funckians and can be joined to almost 
any such system with relatively little effort. It is, in addition, able to 
infer the meaning of free-form English expressions, as they pertain to the 
host system, without requiring any formal description or representation of 
English. 
THE SEMANTIC INTEREACE ALTERNATIVE 
The syntactic inflexibiiity of existing natural-language processors limits 
their usefulness in interactive man-madine tasks. Our approach does not 
use a collection of syntax rules or equations as they are normally defined. 
Instead, we construct a dictionary in which we define words in terms of their 
possible meanings with respect to the particular data base and data manage- 
ment system (DMS) we want to use and according to the possible relations 
that can exist between data-base and I3MS elements (e.g., an averaging func- 
tion on a group CKE numbers) in the limited "micro-world" of this precisely 
organized data collection. Words appearing in a user's expression that are 
not explicitly defined are ignored by the system in processing the expres- 
sion; an example would be the word "the," which is usually not meaningful in 
a data management environment. Wa thus avoid the expressive rigidity that 
formal syntactic methods hposa on tha user and the excesaivcs time and 
resource consumption that results from the catibinatorial explosions usually 
produced by such rnethade. 
We distinguish in their definitions beween two types of words: content 
words md function worb (or "operatore"). 
Content words are wads whoae 
'meaningsw are the objects, events, and concepts that make up the subjects 
being referred to by users, 
More precisely, for data axetnagernent systems, 
these meanings (or "concepts") are the field names and entz'y identifiers for 
*e data b-e and the names for available IHS operations such as averaging, 
sdng, sorting, comparing, etc. Function words serve as connectors of 
content words. 
Their use in natural language is to indicate khe manner in 
which neighboring conltent words ar'e intended to relate to one another. 
In 
the example "the salary of the secretary ," used belaw, "salary" and 
"secretary," are content words, and "of" is a function word used to connect 
theta. 
Many cmntent wor& are context sensitive, In a particular data base, for 
btmcm, the ward "salary" may refer to the data-base field name SECSAL if 
the saXW frs "of a secretary," but may also indicate the field name CLKSAL 
if it is a *salary of a clerk." In recpgnition of this we therefore define 
eaah aontent word by a set of one or more pairs of the form 
((XI Yl) (X2 Y2) . . . (Xn Yn)) 
where the Xi ad Yi are "ooncep~" (that is, field names, etc.) as described 
above. This expression may be interpreted as, "if the word so defined irjt 
contactually related in a sehtance to Xl, its particular meaning in this 
centact is Y1, if it isr eo related b X2, it meme Y2, md ao forth." This 
particular oontextual mnaranfng af the word is callad its sense. Two content 
warm are consrid=& to bls artmantically related if the intersection of the 
Xi'a fmtn the definition of one wort! with the Yi's from the definition of 
U1Q other ira not empty. 
To get a more intuitive understanding of this process, suppose, again, that 
a data base contains entries for both secretaries and clerks with salaries 
fox each. 
Suppose "Suzi&' is an instance of a secretary and  om" is an 
instance of a clerk. We then have three words defined as follms: 
Suzie ( (SUZIE SECY) ) 
Torn ( (TOM C-LK) ) 
Salary ( ( sECY SECSAL) (CLK CLKSAL) ) 
Processing me phrase "Suzie ' s salary" would intersect the Yi (" (SECY) " ) 
from the definition of "Suzie" with the Xi's ("SECY" and "CLK") from the 
definition of "salary." The intersection is nan-empty ("(SECY)") , and, in 
discovering the semantic relationship the sense "SECSALI-' is assigned to the 
word "salary." Similarly, "Tan's salary" assigns the sense "CLKSAL" to 
"salary. !I 
A particular bplmentation of the natural-language interface processor 
operates for a particular DMS/data-base target system. It contains a 
particular &&ion- created for that target system. For a particular dic- 
tionary, the set of a21 lists 05 pairs as described above, therefore, 
constitutes the equivalent of a ~anccpt q~aph ox network for the particular 
data baa malogous to those URQ~ hy many of the more conventj-onall, parsers 
Pox semantic analysis folluwing (or during) the syntactic phase of parsing. 
In the analysis of a particular input by our system, two words in context 
are te~ted using the "intersection" method described abave and, if they are 
found to be semantically related, they are considered candidates for 
"connection" as descrrLbed below. Two words so connected £om a phrase. 
Function words are defined as operators or processors that perform this 
semantic test. The definition of one function word differs fm that of 
another according to its slope (see belaw) and also in that the operational 
definition of a function word can reject a connection even though the two 
words may be samntically related. 
In the operational definition of the 
function word may be a list of acceptable concepts or a rejection list of 
unacceptable concepts. In most conceivable data bases, the phrase "salary 
in the secretary" would be thus rejected by the function word "in. 
n 
As the analysis of an input expression proceeds, a "clumpifig" of word and 
phr as e meanings more and more explicitly normally, 
processing of the entire sentence results in a tree structure made up of the 
connected senses of all the content words fran the sentence. This result we 
term the sentence qraph even though the input expression may not be a 
grammatically cmplete sentence. This sentence graph will be translated 
into statement. 
We recognize that the linear ordering of the words in an input expression 
is not entirely randm and that certain aspects of me function of syntax 
must be taken into accorunt. This is done by means of a new and pwerful 
azgorithm bkd on what we call the syntactic-semantic slope. Linguists 
generally recognize that whenever two units of meaning are combined, one is 
semantically domfnant and the other subordinate, as a modifier is sub- 
ordinate to the modified word. After coenbinatfon, the ddnant word may be 
wed in most cases to refar to the canjoined pair. Thus, a "red herring" 
18 a "herring" (not a "red") , and the "salary of the secretary" is a 
"salary." 
If this relationship of dominance is represented vertically on a 
ltrectangular graph (i.e., dominance on the Y-axis), and if t&e linear order- 
ing of the words in the expression is represented on the X-axis in now1 
left---right: order, then the connection of an adjacent pair of content 
words or phrases will describe a linear slope on the graph. The slope is 
positive eir negative as the dominating sub-unit is, respectively, to the 
right or to the left of the subordinate sub-unit. For example, the phrase 
"red herring" makes a positive slope, thus: 
HERRING 
/ 
RED 
and "the salary of the secre=" makes a negative slope: 
S;71LARY 
Thus, the ~pera~onal meanings of fqnctian words operate on the meanings of 
nearby content words. Dominance is assigned, semantic relationships are 
verified, and the relationships so discovered are accepted or rejected. If 
accepted, the two word-meanings are connected, and the acceptable sense is 
assigned to the dumllnant word. 
Eunction words may connect content words in "positive," "negative ," or 
"peak" connections. me follming are examples of each mannax of connection: 
1. "Of" is a negative operator, as in "the salary of the 
SALARY 
2. "'8" is a positive operator, as in "the secretary's salary": 
3. "And" is a peak operator, as in "Atlantic and Pacific. " In 
contrast with positive and negative operators, peak operators add 
a representation of their m semantics into the structures they 
build ; 
AND 
\ 
A-IC PACIFIC 
4. Between any two adjacent content words there is an implicit "empty" 
operator that is a positive operator, as in "red herring": 
RED 
In general, all prepositions are defined as negative operators. This is 
equivalent Go the rule 
used by syntactic processors. The positive empty operator is equivalent to 
the rule 
NP+AxxrP3P 
and athew, while vexbe and conjunctions are defined as peak operators, 
giving our atatemcnt of rules such errs 
s+NPvE'NP 
MP + NP CONJ NP. 
Each operator has the facility to accept or reject any semantic rejlation 
accordin9 to the precise definition of the function word for the host data 
management system. 
Progressive connection of word meanings and previously connected groups or 
"phrase meanings" results in a tree graph that we call the sentence qraph. 
For example, the question "What is ;t;he surface displacement of US. diesel 
submarines?" could, for a particular data base, produce from the dictionary 
a string of content-word and funeion-word definitions that might be rep- 
resented typographically like this: 
( (SUB SURE-DISC) ) <OF> ( (U . S. LOC) ( (DIESEL TYPE) ) ( (LOC SUBS) 
(TYPE SUBS) 
As a xesult of processing, these will assemble into a tree structured (using 
the senseg of the words) like this: 
WHAT 
/ sUm-D=sP P 
LOC AsuBs TYPE 
U,S. DIESEL 
Even though this tree, or sentence graph, is created as a result of semantic 
relationships instead of Eonnal rules of grammar, it still. closely resembles 
the "parse tree" produced by mo~t conventional syntactic language processors. 
With respect to the user's target data management system, the sentence graph 
is preci~e and unambiguous and contains enough information for a 
straightforward translation into the formal query language of the EMS. 
In 
SDCrs DS/3 lanwage, for example, the above question would be expressed as 
PRINT SURF-DISP WHERE TYPE EQ DIESEL AND lXXl EQ U.S. 
The response to the usex's question will thus be the response frclrn his DMS 
to the formal query statement. 
The user's input in this hypothetical example is proper in fom and grammar. 
However, it need not have been. The request 
OBTAIN SURFACE DISP FOR US SUBS SUCH AS HAS TYPE EQ DIE=. 
would produce exactly the same sentence graph and thexefore, exactly the 
same foml query statement with the same response from the DMS. 
It is not likely that a syntax-based parser would have anticipated the odd 
laxxguage-use and grammar of this last request. Without a syntax rule that 
would alluw for the phrase "such as has" such a parser would not look at the 
semantics involved and would be unable to interpret the request. Our syntax 
algorithm gets the same results that would be expected fmm the application 
of syntax rules without the need to anticipate each grammatical construct 
expected from the user. 
In overview, the parsing algorithm makes a series of positive, negative, and 
peak connections based on the operational meanings of the function wards 
(including the "empty" aperator) and on the relations between meanings of the 
content wort%?. The algoridt-Xlm adheres to the following rules: 
e 1 Connections between content words are possible only if 
the result of the intez'sectfon test described &me is non-empty 
and if this result is not rejected by the operation of the function 
word perfodng the test. The function word definition also deter- 
mines which word supplies its X's and which its Y's for the test, 
It thus controls which word has its sense detedned if the test 
ia successful. Most of ten (though there are exceptions) , positive 
operators use the X's from the word to the right and the Y's from 
the word to the left of .be operator. Positive operators, these- 
fore, determine the sense of the word to the right. This is 
illustrated using, again, the secretaxy and her salary, Consider 
the definition of "Suzie" and "salary" as shown on page 5, The 
phrase "Suzie's salazy" has two content words, "Suzie" and 
"salary, " separated by the function word , " s , " This function 
word is a positive operator and, hence, applies the intersection 
test to the Xi from the definition of "salary" with the Yi from 
the definition of "~uzie." These values are, xespactively, 
'I (SECY CLK) " and " (km) . " The intersection yields " (SECY) , " 
which is acceptable to the " 's" operator, and the connection is 
made with "salary" as the dominant word. The sense of "salary" 
is the Yi associated with "SECY" in the definition of "salary," 
hence, "SECSAL." This selection process is reversed for negative 
aperators, while peak operators employ both kinds of tests, one 
on each side of the peak. 
Rule 2: No node in a sentence graph may have more .than one dominating 
node. That is to say, all connections must result in trees, This 
Is a canmon asswnptLon consistent with conventional syntax-driven 
parsers. 
Rule 3: 
Given a subtree, a constituent on its left has the possibility 
of conneation only to nodes of the subtree's positive adjacent 
slope, and a constituent on the right can connect onLy to the nodes 
in the adjacent negative slope. 
Intuitively, this means that if 
the nodes of a subtree are connected by 
"lines" that are "opaque 
bariersrn then a constituent on either side of the subtree may 
connect to it only on those nodes that it can rlsee.r' It may not 
connect to nodes on the "inside" or the "fax side" of the subtree. 
This is a powerful heuristic rule that eliminates the need to try 
connections to many syntactically impossible portions of the sub- 
tree. In effect this one rule, together with the definitions of 
the function words, replaces all the syntax rules used by most 
conventional parsers. 
Rule 4: In order to minimize disconnection of existing subtree 
structures (badcup) and still consider all possible connections, 
the system should, whenever possible, constrztct,subtrees starting 
from the top and make new connections from belaw. This rule leads 
to the following algorithm: Scan the consUtuents from left to 
right making negative connections, then scan from right to left 
making positive connections. Scan thus back and forth until no 
more connections can be made. Then make any poasible peak aonnec- 
tions and repeat the algorithm. Continue this process until all 
constituents have been connected into a single tree, 
We have observed that if ambiguities exist under these conditions, they will 
be semantic and, in all probability. not resolvable by any further processing 
or analysis of the expression. Therefore. there is no need to carry along 
temporary multiple construction possibilities, The algorithm may eirher 
query the user at this point for disambiguation or Wdwt the pxocesging and 
inf om reason, 
American Journal of Computational Linguis ties Microfiche 32 : 7 2 
P. MEDEMA, W. J. BRONNENBERG, H. C. BUNT. 5. P. J. LANDSBERGEN, 
R, J. H. SCHA, W. J. SCHOENMAKERS, AND E. P. c. VAN UTTEREN 
Philips Research Laboratories 
Eindhoven, The Netherlands 
ABSTRACT 
This paper outlinee a recently implemented que~tion answering system , called 
PHLIQA 1 , which answers English questions about a data base . 
Unlike other existing aysteme , that directly tramlate a syntactic deep structure 
into a program to be executed, PHLIQA 1 leads a question through several 
intermediate etages of semantic analysis . In every stage the question is repre- 
sented a0 an expression of a formal language, The paper describes aome features 
of the Languages that are &uc~essivelg used during the analyeis process : the 
English-oriented Formal Language , the World Model Language and the Data Base 
Language . Next, we ahow the separate conversion steps that can be distinguished 
in the process. We indicate the problems that are handled by these conversions , 
and that are often neglected in other systems. 
1. Introduction 
PHLIQA 1 is an experimental ~yetem for answering isolated English questions 
about a data base . We have singled this out as the central problem of queation 
anawerlng , and therefore postponed the treatment of declaratives and imperrt 
tives , as well aa the analyak of discourse untll a later vereion of the system . 
The data baee is about computer installations in Europe and their users . At 
the moment, it is small and resides in core- but its structure and content 
are those of a realistic Codagyl format data base on disk ( CODASYL Data 
Base Task Group [ 1971 'J ) 
Only one module of the system , the wevaluation componenVT , would have to be 
chmqpd in order to handle a lhaltf data base . 
2, PELIQA 1 ' e top level design 
Like other recent QA systems ( e,g, Petrick 1 1973 ] , Plath 1 1973 ] , 
Winograd 1 1972 ] , Woo& [ 1972 ] ) , the PHLIQA 1 system can , on the 
most global level , be divided into 3 parts ( aee fig. 1 ) : 
-- Underetandtng the question : 
Translating the question into a formal expree- 
sion which represents its meaning with respect to the world model of the 
- Computing the answer : Elaborating this expreseion , thereby finding the 
answer, it is repreeented in the system' s internal formalism. 
-- Formulating the answer : Translating this answer into a form that can be 
more readily under8 toad . 
questlon in English 
I 
formal expression , representing 
the meaning of the question 
I 
Answer 
Computation 
I 
answer In internal format 
Answer 
Formulation 
answer in external format 
Fig . 1. Global subdivision of PHLIQA 1, 
The interface between the Question understanding component and the Answer 
Computation component 1s a formal language , called the World Model Language 
( WML) . Expressions of this language represent the meaning of questions with 
respect to the world model of th@ system. Its conrrtants correspond to the concepts 
that canstitute the universe of discourse . The language is independent of the input 
language that ie udled ( in this case English) , and also independent of the storage 
structure of the data base. 
If we now look at a further subdivierion of the component& , the difference between 
PHLIQA 1 and other systems becornea apparent . Both above and below the World 
Model level, there is an intermediate stage of analysis , characterized by a 
formal language , resp r 
- 
The Engliaboriented Formal Language ( EFL) , which containa  constant^ that 
correspond to the terms of English, This language is wed to represent the 
semantic deep structure 
of the question , That divides the Question Unde~ 
standing component into two succes~ive subcomponents I 
a. Constructing an EFL expression . using only linguistic knowledge . 
b, Translating the EFL expression into a WML expression, by taking 
knowledge about the structuf.e of the world into account. 
- The Data Base Language ( DBL ) , which contains conatants that correspond 
to data base primitives . ( The World Model constants do not correspond to 
daW base primitives , because we want to handle a realfs tic " data base : 
one that was designed to be stored efficiently , rather than to reflect neatly the 
structure of the world . ) 
This splits the Answer Computation component into two successive subcomp* 
nenta : 
a. Translating a WML expression into a DBL expression taking knowledge 
abut the data base structure into account, 
b. Evaluating the DBL expre~sion . 
The aebup of the system that one arrives at in this way, is shown in fig, 2. 
In section 3 , we gay eamething more about PHLIQAq s formal languagqs in 
general . How the three succeesive translation modules are further divided into 
smaller modules , caUd ftconvertorsw , 
is dfscu~sed fn the sections 4 , 5 and 6, 
Section 7 treats the evaluation component . The Answer Formulation component 
is very primitive , and will not be considered further . 
question in English 
I 
Question 
Under0 tanding 
Answer 
Computation 
expreabion of Englisboriented Formal Langua$te 
I 
( Semantic Deep Structure ) 
EFL- WML 
- -- - - 
owledge of 
tsanslation ----- World Structure 
expre $ sion of World Model Language 
I 
- 
WML- DBL 
--t-- 
translation 
f - - - 
[ 
expredsion of Data Base Language 
1 
I 
answer in internal format 
Formulation 
anrswer in external format 
Fie 2, PHLIQA 1 main components . 
3. PHLIQA 1' B formal laxlguages 
3. 1, sylitax 
The three PHLIQA languages ( the English-oriented Formal Language , the 
World Model Language and the Data Base Language) have largely identfcal 
syntactic definitions . As pointed out already, their moat important difference 
is in the constants they contain . Thy share most , but not all , syntactic 
COIlJ3 t~C!tf~Ils , 
PHLIQA expresgions are rt trees TT that conaists of terminal nodes ( conetants 
and variables) and syntactic constructions . A syntact'ic construction is an 
unordered collection of labeled branches , departing from one node . 
The branches of a PHLIQA fl tree " can converge to a common subtree . 
Using a system of semantic types , the syntax of a PHLIQA language defines 
how expressions cm be combined to form a larger expressfan. For every 
syntactic conetruetion, there ie a rule which specffies : 
- What the semantic types of it8 Immediate sub-expressions are allowed to be . 
( There is never a restriction on the syntactic form of the sub-expressions , ) 
- How the semantic type of the remitting expression is derived from the 
semantic types of the immediate sub-expressions . 
Given the types of the elementary expressions ( the constants and variables ) , 
this def'lnes the language, ( Sources of inspiration for the syntax of our formal 
languages were the Vienna Definition Language- ( Wegner [ 1972 ] ) , and a 
formulation of Higher - Order Lo@c by J.A. Robinson [ 1969 ] 
. ) 
Some ~imple examples of semantic types are the foXlowing : 
A comtant reprersenting a single object has a simple type . E.g, , 6 has 
the type " integer " , A c6nstant representing a collection of objedta of type oc 
has a type of the form <d> . E,g. , companies has the type "(company) 
" intagera has the type "(integer) . 
A constant representing a function that can have arguments of type and 
values of type ('3 has the type + . E.g. , the function 
Tt IL-cornpany-sites TI has the type ?? company* &il%y: the function &sum " 
has the type tv (integer) integerw. 
The syntactic rule for the construction function - application t' could state 
that the emreasion 
is well -- formed if T is a well-formed expre~lsion of type and T is a 
2 1 
well - formed expression of type 6 -+ /3 , where oC and may be 
any type ; the whole expression then has the type 
P 
The PHLIQA languages contaln a wide variety of syntactic constructions , e,g. 
constructions for different kinds of quantification , for selecting elements from 
a list, for reordering a list, etc , 
3. 2, Semantics 
The PaIQA language8 have a formal semantics which recursively defines the 
values of the expressions, This definition assumes as primitive nations the 
denotatian~ of the conetants of the language : function - constants denote 
procedures , and the other canstants denoh value - expressions , This means 
that if we know the denotations of the constants occurring in an expreesion , the 
value of the expression fs defined by the semantic rules of the language , For 
tb Data Base Language , we indeed know the denotations of the constants ; what 
we call the data base is nothing but the implementation of the " primitive 
procedure8 ", t e. : the procedures corresponding to DBL functions , and 
the procedures for finding the value - expres~ions of the other DBL constants . 
Therefore , the DBL expressione are actually evaluable . 
For the World Model Language and the English-orientad Formal Language , such 
a data base does not exiat , but one could be imagined . We express thls by saying 
t4&t the WML and EFL expressions are * evaluable with respect to a virtual data 
base 
4, Constraction of the semantic deep structure of a question. 
As we have seen, the EnglfsMriented Formal Lmage differ8 from the other 
tfttu, languagee in two respect8 : 
1, It has different constants , of'whieh the most important are t 
a names of sets corresponding to noune ( e.g. * computers ") , to verbs 
( " buy - sitrtatiane * ) and to ssme of the prepoeitions 
( in - place - situations ) . 
b. grammatical functions t subject, object, etc . 
2, It Borne different constructione . Here the most striking difference is that 
EFL conekuctinns contain eemantic and syntactic featurea . The semantic 
features influence the formal semagtfca of the constructlorn ( e,g, the definite- 
nees or indefiniteness of a noun phrase influences the choice of the kfnd of 
quantification for that noun phrase ) . The syntactic features only play a role 
during the tranaiormatian process from English to EFL . 
Tt should be noted that Ln general two eynonymoue eenteqes need not be represented 
by tho same semantic deep structure in EFL . For example , 
the synonymy of 
A buys B from C and C sells B to A is not accounted for at tbia level . 
Hwever ,at the level of the World Model Language synonymous sentences are 
mapped onto equivalent ( not necesaarilg identical ) WML emrerssr iom . 
The construction of the semantic deep structure in EFL consists of three main 
phanes r 
phase 1: a lexicon , providing for each word one or more interpretations , 
represented by pairs ( CATi, SEM \ , where CAT Is a syntactic category 
i i 
and SEM an EFL expression . 
i 
phase 2: a set of rules that enables to combine the sequence of pairs ( CAT 
SEM1) , 
it 
corresponding to the original sequence of words , into higher level categories and 
more complex structures , until we have ultimately the pair ( SENTENCE , SEM ) , 
S 
where SEM is the EFL expression for the bomplete sentence . 
S 
A rule of phase 2 is a combination of a context free rule and a set of rules on EFL 
expressions , that show when and how a sequence of pairs 
can be reduced fo a pair ( CAT 
, SEMR) . 
R 
The general format of theae rules is : 
- context free reduction rule : 
........ CATl +. + CATk -> CAT 
R 
- EFL rules : 
The COND~'s are conditions on the EFL expressions SEM . . , , , 
1' 
SEMk . 
The ACTION ' s ahow how a new EFL expression SEM 
can be constructed with the 
i R 
helpofSEM ..... 
I' 
SEMk . The rule is applicable if at least one of the 
conditions COND is true . Then SEM ia constructed according to ACTION and 
I a i 
the aequence of pairs is reduced to ( CAT 
SEM ) . If more than one of the 
R' R 
COND is true , we have a local ambiguity. 
i 
phase 3: transformation rules that transform the semantic surface structure into 
an EFL expression that Is called the semantic deep structure . ~heee tr&mf~r 
mation rules handle aspecte of meaning that could not be resolved locally , during 
phase 2. This applies for Instance to anaphoric references and elllptic clauses 
in comparative cons-ctlons . 
A ~impler example is the specification of the subject in a clauae like ' to uee a 
computer ', The eemantic surface structure of this clause means: 
there is a 
usesituation , with ~ame computer as its object , and an unspecified subject . 
Phase 2 can be said to ' disambiguate ' thi@ expression in a context like 
' when did Shell start to qe a computer 3 
. 
A transformation specifies the subject of the use-situation as Shell '. This 
transformation would not apply if we had the verb propose instead of start ' . 
The condition8 of phase 2 and phase 3 contain a rkhortcuV' to the world model1 
the semantic types of the world model interpretations of the EFL congtants are 
inspected in order to avoid the construction of semantic deep e tructures that 
have no interpretation in the world model . This blocks many unfruitful parsing 
paths. 
5 . Translation from semantic deep structure to unambiguous World Model 
Language expression 
The translation from a semantic deep structure ( EFL expraseion ) into an un- 
arnbiguoua World Model Language expmsarion proceeds in 3 phases1 
phase 1s Translation from EFL expression Into ambiguous WML expression. 
b tbls phase , traneformations are applied which replace expressions containing 
EFL conetants by expreiseiolu containing WML canatants . Their most conspip 
uow effect is the elimination of "situations" and rTgrarnrnatical functionst1. It is 
important to note that the resulting expreseion often contains several "ambig- 
uous constantsW, These ariae from polyeemous brms in English r words that 
have a "range1? of posaible meanings . Such terms lead now to expressions with 
ambiguous constants8 constants that stand for a whole class of possible "insta* 
cesT' . An expression containing such constants , stands for the class of wellr 
formed expressions that can be generated by 'Ymtantlating" the ambiguous cow 
stants . 
phase 2% Disambiguation of  quantification^ . 
Many sentences are ambiguous with respect to quantification , 
E .g . Were the largest 3 computers bought by 2 French companies ? can either 
ask whether there are 2 French companies such that they both bought each of 
these computers , or, perhaps more plausibly , it can ask whether there are 2 
French companies such that together they bought these computers . 
Until thie stage in the process , the representation of such questions contains 
constructions which stand for both interpretatiow at once . But now that the 
system' 8 assumptions about the structure sf the world are reflected In the ex- 
pression, some such interpretations may be ruled out as implausible , because 
they would lead to the same answer , independent of what the atate of affairs in 
the world is . E ,g ., the first interpretation of the above example question 
has the value 'YalseW , independently of the values of the constants in the ex- 
preaeion . ( Because the assumption that a computer can only be bought by one 
company wapJ Introduced by a previous traneformatfon ) . Therefore , the second 
interpretation is chosen, 
phase 32 Di~arnbiguation of WML conestants . 
The ambiguous WML constants can be instantiated in a very efficient manner by 
using the semantic type system: The possible interpretations of an ambiguous 
comtant are severely restricted by the semantic types of the other constants 
that appear in it8 context, 
6. Tramlation from World Model Lanwge 
expression to Data Base 
Laqpage expression 
- 
In the World Model Language , constants correspond to the concepts of the universe 
of discourse, In the Data Base Language, conatants correspond to primitive 
logical and arithmetical procedures and to primitives of the data base . The choice 
of these primitives was governed by coneiderations of efficiency, rather than by 
the wish to represent neatly the structure of the univeree of discourse. Therefore , 
WML and DB conb fn different conatants . 
The translation from a WML expression to the DBL expression that will be evalu- 
ated, proceeb in three stages : 
1, Paraphrase of the WML expression, in order to eliminate * infinite notions ". 
WML contains conrrtanb representing infinite sets or infinite continua , like 
integer8 * , * moaey~amounts and ?' time 'l. Such comtants can not be 
directly or hidirectly represented in the data base , and hence have no DBb 
tramlation. By paraphrasing the expression, the infinite notions can of*n 
be elirntnated . 
2, Translation of expressions conklning WML constants into expressions con- 
&ining DBL cow tanh , 
This tranalatlon is required by phenomena like the following : 
- it Ls poasible that a class of objects is not represented explicitly in the data 
baee , while propertlee of ib elementa are represented indirectly, as 
properties of other , related objects , ( E.g. , cities do not occur in the 
PHLIC&Il data base , but their names are represented as the ciwnarnes 
of sites . ) 
A special case of this phenomenon ie the representation of a continuum by a 
class of diacrete objects ( E.g. , core ie represented by rr core 
memories ") t 
-- objects may be represented more than once in the data base. E.g. , in the 
PHLIQA 1 database, the flle of computer users and the file of manufacturers 
can contain records that represent one and the same firm. 
-- the data baee is more limited than the world model . Some questions that 
can be expreased in WML can be answered only partially or not at all r 
the WML expresrition has no DBL translation. The present convertor detects 
such expressions and can generate a message which specifies what informa- 
tion ia lacking . 
Examples of this caae are r the set '' integers '* ( if the attempt of the previous 
convertor to eliminate it has been umuccesr~ful ) , and the date-ottaking- 
out--owe ?* of a computer ( which happens to be not in the data base ) . 
3. Paraphrase of the DBL exprenr~ion , in order to improve the efficiency of its 
evaluation . 
The DBL expression produced by the previous convertor can already be evalu- 
ated, but it may be possible to paraphrase it in such a way, that the evaluaii~n 
of the paraphrase expression is more efficient, This conversion is worthwhile 
because , even with our small data base , the evaluation is often the most 
time-consuming part of the whole process ; compared to thie , the time that 
transformations take is negligible . 
7. The evaluation of a Data Base Language expression 
The value of a Data Base Language expression is completely defined by the sernaxl- 
tic rules of the Data Base Language ( see section 3 . 2 . ) , and one could cohceive 
of an algorithm that corresponds exactly to these rules . For reasons of efficiency, 
the actual algorithm differs from such an qlgorithm in some major respects r 
- in evaluating quantlficatiom over sets , it does not evaluate more element0 of 
the sat than ie necessary for determining the value of the quantification . 
- if ( e-g. during the evaluation of a quantification) , a variable assumes a new 
value , this doe8 not cause the, re-evaluation of any subexpressions that don* t 
contain this variable . 
Currently , evaluation occurs with respeet to a small data base in Core , To handle 
a real data base on dierk , only the evaluation of constantn would have to change . 
8, PELIQA I ' s Control Smckrrc3 
The sections 4 thmugh 7 sketched what the basic modulea of the system ( the 
convertors ") do . We shall now make some very general rernarh about the 
way they were implemented . These remark apply to all convertors except the 
parser, whioh is described in some detail by Medema [ 1975 ] . 
The convertors can be viewed as functiong which map an input expression into a set 
of zero or more output expressions . 
Such a function fa defined by a collection, of 
transformations , acting on subexpresslons of the input expression . Each tr&aa- 
formation wnrrists of a condition and an action , 
The action ie applied to a sub- 
expression if the condition holde for it . The action can either be a procedure 
transformfngra subexpression to its * lower level equivalent '' or it can be the 
decbian this subexpressfon cannot be translated to the next lower level '' , 
"I1 convertore are implemented as procedures which operate on the tree that 
repregents the whole f~uestion . The procedures cooperate in a " deptb-first ?' 
mmr : a conversion procedure finds suc~essively all interpretations that the input 
expression haa on the next lower level . Far each of theae Interpretations , as soon 
as it is found, the next convertbr ie called. If no interpretation can be found, a 
message Bving the reason for this dead end is buffered , and control fe returned 
to the calling convertor , 
If the answer fs found, it is displayed. If requested, the ayatem can continue its 
search for more interpretatlorn . If the answer level is not reached , it displays 
the buffered message from the " lowest " convertor that was reached , 
Colophon 
The PHLIQA 1 program was written in SPL ( a PL/1 dialect) , and runs under the 
MDS time sharing system on the Philips Pl.400 computer of the Philips Research 
Laboratories at Eindhoven . 
The quantfflcatio~i~lambiguation ghaae of the EFG-WML translation, the effi- 
ciency-conVersion ( step 3 ) in the WML-DBL translation , as well as some parts 
of the grammar , are not yet part of the running system , though the convertors 
are complekly coded and the grammar is elaborately specified. 
During the design of PHLIQA 1 , the PHLIQA project was coordinated by Piet 
Medema . He and Eric van Utteren deaigned the algorithmic structure of the aye- 
tern and made decisions about many general aspectxi of implsrnentatlon . 
The formal languages and related transformation rules were designed by Harry 
Bunt . Jan Landabergen and Remko Scha . Wijnand Schoenmakera deaigned the evalu- 
ation component. Jan Landsbergen wrote a grammar for an extensive subset of English 
All author6 were involved in the implementation of the system . 
During the design of PHLIQA 1 , exteneiva discussione with members of the SRI 
Speech Understanding team have helped us in making our ideasl more explicit, 

References 
CODASYL Data Base Task Group April 71 report. ACM, New York, 1971. 

P. Medema A control structure for a question answering sys tern . Proceedings of the 4th Inte~national Joint C~nferen~ce on Artificial Intelligence . Tbilisi , USSR , 1975. Vol. 2 . 

S,RPetrick SemanticInterpretaticmintheREQUESTsystem. Proceedings of the International Conference on Computational Linguistice , VoL 1 , Pisa , 1973 . 

W, J. Plath Transformational Grammar and Transformational Pars fng in the REQUEST system, Proceedings of the International. Conference on Computational Linguistics , Vol. 2 , Pisa , 1973 . 

J. A. Robinson Mechanizing HighexLQrdelr Logic , In : B, Meltzer and D. Michie ( eds. ) , Machine Intelligence 4 , Edinburgh University Pres~l , 1969. 

P. Wegner The Vienna Definition Language . Computing Surveys , Vol, 4 , no. 1 , 1972 . 

T, Winograd Understanding Natural Language . Cognitive Psychology , VoL 3 , no. 1 , 1972 , 

W. A, Woode , R. M. Kaplan and B. Nash-Webber The Lunar Sciences Natural Language Information System : Final Report . BBN , Cambridge , Masa, 1972 . 

Earley, J. (1970), llAn Efficient Context-Free Parsing Algorithm,I1 Comm. ACM 13, number 2, (February 1970)) pp, 94-102. 

Fabens, W, (1972), PEDAGLOT Users Manual, Rutgers University CBM-TR-12, kt. 19722, 

Fabens, W. (1973), PEDAGLOT Users Manual : Part 11, Rutgers University CBM-TR-23, Nov. 1973. 

Kaplan, R.M. (1973), "A General Syntactic Proce~sor,~~ in R. Rustin (ed.) Natural Language Processing, New York: Algorithmics Press, (1973), pp. 193-242. 

Kay, M. (1973), llThe MIND Systemjfl in R. Rustin (ed.) Natural Language Processing, New York: Algorithmics Press, (1973). pp. 155-188. 

Lyon, G. (1974)) "Syntax-Directed Least-Errors Analysis for Context-Free Languages: A Practical Approach.lr Comm. ACM 17, number 1, (January 1974), pp. 3-13. 

Simmons, R. and Slocum, J. (1972), "Generating English Discourse from Semantic Networks,''l Comm. ACM 15, number 10, (October 1972), pp. 891-905, 

Woods, W.A. (1970), "Transition Network Grammars for Natural Language Analysis," Comm, ACkl 13, number 10, (October 1970)) pp. 591-606, 

Woods, W.A., [1975), Syntax, Semantics, and Speech, BBN Report No. 3067, A.I. Report No, 27. Bolt Beranek and Newman Inc , , to appear in D, R Reddy (ed ,) ~Sech Recognition, Academic Press (1975) . 

[ l] Davies, Q.J.M., and Isard, S.D., 'Utterances as Programs, "resented at the 7th International Machine Intelligence Workshop, Edinburg, June 1972. 

[2] Enea, H., and Colby, K,M., ' Ideolectic Language Analysis for Understanding Doctor-Patient Dialogs', Proceedings of the 3rd IJCAI, Stanford, August 1973. 

[3] Fillmore, C.J., 'The Case for Case', in 'Universals in Linguistic Theory', Bach and Warms (Eds. ), Wolt, Rinehart, and Winston, Inc., Chicago 1968. 

[4] Joshi, A.K., and Weischedel, R.M., 'Some Frills far the Hodaf TIC- TAC-TOE of Isard and Davies: Semantics of Predicate Complement Constructions,' Proceedings of the 3rd IJCAI, Stanford, August 1973. 

5 ] e, P .L., 'A Locally Organized Parser for Spoken Input', Corn. ACM 17, 11 -(Nov, 19741, 621-63@. 

163 Miller, P.L., 'An Adaptive System: for Natural Language Understanding and Assimilation', RLE Natural Language memo No. 25, HIT, February 1974. 

[7] Reddy, D.R., Erman, L.D., Fennell, R.B., and Nealey, R.B., 'The HEARSAY Speech Understanding Systemt, Proceedings of' the 3rd HJCAZ, Stanford, August 1973. 

[a] Walker, D.E., 'Speech Understanding through Syntactic and Semantic Analysis', Proceedings of the 3rd IJCAI, Stanford, August 1973. 

[93 Weizenbaum, J., 'Eliza- a Computer Program for the Study of Natural Comunicatian between Man and Machine', CACM 9, 1972. 

[lo] Winograd, T. Procedures as a Representation of Knowledge Fw a Computer Program Tqr Understanding Natural Language, MAC-TR-84, Project MAC, MIT, Cambridge, Mass., February 1971. 

[ll] Woods, W.A., and Kaplan, R.N., 'The Lunar Sciences Natural Language Information System" BBN Report No. 2265, Bolt, Beranek, and Neman Xnc. September 1971, 

[12] Woods-, W.A., and MakhsuP, J., 'Ovlechanical Inference Problems in Continuous Speech Understanding , Proceedings of the 3rd HJCAB, Stanford, 1973. 

Grishman, R., Sager, N., Raze, C., & Bookchin,B.,"~he ~inguistic String Parser," Proc. NCC, MIPS Press, Montvale, N.J. 1973. 

Hobbs, Jet "A Model for Natural Language Semantics, Part I: The Model," Yale Univ. Dept. Comp. Sci. Res. Rep. 36, Nov. 1974. 

Hobbs, J., and Grishman, R., "The Automatic Transformational Analysis of Engljsh Sentences: An Implementation," Submitted to International Journal of Computer Mathematics. 

Holzman, M., "Ellipsis in Discourse: Implications for Linguistic Analysis by Computer, The Child's Acquisition of Language, and Semantic ~heory," Language and Speech (1971, 86-98. 

Joos, M., "Semantic Axiom Number One," Language (1972) 257-265. 

Hnuth, D. The Art of Computer Programming, - 3, Addison-Wesley, Reading, Mass., 1973. 

Minsky, M., "A Framework for Representing Knowledge," MIT A1 Memo 306, June 1974. 

Sager, N., and Grishman-, R., "The Restriction Language for Computer Grammars of Natural Language," CACM 18, 7 (7/75) 390-400, 

I. Chapanis, Alphonse. Interactive human cammunlcation, Scientific American, May, 1975. 

2. Woods, W. A, Trahsition network gr-ars for natural language analysis. Cozmnunications of the ACM, October 13, 1970, 

3. Kellogg, C. H,, et al, The CONVEXGE natural language data management system: current status and plans. ACM Sym~osium on Information Storaqe and Ratrieval, University of Maryland, 1971. 

4, Thompson, F, B.; 'Lockman, P. C.; Dostert, B.; Deverill, R, S. REL: a rapidly extensible language. Proceedings of 24th National Conference, ACM, New York, 1969, 399-417, 

Riesbeck, C, K. Computational understanding. Theoretical Issues in Natural Langu~ge Processinq: Proceedinqs of an Interdisciplinary Workshop in Canputaticmal ~inguist&cs, Psychology, Linguistics and Artificial Intelligence. Cambridge, Massachuastts, June 10-13, l975. 

6, Waltz, D. L. On understanding poetry, Theoretical Issues in Natural Langtmgs Processing, Proceedings of an Interdisciplinary Workshop in Camputational Linguistics, Psychology, Limuistics and ~rtificial Intelligence. Cambridge, Massachuset-, June 10-13, 1975, 

7. Sdhank, Roger, and Tesler, L. G. A Conceptual Parser for Natural. Language. Stanford Artificial InteUigence Project. Memo No. AI-76, Januaq, 1969. 
