perm filename FIFTEE.MSS[BIB,CSR]2 blob sn#649940 filedate 1982-03-25 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.