perm filename SEVEN[BIB,CSR] blob sn#489637 filedate 1979-12-18 generic text, type C, neo UTF8

COMMENT ⊗ VALID 00010 PAGES C REC PAGE DESCRIPTION C00001 00001 C00002 00002 .require "setup.abs[bib,csr]" source file C00003 00003 .begin center C00005 00004 AIM-333↔(STAN-CS-79-772) C00013 00005 STAN-CS-79-773 C00015 00006 STAN-CS-79-774 C00018 00007 STAN-CS-79-775 C00020 00008 STAN-CS-79-776 C00021 00009 STAN-CS-79-777 C00022 00010 .END C00026 ENDMK C⊗; .require "setup.abs[bib,csr]" source file; .font A "math40"; .font B "math50"; .at "⊗" ⊂"%5αQ%*"⊃ .begin center S T A N F O R D U N I V E R S I T Y MOST RECENT COMPUTER SCIENCE REPORTS - 1979 .end No. 7↔December @Listed here are abstracts of the most recent reports published by the Department of Computer Science at 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 February 28, 1980. In many cases we can print only a limited number of copies, and requests will be filled on a first come, first served 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 the 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. .skip .BEGIN NOFILL -↔- .SKIP AIM-333↔(STAN-CS-79-772) @BUILDING PROGRAM MODELS INCREMENTALLY FROM INFORMAL DESCRIPTIONS Author: Brian P. McCune↔(Thesis) 146 pages↔Cost: $5.70 .end @Program acquisition is the transformation of a program specification into an executable, but not necessarily efficient, program that meets the given specification. This thesis presents a solution to one aspect of the program acquisition problem: the incremental construction of program models from informal descriptions. The key to the solution is a framework for incremental program acquisition that includes (1) a formal language for expressing program fragments that contain informalities, (2) a control structure for the incremental recognition and assimilation of such fragments, and (3) a knowledge base of rules for acquiring programs specified with informalities. @The thesis describes a LISP based computer system called the %2Program Model Builder%1 (abbreviated "PMB"), which receives informal program fragments incrementally and assembles them into a very high level program model that is complete, semantically consistent, unambiguous, and executable. The program specification comes in the form of partial program fragments that arrive in any order and may exhibit such informalities as inconsistencies and ambiguous references. Possible sources of fragments are a natural language parser or a parser for a surface form of the fragments. PMB produces a program model that is a complete and executable computer program. The %2program fragment language%1 used for specifications is a superset of the language in which program models are built. This %2program modelling language%1 is a very high level programming language for symbolic processing that deals with such information structures as sets and mappings. @PMB has expertise in the general area of simple symbolic computations, but PMB is designed to be independent of more specific programming domains and particular program specification techniques at the user level. However, the specifications given to PMB must still be algorithmic in nature. Because of the very high level nature of the program model produced, PMB also operates independently from implementation details such as the target computer and low level language. PMB has been tested both as a module of the PSI program synthesis system and independently. Models built as part of PSI have been acquired via natural language dialogs and execution traces and have been automatically coded into LISP by other PSI modules. PMB has successfully built a number of moderately complex programs for symbolic computation. @By design the user is allowed to have control of the specification process. Therefore PMB must handle program fragments interactively and incrementally. Interesting problems arise because these informal fragments may arrive in an arbitrary order, may convey an arbitrarily small amount of new information, and may be incomplete, semantically inconsistent, and ambiguous. To allow the current point of focus to change, a %2program reference language%1 has been designed for expressing patterns that specify what part of the model a fragment refers to. Various combinations of syntactic and semantic reference patterns in the model may be specified. @The recognition paradigm used by PMB is a form of subgoaling that allows the parts of the program to be specified in an order chosen by the user, rather than dictated by the system. Knowledge is represented as a set of data driven antecedent rules of two types, %2response rules%1 and %2demons%1, which are triggered respectively by either the input of new fragments or changes in the partial program model. In processing a fragment, a response rule may update the partial program model and create new subgoals with associated response rules. To process subgoals that are completely internal to PMB, demon rules are created that delay execution until their prerequisite information in the program model has been filled in by response rules or perhaps other demons. @PMB has a knowledge base of rules for handling modelling language constructs, processing informalities in fragments, monitoring the consistency of the model, and transforming the program to canonical form. Response rules and simple demons are procedural. %2Compound demons%1 have more complex antecedents that test more than one object in the program model. Compound demons use declarative antecedent patterns that are expanded automatically into procedural form. .skip .begin nofill -↔- .skip STAN-CS-79-773 @UPDATING FORMULAE AND A PAIRWISE ALGORITHM FOR COMPUTING SAMPLE VARIANCES Authors: Tony F. Chan, Gene H. Golub and Randal J. LeVeque 19 pages↔Available in microfiche only. .end @A general formula is presented for computing the sample variance for a sample of size %2m + n%1 given the means of variances for two subsamples of sizes %2m%1 and %2n%1. This formula is used in the construction of a pairwise algorithm for computing the variance. Other applications are discussed as well, including the use of updating formulae in a parallel computing environment. We present numerical results and rounding error analyses for several numerical schemes. .skip .begin nofill -↔- .skip STAN-CS-79-774 @LARGE SCALE GEODETIC LEAST SQUARES ADJUSTMENT BY DISSECTION AND @ORTHOGONAL DECOMPOSITION Authors: Gene H. Golub and Robert J. Plemmons 33 pages↔Available in microfiche only. .end @Very large scale matrix problems currently arise in the context of accurately computing the coordinates of points on the surface of the earth. Here geodesists adjust the approximate values of these coordinates by computing least squares solutions to large sparse systems of equations which result from relating the coordinates to certain observations such as distances or angles between points. The purpose of this paper is to suggest an alternative to the formation and solution of the normal equations for these least squares adjustment problems. In particular, it is shown how a block-orthogonal decomposition method can be used in conjunction with a nested dissection scheme to produce an algorithm for solving such problems which combines efficient data management with numerical stability. As an indication of the magnitude that these least squares adjustment problems ca sometimes atain, the forthcoming readjustment of the North American Datum in 1983 by the National Deodetic Survey is discussed. Here it becomes necessary to linearize and solve an overdetermined system of approximately 6,000,000 equations in 400,000 unknowns - a truly large-scale matrix problem. .skip .begin nofill -↔- .skip STAN-CS-79-775 @THE ANALYSIS OF SEQUENTIAL EXPERIMENTS WITH FEEDBACK TO SUBJECTS Authors: Persi Diaconis and Ronald Grahm 48 pages↔cost: $3.05 .end @A problem arising in taste testing, medical, and parapsychology experiments can be modeled as follows. A deck of %2n%1 cards contains %2c↓i%1 cards labeled %2i, 1#≤#i#≤#r%1. A subject guesses at the cards sequentially. After each guess the subject is told the card just guessed (or at least if the guess was correct or not). We determine the optimal and worst case strategies for subjects and the distribution of the number of correct guesses under these strategies. We show how to use skill scoring to evaluate such experiments in a way which (asymptotically) does not depend on the subject's strategy. .skip .begin nofill -↔- .skip STAN-CS-79-776 @KHACHIYAN'S LINEAR PROGRAMMING ALGORITHM Authors: Bengt Aspvall and Richard E. Stone (This paper supersedes STAN-CS-79-750 by Lovas and Gacs.) 13 pages↔Cost: $2.10 .end @L.G. Khachiyan's polynomial time algorithm for determining whether a system of linear inequalities is satisfiable is presented together with a proof of its validity. The algorithm can be used to solve linear programs in polynomial time. .skip .begin nofill -↔- .skip STAN-CS-79-777 @ON CONSTANT WEIGHT CODES AND HARMONIOUS GRAPHS Authors: R.L. Graham and N.J.A. Sloane 17 pages .end @Very recently a new method has been developed for finding lower bounds on the maximum number of codewords possible in a code of minimum distance %2d%1 and length %2n%1. This method has led in turn to a number of interesting questions in graph theory and additive number theory. In this brief survey we summarise some of these developments .skip .begin nofill -↔- .skip .END .select 4 <<order form>> REPORT ORDER FORM #6↔Order Deadline: December 28, 1979 To order reports, or to change your mailing address, complete and return the ENTIRE form (including the mailing label) to: Publications Coordinator, Department of Computer Science, Stanford University, Stanford, California 94305, U.S.A. .skip .begin nofill Hardcopy Microfiche 1._____ AIM-333 $5.70 2._____ AIM-333 FREE 4._____ STAN-CS-79-773 FREE 6._____ STAN-CS-79-774 FREE 7._____ STAN-CS-79-775 $3.05 8._____ STAN-CS-79-775 FREE 9._____ STAN-CS-79-776 $2.10 A._____ STAN-CS-79-776 FREE B._____ STAN-CS-79- $ C._____ STAN-CS-79- FREE D._____ STAN-CS-79- $ E._____ STAN-CS-79- FREE F._____ STAN-CS-79- $ G._____ STAN-CS-79- FREE H._____ STAN-CS-79- $ I._____ STAN-CS-79- FREE J._____ STAN-CS-79- $ K._____ STAN-CS-79- FREE L._____ STAN-CS-79- $ M._____ STAN-CS-79- FREE N._____ STAN-CS-79- $ O._____ STAN-CS-79- FREE P._____ STAN-CS-79- $ Q._____ STAN-CS-79- FREE R._____ STAN-CS-79- $ S._____ STAN-CS-79- FREE T._____ STAN-CS-79- $ U._____ STAN-CS-79- FREE V._____ STAN-CS-79- $ W._____ STAN-CS-79- FREE X._____ STAN-CS-79- $ Y._____ STAN-CS-79- FREE .end %4Please do NOT send money with your order. Wait until you receive an invoice, which is enclosed with the reports when they're sent. .skip .begin indent 0,8,0 _____ Check here to change your address. Print the changes above the mailing label, and return this ENTIRE form (including the mailing label) to: Publications Coordinator, Department of Computer Science, Stanford University. .end .skip 10 .begin nofill %4Stanford University Department of Computer Science Stanford, California 94305 .end