perm filename ABS3[BIB,CSR] blob
sn#422928 filedate 1979-03-07 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00015 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 .DEVICE XGP
C00003 00003 .once center
C00005 00004 .begin nofill <<CS-710>>
C00008 00005 .begin nofill <<CS-711>>
C00012 00006 .begin nofill <<CS-712>>
C00013 00007 .begin nofill <<CS-713>>
C00015 00008 .begin nofill <<AIM-322>>
C00018 00009 .begin nofill <<CS-717>>
C00020 00010 .begin nofill <<AIM-323>>
C00021 00011 .begin nofill <<CS-719>>
C00023 00012 .begin nofill <<CS-720>>
C00024 00013 .begin nofill <<CS-721>>
C00026 00014 .begin nofill <<CS-722>>
C00029 00015 .begin nofill <<CS-723>>
C00032 ENDMK
C⊗;
.DEVICE XGP;
.
.turn on "↔" for "→"
.turn on "%,π,α,#,&,∂,↑,↓,[,]"
.turn on "∩" for "↑"
.turn on "∪" for "↓"
.
.font 1 "nonm";
.font 2 "baxm30";
.font 3 "math30";
.font 4 "fix25";
.font 5 "grkl30";
.
.sides←1;
.require "twocol.pub[sub,sys]" source file;
.
.SELECT 1
.at "@" ⊂"####"⊃
.at "|cd" ⊂"%3α*%*"⊃
.at "≤" ⊂"%4α≤%*"⊃
.
.at "!!" txt ";" ⊂
.("txt"[1]&"∩["&"txt"[2]&"]&∪[ "&"txt"[3]&"]");
. ⊃
.
.PLACE TEXT;
.
.next page
.once center
%1MOST RECENT CS REPORTS - 1979
No. 3↔(month)
@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
June 29, 1979. 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
--↔--
--↔--
.end
.begin nofill <<CS-710>>
STAN-CS-79-710
@NUMERICAL COMPUTATION OF THE
SCHWARZ-CHRISTOFFEL TRANSFORMATION
Author: Lloyd Trefethen
42 pages↔Cost: $2.90
.end
@ABSTRACT: A program is described which computes Schwarz-Christoffel
transformations that map the unit disk conformally onto the interior of a
bounded or unbounded polygon in the complex plane. The inverse map is also
computed. The computational problem is approached by setting up a nonlinear
system whose unknowns are essentially the unknown "accessory parameters" z↓k,
and solving this system with a standard subroutine.
@New features of this work include the evaluation of integrals within the
disk rather than along the boundary, making possible the treatment of unbounded
polygons; the use of a compound form of Gauss-Jacobi quadrature to evaluate the
Schwarz-Christoffel integral, making possible high accuracy at reasonable cost;
and the elimination of constraints in the nonlinear system by a simple change
of variables.
@Application of the Schwarz-Christoffel transformation may lead to practical
methods for solving the Laplace and Poisson equations accurately in two-cimensional
problems with irregular or unbounded (but not curved or multiply connected)
geometrices. Computational examples are presented. The time required to solve
the mapping problem is roughly proportional to N↑3, where N is the number of
vertices of the polygon. A typical set of computations to 8-place accuracy
with N %3≤%1 10 takes 1-10 seconds on an IBM 370/168.
.skip
.begin nofill <<CS-711>>
STAN-CS-78-711
@VERSION SPACES: AN APPROACH TO
CONCEPT LEARNING
Author: Tom Michael Mitchell↔(Thesis)
216 pages↔Microfiche only.
.end
@ABSTRACT: A method is presented for learning general descriptions of concepts
from a sequence of positive and negative training instances. This method involves
examining a predetermined space or language of possible concept descriptions,
finding those which are consistent with the observed training instances. Rather
than use heuristic search techniques to examine this concept description space,
the subspace (version space) of all plausible concept descriptions is represented
and updated with each training instance. This version space approach determines
all concept descriptions consistent with the training instances, without backtracking
to reexamine past training instances or previously rejected concept descriptions.
@The computed version space summarizes the information within the training instances
concerning the identity of the concept to be learned. Version spaces are therefore
useful for making reliable classifications based upon partially learned concepts,
and for proposing informative new training instances to direct further learning.
The uses of version spaces for detecting inconsistency in the training instances,
and for learning in the presence of inconsistency are also described.
@Proofs are given for the correctness of the method for representing version
spaces, and of the associated concept learning algorithm, for any countably
infinite concept description language. Empirical results obtained from computer
implementations in two domains are presented. The version space approach has
been implemented as one component of the Meta-DENDRAL program for learning
production rules in the domain of chemical spectroscopy. Its implementation in
this program is described in detail.
.skip
.begin nofill <<CS-712>>
STAN-CS-79-712
@THE ERRATA OF COMPUTER
PROGRAMMING
Author: Donald E. Knuth
58 pages↔Cost: $3.35
.end
@ABSTRACT: This report lists all corrections and changes of Volumes 1 and 3 of
%2The Art of Computer Programming%1, as of January 5, 1979. This updates the
previous list in report CS-551, May 1976. The second edition of Volume 2 has
been delayed two years due to the fact that it was completely revised and put
into the TEX typesetting language; since publication of this new edition is not
far off, no changes to Volume 2 are listed here.
.skip
.begin nofill <<CS-713>>
STAN-CS-79-713
@A HESSENBERG-SCHUR METHOD FOR THE
PROBLEM AX + XB = C
Authors: Gene Golub, Stephen Nash &
Charles Van Loan
50 pages↔Microfiche only.
.end
@ABSTRACT: One of the most effective methods for solving the matrix equation
AX + XB = C is the Bartels-Stewart algorithm. Key to this technique is the
orthogonal reduction of A and B to triangular form using the QR algorithm for
eigenvalues. A new method is proposed which differes from the Bartels-Stewart
algorithm in that A is only reduced to Hessenberg form. The resulting algorithm
is between 30 and 70 percent faster depending upon the dimensions of the
matrices A and B. The stability of the new method is demonstrated through a
roundoff error analysis and supported by numerical tests. Finally, it is
shown how the techniques described can be applied and generalized to other
matrix equation problems.
.skip
.begin nofill <<AIM-322>>
AIM-322
@A FRAMEWORK FOR CONTROL IN
PRODUCTION SYSTEMS
Author: Michael Georgeff
35 pages↔Cost: $2.70
.end
@Abstract: A formal model for representing control in production systems is defined. The
formalism allows control to be directly specified independently of the conflict
resolution scheme, and thus allows the issues of control and nondeterminism to
be treated separately. Unlike previous approaches, it allows control to be
examined within a uniform and consistent framework.
@It is shown that the formalism provides a basis for implementing control
constructs which, unlike existing schemes, retain all the properties desired
of a knowledge based system --- modularity, flexibility, extensibility and
explanatory capacity. Most importantly, it is shown that these properties are not
a function of the lack of control constrains, but of the type of information
allowed to establish these constraints.
@Within the formalism it is also possible to provide a meaningful notion of
the power of control constructs. This enables the types of control required
in production systems to be examined and the capacity of various schemes to
meet these requirements to be determined.
@Schemes for improving system efficiency and resolving nondeterminism are
examined, and devices for representing such meta-level knowledge are described.
In particular, the objectification of control information is shown to provide a
better paradigm for problem solving and for talking about problem solving.
It is also shown that the notion of control provides a basis for a theory of
transformation of production systems, and that this provides a uniform and
consistent approach to problems involving subgoal protection.
.skip
.begin nofill <<CS-717>>
STAN-CS-79-717
@
Authors:
pages↔Cost: $
.end
@Abstract:
.skip
.begin nofill <<AIM-323>>
AIM-323
@AL USERS' MANUAL
Authors: Shahid Mujtaba & Ron Goldman
136 pages↔Cost: $5.55
.end
@Abstract: This document describes the current state of the AL system now
in operation at the Stanford Artificial Intelligence Laboratory, and
teaches the reader how to use it. The system consists of AL, a high-level
programming language for manipulator control useful in industrial assembly
research; POINTY, an interactive system for specifying representation of
parts; and ALAID, an interactive debugger for AL.
.skip
.begin nofill <<CS-719>>
STAN-CS-79-719
@EXTRAPOLATION OF ASYMPTOTIC
EXPANSIONS BY A MODIFIED AITKEN
%5d%1↑2-FORMULA
Authors: Petter Bj%3O%1rstad,
Germund Dahlquist & Eric Grosse
54 pages↔Microfiche only.
.end
@Abstract: A modified Aitken formula permits iterted extrapolations to
efficiently estimate %5d%4↓∞%1 from %5d%2↓n%1 when an asymptotic expansion
.skip
.once center
%5d%2↓n%2 = %5d%4↓∞%2 + n∩[-k](c↓0 + c↓1n∩[-1] + c↓2n∩[-2] + ...)%1
holds for some (unknown) coefficients %2c↓j%1. We study the truncation and
irregular error and compare the method with other forms of extrapolation.
.skip
.begin nofill <<CS-720>>
STAN-CS-79-720
@ON GRID OPTIMIZATION FOR BOUNDARY
VALUE PROBLEMS
Author: R. Glowinski
22 pages↔Microfiche only.
.end
@Abstract: We discuss in this report the numerical procedures which can be
used to obtain the optimal grid when solving by a finite element method a model
boundary value problem of elliptic type modelling the potential flow of an
incompressible inviscid fluid. Results of numerical experiments are presented.
.skip
.begin nofill <<CS-721>>
STAN-CS-79-721
@ON FAULT-TOLERANT NETWORKS FOR
SORTING
Authors: Andrew C. Yao & F. Frances Yao
20 pages↔Cost: $2.30
.end
@Abstract: The study of constructing reliable systems from unreliable components
goes back to the work of von Neumann, and of Moore and Shannon. The present paper
studies the use of redundancy to enhance reliability for sorting and related
networks build from unreliable comparators. Two models of fault-tolerant networks
are discussed. The first model patterns after the concept of error-dorrecting
codes in information theory, and the other follows the stochastic criterion
used byvon Neumann and Moore-Shannon. It is shown, for example, that an additional
k(2n-3) comparators are sufficient to render a sorting network reliable, provided
that no more than k of its comparators may be faulty.
.skip
.begin nofill <<CS-722>>
STAN-CS-79-722
@A STRUCTURAL MODEL FOR DATABASE
SYSTEMS
Authors: Gio Wiederhold & Ramez El-Masri
57 pages↔Cost: $3.30
.end
@Abstract: A structural database model is presented. The model uses relations
as building blocks of the data model, and classifies each relation into a
structural type. This model can be considered as an extension of Codd's
relational model [Codd70]. Both entities and associations among entities
are represented as relations, and three further types of relations are
introduced. A limited set of possible structural connections between the
different types of relations is specified. The model, which was introduced
informally by Wiederhold [Wiederhold77], implicityly defines a basic, limited
set of integrity constraints. These integrity constraints identify existence
dependencies among tuples from different relations. Rules for the
maintenance of the structural integrity of the model under insertion and
deletion of tuples are given.
@A methodology for combining multiple, overlapping data models, or user
views, is associated with the model. The database model, or conceptual
schema, which represents the integrated database, may thus be derived from
the individual data models of the users. We believe that the structural
model could be used for representation of the data relationships within the
conceptual schema of the ANSI/SPARC DBMS model since it can support database
submodels (or external schema), and maintain the integrity of the submodels
with respect to the integrity constraints expressable in the structural
model.
@We then briefly discuss the use of the structural model in database design
and implementation. The structural model provides a tool to deal effectively
with the complexity of large, real-world databases.
.skip
.begin nofill <<CS-723>>
STAN-CS-79-723
@KNOWLEDGE ENGINEERING FOR MEDICAL
DECISION MAKING: A REVIEW OF
COMPUTER-BASED CLINICAL DECISION AIDS
Authors: Edward Shortliffe,
Bruce Buchanan &
& Edward Feigenbaum
52 pages↔Cost: $3.20
.end
@Abstract: Computer-based models of medical decision making account for a
large proportion of clinical computing efforts. This article reviews representative
examples from each of several major medical computing paradigms. These include
(1) clinical algorithms, (2) clinical databanks that include analytic functions,
(3) mathematical models of physical processes, (4) pattern recognition, (5)
Bayesian statistics, (6) decision analysis, and (7) symbolic reasoning or artificial
intelligence. Because the techniques used in the various systems cannot be
examined exhaustively, the case studies in each category are used as a basis for
studying general strengths and limitations. It is noted that no one method is
best for all applications. However, emphasis is given to thelimitations of
early work that have made artificial intelligence techniques and knowledge engineering
research particularly attractive. We stress that considerable basic research
in medical computing remains to bedone and that powerful new approaches may lie
in the melding of two or more established techniques.
.SKIP