@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.