perm filename SIXTEE.MSS[BIB,CSR] blob
sn#649945 filedate 1982-03-26 generic text, type T, neo UTF8
@make(PublicationOrderForm,Number 16,AnnouncementDate "March 1982")
@begin(center)
List Number 16
@end(center)
@Entry(Code "STAN-CS-80-819",
Title "Computational Uses of the Manipulation of Formal Proofs",
Author "Chris Goad",
Price "$5.90",
Note "130 pages",
Date "August 1980")
@b(REPRINT)
A proof that for each x there exists a y with R(x,y) can serve as a
description of an algorithm which satisfies the specification given by R.
A variety of techniques from proof theory may be used to execute such a
proof - that is, to take the proof and a value for x, and compute a value
for y such that R(x,y) holds. Proofs differ from ordinary programs in
that they formalize information about algorithms beyond what is needed for
the simple execution of the algorithm. This thesis concerns (1) the uses
of this additional information in the automatic transformation of
algorithms, and in particular, in the adaptation of algorithms to special
situations, and (2) efficient methods for executing and transforming
proofs. A system for manipulating proofs has been implemented. Results
@Entry(Code "STAN-CS-81-837",
Title "Research on Expert Systems",
Author "Bruce G. Buchanan",
Price "$3.15",
Note "37 pages",
Date "February 1981")
@b(REPRINT)
To some extent, all AI programs exhibit some expertise at problem solving.
Expert Systems constitute a subclass of AI reasoning programs which are
distinguished by criteria of usefulness and understandability as well as
performance.
In this paper these criteria are discussed, the state of the art of
so-alled "Level-1" Expert Systems is assessed, and the research topics
necessary for moving to Level-2 systems are reviewed.
@Entry(Code "STAN-CS-82-897",
Title "Automatic Construction of Special Purpose Programs",
Author "Chris Goad",
Price "$2.45", FREE,
Note "15 pages",
Date "January 1982")
According to the usual formulation of the automatic programming task, one
starts with a specification of a programming problem, and seeks to
automatically construct a program satisfying that specification. This
paper concerns a different style of automatic programming. Rather than
defining the class of programming problems to be dealt with by the
language in which those problems are formulated, we instead consider
classes of problems defined in ordinary mathematical terms. Also, our
aims are different from the traditional aims of automatic programming in
that we are interested primarily in increasing the efficiency of
computations, rather than in transfering the burden of programming from
human to computer. Let R(p,x,y) be a ternary predicate. Suppose that in
the course of some large computation we are obliged to repeatedly compute
values of y with R(p,x,y) from given values of p and x. Suppose further
that in the sequence of p's and x's to be treated, p changes slowly and x
rapidly. Then we seek to automatically synthesize a fast special purpose
program A for each p; A is expected to compute a y with R(p,x,y) when
given x as input. We present one example of special purpose automatic
programming in detail, namely, a method for synthesizing special purpose
programs for eliminating the hidden surfaces from displays of three
dimensional scenes. (Hidden surface elimination is one of the central
problems in three dimensional computer graphics). In a test of the
method, a synthetic program specialized to treating a particular scene -
but from an arbitrary point of view - proved to be an order of magnitude
faster than the best available general purpose algorithm.
@Entry(Code "STAN-CS-81-898",
Title "Separability as a Physical Database Design Methodology",
Author "Whang, Wiederhold, Sagalowicz",
Price "$3.85", FREE,
Note "62 pages",
Date "October 1981")
A theoretical approach to the optimal design of a large multifile
physical databases is presented. The design algorithm is based on
the theory that, given a set of join methods that satisfy a certain
property called "separability," the problem of optimal assignment of
access structures to the whole database can be reduced to the
subproblem of optimizing individual relations independently of one another.
Coupling factors are defined to represent all the interactions among
the relations. This approach not only reduces the complexity of the
problem significantly, but also provides a better understanding of
underlying mechanisms.
A closed noniterative formula is introduced for estimating the number
of block accesses in a database organization, and the error analyzed. This
formula, an approximation of Yao's exact formula, has a maximum error of
3.7%, and significantly reduces the computation time by eliminating the
iterative loop. It also achieves a much higher accuracy than an
approximation proposed by Cardenas.
@Entry(Code "STAN-CS-82-900",
Title "Discovery and Representation of Causal Relationships from a Large
Time-Oriented Clinical Database: The RX Project",
Author "Robert L. Blum",
Price "$9.90", FREE,
Note "264 pages",
Date "January 1982")
The objectives of the RX Project are 1) to increase the validity of medical
knowledge derived from large time-oriented databases containing routine,
non-randomized clinical data, 2) to provide knowledgable assistance to a
research investigator in studying medical hypotheses on large
databases, 3) to fully automate the process of hypothesis generation and
exploratory confirmation.
RX is a computer program that examines a time-oriented clinical database and
produces a set of (possibly) causal relationships. The algorithm exploits
three properties of causal relationships: time precedence, correlation,
and nonspuriousness. First, a Discovery Module uses lagged,
nonparametric correlations to generate an ordered list of tentative
relationships. Second, a Study Module uses a knowledge base (KB) of medicine
and statistics to try to establish nonspuriousness by controlling for
known confounders.
@begin(center)
@b(ERRATA)
@end(center)
STAN-CS-81-873 Virtual Memory Management, by Richard Carr is now
available in microfiche only.
STAN-CS-81-889 AL Users Manual, by Goldman and Mujtaba is now also
available in microfiche.