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