1990 TECHNICAL REPORTS
         University of California at Santa Cruz 
Baskin Center for Computer Engineering and Information Sciences 
          Santa Cruz, California  95064   U.S.A.

(To obtain these tech reports electronically or as paper copies,
see the directions at the beginning of the file ABSTRACTS.1991.)

UCSC-CRL-90-01 (not available electronically)
ON THE EXPRESSIVE POWER OF DATALOG:  TOOLS AND A CASE STUDY
Phokion G. Kolaitis
January 1990, 17 pages (paper copy $5.00)
Abstract:  We study here the language Datalog(not =), which is the query
language obtained from Datalog by allowing equalities and inequalities 
in the bodies of the rules.  We view Datalog(not =) as a fragment of an 
infinitary logic L^omega and show that L^omega  can be characterized 
in terms of certain two-person pebble games.  This characterization 
provides us with tools for investigating the expressive power of 
Datalog(not =).  As a case study, we classify the expressibility of 
*fixed subgraph homeomorphism* queries on directed graphs.  Fortune 
et al. classified the computational complexity of these queries by 
establishing two dichotomies, which are proper only if P not = NP.  
Without using any complexity-theoretic assumptions, we show here that 
the two dichotomies are indeed proper in terms of expressibility in 
Datalog(not =). 
**********
UCSC-CRL-90-02  (not available electronically) 
HIGH SPEED DISK I/O FOR PARALLEL COMPUTERS  
Daniel Edelson and Darrell D. E. Long
January 1990, 12 pages (paper copy $5.00)
Abstract:  The purpose of this research has been to determine how
disk subsystems can support high speed I/O for large scale 
multiprocessors. A literature survey has identified many of the most 
important techniques for substantially improving disk performance.  
In addition we have designed (and analyzed through simulation) a 
software architecture that supports very high data rates. Our findings 
are summarized in this report.
**********
UCSC-CRL-90-04   (not available electronically)
CHARACTERIZING PAC-LEARNABILITY OF SEMILINEAR SETS  
AND COMMUTATIVE REGULAR LANGUAGES  
Naoki Abe
December 1989, 41 pages (paper copy $8.00)
Abstract:  We characterize learnability of the class of letter-counts
of regular languages (semilinear sets), commutative regular languages
and other related classes of subsets of N^m , with respect to the
distribution-free learning model of Valiant (PAC-learning model).
By utilizing the notion of reducibility among learning problems
due to Pitt and Warmuth called `Prediction Preserving Reducibility',
and a special case thereof, we show a number of positive as well
as partially negative results.  On the positive side, we show that
the class of semilinear sets of dimensions 1 and 2 is learnable when
the integers are encoded in unary.  We also show that the entire
class of commutative deterministic finite-state automata on an
arbitrary alphabet size is learnable.  On the neutral to negative
side, we show that, when the integers are encoded in binary, the
learning problem for semilinear sets as well as a class of subsets
of N^m  much simpler than semilinear sets is as hard as learning DNF,
 a central open problem in the field.  We also show that all
of our positive results are for concept representation classes
for which the problem of finding a minimum consistent representation
is NP-hard.
**********
UCSC-CRL-90-06   (not available electronically)
0-1 LAWS FOR INFINITARY LOGICS  
Phokion G. Kolaitis and Moshe Y. Vardi
March 1990, 16 pages (paper copy $5.00)
Abstract:  We investigate asymptotic probabilities of properties
expressible in the infinitary logic L^omega_{infinity omega} 
on finite structures. Sentences in this logic may have arbitrary
disjunctions and conjunctions, but they involve only a finite
number of distinct variables. We show that the 0-1 law holds
for L^omega_{infinity omega}, i.e., the asymptotic probability
of every sentence in this logic exists and is equal to either 0 or 1.
This result subsumes earlier work on asymptotic probabilities
for various fixpoint logics and reveals the boundary of
0-1 laws for infinitary logics.
**********
UCSC-CRL-90-07   (not available electronically)
PARALLELIZING THE FAST FOURIER TRANSFORM  
Don Fong
March 1990, 12 pages (paper copy $5.00)
Abstract:  The Fourier transform is an operator which maps functions 
from the temporal or spatial domain to the frequency domain.
The  *discrete* Fourier transform (DFT) is the digital analogue
of the Fourier transform; it maps the discrete representation of
a function to the frequency domain.  The *fast* Fourier transform 
(FFT) is a method---in actuality, any one of a number of methods---
for rapid calculation of the DFT. 
     This report describes an investigation into the parallelization 
properties of the FFT.  The first phase (1) of the investigation 
was a brief look at the mathematical basis of the FFT.  The second 
phase (2) consisted of coding a non-parallel test program using 
a particular FFT algorithm.  The third phase (3) consisted of
experiments with a particular parallelizing FORTRAN compiler to test 
its ability to parallelize, vectorize, optimize, and reorganize FFT 
code.  
**********
UCSC-CRL-90-08   (not available electronically)
PARALLEL ALGORITHMS FOR COMPUTER GRAPHICS  
Cindy Ferguson
March 1990, 18  pages (paper copy $5.00)
Abstract:  Over the last 10 years advances in hardware and software 
design have enabled us to obtain more and more realistic computer 
images.  As our capabilities continue to rise so do our expectations.  
These new demands require high quality imagery in an interactive, 
real-time environment.  One method of achieving this goal is to use 
parallel processing techniques to generate these images.  Parallel 
algorithms work well for some problems encountered in generating 
images such as hidden surface removal while for other problems, such 
as clipping parallel algorithms do not work so well.  Possible 
solutions and problems encountered in applying parallel algorithms 
will be presented.
**********
UCSC-CRL-90-09   (available electronically as ucsc-crl-90-09.ps.Z)
VOTING WITH REGENERABLE VOLATILE WITNESSES 
Darrell D. E. Long and Jehan-Franc,ois Pa^ris
April 1990, revised July 1990, 19 pages (paper copy $5.00)
Abstract:  Voting protocols ensure the consistency of replicated 
objects by requiring all read and write requests to collect an 
appropriate quorum of replicas.  We propose to replace some of these 
replicas by *volatile witnesses* that have no data and require no 
stable storage, and to regenerate them instead of waiting for recovery.
The small size of volatile witnesses allows them to be regenerated 
much easier than full replicas.  Regeneration attempts are much more 
likely to succeed since volatile witnesses can be stored on diskless 
nodes. 
     We show that under standard Markovian assumptions two
full replicas and one regenerable volatile witness managed by a 
two-tier dynamic voting protocol provide a higher data availability
than three full replicas managed by majority consensus voting or
optimistic dynamic voting provided site failures can be detected 
significantly faster than they can be repaired. 
Keywords: distributed file systems, replicated data, voting, witnesses.
**********
UCSC-CRL-90-10   (not available electronically)
TRAINING AN ANIMATED ARM TO REACH FOR OBJECTS IN SPACE USING 
NEURAL NETWORKS 
Jeanne Merrill Rich  (M.S. Thesis)
December 1989, 68 pages (paper copy $10.00)
Abstract:  In the past, large amounts of user effort have been 
required to create acceptable animations in commonly used motion
control systems for animation.  In order to reduce user effort,
research in computer animation has been directed towards automatic 
motion control systems.  A new method of automatic motion control
using neural networks (also known as connectionist models) is 
examined as one possible means of reducing user effort.  The main
objective of such a method is to train a neural network to control
the inbetween motion given only the start and goal positions.  If
using neural networks is an appropriate method for automatic motion
control, not only would it have applications in computer animation
but robotics as well. 
      In order to analyze the feasibility of using neural
networks for automatic motion control, the simple motion of an arm
reaching for an object in a two dimensional world was used.
Initially, a multi-layered feed-forward network was trained to
predict the position of an arm at the following time frame, given only
the position of the arm at the current time frame and its relative
position from the object.  After the network was trained using
the back-propagation learning algorithm, the performance of the
network was tested, producing an animated motion that was far from
acceptable, even though the network's training performance leveled 
off to a low mean error.  It was also discovered that a highly
acceptable animated motion could be produced when the network
continued to be trained during the testing phase.  Other network
configurations and data representations were also explored to lower
the mean error during training and to produce more promising arm
motions. 
      The results of this research indicate that many
of the simpler techniques that have been suggested in the neural
net literature simply don't work for automatic motion control.
However, more sophisticated techniques may show some promise, even
though the results of this research are inconclusive. 
**********
UCSC-CRL-90-11   (not available electronically)
DEBUGGING PARALLEL PROGRAMS BY TRACE ANALYSIS 
Jian-Zhong Wang  (M.S. Thesis)
March 1990, 79 pages (paper copy $11.00)
Abstract:  One of the fundamental problems encountered when debugging 
a parallel program is determining the race conditions in the program.
A race condition may exist when two or more tasks access shared data 
in an unspecified order and at least one of them is executing a write
operation.  This paper discusses this problem and presents a tool for
automatically detecting race conditions in parallel programs by 
analyzing program traces. 
     In a parallel system, events can occur concurrently.  
However, programmers are often forced to rely on misleading sequential 
traces for information about their program's behavior.  We view a 
program execution as a partial ordering of events, and define which
executions are consistent with a given trace.  Although it is 
generally not possible to determine which of the executions occurred, 
we define the notion of ``safe orderings'' which are guaranteed to 
occur in every execution that is consistent with the trace. 
     We present a series of algorithms which extract many of 
the ``safe orderings'' from a sequential trace with anonymous 
semaphore-style synchronization.  The initialization algorithm starts 
from a sequential trace and creates a partially ordered canonical 
execution.  The rewinding algorithm strips away the ordering 
relationships particular to the canonical execution, so that the 
resulting partial order is safe.  The expanding algorithm increases 
the amount of ordering information while maintaining a safe partial 
order.  An algorithm is also presented to detect critical regions, to
distinguish unordered sequential events from concurrent events. 
     We have focused on event style communication and 
counting semaphore models because they are one of the most frequently 
used parallel models, especially in various parallel Fortran versions.
The ideas and the algorithms should be applicable to other parallel
systems. 
     A trace analyzer has been implemented, and some 
experiments have been performed.  The current implementation is used 
to analyze traces generated by IBM Parallel Fortran.  The trace 
analyzer can report various data race conditions in parallel programs 
by finding unordered/concurrent events and variable access conflicts. 
Keywords: virtual time, program tracing, parallel processing, debugging.
**********
UCSC-CRL-90-12   (not available electronically)
ADAPTIVE-PREDICTIVE GAME-PLAYING PROGRAMS 
Robert Levinson, Brian Beach, Tal Dayan, Richard Snyder, and Kirack Sohn
April 1990, 15 pages (paper copy $5.00)
Abstract:  Adaptive-predictive search (APS) is a new method by which 
systems can improve their search performance through experience. 
It is believed that the development of such methods is critical
as currently a tremendous amount of computational results are 
potentially wasted by not integrating search and partial search 
results into the knowledge of a problem-solving system. In the 
adaptive-predictive search model pattern formation and associative 
recall are used to improve or replace search.  In this paper the 
theory, background and  motivations behind the model are presented and 
its application to two-player game-playing programs is discussed. In 
these programs, the system develops a knowledge base of patterns 
(boolean features) coupled with weights and using pattern-oriented 
evaluation performs only 1-ply search, yet competes respectably with 
programs that search more.  The learning mechanism is a hybridization 
of machine learning and artificial intelligence techniques that have 
been successful in other settings. Specific examples and performance 
results are taken from the domains of Hexapawn, Tic-Tac-Toe, Pente, 
Othello, and Chess.  [This report is much like 89-22, but focuses 
on 2-player games and gives new results.]
**********
UCSC-CRL-90-13   (not available electronically)
ANALYSIS OF REPLICATION CONTROL PROTOCOLS 
Darrell D. E. Long
April 1990, 6 pages (paper copy $5.00)
Abstract:  In recent years many replication control protocols have been
proposed, but too often these protocols are presented with insufficient
evidence to demonstrate superiority over existing protocols.  In this 
article, some simple analytical tools are presented that allow 
replication control protocols to be compared.  A *dynamic voting* 
protocol is used as an example, but these techniques can be 
successfully applied to many other protocols as well.
**********
UCSC-CRL-90-14   (not available electronically)
TOPOLOGICAL CONSIDERATIONS IN ISOSURFACE GENERATION 
Jane Wilhelms and Allen Van Gelder
April 1990, 26 pages (paper copy $6.00)
Abstract:  An emerging technique for rendition of isosurfaces in 
sampled data is to consider cells with sample points as corners and 
approximate the isosurface in each cell by one or more polygons whose 
vertices are obtained by interpolation of the sample data.  That is, 
each polygon vertex is a point on a cell edge, between two adjacent
sample points, where the function is estimated to equal the desired
threshold value.  The two sample points have values on opposite sides
of the threshold, and the interpolated point is called an 
*intersection point*. 
     When one cell face has an intersection point in each 
of its four edges, then the correct connection among intersection 
points becomes ambiguous.  An incorrect connection can lead to 
erroneous topology in the rendered surface, and possible 
discontinuities.  We show that disambiguation methods, to be at all 
accurate, need to consider sample values in the neighborhood outside 
the cell.  This paper studies the problems of disambiguation,  reports 
on some solutions, and presents some statistics on the occurrence of 
such ambiguities. 
     A natural way to incorporate neighborhood information 
is through the use of calculated gradients at cell corners.  These 
quantities are needed for other purposes, and they provide insight 
into the behavior of a function in well-understood ways.  We introduce 
two *gradient-consistency heuristics*  that use calculated 
gradients at the corners of ambiguous faces, together with the 
function values at those corners, to disambiguate at a reasonable 
computational cost.  These methods give the correct topology on 
several examples that caused problems for other methods we examined.
**********
UCSC-CRL-90-15   (available electronically as ucsc-crl-90-15.ps.Z)
A GENERALIZATION OF SAUER'S LEMMA 
David Haussler and Phil Long
April 1990, 21 pages (paper copy $6.00)
Abstract:  We generalize Sauer's lemma to multivalued functions.  In 
addition, we give an application of this result, bounding the uniform 
rate of convergence of empirical estimates of the expectations of a 
set of random variables to their true expectations. 
**********
UCSC-CRL-90-16   (available electronically as ucsc-crl-90-16.ps.Z)
PROBABLY APPROXIMATELY CORRECT LEARNING 
David Haussler
May 1990, 8 pages (paper copy $5.00)
Abstract:  This paper surveys some recent theoretical results on the
efficiency of machine learning algorithms.  The main tool described
is the notion of Probably Approximately Correct (PAC) learning,
introduced by Valiant.  We define this learning model and then look at 
some of the results obtained in it.  We then consider some criticisms 
of the PAC model and the extensions proposed to address these 
criticisms.  Finally, we look briefly at other models recently 
proposed in computational learning theory.
**********
UCSC-CRL-90-17   (not available electronically)
A STARTER TOOLKIT FOR MODELING WITH IMPLICIT SURFACES 
Jim Kleck
May 1990, 15 pages (paper copy $5.00)
Abstract:  Implicit Surfaces offer an immense amount of power in
modeling.  The set of all mathematical and procedural functions is
a fertile field which contains (or closely approximates) every shape
imaginable.  Despite this, implicit surfaces have not been
extensively used in modeling.  This is in part due to the difficulty
of shaping implicit surfaces.  This paper presents a starter set
of functions that can help in the shaping of implicit surfaces. 
**********
UCSC-CRL-90-18  (not available electronically)
CONFIGMAN  
Don Fong
May 1990, 15 pages (paper copy $5.00)
Abstract:  Configman is a set of programs designed to assist in 
the software development of distributed applications.  The assumed 
environment is a network of machines running UNIX, with rcp, rsh, and 
the usual collection of UNIX tools.  Configman follows the UNIX 
philosophy of providing tools rather than solutions.  The configman 
programs provide functions which can be combined with each other, and 
with other UNIX tools, to meet the needs of a wide range of situations.
There are many styles of development possible under UNIX, and
configman may not be useful with all of them.  As with many other
tools, the maximum benefit is obtained when certain conventions
are followed.  In particular, configman is designed to work well
with RCS and make. 
**********
UCSC-CRL-90-19  (available electronically as ucsc-crl-90-19.ps.Z
and, for a shorter version, as ucsc-crl-90-19-nocode.ps.Z)
DYNAMIC STORAGE RECLAMATION IN C++  
Daniel Ross Edelson  (M.S. Thesis)
June 1990, 146 pages (paper copy $15.00)
Abstract:  Dynamically allocated memory is a pervasive element of
modern programming practices, but efficient dynamic memory 
reclamation is difficult.  One class of algorithms that accomplish 
this is *copying garbage collection*.  These algorithms require one
pass to collect and compact objects in memory.  It is the preferred
form of garbage collection for systems with large virtual memories and 
large free-stores because the work of these algorithms is proportional
to the amount of living data rather than the total data allocated. 
      A copying collector organization appropriate for
object-oriented imperative programming languages is presented.  The
system is both encapsulated and efficient.  The efficiency of
reclaiming a data structure depends solely on the size of the data
structure, not the size of the program.  It remains within the
philosophy of its implementation language, C++, because code
fragments that do not use the collector are not affected in any way.
Any number of collectors can coexist concurrently in an application
on disjoint data structures, making it an appropriate component
of an object-oriented system. 
      This system adds an important feature to C++ that
increases productivity and makes the language more convenient.  It
makes dynamic memory management more efficient than manual
reclamation for an important class of problems.  It serves as a
platform for research into reclamation techniques, particularly
virtual memory issues, and it provides an appropriate organization 
for automatic dynamic memory reclamation in object-oriented imperative 
programming languages. 
**********
UCSC-CRL-90-20   (not available electronically)
MULTIVIEW:  AN INTEGRATED APPROACH TO VISUALIZATION OF PARALLEL PROGRAMS 
Cynthia Hope Ferguson  (M.S. Thesis)
March 1990, 75 pages (paper copy $11.00)
Abstract:  Multiview is an integrated tool for visualizing the
execution of a parallel program.  The design of Multiview was motivated
by the idea that the current tools used to visualize parallel programs
did not provide enough views for the user to get a complete
understanding of her program.  Multiview attempts to solve this problem
with an extensible object-oriented design.  A prototype system was
built and its implementation is described. 
**********
UCSC-CRL-90-21   (not available electronically)
AN IMPLEMENTATION OF THE KEY REACTION APPROACH  IN 
COMPUTER CHEMICAL SYNTHESIS 
Esther H. Lum  (M.S. Thesis)
March 1990, 55 pages (paper copy $9.00)
Abstract:  This thesis identifies one search strategy taken by
organic chemists, the key reaction approach, and describes its
simulation using the AI technique known as means-ends analysis.
Given a target molecule, Synit, the system implementing the key
reaction approach, chooses a starting material, determines what the
ideal reaction would be, and selects the key reaction that most closely
matches the ideal from a database of reactions.  The key reaction is 
used to create an intermediate reaction step;  this also creates
subproblems, which are solved recursively using the same method that
was used in solving the original problem.  The major contributions
of using the key reaction approach are that (1) Synit is not
restricted to a backwards search from the target alone, and (2)
The version of means-ends analysis that is used is an improvement over
its traditional implementation because difference tables are made
unnecessary.  Previous relevant work is also discussed and related
to the key reaction approach, and retrosynthetic methods are
compared to Synit.  Solutions by Synit are provided in the appendix.
**********
UCSC-CRL-90-22   (not available electronically)
A BEST-FIRST ERROR CORRECTION ALGORITHM 
Frank Arnoud Jas  (M.S. Thesis)
March 1990, 57 pages (paper copy $9.00)
Abstract:  An algorithm for repairing syntax errors is presented.  The
algorithm is a modified best-first search which searches for the
shortest repair.  The algorithm adds little time or space costs to the
parsing of correct input.  It performs as well as other published
techniques on a standard set of Pascal programs.  A survey of other
techniques shows a marked similarity between the first phase of each
algorithm.  This phase has been generalized into a full search in the
best-first approach.  A review of the set of programs reveals the
successes of other approaches may be primarily due to this first phase.
**********
UCSC-CRL-90-23   (not available electronically)
SOURCE-LEVEL DEBUGGING OF OPTIMIZED CODE:  DETECTING UNEXPECTED DATA VALUES 
Max Copperman  (M.S. Thesis)
May 1990, 162 pages (paper copy $15.00)
Abstract:  Optimizing compilers produce code that impedes source-level
debugging.  After optimization, the correspondence between a program's
source code and object code is not straightforward.  This thesis 
provides a solution to one of the more difficult source-level
debugging problems caused by optimized code.
      The first third of the thesis examines the problems
caused for source-level debuggers by optimization and presents a
detailed survey of previous research in the area.  It is noted that
some of these problems are not difficult, but remain problems due
to inertia in the production-software development process. 
      The final two-thirds of the thesis develop a
solution for one of the difficult problems examined in the first part
of the thesis.  The problem is that of determining when optimization
has caused a variable to contain an unexpected value, that is, a
value that differs from the value one would expect it to contain from 
an examination of the source code.  More formally, at a breakpoint in 
an executing program, a variable contains an unexpected value if its
value results from a different computation than in an unoptimized 
version of the program stopped at an equivalent breakpoint.  This is
detected by having the optimizing compiler provide information about
how variable definitions in the optimized code differ from 
variable definitions in the source code.  In particular, the compiler
creates records for each statement in the program which are
referred to by pre- and post-optimization versions of the program 
flow graph.  By comparing reaching definitions computed on the two
versions of the flow graph, unexpected values can be detected.
The solution is effective (and uniform) for both local and global
optimizations and is largely independent of the particular
optimizations that have been performed. 
**********
UCSC-CRL-90-24   (not available electronically)
AN ABSTRACT USER INTERFACE MODEL FOR THE SEPARATION  OF 
THE INTERFACE FROM THE APPLICATION 
Sadhana Jain  (M.S. Thesis)
June 1990, 113 pages (paper copy $14.00)
Abstract:  A distributed heterogeneous environment is created
when a variety of different computer systems are connected and
interacting with each other over a network.  In such a situation,
it is often desirable to make the same program work in environments
using different I/O devices, window systems, and processors.  The
purpose of this thesis was to make it easy for application developers
to write programs compatible with different environments.  An
interactive application program has two components, its functionality
(sometimes called computational component) and its user interface.
The only component that changes in a different environment is the
user interface.  The functionality of a program remains the same.
If the user interface is intertwined with the functionality, the whole
program will need to be rewritten when the program is moved to a new
environment.  If the functionality and the user interface are
developed independently, only the user interface will need to be
changed in a different environment. 
      In this thesis the design of an User Interface
Abstraction Model is presented.  The model facilitates dialogue
independence between the functionality and the user interface by
providing an interface abstraction.  Dialogue independence means
that the design decisions affecting the computational component
can be changed independent of the user interface.  The interface
abstraction creates a buffer between the two components using
abstract data types.  The data types support choices from a list for
tables and selections.  The design of the User Interface Abstraction 
Model is validated by the implementation of an `Image Browser'
application in two different environments:  the X Window System
and a character-based terminal environment.  Only the user interface
required changes in a different environment; the computational
component remained unaltered.
**********
UCSC-CRL-90-25   (not available electronically)
USING THE ucsc-report LaTeX STYLE FILE FOR UCSC TECHNICAL REPORTS 
Kevin Karplus
June 1990, 26 pages (paper copy $6.00)
Abstract:  This technical report describes how to use LaTeX to produce
technical reports in the proper format for the UCSC Baskin Center for
Computer Engineering and Information Sciences series.  The style file
can also be used for various other reports and articles, including
theses in a format acceptable to the UCSC Division of Graduate 
Studies.  Two other style files are described: *ucletter* for
business letters that generate University of California letterhead
and *handout* for class handouts.  The report itself is written
using the *ucsc-report* style file, so that the *.tex* file
can be used as an example file.  The reader is expected to refer to
Lamport's manual and to the local guide for details on how to use
LaTeX.
Keywords:  LaTeX, typesetting, document compiler, *ucsc-report*,
*ucletter*, *handout* style file.
**********
UCSC-CRL-90-26   (not available electronically)
OBJECT-ORIENTED RENDERING OF VOLUMETRIC AND GEOMETRIC PRIMITIVES 
Judith Ann Challinger  (M.S. Thesis)
June 1990, 101 pages (paper copy $14.00)
Abstract:  Computer graphics has, since its inception, been an 
invaluable tool for the understanding and analysis of datasets, both
computed and acquired.  The primary means for visualizing abstract
datasets has been to extract two or three-dimensional geometric
information from the data and display it using traditional computer
graphics rendering techniques.  However, this technique is not 
appropriate for many types of datasets and may result in loss of 
information in the visualization process.  Volumetric datasets consist
of a three-dimensional grid of scalar and/or vector values which may
not be inherently representable using geometric methods.  Recently,
researchers haved developed specialized techniques for directly 
rendering volumetric data, however, not many have addressed the need
to incorporate these techniques into traditional rendering systems. 
      The objective of this research is to investigate an
object-oriented approach to the analysis, design, and implementation
of a ray casting rendering system which handles volumetric and
geometric primitives directly.  Particular attention is paid to the
requirement of extensibility of the rendering system.  This feature
is inherent in an object-oriented design and eases the addition of new
types of renderable objects and experimentation with different methods.
To demonstrate, the system is extended to include a new primitive for 
rendering the volumetric results of computational fluid dynamics
simulations on three-dimensional curvilinear solution grids.
Keywords:  computer graphics, scientific visualization, volume 
rendering, ray casting, isosurfaces, object-oriented.
**********
UCSC-CRL-90-27   (not available electronically)
ADAPTATIVE DECISION TREE ALGORITHMS FOR LEARNING FROM EXAMPLES 
Giulia M. Pagallo  (Ph.D. Thesis)
June 1990, 174 pages (paper copy $15.00)
Abstract:  This thesis investigates the problem of designing learning
algorithms that adaptively enlarge the set of primitive attributes
with features (*adaptive algorithms*).  We focus on learning
algorithms that use decision trees as a concept description language.
We motivate the need for this type of algorithm by characterizing the
complexity of the decision tree representation for disjunctive
concepts.  Due to a representational problem, disjunctive concepts do
not always have a concise decision tree description when the tests at
the nodes are limited to the initial attributes.  However, we show that
this representational problem is overcome by using adequate features.
We present two types of adaptive decision tree algorithms:  iterative
algorithms, and separate and conquer algorithms.  Algorithms of the
first type use an iterative control structure.  In each iteration very
simple combinations of features from previous iterations are proposed.
More adequate and complex features are created as the number of
iterations increases.  Algorithms of the second type use a greedy 
top-down approach to explain the training examples by a restricted
kind of decision tree, called a decision list.  The performance of
the algorithms is evaluated empirically on several synthetic and
natural domains that have been used as benchmarks for other learning
algorithms.  The results establish that the algorithms outperform a
standard decision tree method when the target concept can be
described either by a small Disjunctive Normal Form (DNF) formula or
by a small Disjunctive Linear Form formula whose nonzero weights have 
a magnitude 1 ((0,1)DLF), and the examples are drawn from the uniform
distribution over the instance space.  Finally, we prove that one of
the algorithms is a Probably Approximately Correct (PAC) algorithm
for learning muDNF concepts when the examples are drawn from the
uniform distribution.
**********
UCSC-CRL-90-28   (not available electronically)
OCTREES FOR FASTER ISOSURFACE GENERATION  
Jane Wilhelms and Allen Van Gelder
June 1990, 15 pages (paper copy $5.00)
Abstract:  The large size of many volume data sets often prevents 
visualization algorithms from providing interactive rendering.  The use
of hierarchical data structures can ameliorate this problem by storing
summary information to prevent useless exploration of regions of little
or no interest within the volume.  This paper discusses research into
the use of the *octree* hierarchical data structure for this
purpose.  Octrees are well suited to the six-sided cell structure of
many volumes. 
      We introduce a new space-efficient design for octree 
representations of volumes whose dimensions are not conveniently a
power of two; octrees following this design are called
*branch-on-need octrees* (BONOs).  We also describe a caching
method that essentially passes information between octree neighbors
whose visitation times may be quite different, then discards it when
its useful life is over.  Using the application of octrees is
isosurface generation as a focus, we present space and time
comparisons for octree-based versus more traditional ``marching''
methods.
**********
UCSC-CRL-90-29   (not available electronically)
LEARNING COMMUTATIVE DETERMINISTIC FINITE STATE AUTOMATA IN POLYNOMIAL TIME 
Naoki Abe
June 1990, 15 pages (paper copy $5.00)
Abstract:  We consider the problem of learning the commutative 
subclass of regular languages in the on-line model of predicting 
{0,1}-valued functions from examples and reinforcements due to 
Littlestone. We show that the entire class of commutative deterministic
finite state automata (CDFA's) of an arbitrary alphabet size  k  is 
predictable in this model, with the worst case number of mistakes 
bounded above by a polynomial in the number of states  s  in the target
DFA, and independent of the length of example strings.  More precisely
the mistake bound is of order O(s^{2k} k log s).  By Littlestone's 
result on converting a mistake bound in this model to a sample 
Complexity bound for PAC-learning, this result also implies that the 
class of CDFA's is PAC-learnable from random labeled examples only 
in polynomial time with sample complexity 
O(1/epsilon (log 1/delta + s^{2k} k log s)), 
using a different class of representations.   The class of CDFA's is 
one of the few natural, non-trivial subclasses of DFA's which have 
been shown to be polynomially predictable to date.
**********
UCSC-CRL-90-31   (available electronically as ucsc-crl-91-31.ps.Z)
COMPOSITE GEOMETRIC CONCEPTS AND POLYNOMIAL PREDICTABILITY 
Philip M. Long and Manfred K. Warmuth
July 1990, 17 pages (paper copy $5.00)
Abstract:  We study the predictability of geometric concepts, in
particular those defined by boolean combinations of simple geometric
objects.  First, we give a negative result, showing that the problem
of predicting the class of convex polytopes encoded by listing their
vertices is prediction complete for  P .  Thus, an efficient
solution to this prediction problem implies the existence of efficient
solutions to all prediction problems whose associated evaluation
problem is in  P .  Assuming the existence of a one-way function
that is hard on iterates, there are such prediction problems which
do not admit efficient solutions.  Thus we show under minimalist
cryptographic assumptions that the class of convex polytopes encoded
by listing their vertices is not predictable.  As a side effect, we 
show that determining membership in the convex hull of a given set of
points is complete for  P with respect to log space reductions.
Next, we establish the predictability of the class consisting of
unions of a fixed number of flats by reducing its prediction problem
to that of the class of flats, which has previously been shown to be
predictable.  Finally, we given an Occam algorithm for predicting
fixed finite unions of boxes.  Both constructive results for flats
and boxes hold if the dimension is variable.
**********
UCSC-CRL-90-32   (not available electronically)
A NOTE ON DESIGNING TWO-LEVEL CARRY-SKIP ADDERS  
Pak K. Chan and Martine D. F. Schlag
July 1990, 12 pages (paper copy $5.00)
Abstract:  The worst-case carry propagation delays in carry-skip adders
depend on how the full adders are grouped together (into blocks).  We 
report an algorithm to configure 2-level carry-skip adders.  The 
worst-case carry propagation delay of the carry-skip adder 
configurations determined by our algorithm are consistently *less* 
than the ones currently reported in the literature.  Previous methods 
are applicable only to constant skip delay models and either do not 
guarantee an optimal configuration or suffered from a potentially
exponential worst-case time complexity. 
**********
UCSC-CRL-90-33   (not available electronically)
LEARNING INTEGER LATTICES 
David Helmbold, Robert Sloan, and Manfred K. Warmuth
July 1990, 34 pages (paper copy $7.00)
Abstract:  We consider the problem of learning of an integer
lattice of Z^k in an on-line fashion.  That is, the learning 
algorithm is given a sequence of k-tuples of integers and predicts 
for each tuple in the sequence whether it lies in a hidden target 
lattice of Z^k.  The goal of the algorithm is to minimize the 
number of prediction mistakes.  We give an efficient learning algorithm
with an absolute mistake bound of k + | k log (n sqrt{k}) | ,
where  n  is the maximum component of any tuple seen.  We show that 
this bound is approximately a  log log n  factor larger than the 
lower bound on the worst case number of mistakes given by the VC 
dimension of lattices that are restricted 
to {-n, ... , 0, ... , n}^k. 
     This algorithm is used to learn rational lattices,
cosets of lattices, an on-line word problem for abelian groups, and a 
subclass of the commutative regular languages.  Furthermore, adapting 
the results of previous work, we can efficiently learn nested 
differences of each of the above classes (e.g.\ concepts of the 
form c_1-(c_2-(c_3-(c_4-c_5))) where each  c_i  is the coset of a 
lattice).
**********
UCSC-CRL-90-34  (available electronically as ucsc-crl-90-34.ps.Z)
ACCESSING REPLICATED DATA IN AN INTERNETWORK 
Richard Golding and Darrell D. E. Long
August 1990, 21 pages (paper copy $6.00)
Abstract: When accessing a replicated data object across an
internetwork, the time to access different replicas is non-uniform.
Further, the probability that a particular replica is inaccessible is
much higher in an internetwork than in a local-area network because of
partitions and the many intermediate hosts and networks that can fail.
We report three replica-accessing algorithms which can be tuned to 
minimize either the time spent on the access or the number of messages 
sent.  We have obtained performance results for these algorithms by 
simulation.  We find an inverse relationship between the time spent 
processing an access and the number of messages required to complete 
the access.
**********
UCSC-CRL-90-35  (available as ucsc-crl-90-35.ps.Z)
PROTECTING REPLICATED OBJECTS AGAINST MEDIA FAILURES 
Jehan-Franc,ois Pa^ris and Darrell D.E. Long
July 1990, 17 pages (paper copy $5.00)
Abstract:  We present a  replication control protocol that provides 
excellent data availabilities while guaranteeing that all writes to 
the object are recorded in at least two replicas.  The protocol, 
*robust dynamic voting* (RDV) accepts reads and writes as long as 
at least two replicas remain available.  The replicated object remains 
inaccessible until either the two last available replicas recover or 
one of the two last available replicas can collect the votes of a 
majority of replicas. 
     We evaluate the read and write availabilities of 
replicated data objects managed by the RDV protocol and compare them 
with those of replicated objects managed by majority consensus voting, 
dynamic voting and hybrid dynamic voting protocols.  We show that RDV 
can provide extra protection against media failures with no significant
loss of availability.
**********
UCSC-CRL-90-36   (available electronically as ucsc-crl-90-36.ps.Z)
RESILIENT MEMORY-RESIDENT DATA OBJECTS 
Jehan-Franc,ois Pa^ris and Darrell D.E. Long
July 1990, 21 pages (paper copy $6.00)
Abstract:  Data replication has been widely used to build resilient 
data objects.  These objects normally consist of several replicas 
stored in stable storage and a replication control protocol managing 
these replicas. 
     Replicated data objects incur a significant penalty 
resulting from the increased number of disk accesses.  We propose 
several protocols that improve performance while not significantly
impacting the availability of the replicated data object.  Our 
replicated data objects consist of several memory-resident replicas and
one append-only log maintained on disk. 
      We analyze, under standard Markovian hypotheses, the 
availability of these data objects when combined with three of the most
popular replication control protocols:  *available copy* (AC), 
*majority consensus voting* (MCV), and *dynamic-linear voting* (DLV).  
We show that replicated objects consisting of  n  memory-resident 
replicas and a disk-resident log have almost the same availability as 
replicated objects having  n  disk-resident replicas. 
Keywords:  File replication, replicated databases, memory-resident 
databases, majority consensus voting.
**********
UCSC-CRL-90-37   (not available electronically)
THE CASE FOR GARBAGE COLLECTION IN C++  
Daniel Edelson and Ira Pohl
August 1990, 4 pages (paper copy $5.00)
Abstract:  C++ is an object-oriented imperative programming language 
that provides low-level access to the machine and efficient run-time 
code.  C++ provides access to dynamically allocated storage in a way 
that allows class designers to create customized memory allocators and 
deallocators. Unlike Eiffel and Modula-3, C++ does not provide garbage 
collection.  The benefits of garbage collection are substantial:
rapid-prototyping and runtime efficiency. However, it has not been 
clear that garbage collection could be provided for C++ in a way that
is consistent with the language's design goals. We argue that garbage 
collection should be an option for C++ programmers. We cite an 
implementation that demonstrates that it can be provided in a way that 
is consistent with the C++ design goals and philosophy.
**********
UCSC-CRL-90-38   (not available electronically)
A COHERENT PROJECTION APPROACH FOR DIRECT VOLUME RENDERING 
Jane Wilhelms
August 1990, 17 pages (paper copy $5.00)
Abstract:  Direct volume rendering using semi-transparency offers the 
opportunity to visualize all of a three-dimensional sample volume
in one image.  However, because all cells may contribute something
to the image, processing such images can be very expensive and good
quality high-resolution images are far from interactive.  This paper
introduces a projection approach for directly rendering sample
volumes that takes advantage of coherence combined with the polygon
rendering facilities of the newer graphics machines to produce
images (relatively) quickly.  It projects each volume cell as one to
seven polygons, calculates color and opacity for each vertex, and
interpolates across the polygons to render the cell.  In its fastest
form, the interpolation is linear in color and opacity and amounts
to Gouraud shaded polygon scan conversion.  It is limited to
rectilinear sample volumes rendered without perspective.
**********
UCSC-CRL-90-39   (not available electronically)
AUGEND-BASED ARITHMETIC CODES AND THE GOLOMB CODE 
Glen G. Langdon, Jr.
August 1990, 35 pages (paper copy $7.00)
Abstract:  Results of Gallager and VanVoorhis are employed to show that
all augend-based binary arithmetic coders in the fixed augend case
generate code strings of identical length to some Golomb code and
vice-versa.  A-based coders are studied for the random augend case 
(random interval model) that assume a randomization of successive 
augend values.  When augend Q and the smaller binary probability
q_{bpd} of the stationary binary input sequence are *matched*,
then the best coding efficiency is achieved.  The matching values of
Q/q_{opt} differ for fixed and random augend cases, but converge as q
becomes small.  The coding efficiencies are also compared.  The
Golomb code matching point for best efficiency is the basis for
Golomb number m.
**********
UCSC-CRL-90-40   (not available electronically)
ON ADAPTATION TO MULTIPLE CONTEXT BINARY SOURCES  
Glen G. Langdon, Jr.
August 1990, 31 pages (paper copy $7.00)
Abstract:  An introduction and entry into the literature of practical 
deterministic algorithms that adaptively estimate the relative
frequency distribution of binary sequences is provided.  Deterministic
adaptation appraoches typically maintain and adjust a count ratio 
that is based on past symbols seen in the past sequence.  Adapters
are finite state machines and some algorithms use a small number of
states by restricting the count numberator value, at a cost of wandering
about the optimum index in the case of stationary sources.
Issues of adaptation inertia (or speed) are covered.  A performance
measure of Rissanen and Langdon, the ideal code length
IL(M,F) of the data file F under a given context model M, is
supplemented by another closed form code length estimator, the
enumerative code length EL(M,F) of Cleary and Witten.
The novel application of IL or EL to calculate the information content
of the binary adapter output allows a new means of comparison of the
context model and adaptive statistics model.  The binary adapter
treatment includes results from reports not generally known or
available.  Wandering binary adapters are defined, then described
in the statistical significance testing metaphor, and designs are
presented that employ a simple wandering heuristic.  A simple
example illustrates the mean-median anomaly that differentiates
significance testing on a count ratio random variable versus a
runlength random variable.  Goladap, an adaptive Golomb code, uses the
Golomb coding operation itself as a trigger for adaptation, and the
runlength variable for adaptation.
**********
UCSC-CRL-90-41   (not available electronically)
CATEGORIZATION OF MACROMOLECULAR SEQUENCES BY MINIMAL LENGTH ENCODING  
Aleksandar Dusan Milosavljevic'  (Ph.D. Thesis)
September 1990, 138 pages (paper copy $15.00)
Abstract:  A new method for categorization  of macromolecular sequences
is developed by applying the Minimal Length Encoding principle.  While 
the method is developed with the particular application in mind, the 
formal model may be applied to any categorization problem where the 
observations can be represented by using a finite set of attributes 
that take values from a finite set.  The proposed method is shown to 
be more general than the categorization procedures based on Weighted 
Parsimony and Compatibility principles.  The proposed method also 
provides a principled tradeoff between the number of inferred classes 
and their fit to data.  A statistical significance test for the 
presence of classes is also proposed. 
     The categorization problem is proven to be 
computationally hard even under various simplifying assumptions.  To 
avoid the excessive computation time, an algorithm that is based on a 
local search strategy is proposed.  The algorithm was applied to 
rediscover several known macromolecular sequence families as well as to
discover new classes of Bacteriophage T7 promoters and Alu sequences.  
The algorithm was also tested on simulated data to determine the range 
of data parameters where it categorizes the sequences correctly. 
     While the application of the Minimal Length Encoding 
principle was restricted to the categorization of macromolecules, a 
very general background on the process of categorization and the 
Minimal Length Encoding principle is also provided.  It is proposed 
that categorization, and perhaps inductive inference in general, can 
be viewed as a process of minimal length encoding of observations. 
**********
UCSC-CRL-90-42   (not available electronically)
DIRECT VOLUME RENDERING OF CURVILINEAR VOLUMES  
Jane Wilhelms, Judy Challinger, Naim Alper, Shankar Ramamamoorthy.
September 1990, 17 pages (paper copy $5.00)
Abstract:  Direct volume rendering makes it possible to visualize 
sampled 3D scalar data as a continuous medium or to extract features,
avoiding the necessity of making binary decisions inherent in
methods which extract geometrical representations.  However, direct 
rendering is generally slow and images must
be recomputed, to a significant extent, for different viewpoints.
Furthermore, most algorithms for direct volume rendering have assumed
rectilinear gridded data. 
     This paper discusses methods for using direct volume 
rendering when the original volume is curvilinear, i.e., is divided 
into six-sided cells which are not necessarily equilateral hexahedra.
One approach is to ray-cast such volumes directly.  An alternative
approach is to interpolate the sample volumes to a rectilinear grid,
and use this regular volume for rendering.  Advantages and
disadvantages of the two appraoches in terms of speed and image
quality are explored.
**********
UCSC-CRL-90-43  (available electronically as ucsc-crl-90-43.ps.Z)
USING IF-THEN-ELSE DAGS TO DO   
TECHNOLOGY MAPPING FOR FIELD-PROGRAMMABLE GATE ARRAYS 
Kevin Karplus
September 1990, 17 pages (paper copy $5.00)
Abstract:  This paper presents two new algorithms for doing mapping
from multi-level logic to field-programmable gate arrays.  One
algorithm, Xmap, is for mapping to table-lookup gates (for example, 
the Xilinx chip); the other, Amap, is for mapping to selector-based
architectures (for example, the Actel chip).  Mapping to the Actel
architecture can also be achieved by mapping to 3-input tables,
and replacing them with equivalent Actel cells (XAmap). 
     The algorithms are based on an if-then-else
DAG representation of the functions.  The technology mappers
differ from previous mappers in that the circuit is not decomposed
into fan-out-free trees. 
      The gate counts and CPU time are compared with three 
previous mappers for these architectures:  misII, Chortle, and mis-pga.
The Xmap algorithm for table-lookup architectures gets 7\% fewer cells 
than Chortle, 11\% fewer than misII, and 14\% fewer than mis-pga,
and is 4.5 times faster than Chortle, 17 times faster than misII,
and at least 150 times faster than mis-pga.  The Amap algorithm for
Actel cells use 6\% fewer cells than misII and about 8\% more cells
than the best achieved by mis-pga, and is at least 25 times as fast
as misII and at least 586 times as fast as mis-pga. 
Keywords:  Xilinx, Actel, logic minimization, Xmap, Amap, XAmap, 
if-then-else DAG, table-lookup gates.
**********
UCSC-CRL-90-45   (not available electronically) 
PROXIMITY CONTENT-ADDRESSABLE MEMORY:  
AN EFFICIENT EXTENSION TO k-NEAREST NEIGHBORS SEARCH 
James Donald Roberts  (M.S. Thesis)
September 1990, 124 pages (paper copy $15.00)
Abstract:  This thesis presents the development of *proximity
content addressable memory (PCAM)*, an extension to nearest neighbors
search for high dimensional parameter spaces with variable
weighting.  In PCAM, the parameter space is mapped to Boolean space by 
a family of matching and magnitude comparison functions.
A weighted distance is computed. 
      Three methods were developed, the first two being
software algorithms for conventional processors, and the third a
hardware implementation.  The first algorithm preprocesses the query
into a look-up table, whereas the second preprocesses the data points
into an inverted index.  The latter is preferable when indexing is
sparse or the queries contain few attributes.  The hardware 
implementation represents several extensions to prior
*content addressable memory (CAM)* systems and uses a modified
tree architecture.
      A survey was unable to identify any software 
algorithms asymptotically better than exhaustive search for
high-dimensional spaces with variable distance weighting.  All the
PCAM implementations have time and space linear in the number of
data points and dimension of the parameter space, excluding
read out.  The PCAM algorithms equal the performance of the best
k-nearest neighbors algorithms surveyed.  For an example
database, a 10 to 100 times speed up over linear search is
achieved.  A hardware system with fewer than 100 processing elements
is projected to provide one to two orders of magnitude acceleration
for personal computers and workstations.  Systems with thousands
of processing elements appear feasible.  If one hardware processing
element is available for each data point, time  O(1)  and space
 O(N)  can be achieved, excluding read out time.  A CMOS VLSI
chip containing 8 processing elements and the associated response
resolver network has recently been completed. 
     Applications where PCAM may provide constant factor
or asymptotically better space-time performance include information
retrieval based on similarity, computer aided VLSI and circuit board 
design, and pattern matching and classfication in the presence of
noisy, erroneous, or incomplete data.  Efficient recall based on
content and similarity may also prove important in the development
of intelligent systems. 
Keywords:  k-nearest neighbors, information retrieval, content
addressable memory, Minkowski distance metric.
**********
UCSC-CRL-90-46   (available electronically as ucsc-crl-90-46.ps.Z)
A STUDY OF THE RELIABILITY OF INTERNET SITES 
D. D. E. Long, J. L. Carroll, and C. J. Park
September 1990, 17 pages (paper copy $5.00)
Abstract:  It is often assumed that the failure and repair rates of
components are exponentially distributed.  This hypothesis is testable 
for failure rates, though the process of gathering the necessary data 
and reducing it to a usable form can be difficult.  While no amount
of testing can prove that a sample is drawn from an exponential
distribution, the hypothesis that a population distribution is
exponential can in many cases be rejected with confidence. 
     For this study, data were collected from as many hosts 
as was feasible using only data that could be obtained via the Internet
with no special privileges or added monitoring facilities.
The Internet was used to poll over 100,000 hosts to determine the
length of time that each had been up, and again polled after several
months to determine average host availability.  A surprisingly rich
collection of information was gathered in this fashion, allowing
estimates of availability, mean-time-to-failure (MTTF) and
mean-time-to-repair (MTTR) to be derived.  The measurements
reported here correspond with common experience and certainly fall in
the range of reasonable values. 
     By applying an appropriate test statistic, some of
the samples were found to have a realistic chance of being drawn
from an exponential distribution, while others can be confidently
classed as non-exponential.  With very large sample sizes,
sufficient evidence could be accumulated to reject the exponential
hypothesis.  However, for moderately-sized samples, it was
often not possible to exhibit the deviation from exponentiality,
lending credence to the common practice of assuming the MTTF is
exponentially distributed. 
**********
UCSC-CRL-90-47   (not available electronically)
0-1 LAWS FOR FRAGMENTS OF SECOND-ORDER LOGIC:  AN OVERVIEW  
Phokion G. Kolaitis and Moshe Y. Vardi
December 1990, 20 pages (paper copy $5.00)
Abstract:  The probability of a property on the collection of all 
finite relational structures is the limit as n --> infinity   of 
the fraction of structures with  n  elements satisfying the property, 
provided the limit exists.  It is known that the 0-1 law holds for any 
property expressible in first-order logic, i.e., the probability of any
such property exists and is either 0 or 1.  Moreover, the associated 
decision problem for the probabilities is solvable. 
     We investigate here fragments of existential 
second-order logic in which we restrict  the patterns of first-order 
quantifiers.  We focus on fragments in which the first-order part 
belongs to a prefix class.  We show that the classifications of prefix
classes of first-order logic with equality according to the solvability
of the finite satisfiability problem and according to the 0-1 law for 
the corresponding  Sigma_1^1 fragment are identical.
**********
UCSC-CRL-90-48   (available electronically as ucsc-crl-90-48.ps.Z)
LOGICAL DEFINABILITY OF NP OPTIMIZATION PROBLEMS  
Phokion G. Kolaitis and Madhukar N. Thakur
September 1990, 27 pages (paper copy $6.00)
Abstract:  We investigate here NP optimization problems from
a logical definability standpoint.  We show  that the class of 
optimization problems whose optimum is definable using first-order 
formulae coincides with the class of polynomially bounded NP 
optimization problems on finite structures. After this, we analyze 
the relative expressive power of various classes of optimization 
problems that arise in this framework.  Some of our results show that 
logical definability has different implications for NP maximization 
problems than it has for NP minimization problems, in terms of both
expressive power and approximation properties.
**********
UCSC-CRL-90-49  (not available electronically) 
UNIVERSAL COVERS OF EDGE-LABELED DIGRAPHS:  
ISOMORPHISM TO DEPTH  n - 1  IMPLIES ISOMORPHISM TO ALL DEPTHS  
N. Norris
October 1990, 10 pages (paper copy $5.00)
Abstract:  Edge-labeled digraphs have been used to model computer
networks, and the universal covers of such graphs to describe what a
processor in an anonymous network ``knows'' about the network.  If
G  is a connected edge-labeled directed graph with  n  vertices,
write  U^k_v  for the universal cover of  G, rooted at a vertex  v  and 
truncated at depth  k .  In this note we consider the smallest depth  m 
for which isomorphism between   U^m_v  and   U^m_w  guarantees that   
U^k_v  and   U^k_w  are isomorphic to all depths, k, for v, w vertices 
in the universal cover of  G.  We show that this m equals  n - 1 .  
Isomorphism to a depth smaller than  n - 1  does not insure isomorphism
to all depths.  Our result is an improvement over the previous result of
n^2 due to Yamashita and Kameda.  It applies immediately to graphs 
without edge-labels. 
Keywords:  graph covers, edge-labeled digraphs, anonymous computer
networks.
**********
UCSC-CRL-90-53  (not available electronically) 
A CONSTRAINT-BASED SKIN MODEL FOR HUMAN FIGURE ANIMATION  
Mark Henne  (M.S. Thesis)
December 1990, 65 pages (paper copy $10.00)
Abstract:  One of the difficult problems in computer character 
animation has been creating a skin model which deforms naturally over 
joints.  A method for solving this problem is described, which 
includes such desirable characteristics as the formation of creases on 
the inside of joints and muscle bulging during flexing. 
     In this model the skin is represented using a mesh of 
bicubic surface patches, with the control points acting as sample 
points in a constraint balancing equation.  Two main constraints are 
used: the skin is described as a flexible surface that resists 
stretching, and bones, fat, and muscle are represented by localized 
fields pushing out on the skin.  The final shape of the figure is a
compromise between the skin's surface area constraints and the
arrangement of underlying tissue. 
     Modeling with bicubic patches allows the granularity 
of the constraint computations to be much more coarse than if a 
polygonal model were used, and provides for well-defined and stable 
surface texture coordinates.  In addition, this method is capable of
incorporating tissue-bouncing due to rigid body motion. 
Keywords:  animation, constraints, dynamics, human modeling, implicit surfaces.
**********
UCSC-CRL-90-54  (revised version not yet available electronically)
PREDICTING {0,1}-FUNCTIONS ON RANDOMLY DRAWN POINTS  
D. Haussler, N. Littlestone, and M. K. Warmuth
December 1990, revised June 1992, 41 pages (paper copy $8.00)
Abstract:  We consider the problem of predicting  {0,1}-valued 
functions on  R^n  and smaller domains, based on their values 
on randomly drawn points.  Our model is related to Valiant's PAC 
learning model, but does not require the hypotheses used for prediction
to be represented in any specified form.  In our main result we show 
how to construct prediction strategies that are optimal to within a 
constant factor for any reasonable class  F  of target functions. 
This result is based on new combinatorial results about classes of 
functions of finite VC dimension.  We also discuss more computationally
efficient algorithms for predicting indicator functions of 
axis-parallel rectangles, more general intersection closed concept 
classes, and halfspaces in   R^n .  These are also optimal to 
within a constant factor.  Finally, we compare the general performance 
of prediction strategies derived by our method to those derived from 
methods in PAC learning theory. 
**********
UCSC-CRL-90-55   (not available electronically)
DETECTION OF ALL MULTIPLE FAULTY CELLS IN ARRAY MULTIPLIERS 
Martine Schlag and F. Joel Ferguson
December 1990, 19 pages (paper copy $5.00)
Abstract:  Array multipliers are well suited for VLSI implementation
because of their regular structure and relative ease of test.
Previous research has provided test sets that detect all single
faulty cells in array multipliers.  We provide tests that detect all
multiple faulty cells in the two-dimensional array of full-adders in the
multiplier  with a test set whose length is proportional to the
square root of the number of cells in the multiplier array.  We show 
an Omega(n / log n)  lower bound on the number of tests required to 
detect all multiple faulty cells in the full adder array of an  n X n 
multiplier.
**********
UCSC-CRL-90-56   (not available electronically)
DETECTING UNEXPECTED DATA VALUES IN OPTIMIZED CODE 
Max Copperman and Charles E. McDowell
October 1990, 20 pages (paper copy $5.00)
Abstract:  Optimizing compilers produce code that impedes source-level
debugging.  After optimization, the correspondence between a program's
source code and object code is not straightforward.  An important
problem for a source-level debugger of optimized programs is to be able
to determine when, because of optimizations, the value of a variable
does not correspond to what the user expects.  The paper describes a
solution to this problem.  The solution uses reaching sets to
determine when the definitions of a variable that reach a breakpoint
location in an optimized program are not the definitions that would
have reached in the unoptimized program. 
Keywords:  debugging, compilers, optimization.
**********
UCSC-CRL-90-57   (available electronically as ucsc-crl-90-57.ps.Z or in 
two parts as ucsc-crl-90-57.part1.ps.Z and ucsc-crl-90-57.part2.ps.Z)
DETECTING DATA RACES BY ANALYZING SEQUENTIAL TRACES 
David P. Helmbold, Charles E. McDowell, and Jian-Zhong Wang
October 1990, 29 pages (paper copy $6.00)
Abstract:  One of the fundamental problems encountered when
debugging a parallel program is determining the potential race
conditions in the program.  A race condition exists when multiple tasks
access shared data in an unconstrained order and at least one of the 
accesses is a write operation.  The program's behavior can be
unpredictable when race conditions are present.  This paper describes
techniques which automatically detect data races in parallel programs
by analyzing program traces. 
     We view a program execution as a partial ordering of
events, and define which executions are consistent with a given trace.
In general, it is not possible to determine which of the consistent 
executions occurred.  Therefore we introduce the notion of ``safe
orderings'' between events which are guaranteed to hold in every
execution which is consistent with the trace.  The main result of the
paper is a series of algorithms which determine many of the ``safe
orderings''.  An algorithm is also presented to distinguish
unordered sequential events from concurrent events. 
     A working trace analyzer has been implemented.
The trace analyzer can report various data races in parallel
programs by finding unordered pairs ofevents and variable
access conflicts. 
Keywords:  data race, time vector, program trace, parallel programming,
debugging, distributed systems.
**********
UCSC-CRL-90-58   (available electronically as ucsc-crl-90-58.ps.Z or in
two parts as ucsc-crl-90-58.part1.ps.Z and ucsc-crl-90-58.part2.ps.Z)
COMPUTING REACHABLE STATES OF PARALLEL PROGRAMS 
David P. Helmbold and Charles E. McDowell
October 1990, 24 pages (paper copy $6.00)
Abstract:  A concurrency history graph is a representation of the
reachable states of a parallel program.  A new abstraction for 
representing the state of a parallel program is presented.  This new
abstraction is more general than previous work by the authors.
At the same time, the new abstraction makes it possible to produce
concurrency history graphs that require much less storage than that 
suggested by a simple worst case complexity analysis.  Concurrency
history graphs based on this new abstraction form the foundation
upon which a static analysis tool capable of detecting race
conditions in parallel programs is being built. 
Keywords:  parallel processing, debugging, static program analysis.
**********
UCSC-CRL-90-59   (not available electronically)
TRACEVIEWER:  A GRAPHICAL BROWSER FOR TRACE ANALYSIS  
David P. Helmbold, Charles E. McDowell, and Jian-Zhong Wang
October 1990, 9 pages (paper copy $5.00)
Abstract:  This report contains a brief description of the operation of
TraceViewer.  TraceViewer is a graphical tool for browsing the trace of
the execution of a parallel Fortran program written using IBM's
parallel Fortran.  TraceViewer is intended for examining the ordering
relationships between events (which must come first if either) and
for reporting data races detected by a companion trace analyzer.
Keywords:  data race, time vector, program trace, parallel
programming, debugging, distributed systems.
*********
UCSC-CRL-90-61   (available electronically as ucsc-crl-90-61.ps.Z)
CARAFE USER'S MANUAL,  Alpha.2 Release 
Alvin Jee
December 1990, 44 pages (paper copy $8.00)
Abstract:  This document describes the user interface for CARAFE, the
second generation Inductive Fault Analysis (IFA) program.
The syntax of all the commands and their parameters are all described 
in this document along with a description of the formats
of the various files used and created by CARAFE.
**********
UCSC-CRL-90-62   (not available electronically)
PRODUCING A CORRECT CALL-STACK TRACE IN THE  
OCCASIONAL ABSENCE OF FRAME POINTERS 
Max Copperman
November 1990, 13 pages (paper copy $5.00)
Abstract:  Optimizing compilers produce code that impedes debugging.
An important facility for an interactive debugger of optimized 
programs is to be able to provide a call-stack trace, listing active 
subroutines in reverse order of their invocations.  This facility 
relies on information provided by code within each called routine.  
This paper describes an alternative way to support this facility in 
the circumstance that this code is optimized away. 
Keywords:  debugging, compilers, optimization.
**********
UCSC-CRL-90-63   (available electronically as ucsc-crl-90-63.ps.Z or in 
two parts as ucsc-crl-90-63.part1.ps.Z and ucsc-crl-90-63.part2.ps.Z)
ON THE COMPUTATIONAL COMPLEXITY OF 
APPROXIMATING DISTRIBUTIONS BY PROBABILISTIC AUTOMATA 
Naoki Abe and Manfred K. Warmuth
December 1990, 48 pages (paper copy $8.00)
Abstract:  We introduce a rigorous performance criterion for
training algorithms for probabilistic automata (PAs) and hidden
Markov models (HMMs), used extensively for speech recognition,
and analyze the complexity of the training problem as a computational
problem.  The PA training problem is the problem of approximating an 
arbitrary, unknown source distribution by distributions generated by
a PA.  We investigate the following question about this important,
well-studied problem:  Does there exist an *efficient* training
algorithm such that the trained PAs *provably converge* to a
model close to an optimum one with high confidence, after only a
feasibly small set of training data?  We model this problem in the
framework of computational learning theory and analyze the sample
as well as computational complexity.  We show that the number of
examples required for training PAs is moderate -- essentially linear
in the number of transition probabilities to be trained and a
low-degree polynomial in the example length and parameters
quantifying the accuracy and confidence.  Computationally, however,
training PAs is quite demanding:  Fixed state size PAs are trainable
in time polynomial in the accuracy and confidence parameters and
example length, but *not* in the alphabet size, unless RP = NP.  
The latter result is shown via a strong non-approximability result for 
the single string maximum likelihood model problem for 2-state PAs, 
which is of independent interest.
**********
UCSC-CRL-90-64   (not available electronically)
INCREMENTAL, BOTTOM-UP, WELL-FOUNDED DEDUCTION (EXTENDED ABSTRACT)  
Brian W. Beach
December 1990, 13 pages (paper copy $5.00)
Abstract:  In this paper we describe an algorithm, called AFP, for the
bottom-up execution of logic programs well suited to data-driven 
applications, where incremental updates to the base relations are 
propagated through the program to produce updated answers
without completely re-executing the program.  We show that AFP
conforms to the well-founded semantics for general logic programs
and that it terminates in polynomial time for DATALOG programs
with negation. 
     AFP is based on a modified formulation of
well-founded negation that does not rely on computing sets of false
atoms, avoiding the instantiation of the entire Herbrand base.  AFP 
solves the two major problems in incremental bottom-up computation,
recursion through negation and self-supporting conclusions, by using
a counting technique over a two-dimensional representation of time
to detect and stop such loops.  Its feasibility has been verified
with an implementation in Prolog. 
Keywords:  DATALOG, incremental computation, logic progamming.
**********
UCSC-CRL-90-65   (not available electronically)
ASPECTS OF THE SOLUTION OF SOME MULTICLASS LOSS SYSTEMS  
Alexandre Brandwajn and Anil K. Sahai  (Supersedes 90-03.)
December 1990, 23 pages (paper copy $6.00)
Abstract:  Stochastic service systems in which no queueing is allowed
have been around for quite some time as models of telephone systems.
Recently, such loss systems with a finite number of request sources
were shown to be of interest in the modeling of path contention
occurring in many current I/O computer architectures. 
     This paper considers two aspects of finite source
loss sytems with several classes of requests (``customers'')
arising, for instance, in the representation of more realistic
I/O workloads.  First, we present a simple approach to the solution
of such systems in the case of classical multiple servers.  This
approach is based on the use of recurrence relationships which can
be shown to exist among conditional averages, and leads to an
efficient computation of server utilizations and loss probabilities. 
     In the second part of this paper, we consider
generalized loss systems in which the service resources are viewed as 
a global quantity (rather than a specific fixed number of servers),
each class of customers requesting a given amount of the global
resource.  Such systems are useful, for example, as models of bus
bandwidth shared among several types of transfers.  We find that,
although these systems exhibit a product-form solution, the
simple recurrences derived for regular multiserver loss systems do
not seem to carry over to the generalized systems.  Therefore, we
present an alternative approach, based on equivalence techniques,
which allows to obtain the solution of such generalized systems
through repeated solutions of a single-class loss model.  A 
comparison with the existing convolution method for evaluation the
product-form solution, indicates that the proposed method is
significantly more efficient both in terms of computational
complexity and computer memory requirements.
**********
UCSC-CRL-90-66   (not available electronically)
PERFORMANCE EVALUATION OF BUFFERED SWITCHES IN  
PACKET SWITCHING NETWORKS WITH MESH TOPOLOGIES  
Anil Kumar Sahai
December 1990, 132 pages (paper copy $15.00)
Abstract:  The goal of this thesis is to evaluate the performance of
buffered switches in regular mesh topology packet switching networks.
The thesis consists of three parts.  The first part presents a
simulation model of a mesh topology packet switching network.  The 
simulation results suggest that providing a small source and output 
buffer at switching nodes can significantly improve the total 
throughput of the network.  We also investigate the performance
of buffered switches in a Manhattan network, a particular case of
mesh networks.  We propose a design of a  2 X 2  packet 
switch and a routing protocol which limits to 3 the number of times a 
packet needs to be buffered in an arbitrary sized Manhattan network
before reaching its destination.  The second part presents an
approximate method to compute the throughput, and average 
end-to-end delays in the network.  This method is based on solving
a system of recurrence equations using a fixed point iterative
scheme.  Comparison with the simulation results show that the 
approximations are sharp.  The third part addresses blocking
in tandem queues.  Finite buffers can cause blocking in networks.
The exact numerical solution of such networks very quickly
becomes intactable due to the large state space.  We study a
speed-up technique to an approximate method for solving such networks.
We find that our technique can speed-up the solution by an order
of magnitude, especially for large networks.  The major
contributions of this thesis are:  (1) an extensive simulation
study which suggests that providing small buffers at the switching
nodes can significantly improve the throughput in regular mesh
topology networks; (2) proposed design of a packet switch and a
routing protocol which limits the number of times a packet needs to
be buffered in a Manhattan network; (3) analytical models to
estimate the performance of regular mesh networks using both
buffered and unbuffered packet switches; and (4) a study of a
speed-up technique to one of the approximation methods for solving
tandem queues with blocking.
**********
UCSC-CRL-90-67   (not available electronically)
CIRCUMSCRIPTION:  A FORMALISM OF NONMONOTONIC REASONING 
Madhavan Thirumalai
December 1990, 61 pages (paper copy $10.00)
Abstract:  It is commonsense to conclude, in the absence of any 
statement to the contrary, that a particular instance of a certain
class of objects is typical in that it has all the attributes of that
class of objects.  Later, one withdraws one's conclusion if one learns
that the object in question varies from the typical in some way.  Such
reasoning, called *Nonmonotonic Reasoning*, is beyond the realm
of classical logic.  In this thesis we explore *Circumscription*,
one of the formalisms of nonmonotonic reasoning.
**********
UCSC-CRL-90-68   (not available electronically)
THE JPEG AND IMAGE DATA COMPRESSION ALGORITHMS  
Manyun Zhang (Chang)
December 1990, 68 pages (paper copy $10.00)
Abstract:  A set of still image compression algorithms JPEG (Joint
Photographic Experts Group) is becoming an international standard.
Here we investigate the algorithms and explore why these algorithms
were chosen by JPEG among many other comparable algorithms.  We also
present our results, observations and analysis on simulating the
JPEG sequential baseline system.  Based on our simulator, a comparison
of Huffman coder, arithmetic coder and LZW algorithm is also included.
**********
UCSC-CRL-90-69   (not available electronically)
DETECTION OF ALL MULTIPLE FAULTS IN TWO-DIMENSIONAL LOGIC ARRAYS  
Martine Schlag and F. Joel Ferguson
December 1990, 20 pages (paper copy $5.00)
Abstract:  Previous research has provided test sets for detecting all 
multiple faulty cells in two-dimensional arrays whose lengths are 
proportional to the number of cells in the array.  Constant length 
test sets for array multipliers have been found under the single 
faulty cell model if the array is modified and otherwise test sets are 
proportional to the number of bits.  Prasad and Gray studied the 
problem of detecting multiple faulty cells in two dimensional arrays
and provided test sets of length proportional to the number of cells
for a restricted class of cells.  We provide test sets proportional to 
the sum of the two dimensions of the array for a larger class of cells,
which allow us to test rows (or columns) of cells of the array 
independently.  A  17n + 2m + 5  test set is constructed detecting all 
multiple faulty full~adder cells in an  n X m  carry-save array 
multiplier.  We show that no constant length test set exists for this 
array under the multiple faulty cell (MFC) model, by providing an 
Omega(n / log n) lower bound for testing array multipliers.
**********