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).

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.

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.

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.

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.