COMMENT ⊗   VALID 00009 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	.REQUIRE "ABSTRA.CMD[BIB,CSR]" SOURCE FILE
C00004 00003	.once center <<general instructions>>
C00006 00004	%3AIM-316  NATURAL LANGUAGE PROCESSING IN AN AUTOMATIC PROGRAMMING DOMAIN
C00010 00005	%3STAN-CS-78-673  A NUMERICAL LIBRARY AND ITS SUPPORT
C00013 00006	%3AIM-317  TAU EPSILON CHI, A SYSTEM FOR TECHNICAL TEXT
C00018 00007	%3STAN-CS-78-677:  COMPREHENSIVE EXAMINATIONS IN COMPUTER SCIENCE, 1972-1978
C00021 00008	%3STAN-CS-78-679   STEPLENGTH ALGORITHMS FOR MINIMIZING A CLASS OF NONDIFFERENTIABLE
C00025 00009	.<<SLAC>>
C00032 ENDMK
C⊗;
.REQUIRE "ABSTRA.CMD[BIB,CSR]" SOURCE FILE
.every heading (November Reports,,{Page})
.next page
.once center <<general instructions>>
%3MOST RECENT CS REPORTS - NOVEMBER 1978%1

@Listed below are abstracts of the most recent reports published by the Computer
Science Department of Stanford University.

@TO REQUEST REPORTS:##Check the appropriate places on the enclosed order form,
and return the entire order form page (including mailing label) by  November 3, 1978.
In many cases we can print only a limited number of copies, and requests will
be filled on a first come, first serve basis.  If the code (FREE) is printed
on your mailing label, you will not be charged for hardcopy.  This exemption
from payment is limited primarily to libraries.  (The costs shown include all
applicable sales taxes.  PLEASE SEND NO MONEY NOW, WAIT UNTIL YOU GET AN INVOICE.)

@ALTERNATIVELY:  Copies of most Stanford CS Reports may be obtained by writing
(about 2 months after MOST RECENT CS REPORTS listing) to NATIONAL TECHNICAL
INFORMATION SERVICE, 5285 Port Royal Road, Springfield, Virginia 22161.  Stanford
Ph.D. theses are available from UNIVERSITY MICROFILMS, 300 North Zeeb Road,
Ann Arbor, Michigan 48106.
.begin nofill
%4-------------------------------------------------------------------------------------%1
%3AIM-316  NATURAL LANGUAGE PROCESSING IN AN AUTOMATIC PROGRAMMING DOMAIN
%3Author:%1  Jerrold Ginsparg ↔(Thesis)
.end
@%3Abstract:%1@This paper is about communicating with computers
in English.  In particular, it describes an interface system which allows
a human user to communicate with an automatic programming system in an
English dialogue.

@The interface consists of two parts.  The first is a parser called Reader.
Reader was designed to facilitate writing English grammars which
are nearly deterministic in that they consider a very small number of parse
paths during the processing of a sentence.
This efficiency is primarily derived from using a single parse structure
to represent more than one syntactic interpretation of the input sentence.

@The second part of the interface is an
an interpreter which represents Reader's output in a form that
can be used by a computer program without linguistic knowledge.  
The Interpreter is responsible for asking questions of the user, processing
the user's replies, building a representation of the program the user's replies
describe, and supplying the parser with any of the
contextual information  or general knowledge it needs while parsing.
.break
.begin nofill
No. of pages:  172
Cost:  $ 6.55
%4-----------------------------------------------------------------------------------------------%1
%3STAN-CS-78-672  COMPARISON OF NUMERICAL METHODS FOR INITIAL VALUE PROBLEMS
%3Author:%1  Tony F. Chan ↔(Thesis)
.end
@%3Abstract:%1@A framework is set up within which the efficiency and storage
requirements of different numerical methods for solving time dependent partial
differential equations can be realistically and rigorously compared.  The
approach is based on getting good error estimates for a one-dimensional model
equation u↓[t] = au↓[x] + bu↓[xx] + cu↓[xxx] .  Results on the comparison
of different orders of centered-differencing in space and various commonly used
methods for differencing in time will be discussed.  Both semi-discrete and
fully-discrete studies will be presented.
.break
.begin nofill
No. of pages:  195
Available in microfiche only.
%4-----------------------------------------------------------------------------------------------%1
%3STAN-CS-78-673  A NUMERICAL LIBRARY AND ITS SUPPORT
%3Authors:%1  Tony F. Chan, William M. Coughran, Jr., Eric H. Grosse & Michael T. Heath
.end
@%3Abstract:%1@Reflecting on four years of numerical consulting at the Stanford
Linear Accelerator Center, we point out solved and outstanding problems in
selecting and installing mathematical software, helping users, maintaining the
library and monitoring its use, and managing the consulting operation.
.break
.begin nofill
No. of pages:  22
Cost:  $ 2.35
%4-----------------------------------------------------------------------------------------------%1
%3STAN-CS-78-674  FINITE ELEMENT APPOXIMATION AND ITERATIVE SOLUTION OF A CLASS OF
				MILDLY NON-LINEAR ELLIPTIC EQUATIONS
%3Authors:%1  Tony F. Chan and Roland Glowinski
.end
@%3Abstract:%1@We describe in this report the numerical analysis of a particular
class of nonlinear Dirichlet problems.  We consider an equivalent variational
inequality formulation on which the problems of existence, uniqueness and
approximation are easier to discuss.  We prove in particular the convergence of
an approximation by piecewise linear finite elements.  Finally, we describe and
compare several iterative methods for solving the approximate problems and
particularly some new algorithms of augmented lagrangian type, which contain
as special case some well-known alternating direction methods.  Numerical
results are presented.
.break
.begin nofill
No. of pages:  76
Cost:  $ 3.85
%4-----------------------------------------------------------------------------------------------%1
%3AIM-317  TAU EPSILON CHI, A SYSTEM FOR TECHNICAL TEXT
%3Author:%1  Donald E. Knuth
.end
@%3Abstract:%1@This is the user manual for TEX, a new document compiler at SU-AI, 
intended to be an advance in computer typesetting. It is primarily of interest 
to the Stanford user community and to people contemplating the installation of
TEX at their computer center.
.break
.begin nofill
No. of pages:  200
Cost:  $ 7.30
%4-----------------------------------------------------------------------------------------------%1
%3STAN-CS-78-676  A METHOD FOR DETERMINING THE SIDE EFFECTS OF PROCEDURE CALLS
%3Author:%1  John Phineas Banning ↔(Thesis)
.end
@%3Abstract:%1@The presence of procedures and procedure calls in a programming
language can give rise to various kinds of side effects.  Calling a procedure
can cause unexpected references and modifications to variables (variable side
effects) and non-obvious transfers of control (exit side effects).  In addition
procedure calls and parameter passing mechanisms can cause several different
variable names to refer to the same location thus making them aliases.  This in
turn causes all of these variables to be accessed whenever one of the variables
is modified or referenced.  Determining the aliases of variables and the exit
and variable side effects of procedure calls is important for a number of
purposes including the generation of optimized code for high level languages.

@This paper presents a method of determining exit and variable side effects and
gives an algorithm for determining the aliases of variables.  The principal
advantage over previous methods is that only one pass over a program is used to
gather the information needed to compute certain variable side effects precisely,
even in the presence of recursion and reference parameters.  In addition, these
methods can be extended to cover programs with a number of features including
procedure and label parameters.

@An abstract model of block-structured programs is developed and used to prove
that the methods given yield approximations which are safe for use in program
optimization and, for certain side effects, are at least as precise as those
given by any previous method.

@The implementation of these methods is discussed in general and a particular
implementation for the programming language PASCAL is described.  Finally, the
results of an empirical study of side effects and aliases in a collection of
PASCAL programs are presented.
.break
.begin nofill
No. of pages:  283
Available in microfiche only.
%4-----------------------------------------------------------------------------------------------%1
%3STAN-CS-78-677:  COMPREHENSIVE EXAMINATIONS IN COMPUTER SCIENCE, 1972-1978
%3Editor:%1  Frank M. Liang
.END
@%3Abstract:%1@Since Spring 1972, the Stanford Computer Science Department has
periodically given a "comprehensive examination" as one of the qualifying
exams for graduate students.  Such exams generally have consisted of a
six-hour written test followed by a several-day programming problem.
Their intent is to make it possible to assess whether a student is
sufficiently prepared in all the important aspects of computer science.
This report presents the examination questions from thirteen comprehensive
examinations, along with their solutions.
.break
.begin nofill
No. of pages:  238
Cost:  $ 8.40
%4-----------------------------------------------------------------------------------------------%1
%3AIM-314  REASONING ABOUT RECURSIVELY DEFINED DATA STRUCTURES
%3Author:%1  Derek C. Oppen
.END
@%3Abstract:%1@A decision algorithm is given for the quantifier-free theory of
recursively defined data structures which, for a conjunction of length %2n%1,
decides its satisfiability in time linear in %2n%1.  The first-order theory of
recursively defined data structures, in particular the first-order theory
of LISP list structure (the theory of CONS, CAR and CDR), is shown
to be decidable but not elementary recursive.
.break
.begin nofill
No. of pages:  15
Cost:  $ 2.15
%4-----------------------------------------------------------------------------------------------%1
%3STAN-CS-78-679   STEPLENGTH ALGORITHMS FOR MINIMIZING A CLASS OF NONDIFFERENTIABLE
				FUNCTIONS
%3Authors:%1  Walter Murray and Michael L. Overton
.END
.break
@%3Abstract:%1@Four steplength algorithms are presented for minimizing a class of
nondifferentiable functions which includes functions arising from %2l%1↓1 and
%2l%1∪[%4∞%1] approximation problems and penalty functions arising from constrained
optimization problems.  Two algorithms are given for the case when derivatives
are available whenever they exist and two for the case when they are not
available.  We take the view that although a simple steplength algorithm may
be all that is required to meet convergence criteria for the overall algorithm,
from the point of view of efficiency it is important that the step achieve as
large a reduction in the function value as possible, given a certain limit on
the effort to be expended.  The algorithms include the facility for varying this
limit, producing anything from an algorithm requiring a single function evaluation
to one doing an exact linear search.  They are based on univariate minimization
algorithms which we present first.  These are normally at least quadratically
convergent when derivatives are used and superlinearly convergent otherwise,
regardless of whether or not the function is differentiable at the minimum.
.break
.begin nofill
No. of pages:  57
Cost:  $ 3.30
%4-----------------------------------------------------------------------------------------------%1
%3STAN-CS-78-680   BIBLIOGRAPHY OF STANFORD COMPUTER SCIENCE REPORTS, 1963-1978
%3Editor:%1  Connie J. Stanley
.END
.break
@%3Abstract:%1@This report lists, in chronological order, all reports published
by the Stanford Computer Science Department since 1963.  Each report
is identified by Computer Science number, author's name, title, National
Technical Information Service (NTIS) retrieval number, date, and
number of pages.  Complete listings of
Artificial Intelligence Memos and Heuristic Programming Reports are given 
in the Appendix.

@Also, for the first time, each report has been marked as to its availability
for ordering and the cost if applicable.
.break
.begin nofill
No. of pages:  95
Available in hardcopy only, free of charge
%4-----------------------------------------------------------------------------------------------%1
.<<SLAC>>

%4-----------------------------------------------------------------------------------------------%1
%3SLAC PUB-2006   A NESTED PARTITIONING PROCEDURE FOR NUMERICAL MULTIPLE INTEGRATION
				AND ADAPTIVE IMPORTANCE SAMPLING
%3Author:%1  Jerome H. Friedman
.END
.break
@%3Abstract:%1@An algorithm for adaptively partitioning a multidimensional coordinate
space, based on a scalar function of the coordinates, is presented.  The method
is based on multiparameter optimization.  The goal is to adjust the size, shape
and number of resulting hyperrectangular regions so that the variation of function
values within each is relatively small.  These regions can then be used as a basis
for a stratified sampling estimate of the definite integral of the function, or
to efficiently sample points with the function as their probability density.

Available by writing directly to:  Harriet Canfield, Bin 88, Stanford Linear
Accelerator Center, P.O. Box 4349, Stanford, California 94305  U.S.A.
.begin nofill
%4-----------------------------------------------------------------------------------------------%1
%3SLAC PUB-2189   A SURVEY OF ALGORITHMS AND DATA STRUCTURES FOR RANGE SEARCHING
%3Authors:%1  Jon Louis Bentley and Jerome H. Friedman
.END
.break
@%3Abstract:%1@An important problem in database systems is answering queries
quickly.  This paper surveys a number of algorithms for efficiently answering
range queries.  First a set of "logical structures" is described and then their
implementation in primary and secondary memories is discussed.  The algorithms
included are of both "practical" and "theoretical" interest.  Although some new
results are presented, the primary purpose of this paper is to collect together
the known results on range searching and to present them in a common terminology.

Available by writing directly to:  Harriet Canfield, Bin 88, Stanford Linear
Accelerator Center, P.O. Box 4349, Stanford, California 94305  U.S.A.
.begin nofill
%4-----------------------------------------------------------------------------------------------%1
.end