leff@smu.UUCP (Laurence Leff) (04/20/88)
Hello again, I promised to send you this list a few days ago. I have been
trying to find a way to send this to you in BIB format, but alas
our programming staff is very busy at this time. I normally use
Microsoft WORD on my Macintosh Plus for all desk publishing items such
as this list. I can easily take my electronic UNIX data and telenet
it into my Macintosh programs, however, it seems impossible to take
the data off WORD and ship it back to UNIX.
As I would like to send you our most updated version twice a year, it
behooves me to find a systematic way to format this data into BIB style.
For now, however, I am sending you the only UNIX file version of this
data that I have. It is set in "vi" commands and can be "nroff"ed to
visually eliminate the dot commands. Some of the equations in the
abstracts will not come out right, but it's the best I can do for now.
If you have any questions or suggestions, I'd like to hear them.
Thanks, jennifer
p.s. Am I automatically put on the user list for REFER/BIB?
.op
.nf
.po 2cm
.sz 8
.vs 12
.he''%''
.ll 7i
.nr fi 0
.EQ
delim $$
define prime '"\s10\aa\s0"'
.gsize 10
.EN
.ps 14
.ce 8
University of California, Santa Cruz
Computer Research Laboratory
Baskin Center for Computer Engineering & Information Sciences
225 Applied Science Building
Santa Cruz, CA 95064
-PLEASE MAKE CHECK PAYABLE TO THE U.C.REGENTS-
.ps 8
.nf
\fBUCSC-CRL-86-2
OCCAM's RAZOR\fR
Anselm Blumer, Andrzej Ehrenfeucht
David Haussler, Manfred Warmuth
February, 1986
5 pages
($1.00)
.fi
\fBABSTRACT:\fR We show that a polynomial learning algorithm,
as defined in [5], is obtained whenever there exists a
polynomial-time method of producing, for any sequence of
observations, a nearly minimum hypothesis that is
consistent with these observations.
.nf
\fBUCSC-CRL-86-3
FORMALIZATION OF REASONING IN JUDICIAL
EXPERT SYSTEMS THROUGH DEONTIC LOGIC\fR
Mohyeldin Said, K.
February, 1986
13 pages
($2.00)
.fi
\fBABSTRACT:\fR Deontic logic is the logic of normative systems.
It deals with the logical relationships between the principles
governing the concepts of obligation and permission. Hence it
can be used in juridistic and legal-advice expert systems as a
formalization of the reasoning process. I consider various
axiomatizations of deontic logics and their relational
semantics as based on possible worlds, in addition to their
use in expert systems.
.nf
\fBUCSC-CRL-86-4
VIRYA-A MOTION CONTROL EDITOR FOR KINEMATIC AND DYNAMIC ANIMATION\fR
Jane Wilhelms
April, 1986
13 pages
($2.00)
.fi
\fBABSTRACT:\fR \fIVirya\fR is an interactive graphical
motion control editor for
kinematic and dynamic animation. Most animation is controlled
\fIkinematically\fR, by designating objects' positions taken over
time without consideration for the causes of
the motion. An alternative is \fIdynamic\fR motion control,
where objects are seen as masses moving under the influence of
forces and torques. Dynamic motion control has some advantages in
that motion more naturally simulates real world conditions and many
complex motions can be automatically calculated, though calculating
motion is quite expensive and control is sometimes less intuitive.
The editor \fIVirya\fR works both for kinematic and dynamic motion
control. It has two main tasks: to specify \fIcontrol functions\fR
representing positions (kinematic) or forces and torques (dynamic)
controlling motion, and to specify \fIcontrol modes\fR which designate
how control functions are interpreted or whether joints are frozen
in place, relaxed, or balanced. Using these control modes,
the user can designate motion using a convenient kinematic method
and still use dynamic analysis as a final step to constrain and
add realism.
\fIKEYWORDS\fR: computer animation, human modeling, dynamics, simulation
.bp
.nf
\fBUCSC-CRL-86-6
OPTIMAL ALGORITHMS FOR SOLVING A SYSTEM OF LINEAR EQUATIONS
WITH THE CONSECUTIVE-ONES PROPERTY\fR
Don Hatch, Manfred K. Warmuth
April, 1986
12 pages
($2.00)
.fi
\fBABSTRACT:\fR A matrix has the \fIconsecutive ones\fP property
\fIfor rows\fP (resp. \fIcolumns\fP) if all elements are
either zero or one, and there is at most one sequence of
consecutive ones in any row (resp. column). We show that a
system of linear equations
.ce 2
.ft B
A x = b
.ft
$ ~~n times n~~n times 1~~~n x 1 $
can be solved in $ O~( n ) $ time, if
.ft B
A
.ft
is a consecutive-ones matrix of either type. The vector
.ft B
b
.ft
is allowed to contain arbitrary real numbers.
.nf
\fBUCSC-CRL-86-7
THE RENYI REDUNDANCY OF GENERALIZED HUFFMAN CODES\fP
Anselm Blumer, Robert J. McEliece
April, 1986
13 pages
($2.00)
.fi
\fBABSTRACT:\fR If optimality is measured by average codeword length, Huffman's
algorithm gives optimal codes, and the redundancy can be measured as the
difference between the average codeword length and Shannon's entropy.
If the objective function is replaced by an exponentially weighted
average, then a simple modification of Huffman's algorithm gives
optimal codes. The redundancy can now be measured as the difference
between this new average and Renyi's generalization of Shannon's
entropy. This paper provides a new proof of Kricevski's results on
the redundancy of Huffman codes, and generalizes these results to the
Renyi case. These results are also related to Gallager's bounds on the
redundancy of Huffman codes.
.nf
\fBUCSC-CRL-86-8
MINIMAX UNIVERSAL NOISELESS CODING FOR UNIFILAR AND MARKOV SOURCES\fR
Anselm Blumer
April, 1986
9 pages
($1.00)
.fi
\fBABSTRACT:\fR Constructive upper bounds are
presented for minimax universal noiseless
coding of unifilar sources without any ergodicity assumptions. These bounds are
obtained by quantizing the estimated probability distribution of source letters
with respect to the relative entropy. They apply both to fixed-length to
variable-length (FV) and variable-length to fixed-length (VF) codes.
Unifilar sources are a generalization of the usual definition of Markov sources,
so these results apply to Markov sources as well. These upper bounds agree
asymptotically with the lower bounds given by Davisson for FV coding
of stationary ergodic Markov sources.
.bp
.nf
\fBUCSC-CRL-86-9
A FAST ALGORITHM FOR MULTIPROCESSOR SCHEDULING OF UNIT-LENGTH JOBS\fR
Barbara Simons, Manfred K. Warmuth
April, 1986
35 pages
($4.00)
.fi
\fBABSTRACT:\fR We present an efficient polynomial time algorithm for the
problem of scheduling n unit length jobs with rational
release times and deadlines on m identical parallel
machines. By doing preprocessing before the jobs are actually
scheduled, we obtain a running time of $ roman O~( mn sup 2 ) $,
which is an improvement over the previous best running time
of $ roman O~( n sup 3~log~log~n ) $. We also present new
NP-completeness result for two closely related problems.
.nf
\fBUCSC-CRL-86-10
THE CONSTRUCTION OF HEURISTIC FUNCTIONS\fR
George Politowski
April, 1986
14 pages
($2.00)
.fi
\fBABSTRACT:\fR It is well established in heuristic
search theory that there is a
strong connection between the accuracy of the heuristic used to
guide a search and the resulting search efficiency [Pearl 84].
This suggests that the formulation of heuristics is one of the
most crucial areas in the application of heuristic search.
Despite this there has been little research to establish a
methodology for discovering and refining heuristics.
Our current work addresses this problem by developing a theory of
parameter-based heuristic functions. In this theory the heuristic
function is represented as an explicit table of feature vectors and
their corresponding heuristic values. We show under what conditions
the addition of parameters can never worsen the performance
of such a heuristic. We also suggest a simple method whereby
interaction with a search system can facilitate the discovery
of useful parameters or features. With these methods we have
constructed a heuristic for the 15-puzzle that is superior to
anything reported in the literature. We have also constructed
what we believe to be the first successful
distance-estimating heuristic for the
2x2x2 Rubik's cube. The latter was accomplished
despite the fact that we ourselves are not
adept at solving the puzzle.
.sp
.nf
\fBUCSC-CRL-86-11
ONLINE CONSTRUCTION OF A COMPLETE INVERTED FILE\fR
J. Blume, A. Blumer
April, 1986
21 pages
($3.00)
.fi
\fBABSTRACT:\fR The compact Directed Acyclic Word Graph
(DAWG) can be used to implement a
complete inverted file, and thus to find, in optimal time, the locations and
number of occurrences of any string occurring in a set of texts. The
compact DAWG can be built in linear time [Blu 86], but this requires a
postprocessing phase, so that further texts cannot be added efficiently.
This paper presents an algorithm which builds the compact DAWG on-line in
$O(n~log~n)$ time, where $n$ denotes the total length of all the texts.
This combination of features gives the compact DAWG an advantage over
other data structures, such as PATRICIA trees, compact position trees, or
suffix trees, which could be used to implement a complete inverted file.
.bp
.nf
\fBUCSC-CRL-86-12
A TRANSFORM THEORY FOR A CLASS OF GROUP-INVARIANT CODES\fR
R. Michael Tanner
September, 1987 (Revised)
45 pages
($4.00)
.fi
\fBABSTRACT:\fR A binary cyclic code of length $n$ can be
defined by a set of parity-check equations
that is invariant under the cyclic additive group of permutations generated
by $ A:i -> ~i+1 ~mod~n $. This group-invariance permits the parity-check
equations to be transformed to a set of equivalent equations over
an extension field. A general theorem shows that any set of equations that
is invariant under the action of a group that can be represented by a linear
permutation group on some extension field can be similarly transformed. The
application of the theorem focuses on a class of codes that have parity-check
equations invariant under the group generated by a subgroup of A and a
subgroup of the multiplicative group
$ M:i -> 2 sup k i $. Generally these codes are quasi-cylic rather than
cyclic and are organized into multiple shorter cycles.
The Fourier transform transforms the
action of the additive group, and a $linearized ~ polynomial ~ transform $
transforms the action of
the multiplicative group. The form of the transformed code
equations permits a BCH-like bound on the minimum distance of the code.
The techniques are illustrated by the construction of several codes that
are decodable by the Berlekamp-Massey algorithm and that have parameters
that approach or surpass those of the best codes listed in [13].
.nf
\fBUCSC-CRL-86-13
TOWARDS AUTOMATIC MOTION CONTROL\fR
Jane Wilhelms
June, 1986
23 pages
($3.00)
.fi
\fBABSTRACT:\fR Motion control for computer animation is a rich area for new
research. The trend toward greater complexity animation makes
the development of more convenient and automatic methods of
motion control important. Most commonly used motion control
methods, such as keyframing and scripts, require a great deal
of user effort to design acceptable animations. More automatic
methods of motion control will allow the production of
sophisticated animation with less user effort. Automatic
methods worth investigating include dynamic analysis, path planning
and collision avoidance, stimulus-response control, and learning
algorithms.
.nf
\fBUCSC-CRL-86-14
USING DYNAMIC ANALYSIS FOR REALISTIC ANIMATION OF ARTICULATED BODIES\fR
Jane Wilhelms
June, 1986
46 pages
($4.00)
.fi
\fBABSTRACT:\fR A major problem in computer animation
is creating motion that appears
natural and realistic, particularly in the case of complex articulated
bodies such as humans and other animals. At present, truly lifelike motion
is produced mainly by copying recorded images, a tedious and lengthy
process requiring considerable external equipment. An alternative
that is explored here is the use of \fIdynamic analysis\fR to
predict realistic motion. Using dynamic motion control, bodies are treated
as masses acting under the influence of external and
internal forces and torques. Dynamic control is advantageous
because motion is more naturally restricted to physically-realizable
patterns, and many types of motion can be automatically predicted.
Use of dynamics suffers from problems of computational cost
and the difficulty of specifying controlling forces and torques.
However, evidence has accumulated that dynamics does offer hope
for more realistic, natural, and automatic motion control.
Because such motion simulates real world conditions, an animation
system using dynamic analysis is also a useful tool in such
related fields as robotics and biomechanics.
.bp
.nf
\fBUCSC-CRL-86-15
Joint and LPA*: COMBINATION OF APPROXIMATION AND SEARCH\fR
Daniel Ratner
Ira Pohl
June, 1986
14 pages
($2.00)
.fi
\fBABSTRACT:\fR This paper describes two new algorithms, Joint and LPA*,
which can be used to solve difficult combinatorial problems heuristically.
The algorithms find reasonably short solution paths and are very fast.
The algorithms work in polynomial time in the length of the solution.
The algorithms have been benchmarked on the 15-$ puzzle $, whose
generalization has recently been shown to be NP hard, and outperform
other known methods within this context.
.nf
\fBUCSC-CRL-86-16
$ N times N $ - PUZZLE and RELATED RELOCATION PROBLEM\fR
Daniel Ratner, Manfred Warmuth
($4.00)
.fi
\fBABSTRACT:\fR The 8-puzzle and the 15-puzzle have been used for many
years as a domain for testing heuristic search techniques. From
experience it is known that these puzzles are "difficult" and
therefore useful for testing search techniques. In this paper
we give strong evidence that these puzzles are indeed good test problems.
We extend the 8-puzzle and the 15-puzzle to an $ n times n $ board
and show that finding a shortest solution for the extended puzzle
is NP-hard and thus computationally infeasible.
We also present an approximation algorithm for transforming boards that
is guaranteed to use no more than $ c~cdot~L~( SP ) $ moves, where
$ L~( SP ) $ is the length of a shortest solution and $ c $ is a
constant which is independent of the given boards and their size $ n $.
The studied puzzles are instances of planar relocation problems where
the reachability question is polynomial but efficient relocation
is NP-hard. These problems are natural robotics problems: a robot
needs to efficiently relocate packages in the plane. Our research
opens the study of polynomial approximation algorithms for
problems of this type.
.nf
\fBUCSC-CRL-86-17
REGISTER ALLOCATION VIA TWO COLORED PEBBLING\fR
Ashfaq A. Munshi, Karl M. Schimpf
July, 1986
13 pages
($2.00)
.fi
\fBABSTRACT:\fR We present a new polynomial time heuristic for register
allocation that does more than just allocation. It performs optimizations,
via code motion, along with generating the allocation. We partition
the allocation problem into two subproblems -- local and global.
The local allocation problem, that of allocating registers for basic
blocks, is viewed as a pebble game played on graphs where one type of
pebble registers while another type represents memory locations. Using
this approach we are able to give a heuristic that is independent of
the textual ordering of the code and is intelligent in its choice
of spilling computations. The heuristic depends only on the data
dependences present in the program. The global allocation problem,
that of integrating the local allocations to yield a global
allocation, is performed by examining the flow graph of the program
and propagating local information appropriately. We provide a
comparison of our heuristic against Chaitin's graph coloring
scheme on a set of computation benchmarks known as the Lawrence
Livermore Loops. It can be concluded from the data that our
heuristic technique is superior to Chaitin's when the number of
available registers is small. As the number of registers increases,
the two approaches give virtually identical results.
.bp
.nf
\fBUCSC-CRL-86-18
A UNIFYING MODEL FOR LOOK-AHEAD LR PARSING\fR
Manuel E. Bermudez, Karl M. Schimpf
August, 1986
10 pages
($1.00)
.fi
\fBABSTRACT\fR We present a construction method
for look-ahead LR parsers, that unifies
many of the construction algorithms available in the literature, and
describes them with a single notation. The model allows single,
multiple and arbitrary symbol look-ahead. The construction method is
based on three user-supplied parameters; specific settings for these
parameters yield well-known grammar classes such as $ LALR ( k )^,~SLR ( k ) $,
and certain subsets of the $ LR - Regular $ class, among others. The
three parameters also serve to illustrate trade-offs between
parsing power and construction termination. The model captures the
essence of the problem of computing look-ahead for LR parsers, and
provides a better understanding of the relationships among these classes.
.nf
\fBUCSC-CRL-86-19
AN APPROXIMATION METHOD FOR TANDEM QUEUES WITH BLOCKING\fR
Alexandre Brandwajn, Yung-Li Lily Jow
September, 1986
37 pages
($4.00)
.fi
\fBABSTRACT:\fR In this paper, we propose an approximate analysis
of open systems of tandem queues with blocking caused by finite
buffers between servers. Our approach relies on the use of
marginal probability distributions ("state equivalence")
coupled with an approximate evaluation of the conditional
probabilities introduced through the equivalence. The method
iterates over consecutive parts of servers using the solution
of a two queue system as a building block. It produces
performance measures for individual servers as well as an
approximation to joint queue length probability distributions
for pairs of neighboring stations. Experience seems to indicate that
the number of iterations required grows moderately with the
number of nodes in the network. Examples are given to demonstrate
the accuracy and the convergence properties of the proposed
approximation.
Subject Classification - #683 Approximate Solution - #703 Open Tandem Queues
.nf
\fBUCSC-CRL-86-20
A PROPOSED TOOL FOR PARALLEL PROGRAMMING MULTIPLE 3081/E's\fR
Brian F. Hanks, Charles E. McDowell
July, 1986
11 pages
($2.00)
.fi
\fBABSTRACT:\fR In an effort to make use of the
parallelism available with the addition of one
or more
3081/E's to the UCSC-CRL IBM 4381 system, it would be desirable to extend
the FORTRAN
language with constructs for task creation, synchronization, and communication.
These extensions will make the 3081/E more accessible to the user community,
as well as improve the portability of programs written using the system.
This will make it possible for the user to write a program using only the
parallel extensions, without having to worry about the low level details of the
3081/E.
This report will describe how a small set of primitives
can be translated using a preprocessor
into standard FORTRAN with calls to existing routines for
communication with the 3081/E.
In addition some problems resulting from the star topology of the system
and the inability of a 3081/E to interrupt the 4381 will be discussed.
.bp
.nf
\fBUCSC-CRL-86-21
A PRACTICAL ARBITRARY LOOK-AHEAD LR PARSING TECHNIQUE\fR
Manuel E. Bermudez, Karl M. Schimpf
September, 1986
10 pages
($1.00)
.fi
\fBABSTRACT:\fR We present a practical technique
that provides an $ LR $ (0) parser
with either fixed or arbitrary look-ahead. The construction algorithm
is based on certain paths in the $ LR $ (0) state diagram, which
must be restricted to a maximum length $ m $. The technique
determines the amount of look-ahead required, and the user is
spared the task of guessing it. Instead, the user provides $ m $.
In situations where single symbol look-ahead is sufficient, the
corresponding grammar class (called $ LAR~( m ) $) is identical
to the $ NQLALR $ (1) class. For practical grammars that require
arbitrary look-ahead, the storage requirements typically do not exceed
an amount linear in the size of the corresponding $ LR $ (0) parser.
The technique is shown to work for a practical programming language
grammar, and has been used to solve particular cases of the PL/1
keyword problem.
.nf
\fBUCSC-CRL-86-22
EPSILON-NETS AND SIMPLEX RANGE QUERIES\fR
David Haussler, Emo Welzl
July, 1986
34 pages
($4.00)
.fi
\fBABSTRACT:\fR We demonstrate the existence of data
structures for half-space and simplex
range queries on finite point sets in $ d - $dimensional space,
$ d~\(>=~2 $, with linear storage and $ O~( n sup alpha ) $ query
time, $ alpha~=~{ d ( d - 1 ) } over { d ( d - 1 )~+~1 }~+~gamma $,
for all $ gamma > 0 $. These bounds are better than those previously
published for all $ d \(>= $ 2. Based on ideas due to Vapnik and
Chervonenkis, we introduce the concept of an $ epsilon - roman net $
of a set of points for an abstract set of ranges and give sufficient
conditions that a random sample is an $ epsilon - roman net $ with
any desired probability. Using these results, we demonstrate how
random samples can be used to build a partition-tree structure that
achieves the above query time.
\fB Keywords:\fR range search, Vapnik-Chervonenkis classes,
random sampling
.nf
\fBUCSC-CRL-86-23
SCATTERED DATA APPROXIMATION BASED ON DELAUNAY TESSELLATION\fR
Kyoya Tsutsui
September, 1986
63 pages
($4.00)
.fi
\fBABSTRACT:\fR A solution for the problem of
approximating a data distribution
based on time varying data measured at scattered points in
three-dimensional space is presented.
The solution method tessellates the whole space with Delaunay tetrahedra
using only recent data points.
Reliability and efficiency of the solution method are analyzed.
A stochastic, Poisson model is presented to describe the distribution of
data points in space and time.
An error bound analysis of the Delaunay
tessellation approximation scheme is
presented.
Two algorithms, for incremental addition and incremental deletion
of a data node, are described.
Experimental results are illustrated by
exhibits of contour surfaces computed
upon a space that has been tessellated from pseudo-random data.
.bp
.nf
\fBUCSC-CRL-86-24
ON THE (NON) RELATIONSHIP BETWEEN SLR(1) AND NQLALR(1) GRAMMARS\fR
Manuel E. Bermudez, Karl M. Schimpf
October, 1986
5 pages
($1.00)
.fi
\fBABSTRACT:\fR A popular but "not-quite" correct technique for
computing LALR(1) look-ahead sets has been formalized by
DeRemer and Pennello, and dubbed NQLALR(1). They also claim that
the class of SLR(1) grammars is a subset of the class of NQLALR(1)
grammars. We prove here that no such relationship exists between
those two classes. We do so with a counterexample that, ironically,
appeared in DeRemer and Pennello's own paper.
.nf
\fBUCSC-CRL-86-25
QUANTIFYING INDUCTIVE BIAS IN CONCEPT LEARNING\fR
David Haussler
November, 1986
37 pages
($4.00)
.fi
\fBABSTRACT:\fR We show that the notion of
bias in inductive concept learning can be quantified in
a way that directly relates to learning performance, and that this
quantitative theory of bias can provide guidance in the design of
effective learning algorithms.
We apply this idea by measuring some common language biases,
including restriction to conjunctive concepts, conjunctive concepts
with internal disjunction
and $k$-DNF concepts, and
guided by these measurements, develop learning algorithms for these
classes of concepts that have provably good convergence properties.
.nf
\fBUCSC-CRL-86-26
A MODEL OF CACHED I/O\FR
\fRAlexandre Brandwajn
October, 1986
19 pages
($2.00)
.fi
\fBABSTRACT:\fR This study deals with analytical
modelling of path contention in a
cached disk controller. To present cache hits and disk accesses, we
propose a model of "wait and rejection" as an extension of the loss-system
model applied in the literature to non-cached I/O. We present a simple
solution of such a model using the technique of state aggregation
(equivalence and decomposition). The model produces an estimate of the
average path wait and of the probability of an RPS miss.
A simple method is proposed for the estimation of device queueing
whereby path waits are included as part of the I/O service time.
The expected queueing time for device availability is obtained by
viewing the device as an M/G/1 queue with a coefficient of
variation estimated from the components of the device busy time.
A comparison of model results with those of discrete-event simulations
indicates that the accuracy is generally fair with a tendency, under
higher loads, to underestimate the device queueing. Needed model
improvements are proposed for high device utilizations with very
high read hit ratios.
.bp
.nf
\fBUCSC-CRL-86-27
A NEW DISTANCE METRIC ON STRINGS COMPUTABLE IN LINEAR TIME\fR
Andrzej Ehrenfeucht, David Haussler
October, 1986
11 pages
($2.00)
.fi
\fBABSTRACT:\fR We describe a new metric for sequence comparison
that emphasizes global similarity over sequential matching at the
local level. It has the advantage over the Levenshtein metric that
strings of lengths $ n $ and $ m $ can be compared in time
proportional to $ n~+~m $ instead of $ nm $. Various
mathematical properties of the metric are established.
\fBKeywords:\fR sequence comparison, string matching, partial match,
distance metric, clustering, text processing, editing, spelling
correction
.nf
\fBUCSC-CRL-86-28
QUASI-MONOTONIC SEQUENCES: Theory, Algorithms and Application\fR
A. Ehrenfeucht, J. Haemer, David Haussler
November, 1986
20 pages
($2.00)
.fi
\fBABSTRACT:\fR We present a simple algebraic theory which allows
us to solve a variety of combinatorial problems, including the
problem of finding convex hulls in two dimensions, the "Trip
Around the Moon" problem, a version of the ballot problem, and
the problem of enumerating and randomly generating ordered trees
of a given size. Individual problems are solved by applying
general algorithms and theorems developed within this algebraic theory.
.nf
\fBUCSC-CRL-87-1
LEARNING CONJUNCTIVE CONCEPTS IN STRUCTURAL DOMAINS\fR
David Haussler
February, 1987
27 pages
($3.00)
.fi
\fBABSTRACT:\fR We study the problem of learning
conjunctive concepts from examples
on structural domains like the blocks world.
This class of concepts is formally defined
and it is shown that even for samples in which each
example (positive or negative) is a two-object scene it is
NP-complete to determine if there is any concept in this class that
is consistent with the sample. We demonstrate how this result affects the
feasibility of Mitchell's version space approach and how
it shows that it
is unlikely that this class of concepts is polynomially learnable from
random examples in the sense of Valiant. On the other hand, we show
that this class is polynomially learnable in the sense of Valiant for scenes
containing a constant number of objects if we allow a larger
hypothesis space. We also calculate the Vapnik-Chervonenkis
dimension of this class and thereby show that heuristic
methods, when they succeed in finding a relatively simple
conjunctive hypothesis
consistent with a large enough random
sample, are likely to give an accurate hypothesis.
.bp
.nf
\fBUCSC-CRL-87-2
MANIKIN: DYNAMIC ANALYSIS FOR ARTICULATED BODY MANIPULATION
\fRJane Wilhelms, David Forsey, Pat Hanrahan
April, 1987
29 pages
($3.00)
.fi
\fBABSTRACT:\fR Manipulating articulated bodies for
animation is a laborious task
because of the many degrees of freedom, the interaction between
segments, and the complex relationship between local and world space.
Dynamic analysis model articulated bodies as rigid masses acting
under the influence of forces and torques and simulates their
behavior. This method automatically accounts for interaction between
segments and the relation between local and world space. It can
provide inverse kinematics, goa-directed movement, and constraints.
Because of complex control issues, dynamics is not yet reasonable
for total motion control, but it is a convenient way to manipulate
articulated bodies for keypositioning. While not realtime, it is fast
enough for interactive use by a patient user. A system,
\fIManikin,\fP for manipulating bodies dynamically, is described.
\fBKeywords:\fR computer graphics, animation, character animation,
interactive modeling, dynamics, simulation.
.nf
\fBUCSC-CRL-87-3
AN ENVIRONMENT MODEL FOR THE INTEGRATION OF LOGIC AND FUNCTIONAL PROGRAMMING\fR
Pierre Bonzon
January, 1987
37 pages
($4.00)
.fi
\fBABSTRACT:\fR We propose a unified environment
model for the evaluation of both function
and relation (or predicate) applications; as an illustration, simple
extensions of a subset of Scheme (i.e. a Lisp dialect) are introduced,
together with their interpreter.
.nf
\fBUCSC-CRL-87-4
SHOULD ROBOTS HAVE NUCLEAR ARMS?\fR
Ira Pohl
March, 1987
9 pages
($1.00)
.fi
\fBABSTRACT:\fR
This paper analyzes the use of Artificial Intelligence (AI) in designing
SDI software. Two major uses are foreseen: (1) as an aid to writing
the ten million plus lines of trustworthy SDI software that will be
needed; (2) as a component of the battle management software. This
second use allows the software to be adequately responsive to SDI
countermeasures and autonomous in a manner fitting overrall SDI
requirements. This paper suggests that these uses of AI in SDI are
infeasible and that rather than creating greater security, they would
be more likely lead to a nuclear war.
.bp
.nf
\fBUCSC-CRL-87-5
LANGUAGE PRIMITIVES FOR PARALLEL NUMERICAL ALGORITHMS\fR
Charles McDowell, William Appelbe, Alan Finke
May, 1987
18 pages
($2.00)
.fi
\fBABSTRACT:\fR This paper describes a set of
high-level language extensions for
designing and implementing
parallel algorithms composed of tightly coupled tasks.
The extensions have been implemented for Fortran
using a preprocessor (written in m4 for UNIX $ \(dg $ )
to generate HEP Fortran, and used to
implement a wide range of numerical Fortran programs.
A static analyzer for programs written using the primitives is being
developed to locate potential bugs in parallel programs such as
concurrent variable updates.
.PP
The primitives provide a flexible set of high-level mechanisms,
to simplify the task of
developing reliable, portable, parallel numerical software.
.nf
\fBUCSC-CRL-87-6
DYNAMICS FOR EVERYONE\fR
Jane Wilhelms
May, 1987
26 pages
($3.00)
.fi
\fBABSTRACT:\fR There is a move in computer
graphics toward more correctly simulating
the world being modeled in hopes of achieving more realistic and
interesting still images and animation. An important component of this
move is use of dynamics, i.e. considering the world as masses acting
under the influence of forces and torques. Dynamics an be useful in
providing inverse kinematics, constraints, collisions, and, in general,
help produce realistic positions and rates of motion. However, it is
computationally expensive, involved to program, and complex to control.
.nf
\fBUCSC-CRL-87-7
ALGEBRAIC CONSTRUCTION OF LARGE EUCLIDEANDISTANCE
COMBINED CODING/MODULATION SYSTEMS\fR
R. Michael Tanner
June, 1987
48 pages
($4.00)
.fi
\fBABSTRACT:\fR Ideas underlying Ungerboeck's
trellis codes and Ginzburg's multidimensional
signals are extended, providing new methods for constructing power and
bandwidth efficient signal sets. Appropriately linking subspaces of an
unequal error protection algebraic code with partitioned signals indexed
by subspaces of digital vector spaces guarantees a large minimum separation
between signals in the resulting signal set. Analogies are drawn with
algebraic block error-correcting code constructions such as those of
Blokh and Zyablov. For PSK modulations, the "layered" constructions
shown have the additional advantage of making the effects of a phase
ambiguity "transparent" to the decoding process, permitting efficient
resolution of the ambiguity. Practical high-speed decoders can be
implemented using low-complexity soft decision decoding algorithms of
Tanner. Simulation studies of one such system show better than 6 dB.
of gain over 8-PSK at an operating SNR of 13 dB. with a rate 0.83 code.
.bp
.nf
\fBUCSC-CRL-87-8
GAP THEOREMS FOR DISTRIBUTED COMPUTATION\fR
Shlomo Moran, Manfred Warmuth
January, 1987
18 pages
($2.00)
.fi
Consider a ring of $ n $ anonymous processors,
i.e. the processors have no id's. Each processor receives an
input string and the ring is to compute a function of the circular
input configuration in the asynchronous bidirectional model
of computation. The complexity of an algorithm is the number
of bits or the number of messages sent in the worst case. The
complexity of a function is the lowest complexity of any
algorithm that computes that function. If the function value
is constant for all input configurations, the processors do
not need to send any messages (complexity zero). On the
other hand, we prove that any non-constant function has bit
complexity $ OMEGA~( n log n ) $ for anonymous rings. There
are non-constant functions that reach the upper end of the
gap, i.e., we exhibit a non-constant function of bit complexity
$ O~( n log n ) $.
The same gap for the bit complexity of non-constant functions
remains even if the processors have distinct id's, provided
that the id's are taken from a large enough domain.
For the case of using the number of messages sent rather
than the number of bits as the complexity measure, we
present a non-constant function that can be computed with
$ O~( n^ log sup +~n ) $ messages on an anonymous ring.
.nf
\fBUCSC-CRL-87-9
c-util UTILITY PACKAGE FOR C\fR
Kevin Karplus
July, 1987
17 pages
($2.00)
.fi
\fBABSTRACT:\fR The c-util package is a collection of c procedures and
macros for general-purpose programming. The package is intended
to be used in addition to the standard c library, not in place of it.
The package handles the following common tasks:
.nf
\(bu Memory allocation
\(bu Error-handling and general-purpose printing
\(bu Character input and output
\(bu String manipulation
\(bu Set manipulation
\(bu Program argument handling
.nf
\fBUCSC-CRL-87-10
USING THE UCSC-REPORT LaTeX STYLE FILE FOR UCSC TECHNICAL REPORTS\fR
Kevin Karplus
August, 1987
17 pages
($2.00)
.fi
\fBABSTRACT:\fR This technical report describes how to use LaTeX
to produce technical reports in the proper format for the UCSC
Computer and Information Science series. 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 \fILaTeX, a Document
Preparation System\fP [Lam86] for details on how to use LaTeX.
.bp
.nf
\fBUCSC-CRL-87-11
APPLYING VALIANT's LEARNING FRAMEWORK TO AI CONCEPT LEARNING PROBLEMS\fR
David Haussler
September, 1987
22 pages
($3.00)
.fi
\fBABSTRACT:\fR We present an overview of some
recent theoretical results in the learning
framework introduced by Valiant in (Valiant, 1984) and further developed in
(Valiant 1985; Blumer, et. al., 1986, 1987a,b;
Pitt & Valiant, 1986; Haussler, 1986;
Angluin & Laird, 1986; Angluin, 1986a; Rivest, in press; Haussler, 1987a;
Kearns, et. al., 1987a,b).
Our focus is on applications
to AI problems of learning from examples as given in (Haussler, 1986, 1987a) and
(Kearns, et. al., 1987a,b), along with a comparison to the work
of Mitchell on version spaces
(Mitchell, 1982). We discuss learning problems for both
attribute-based and structural domains.
This is a revised and expanded version of (Haussler, 1987b).
.nf
\fBUCSC-CRL-87-12
A DATABASE APPLICATION FOR THE SPECIFICATION OF COMPUTER GENERATED IMAGES
\fRJames L. Murphy
October, 1987
15 pages
($2.00)
.fi
\fBABSTRACT:\fR There are several renderers available which generate three-dimensional scenes according to some specification. A ray tracing system, rt, from the University of Waterloo uses a scene file prepared in an editor to specify lights, surface c
haracteristics, and primitive objects placed in a directed acyclic graph to support hierarchical modeling. An interactive ray tracing system, Optik, from the University of Toronto, allows objects, lights and surfaces to be added to a scene and transforme
d via commands given interactively or redirected from a text file. An interactive scan line system, 3d, also from the University of Toronto, allows instances of masters including spheres, cylinders, polygons, and parametric patches to be added to a scene
and altered via commands given interactively or redirected from a text file.
This paper presents an overview of scene specification as defined in these three renderers and then proposes a database and application programs to manage image files and their scene specifications independent of renderer. This database supports a graphi
cs interface which allows a user to interactively specify a three dimensional scene using specifications of previously generated images. The user is allowed to find pictures by content and browse through qualifying images.
.nf
\fBUCSC-CRL-87-13
AN APPROXIMATION ALGORITHM AND AN OPTIMAL
ALGORITHM FOR FINDING VERTEX COVERS\fR
Robert A. Levinson
October, 1987
11 pages
($2.00)
.fi
\fBABSTRACT:\fR An approximation algorithm for the vertex covering problem for cubic graphs is presented. The algorithm has worst case complexity n\u4\d where n is the number of vertices in the graph. The algorithm is based on finding vertex coverings
based on breadth-first spanning trees starting from individual vertices and pairs of vertices. Despite the fact that this problem is NP-complete, this polynomial time algorithm has not yet failed to produce an optimal solution. An obvious, yet often eff
icient branch-and-bound algorithm is also presented for finding vertex covers on arbitrary graphs.
.bp
.nf
\fBUCSC-CRL-87-14
A SIMPLE MODEL OF AN AUTOMATED LIBRARY SYSTEM
\fRAlexandre Brandwajn
November, 1987
10 pages
($1.00)
.fi
\fBABSTRACT:\fR An Automated Library System for data storage in a computer
installation can be viewed as a collection of items, such as
magnetic cartridges or optical disks, stored in a shelf-like structure, with one or more pickers (robots) to pick the requested item and place it in a processing station (player). This note presents a simple analytical model which allows us to evaluate t
he performance of such a library system for a given I/O workload
as a function of the number and characteristics of robots and players.
.nf
\fBUCSC-CRL-87-15
LEARNING DECISION TREES FROM RANDOM EXAMPLES
\fRAndrzej Ehrenfeucht, David Haussler
October, 1987
9 pages
($1.00)
.fi
\fBABSTRACT:\fR We show that \fIs\fR-node decision trees on \fIn\fR Boolean variables are learnable from random examples
in time proportional to \fIn\fR\(u0(logs)\(d. The procedure is linear in 1/\(*e and log 1/\(*d, where \(*e is the accuracy parameter and \(*d the confidence parameter. We also define the rank of a decision tree
and show that for any fixed \fIr\fR, the class of all decision trees of
rank at most \fIr\fR on \fIn\fR Boolean variables is
learnable from random examples in time polynomial in
\fIn\fR, 1/\(*e and log 1/\(*d. Using
a suitable encoding of variables, Rivest's polynomial learnability result for decision lists can be interpreted as a special case of this result for rank 1.
.nf
\fBUCSC-CRL-87-16
ASPECTS OF PATH SHARING IN I/O
\fRAlexandre Brandwajn
November, 1987
20 pages
($2.00)
.fi
\fBABSTRACT:\fR We consider two problems abstracted from the sharing of I/O transfer paths by disks with Rotational Position Sensing.
Both problems are related to the idea of partitioning a set of available resources into different numbers of servers of different speeds.
First, we propose a simple model for the reconnection to a set of buffers ports in a control unit supporting asynchronous disk I/O.
The model, based on a classical loss queueing
system, allows us to investigate the relative performance
merits of sequential versus overlapped organization of read transfers.
The results obtained show that, as the I/O throughput increases, it is possible for the
performance of overlapped I/O to become worse than that of sequential accesses. This is due to the fact that overlapped transfers experience a lower probability of
finding a free buffer port, caused by the pattern of resource acquisition.
In the second part of this paper, we consider a model of a bus bandwidth shared by transfers proceeding
at different speeds. The problem is a generalization of a multiserver loss system with classes of
requests in that the available bandwidth is partitioned into a varying number of "channels". We propose a simple solution for this model, and apply it to study the effects of different data transfer rates on the performance of two groups of disks sharing
a bus.
Comparisons with simulation results illustrate the generally good accuracy of the proposed models.
.nf
.bp
\fBUCSC-CRL-87-17
DASD DYNAMIC RECONNECTION
\fRAlexandre Brandwajn
November, 1987
20 pages
($2.00)
.fi
\fBABSTRACT:\fR With Dynamic Path Reconnection (DPR), a disk can reconnect to any available I/O path leading to the proper host system. Herein, we focus our attention on systems with Dynamic Reconnection because we believe that they represent a majority
of new installations.
Measurements of actual DASD subsystems show that there is often a considerable
imbalance in the load, i.e., rates of I/Os and, possibly, other I/O characteristics, among
strings of disks, as well as among devices of a single string. This can be the case when a small subset of drives accounts for much of the string activity ("dominant devices"),
and could also be expected in strings mixing single and multiple capacity DASDs. Therefore, it is important to be able to accurately represent multipath DPR configurations with imbalanced load.
The approach we propose is based on modeling reconnection attempts as requests in a loss system. Extensive comparisons with simulation show that our approach produces
consistently more accurate results than existing methods. It is also easily applicable to configurations with more than two paths (such as the
four-ported IBM 3990 controller).
.nf
\fBUCSC-CRL-87-18
A GENERAL MODEL FOR FIXED LOOK-AHEAD LR PARSERS
\fRManuel Bermudez, Karl Schimpf
November, 1987
32 pages
($4.00)
.fi
\fBABSTRACT:\fR A single construction method for SLR, LALR, NQLALR and NQSLR parsers is presented. The latter two are generalizations of NQLALR(1) grammars, defined for the first time here. The construction method is based on two relations that capture
the essential structure of the problem of computing fixed look-ahead for LR parsers. These relations capture both the similarities and the differences among the various techniques, which have been misunderstood in the past. Three parameters are used to
specify the type of parser to be constructed and the amount of look-ahead to be used.
.nf
\fBUCSC-CRL-87-19
A FLEXIBLE OBJECT ANIMATION SYSTEM
\fRMatthew P. Moore
November, 1987
75 pages
($4.00)
.fi
\fBABSTRACT:\fR A software system is developed for animating the motion of flexible objects. Objects are described as collections of point masses, acted upon by forces from springs, pressurized volumes, hard surfaces, gravity, and other aspects of the e
xternal environment. The dynamic equations of motion for the point masses are described as a system of ordinary differential equations, which is solved numerically for the objects' positions in each animation frame. Provisions are made for real-time pre
view of the resulting motion, and for full rendering of the resulting movie onto video tape.
.bp
.nf
\fBUCSC-CRL-87-20
LEARNABILIBY AND THE VAPNIK-CHERVONENKIS DIMENSION
\fRAnselm Blumer, Andrzej Ehrenfeucht,
David Haussler, Manfred K. Warmuth
November, 1987
34 pages
($4.00)
.fi
\fBABSTRACT:\fR We extend Valiant's learnability model to learning classes of concepts defined by regions in Euclidean space E\un\d. Our methods lead to a unified treatment of some of Valiant's results, along with previous results on distribution-free c
onvergence of certain pattern recognition algorithms. We show that the essential condition for distribution-free learnability is finiteness of the Vapnik-Chervonenkis dimension, a simple combinatorial parameter of the class of concepts to be learned. Us
ing this parameter, we analyze the complexity and closure properties of learnable classes, and provide necessary and sufficient conditions for feasible learnability.
.nf
\fBUCSC-CRL-87-21
CONVOLUTIONAL CODES FROM QUASI-CYCLIC CODES:
A LINK BETWEEN THE THEORIES OF BLOCK AND CONVOLUTIONAL CODES
\fRR. Michael Tanner
November, 1987
34 pages
($4.00)
.fi
\fBABSTRACT:\fR This paper extends the work of Massey, Costello, and Justesen by giving a method of constructing convolutional
code with large free distances algebraically. A convolutional code can be defined by a
syndrome former transfer matrix \fBH\fR \uT\d (D) whose entries are polynomials in the
indeterminate delay operator D. A quasi-cyclic block code with cycles of length \fIm\fR can be
defined by a parity-check matrix that consists of blocks of \fIm\fR X \fIm\fR circulant matrices;
such a matrix is characterized by a polynomial matrix \fBH\fR \uT\d\dm\u (X) with entries in the ring of polynomials modulo (X\um\d -1). A quasi-cyclic code is associated with a convolutional code by setting
\fBH\fR\uT\d\dm\u (X) = \fBH\fR\uT\d(D)\(br\dD=X\umod (X\um\d -1). The
main theorem shows that the minimum distance of the quasi-cyclic code is lower bound on the free distance of the associated convolutional code. The relation between the rates of the two codes is analyzed, and examples of construction of convolutional cod
es from cyclic codes in quasi-cyclic form are given.
.nf
\fBUCSC-CRL-87-22
A SURVEY OF DEBUGGING TOOLS FOR CONCURRENT PROGRAMS
\fRCharles McDowell, David Helmbold, Anil Sahai
December, 1987
65 pages
($4.00)
.fi
\fBABSTRACT:\fR This report presents a survey of tools used to aid in debugging concurrent programs. Three
types of systems are surveyed: traditional or breakpoint style debuggers, event monitoring systems, and static analysis systems.
It does not discuss formal proofs of correctness or functional testing and
verification.
Three problems associated with debugging concurrent programs are discussed. They are the "probe-effect", non-repeatability and the lack of a synchronized global
clock. In addition, techniques for filtering, organizing and displaying the large amount of data produced by monitoring are discussed.
A table summarizing the characteristics of 28 different debugging tools, and
an annotated bibliography of papers are included in the appendices.
.bp
.nf
\fBUCSC-CRL-87-23
A PRACTICAL ALGORITHM FOR STATIC ANALYSIS OF PARALLEL PROGRAMS
\fRCharles E. McDowell
December, 1987
24 pages
($3.00)
.nf
\fBUCSC-CRL-87-24
MANAGING DIGITAL IMAGES IN A NETWORK ENVIRONMENT
\fRJames Murphy, Daniel Helman, Lewis Hitchner
December, 1987
10 pages
($1.00)
.fi
\fBABSTRACT:\fR We present a method for displaying reduced resolution versions
of images in order to quickly browse through a large archive of digital images.
The browse image requires only one kilobyte and, thus, can be stored in the header of the image
file and can be quickly retrieved from that disk file and transferred over a
network for viewing on a high resolution image display.
This method differs from past research on progressive transmission of reduced resolution images.
Our browse image, the displayed image, and the original image are all of different spatial and color resolutions.
Typical values would be a 32x32 by 8 bit encoded color browse image from a 512x512 by 24 bit full color original to be displayed at 128x128 full color.
We analyze and compare several methods of compression and decompression of digital images reporting
their performance on both isolated workstations and over the network.
.nf
\fBUCSC-CRL-87-25
INTELLIGENT SIGNAL ANALYSIS AND RECOGNITION USING A SELF ORGANIZING DATABASE
\fRRobert Levinson, Daniel Helman, Edward Oswalt
December, 1987
23 pages
($3.00)
.fi
\fBABSTRACT:\fR In this report, we describe our progress in the research and development of a self-organizing database system that can
support the identification and characterization of signals in an RF
environment. This report is for the first-year of a three-year plan to develop such a system. As the radio frequency spectrum becomes more crowded, there are a growing number of situations that require a characterization of the RF environment. This dat
abase system is designed to be practical in applications where communications and other instrumentation encounter a time varying and complex RF environment.
The primary application of this system is the guidance and control of NASA's SETI (Search for Extra-Terrestial Intelligence) Microwave Observing Project.
Other possible applications include selection of telemetry bands for communication with spacecraft, and the scheduling of antenna
for radio astronomy are two examples where characterization of the RF
environment is required. In these applications, the RF environment is constantly changing,
and even experienced operators cannot quickly identify the multitude of signals that can be encountered.
Some of these signals are repetitive, others appear to occur sporadically.
.nf
\fBUCSC-CRL-87-26
A GENERAL LOWER BOUND ON THE NUMBER OF EXAMPLES NEEDED FOR LEARNING
\fRAndrzej Ehrenfeucht, David Haussler
Michael Kearns, Leslie Valiant
December, 1987
12 pages
($2.00)
.nf
\fBUCSC-CRL-87-27
LEARNING IN THE PRESENCE OF BACKGROUND KNOWLEDGE
\fRAleksandar Milosavljevic
December, 1987
32 pages
($4.00)
.fi
\fBABSTRACT:\fR We discuss the efficiency of learning algorithms for conjunctive concepts in the presence of background knowledge.
In contrast to the standard learning setting in which instances are points in
{0,1}\fI \un\d \fR (e.g. [VAL 84], [H2 87]), we use a \fIuniform learning setting\fR in which both instances, background knowledge,
and hypotheses are represented as conjunctions of clauses.
Consequently, instances in our setting are subsets of {0,1}\fI\un\d\fR.
Efficient learning algorithms exist if instances and background knowledge are represented by Horn-sentences with no more than \fIk\fR literals
per clause for any fixed \fIk\fR, or arbitrary k-CNF formulae with \fIk\fR 2 literals per clause.
However, if examples or background knowledge are represented by k-CNF formulae for \fIk\fR 3, even classifying a new instance based on the current hypothesis becomes NP-hard.
We carry out our analysis in a variety of models of learning. Probabilistic off-line [VAL 84], mistake-bounded on-line [LI 87], and query [ANG 87] models of supervised learning are used. Unsupervised learning is analysed using the model of conceptual cl
ustering from [PR 87].
Our learning algorithms involve both deduction and induction.
The "tree-climbing heuristic" [MICH 83] [MS 83] turns out to be a special case of the deductive phase. No need arises for the "internal disjuction" restriction [H1 87] in our setting.
.nf
\fBUCSC-CRL-87-28
LEARNING QUICKLY WHEN IRRELEVANT ATTRIBUTES ABOUND:
A NEW LINEAR-THRESHOLD ALGORITHM
\fRNick Littlestone
December, 1987
30 pages
($4.00)
.fi
\fBABSTRACT:\fR Valiant and others have studied the problem of learning various classes of Boolean functions from examples.
Here we discuss incremental learning of these functions.
We consider a setting in which the learner responds to each example according to a current hypothesis.
Then the learner updates the hypothesis, if necessary, based on the correct classification of the example.
One natural measure of the quality of learning in this setting is the number of mistakes the learner makes.
For suitable classes of functions, learning algorithms are available that make a bounded number of mistakes, with the bound independent of the number of examples seen by the learner.
We present one such algorithm, which learns disjunctive Boolean functions, and variants of the algorithm for learning other classes of Boolean functions.
The algorithm can be expressed as a linear-threshold algorithm.
A primary advantage of this algorithm is that the number of mistakes that it makes is relatively little affected by the presence of large numbers of irrelevant attributes in the examples; we show that the number of mistakes grows only logarithmically wit
h the number of irrelevant attributes.
At the same time, the algorithm is computationally time and space efficient.
.nf
\fBUCSC-CRL-87-29
THE MEANING OF TSL -- AN ABSTRACT IMPLEMENTATION OF TSL-1
\fRDavid Helmbold
December, 1987
30 pages
($3.00)
.fi
\fBABSTRACT:\fR TSL is a language for specifying the inter-task communication which takes place in an Ada* program.
TSL statements are embedded in the program as formal comments, therefore they do not interfere with other Ada tools. The Ada program containing TSL comments is transformed into a valid Ada program which is functionally equivalent to the original with the
exception that its behavior is communicated to a monitor. At runtime, the monitor can check the specifications against the transformed program's behavior. This paper first presents the TSL language constructs and then introduces an abstract implementat
ion which defines the meaning of TSL statements.
* Ada is a registered trademark of the U.S. Government (Ada Joint Program Office).
.bp
.nf
\fBUCSC-CRL-87-30
SIZING cMOS GATES ALONG A CRITICAL PATH -- A TUTORIAL
\fRKevin Karplus
December, 1987
21 pages
($3.00)
.fi
\fBABSTRACT:\fR This technical report describes a simple method for sizing the gates on a single critical path of an MOS circuit, with particular attention to static cMOS circuits.
The method is not a new research result -- rather, it is a simplified presentation of known methods for pedagogic purposes.
The material should be suitable for a first course in VLSI design, and exercises are provided at the end.
.nf
\fBUCSC-CRL-87-31
A TO Z: C LANGUAGE SHORTCOMINGS
\fRIra Pohl
Daniel Edelson
November, 1987
18 pages
($2.00)
.fi
\fBABSTRACT:\fR C is one of the most popular generally used languages of the 1980's. Its advantages are well known. In writing three books on the language,
one of the authors has espoused many of its virtues without adequately commenting on its vices. This paper will attempt to redress that balance.
.(f
1-4-87
.)f