This report describes a system of programs which perform natural

language processing based on an underlying language free

(conceptual) representation of meaning. This system is used to

produce sentence paraphrases which demonstrate a form of

understanding with respect to a given context. Particular emphasis

has been placed on the major subtasks of language analysis (mapping

natural language into conceptual structures) and language generation

(mapping conceptual structures into natural language), and on the

interaction between these processes and a conceptual memory model.

In visual-feedback work often a model of an object and its

approximate location are known and it is only necessary to determine

its location and orientation more accurately. The purpose of the

program described herein is to provide such information for the case

in which the model is an edge or corner. Given a model of a line or

a corner with two or three edges, the program searches a TV window

of arbitrary size looking for one or all corners which match the

model. A model-driven program directs the search. It calls on

another program to find all lines inside the window. Then it looks

at these lines and eliminates lines which cannot match any of the

model lines. It next calls on a program to form vertices and then

checks for a matching vertex. If this simple procedure fails, the

model-driver has two backup procedures. First it works with the

lines that it has and tries to form a matching vertex (corner). If

this fails, it matches parts of the model with vertices and lines

that are present and then takes a careful look in a small region in

which it expects to find a missing line. The program often finds

weak contrast edges in this manner. Lines are found by a global

method after the entire window has been scanned with the Hueckel

edge operator.

We present various heuristic techniques for use in proving the

correctness of computer programs. The techniques are designed to

obtain automatically the "inductive assertions" attached to the loops

of the program which previously required human "understanding" of the

program's approaches: one in which we obtain the inductive assertion

by analyzing predicates which are known to be true at the entrances

and exits of the loop (top-down approach), and another in which we

generate the inductive assertion directly from the statements of the

loop (bottom-up approach).

The treatment of a certain class of adverbs in conceptual

representation is given. Certain adverbs are shown to be

representative of complex belief structures. These adverbs serve as

pointers that explain where the sentence that they modify belongs in

a belief structure.

The paper describes a system of semantic analysis and generation,

programmed in LISP 1.5 and designed to pass from paragraph length

input in English to French via an interlingual representation. A

wide class of English input forms will be covered, but the vocabulary

will initially be restricted to one of a few hundred words. With

this subset working, and during the current year (1971-72), it is

also hoped to map the interlingual representation onto some predicate

calculus notation so as to make possible the answering of very simple

questions about the translated matter. The specification of the

translation system itself is complete, and its main points are:

i) It translates phrase by phrase--with facilities for reordering

phrases and establishing essential semantic connectivities between

them--by mapping complex semantic stuctures of "message" onto each

phrase. These constitute the interlingual representation to be

translated. This matching is done without the explicit use of a

conventional syntax analysis, by taking as the appropriate matched

structure the "most dense" of the alternative structures derived.

This method has been found highly successful in earlier versions of

this analysis system.

ii) The French output strings are generated without the explicit use

of a generative grammar. That is done by means of STEREOTYPES:

strings of French words, and functions evaluating to French words,

which are attached to English word senses in the dictionary and built

into the interlingual representation by the analysis routines. The

generation program thus receives an interlingual representation that

already contains both French output and implicit procedures for

assembling the output, since the stereotypea are in effect recursive

procedures specifying the content and production of the output word

strings. Thus the generation program at no:time consults a word

dictionsary or inventory of grammar rules.

It is claimed that the system of notation and translation described

is a convenient one for expressing and handling the items of semantic

information that are ESSENTIAL to any effective MT system. I discuss

in some detail the semantic information needed to ensure the correct

choice of output prepositions in French; a vital matter inadequately

treated by virtually all previous formalisms and projects.

Defining the semantics of programming languages by axioms and rules

of inference yields a deduction system within which proofs may be

given that programs satisfy specifications. The deduction system

herein is shown to be consistent and also deductive complete with

respect to Hoare's sustem. A subgoaler for the deductive system is

described whose input is a significant subset of Pascal programs

plus inductive assertions. The output is a set of verification

conditions or lemmas to be proved. Several non-trivial arithmetic

and sorting programs have been shown to satisfy specifications by

using an interactive theorem prover to automatically generate prrofs

of the veification conditions. Additional components for a more

powerful verficiation system are under construction.

The revival of interest in Automatic Programming is considered. The

research is divided into direct efforts and theoretical developments

and the successes and prospects of each are described.

Expert judges, psychiatrists and computer scientists, could not

correctly distinguish a simulation model of paranoid processes from

actual paranoid patients

We consider the class of linear recursive programs. A linear

recursive program is a set of procedures where each procedure can

make at most one recursive call. The conventional stack

implementation of recursion requires time and space both proportional

to n, the depth of recursion. It is shown that in order to

implement linear recursion so as to execute in time n one doesn't

need space proportional to n: n**ε for sufficiently small ε will do.

It is also known that with constant space one can implement linear

recursion in time n**2. We show that one can do much better:

n**(1+ε) for arbitrarily small ε. We also describe an algorithm that

lies between these two: it takes time n*log n and space log n.

It is shown that several problems are closely related to the linear

recursion problem, for example, the problem of reversing an input

tape given a finite automaton with several one-way heads. By casting

all these problems into canonical form, efficient solutions are

obtained simultaneously for all.

Signature table training method consists of cumulative evaluation of a

function (such as a probability density) at pre-assigned co-ordinate

values of input parameters to the table. The training is conditional:

based on a binary valued "learning" input to a table which is compared to

the label attached to each training sample. Interpretation of an unknown

sample vector is then equivalent of a table lookup, i.e. extraction of the

function value stored at the proper co-ordinates. Such a technique is

very useful when a large number of samples must be interpreted as in the case

of samples must be interpreted as in the case of speech recognition and the

time required for the trainng as well as for the recognition is at a premium.

However, this method is limited by prhibitive storage requirements, even for

a moderate number of parameters, when their relative independence cannot be

assumed. This report investigates the conditions under which the higher

dimensional probability density function can be decomposed so that the

density estimate is obtained by a hierarchy of signature tables with

consequent reduction in the storage requirement. Practical utility of the

theoretical results obtained in the report is demonstrated by a vowel

recognition experiment.

This paper (based on a keynote address presented at the

,

Boston, October 1-3, 1973) presents the view that a programming

language is a tool which should assist the programmer in the most

difficult aspects of his art, namely program design, documentation,

and debugging. It discusses the objective criteria for evaluating a

language design, and illustrates them by application to language

features of both high level languages and machine code programming.

It concludes with an annotated reading list, recommended for all

intending language designers.

A contour image representation is stated and an algorithm for

converting a set of digital television images into this

representation is explained. The algorithm consists of five steps:

digital image thresholding, binary image contouring, polygon

nesting, polygon smoothing, and polygon comparing. An implementation

of the algorithm is the main routine of a program called CRE;

auxiliary routines provide cart and turn table control, TV camera

input, image display, and xerox printer output. A serendip

application of CRE to type font construction is explained. Details

about the intended application of CRE to the perception of physical

objects will appear in sequels to this paper.

The notion of computer understanding of natural language is examined

relative to inference mechanisms designed to function in a language-

free deep conceptual base (Conceptual Dependency). The conceptual

analysis of a natural language seentence into this conceptual base, and

the nature of the memory which stores and operates upon these conceptual

structures are described from both theoretical and practical standpoints.

The various types of inferences which can be made during and after the

conceptual analysis of a sentence are defined, and a functioning program

which performs these inference tasks is described. Actual computer

output is included.

This paper is primarily a user's manual for LCF, a proof-checking

program for a logic of computable functions proposed by Dana Scott in

1969, but unpublised by him. We use the name LCF also for the logic

itself, which is presented at the start of the paper. The

proof-checking program is designed to allow the user interactively to

generate formal proofs about computable functions and functionals

over a variety of domains, including those of interest to the

computer scientist--for example, integers, lists and computer

programs and their semantics. The user's task is alleviated bu two

features: a subgoaling facility and a powerful simplification

mechanism. Applications include proofs of program correctness and in

particular of compiler correctness; these applications are not

discussed herein, but are illustrated in the papers referenced in the

introduction.

The problem (attributed to R. M. Karp by Knuth (see #36 of [1])) is

to describe the sequences of minimum length which contain, as

subsequences, all the permutations of an alphabet of n symbols.

This paper catalogs some of the easy observations on the problem and

proves that the minimum lengths for n=5, n=6 and n=7 are 19, 28, and

39 respectively. Also presented is a construction which yields (for

n>2) many appropriate sequences of length n*-2n+4 so giving an upper

bound on length of minimum strings which matches exactly all known

values.

We consider the power of several programming features such as counters,

pushdown stacks, queues, arrays, recursion and equality. In this study

program schemas are used as the model for computation. The relations

between the powers of these features is completely described by a

comparison diagram.

This paper develops some ideas expounded in [1]. It distinguishes a

number of ways of using parallelism, including disjoint processes,

competition, cooperation, communication and "colluding". In each

case an axiomatic proof rule is given. Some light is thrown on traps

or ON conditions. Warning: the program structuring methods described

here are not suitable for the construction of operating systems.

The recent book "What Computers Can't Do" by Hubert Dreyfus is an

attack on artificial intelligence research. This review takes the

position that the philosophical content of the book is interesting,

but that the attack on artificial intelligence is not well reasoned.

SAIL is a high-level programming language for the PDP-10 computer.

It includes an extended ALGOL 60 compiler and a companion set of

execution-time routines. In addition to ALGOL, the language

features: (1) flexible linking to hand-coded machine language

algorithms, (2) complete access to the PDP-10 I/O facilities, (3) a

complete system of compile-time arithmetic and logic as well as a

flexible macro system (4) user modifiable error handling, (5)

backtracking, and (6) interrupt facilities. Furthermore, a subset

of the SAIL language, called LEAP, provides facilities for (1) sets

and lists, (2) an associative data structure, (3) independent

processes, and (4) procedure variables. The LEAP subset of SAIL is

an extension of the LEAP language, which was designed by J. Feldman

and P. Rovner, and implemented on Lincoln Laboratory's TX-2 (see

[Feldman & Rovner]). The extensions to LEAP are partially described

in "Recent Developments in SAIL" (see [Feldman]).

This manual describes the SAIL language and the execution-time

routines for the typical SAIL user: a non-novice programmer with

some knowledge of ALGOL. It lies somewhere between being a tutorial

and a reference manual.

A computer program has been written that successfully discovers

syntheses for complex organic chemical molecules. The definition of

the search space and strategies for heuristic search are described in

this paper.

The maximum, minimum and average computing times of the classical

Euclidean algorithm for the greatest common divisor of two integers are

derived, to within codominance, as functions of the lengths of the two

inputs and the output.

Previous papers by the author have hypothesized that is is possible to

represent the meaning of natural language sentences using a framework which has

only fourteen primitive ACTs. Thii paper addresses the problem of when and how

these ACTs might be learned by children. The speech of a child of age 2 is

examined for possible knowledge of the primitive ACTs as well as the conceptual

relations underlying language. It is shown that there is evidence that the

conceptual structures underlying language are probably complete by age 2. Next

a child is studied from birth to age l. The emergence of the primitive ACTs

and the conceptual relations is traced. The hypotehsis is made that the

structures that underlie and are necessary for language are present by age l.

A new method of tracking the fundamental frequency of voiced spech is descirbed.

The method is shown to be of similar accuracy as the Cepstrum technique. Since

the method involves only addition, no multiplication, it is shown to be faster

than the SIFT algorithm.

Axioms for a total complexity measure for abstract programs are

presented. Essentially, they require that total complexity be an

unbounded increasing function of the Blum time and size measures.

Algorithms for finding the best program on a finite domain are

presented, and their limiting behavior for infinite domains

described. For total complexity, there are important senses in which

a machine can find the best program for a large class of functions.