perm filename NOV.ABS[BIB,CSR] blob sn#380967 filedate 1978-09-18 generic text, type C, neo UTF8

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: 100 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