🚀 go-pugleaf

The University of Rochester
Computer Science Department
July 1992 Technical Report Abstract List

Listed below are the abstracts of our most recent technical reports.
Most of the TRs can be accessed by anonymous ftp from the host
ftp.cs.rochester.edu (user anonymous, password your_name) in the
directory pub/papers. The files are in compressed PostScript format.
(Use ftp binary mode.) The directory also contains recent abstract lists,
recent publications lists (by academic year), and a cumulative TR titles
list that indicates which TRs have been archived.

There is a nominal charge for hardcopies of each report. Checks (in US
dollars) should be made payable to the University of Rochester. The fee
is waived for libraries in non-profit, educational institutions and for
institutions with which we have exchange agreements. Send orders to:
TR Secretary, Computer Science Dept., 734 Computer Studies Bldg.,
University of Rochester, Rochester, New York, 14627-0226, USA. Hardcopies
can also be ordered electronically by sending email to tr@cs.rochester.edu;
we will enclose a bill with the reports.


%A Cezary Dubnicki and Thomas J. LeBlanc
%T Reconciling Sharing and Spatial Locality using Adjustable 
     Block Size Coherent Caches
%R TR 400 ($2.00; 41 pages; in pub/papers/systems)
%I URCSD
%D November 1991; revised February 1992
%K coherent caches; block size; scalable multiprocessors;
     sharing; spatial locality
%X Several studies have shown that the performance of coherent caches
depends on the relationship between the cache block size and the
granularity of sharing and locality exhibited by the program.
Large cache blocks exploit processor and spatial locality, but
may cause unnecessary cache invalidations due to false sharing.
Small cache blocks can reduce the number of cache invalidations,
but increase the number of bus or network transactions required
to load data into the cache. To reduce the performance impact of
a mismatch between the cache block size and the sharing pattern
exhibited by a given application, we propose to adjust the amount of data
stored in a cache line dynamically according to recent reference patterns.
In this scheme, cache blocks are split across cache lines when
false sharing occurs, and merged back into a single cache line to exploit
spatial locality. Results of simulations of a scalable multiprocessor
indicate that, over a range of applications, an adjustable block size cache
performs better than every fixed block size alternative. 
Moreover, for a given program, the adjustable block size cache is
comparable in performance to the best fixed block size cache for that program. 
We conclude that adjusting the block size in response to reference behavior
can significantly improve performance, especially when there is
variability in the granularity of sharing exhibited by applications.
%X 92.tr400.adjustable_block_size_caches.ps.Z

%A Nigel H. Goddard
%T The Perception of Articulated Motion: Recognizing Moving Light Displays
%R TR 405 and Ph.D. Thesis ($7.50; 171 pages; in pub/papers/ai)
%I URCSD
%D June 1992
%K moving light display; visual motion; cognitive modeling; attention;
     connectionist; recognition; visual sequence; temporal sequence
%X Recognition of motion sequences is a crucial ability for
biological and robot vision systems. We present an architecture
for the higher-level processes involved in recognition of
complex structured motion. The work is focused on modeling human recognition
of Moving Light Displays. MLDs are image sequences that contain
only motion information at a small number of locations.
Despite the extreme paucity of information in these displays,
humans can recognize MLDs generated from a variety of common
human movements. This dissertation explores the high-level representations
and computational processes required for the recognition task.
The structures and algorithms are articulated in the language of
structured connectionist models. The implemented network can
discriminate three human gaits from data generated by several actors.
.pp
Recognition of any motion involves indexing into stored models of movement.
We present a representation for such models, called scenarios,
based on coordinated sequences of discrete motion events. 
A method for indexing into this representation is described.
We develop a parallel model of spatial and conceptual attention that is
essential for disambiguating the spatially and temporally diffuse MLD data.
The major computational problems addressed are: (1) representation
of time-varying visual models; (2) integration of visual stimuli over time;
(3) gestalt formation in and between spatially-localized feature maps
and central movement representations; (4) contextual feedback
to lower levels; and (5) the use of attention to focus processing
on particular spatial locations and particular high-level representations.
Several novel connectionist mechanisms are developed
and used in the implementation.
.pp
In particular, we present advances in connectionist representation of
temporal sequences and in using high-level knowledge to control
an attentional mechanism. We show that recognition of gait can be
achieved directly from motion features, without complex shape information,
and that the motion information need not be finely quantized. 
We show how the "what" and "where" processes in vision can be tightly
coupled in a synergistic fashion. These results indicate the value
of the structured connectionist paradigm in modeling perceptual processes:
no previous computational model has accounted for MLD recognition
and we do not know how it would be approached in any other paradigm.
%X 92.tr405.moving_light_displays.ps.Z

%A H.E. Kyburg, Jr.
%A M. Pittarelli
%T Set-Based Bayesianism
%R TR 407 ($2.00; 41 pages; in pub/papers/ai)
%I URCSD
%D March 1992
%K uncertainty; decision-making; maximum entropy; Bayesian methods
%X Problems for strict and convex Bayesianism are discussed.
A set-based Bayesianism generalizing convex Bayesianism 
and intervalism is proposed. This approach abandons not only the strict
Bayesian requirement of a unique real-valued probability function 
in any decision-making context but also the requirement of convexity 
for a set-based representation of uncertainty. 
Levi's E-admissibility decision criterion is retained 
and is shown to be applicable in the non-convex case.
%X 92.tr407.set_based_bayesianism.ps.Z

%A Henry E. Kyburg, Jr.
%T Semantics for Probabilistic Inference
%R TR 408 ($2.00; 14 pages; in pub/papers/ai)
%I URCSD
%D April 1992 (revised)
%K uncertainty; probability; inference; models; semantics; 
     entailment uncertain inference; probabilistic inference
%X A number of writers (Joseph Halpern and Fahiem Bacchus among them)
have offered semantics for formal languages in which inferences
concerning probabilities can be made. Our concern is different.
This paper provides a formalization of non-monotonic inferences
in which the conclusion is supported only to a certain degree.
Such inferences are clearly "invalid" since they must allow
the falsity of a conclusion even when the premises are true. 
Nevertheless, such inferences can be characterized both syntactically
and semantically. The 'premises' of probabilistic arguments are sets
of statements (as in a database or knowledge base);
the conclusions categorical statements in the language.
We provide standards for both this form of inference, for which
high probability is required, and for an inference in which the
conclusion is qualified by an intermediate interval of support.
%X 92.tr408.semantics_prob_inference.ps.Z

%A Paul F. Dietz
%T Heap Construction in the Parallel Comparison Tree Model
%R TR 409 ($2.00; 10 pages; in pub/papers/theory)
%I URCSD
%D February 1992
%K heap; parallel algorithm; optimal time/processor product; min-max heap;
     parallel decision tree; randomized algorithm; Ackerman's function
%X This paper shows how to put n values into heap order in O(log log n) time
using $n/log log n$ processors in the parallel comparison tree model of
computation, and in $\~{O}(\alpha(n))$ time on $n/\alpha(n)$ processors,
in the randomized parallel comparison tree model, where $\alpha(n)$
is an inverse of Ackerman's function. Similar bounds are proven
for the related problem of putting n values into a min-max heap.
%X 92.tr409.heap_construction.ps.Z

%A E.P. Markatos
%A T.J. LeBlanc
%T Using Processor Affinity in Loop Scheduling on Shared-Memory Multiprocessors
%R TR 410 ($2.00; 31 pages; in pub/papers/systems)
%I URCSD
%D March 1992; revised June 1992
%K loop scheduling, locality management, load balancing, central workqueues 
%X Loops are the single largest source of parallelism in many applications.
One way to exploit this parallelism, and thereby minimize program
execution time, is to execute
loop iterations in parallel on different processors.
Traditional approaches to loop
scheduling  attempt to achieve the minimum completion time
by distributing the workload as evenly as possible,
while minimizing the number of synchronization operations required.
In this paper we  consider a third dimension to the problem of
loop scheduling on shared-memory multiprocessors:
communication overhead caused by accesses to non-local data.
We show that traditional algorithms for loop scheduling,
which ignore the location of data when assigning iterations to processors,
incur a significant performance penalty on
modern shared-memory multiprocessors.
We propose a new loop scheduling algorithm that
attempts to simultaneously balance the workload,
minimize synchronization, and co-locate
loop iterations with the necessary data.
We compare the performance of this new algorithm
to other known algorithms using five representative applications
on a Silicon Graphics multiprocessor workstation, a BBN Butterfly, 
and a Sequent Symmetry, and show that
the new algorithm offers substantial performance improvements,
up to a factor of 3 in some cases.
We conclude that loop scheduling algorithms
for shared-memory multiprocessors cannot afford to ignore
the location of data, particularly in light of the increasing
disparity between processor and memory speeds.
%X 92.TR410.loop_scheduling.ps.Z 

%A Robert J. Fowler and Leonidas I. Kontothanassis
%T Improving Processor and Cache Locality in Fine-Grain Parallel Computations
     using Object-Affinity Scheduling and Continuation Passing (Revised)
%R TR 411 ($2.00; 18 pages; in pub/papers/systems)
%I URCSD
%D June 1992
%K object affinity; scheduling; templates; continuation passing; Mercury
%X On recent high-performance multiprocessors, there is a potential
conflict between the goals of achieving the full performance potential
of the hardware and providing a parallel programming environment
that makes effective use of programmer effort.
On one hand, an explicit coarse-grain programming style
may appear to be necessary, both to achieve good cache performance
and to limit the amount of overhead due to context switching
and synchronization. On the other hand,
it may be more expedient to use more natural and finer-grain
programming styles based on abstractions such as task heaps,
light-weight threads, parallel loops, or object-oriented parallelism.
Unfortunately, using these styles can cause a loss of performance
due to poor locality and high overhead. 
We claim that the locality issue in fine-grain parallel programs
can be addressed effectively by using object-affinity scheduling
and that the overhead can be reduced substantially
by representing tasks as templates that are managed
using continuation-passing style mechanisms.
We present supporting evidence for these claims in the form of
experimental measurements of programs running on Mercury,
an object-oriented system implemented on an SGI 4D/480 multiprocessor.
%X 92.tr411.processor_cache_locality.ps.Z

%A Peter A. Sandon
%T Visually Guided Touching and Manual Tracking
%R TR 412 ($2.00; 33 pages; not available by anon. ftp)
%I URCSD
%D March 1992
%K visual attention; animate vision; differential kinematics;
     visuomotor control
%X Animate vision depends on an ability to choose a region of the visual
environment for task-specific processing. This processing may involve
extraction of image features for object classification or identification,
or it may involve extraction of viewpoint parameters, such as position,
scale and orientation, for guiding movement. It is the role of selective
attention to choose the region to be processed in a task-dependent way.
This paper describes a real-time implementation of a vision-robotics system
that uses the location information provided by the attention mechanism
to guide eye movements and arm movements in touching and
manual tracking behaviors.

%A B.D. Marsh
%T Multi-Model Parallel Programming
%R TR 413 ($4.50; 98 pages; in pub/papers/systems)
%I URCSD
%D January 1992
%K multi-model parallel programming; operating systems; multiprocessors;
   programming model; parallel programming
%X Multi-model parallel programming is the simultaneous use of different 
programming models, either within a single program or in separate programs. 
A variety of programming models is best implemented in runtime libraries, 
yet current operating systems are not designed to support 
user-level implementations of processes and communication. 
Even if an efficient implementation of a programming model can be 
constructed in user space, interaction with other programming models 
is complicated by the lack of a common communication mechanism.
.pp
The thesis of this dissertation is that in order to support 
multi-model parallel programming, an operating system must provide 
first-class user-level processes and model-independent communication. 
First-class user-level processes support the construction of multiple models 
by allowing flexibility and efficiency of user-level implementations 
to be combined with the control over resource allocation 
traditionally enjoyed only by kernel-level implementations. 
Model-independent communication supports the integration 
of multiple models into a single application by eliminating 
model dependencies from the data transfer and 
concurrency control mechanisms used for communication. 
Together, these concepts facilitate multi-model programming, 
making possible a wide variety of high-quality implementations 
that are easily combined within a single application.
.pp
To support the thesis, we designed and implemented a prototype kernel, 
called Psyche, ported the implementations of different 
parallel programming models, and built several multi-model programs. 
Our experiences with the various programming models 
demonstrate the feasibility of according first-class status 
to processes implemented in user space. 
Our experiences with multi-model applications demonstrate 
how model-independent communication facilitates the construction 
of multi-model programs. Through these experiences, 
this dissertation demonstrates the feasibility and utility 
of multi-model parallel programming.
%X 92.tr413.multi_model_parallel_programming.ps.Z

%A J. E. Veenstra
%A R. J. Fowler
%T A Performance Evaluation of Optimal Hybrid Cache Coherency Protocols
%R TR 414 ($2.00; 25 pages; in pub/papers/systems)
%I URCSD
%D May 1992
%K write-invalidate, write-update, hybrid protocols, trace-driven simulation,
performance evaluation
%X The caches within a multiprocessor
typically use either a write-invalidate protocol or 
a write-update protocol to maintain consistency.
The recently introduced MIPS R4000 processor allows
operating system software to select, on a per-page basis, 
which multiprocessor cache coherence protocol
(write-invalidate versus write-update) the hardware will use.
The availability of the R4000 and the prospect of even more
flexible hardware motivated us to examine the potential
performance advantages of allowing user-level control
over the choice of coherence protocol on a per-page basis and to ask whether
more powerful hybrid protocols provide substantially more benefit.
We examine the potential benefits of three classes of hybrid protocols: (1) 
hybrid protocols that choose statically, at the beginning of the program,
between write-invalidate (WI) or write-update (WU) on a
per-page basis, (2) hybrid protocols that choose statically between
WI or WU for each cache block, and (3) dynamic hybrid protocols
that can choose between WI or WU at each write.
In order to determine how much potential benefit could be obtained by
each of these protocol classes, we used trace-driven
simulations to evaluate the optimal off-line protocol for each class.
We found that the use of a hybrid protocol
can substantially reduce the cost of memory references for 
most of the programs studied.  A few programs can also realize large
additional benefits from a per-block static hybrid protocol compared to a
per-page static hybrid protocol. None of the programs, however,
receive a significant additional benefit from using a dynamic
hybrid protocol compared to the per-block static hybrid protocol,
unless cache block sizes are larger than 16 words (64 bytes).
%X 92.TR414.Perf.Eval.Hybrid.Protocols.ps.Z

%A David J. Coombs
%T Real-Time Gaze Holding in Binocular Robot Vision
%R TR 415 and Ph.D. Thesis ($7.00; 154 pages; in /pub/papers/robotics)
%I URCSD
%D June 1992
%K visual following; tracking; pursuit; vergence; active vision;
     animate vision; precategorical vision; sensory-motor systems;
     gaze stabilization; egomotion compensation; visual fixation;
     binocular vision; mobile robots
%X Using a binocular, maneuverable visual system, a robot that holds
its gaze on a visual target can enjoy improved visual perception and
performance in interacting with the world. This dissertation examines
the problem of holding gaze on a moving object from a moving platform,
without requiring the ability to recognize the target.
A novel aspect of the approach taken is the use of controlled
camera movements to simplify the visual processing necessary
to keep the cameras locked on the target.
A gaze holding system on the Rochester robot's binocular head
demonstrates this approach. Even while the robot is moving, the cameras
are able to track an object that rotates and moves in three dimensions.
.pp 
The key observation is that visual fixation can help separate
an object of interest from distracting surroundings.
Camera vergence produces a horopter (surface of zero stereo disparity)
in the scene.  Binocular features with no disparity can be extracted
with a simple filter, showing the object's location in the image.
Similarly, an object that is being tracked will be imaged near
the center of the field of view, so spatially-localized processing
helps concentrate on the target. Rochester's binocular robot
exploits these observations. The vergence and smooth tracking systems
cooperate to hold the cameras on an object moving in three dimensions.
The vergence system changes the vergence angle of the cameras to
drive the disparity of the target to zero, relying on the tracking system
to keep the target in the central field of view.
The tracking system centers the cameras on the zero-disparity signals,
relying on the vergence system to hold vergence on the target. 
Instead of requiring a way to recognize the target, the system relies
on active control of camera movements and binocular fixation segmentation.
%X 92.tr415.real_time_gaze_holding.ps.Z and
   92.tr415.real_time_gaze_holding_nofigures.ps.Z

%A Polly K. Pook
%A Dana H. Ballard
%T Contextually Dependent Control Strategies for Manipulation
%R TR 416 ($2.00; 26 pages; in pub/papers/robotics)
%I URCSD
%D April 1992
%K dexterous manipulation; grasping; Utah/MIT hand
%X Traditional analytic robotics defines grasping 
by knowing the task geometry 
and the forces acting on the manipulator precisely. 
This method is particularly important for non-compliant manipulators 
with few degrees of freedom, such as a parallel jaw gripper, 
that overconstrain the solution space. In contrast, the advent of 
anthropomorphic, high degree-of-freedom grippers allows us to use 
closed-loop strategies that depend heavily on the task context 
but do not require precise positioning knowledge. 
To demonstrate, a robotic hand flips a plastic egg, 
using the finger joint tendon tensions as the sole control signal.
The manipulator is a compliant, sixteen degree-of-freedom, Utah/MIT hand 
mounted on a Puma 760 arm. 
The completion of each subtask, such as picking up the spatula, 
finding the pan, and sliding the spatula under the egg, 
is detected by sensing when the tensions of the hand tendons 
pass a threshold.  Beyond this use of tendon tensions 
and the approximate starting position
of the spatula and pan, no model of the task is constructed. 
The routine is found to be robust to different spatulas and to changes in
the location and orientation of the spatula, egg, and table, 
with some exceptions.
.pp
The egg-flipping example relies on interpreting fluctuating 
tension values within a known temporal sequence of actions.
For instance, knowing when the manipulator is trying to touch the pan
with the spatula provides the context 
to interpret changes in tendon tensions.
Given the success of this task, we go on to propose a method 
for analyzing the temporal sensory output for tasks 
that have not been previously segmented.
This method suggests a means for automatically generating robust
force-control programs to perform previously teleoperated manipulation tasks.
%X 92.tr416.context_dep_control_strategies.ps.Z

%A V. Arvind
%A Y. Han
%A L.A. Hemachandra
%A J. K\"{o}bler
%A A. Lozano
%A M. Mundhenk
%A M. Ogiwara
%A U. Sch\"{o}ning
%A R. Silvestri
%A T. Thierauf
%T Reductions to Sets of Low Information Content
%R TR 417 ($3.00; 56 pages; in pub/papers/theory)
%I URCSD
%D April 1992
%K complexity theory; reductions; sparse sets
%X This paper is concerned with three basic questions about sparse sets: 
(1) With respect to what types of reductions
might NP have hard or complete sparse sets?
(2) If a set A reduces to a sparse set, does it follow that
A is reducible to some sparse set that is "simple" relative to A?
(3) With respect to what types of reductions might NP have
hard or complete sets of low instance complexity, and,
relatedly, what is the structure of the class of sets
with low instance complexity?
.pp
With respect to the first and third questions, intuitively one would expect
that even with respect to flexible reductions NP is unlikely
to have complete sets whose information content is low. 
With respect to the second question, one might intuitively feel
that the structure imposed on a set by the fact that it reduces
to a sparse set makes it plausible that we can indeed
find a simple sparse set that can masquerade as the original sparse set.
These two intuitions are in many ways certified
by the current literature, and by the results of this paper.
%X 92.tr417.reductions_sets_low_inf.ps.Z

%A W. E. Garrett
%A R. Bianchini
%A L. Kontothanassis
%A R. A. McCallum
%A J. Thomas
%A R. Wisniewski
%A M. L. Scott
%T Dynamic Sharing and Backward Compatibility on 64-Bit Machines
%R TR 418 ($2.00; 34 pages; in pub/papers/systems)
%I URCSD
%D April 1992
%X As an alternative to communication via messages or files, shared memory
has the potential to be simpler, faster, and less wasteful of space.
Unfortunately, the mechanisms available for sharing in most multi-user
operating systems are difficult to use.
As a result, shared memory tends to appear primarily in self-contained
parallel applications, where library or compiler support can take care
of the messy details.
.pp
We see a tremendous opportunity to extend the advantages of sharing
across application boundaries.
We believe that these advantages can be realized without introducing
major changes to the Unix programming model.
In particular, we believe that it is both possible and desirable to
incorporate shared memory segments into the hierarchical file system
name space.
.pp
Our approach has two components: First, we use dynamic linking to allow
programs to access shared data and code in the same way they access
ordinary (private) variables and functions.
Second, we unify memory and files into a single-level store that
facilitates the sharing of pointers.
This second component is made feasible by the 64-bit addresses of
emerging microprocessors.
%X 92.TR418.sharing.ps.Z

%A Jin-yi Cai
%A Lane A. Hemachandra
%A Jozef Vysko\v{c}
%T Promise Problems and Access to Unambiguous Computation
%R TR 419 ($2.00; 26 pages; in pub/papers/theory)
%I URCSD
%D April 1992
%K fault-tolerant computing; robust computation
%X This paper studies the power of three types of access
to unambiguous computation: nonadaptive access, fault-tolerant access, 
and guarded access. (1) Though for NP it is known that 
nonadaptive access has exponentially terse adaptive simulations, 
we show that UP has no such relativizable simulations:
there are worlds in which (k+1)-truth-table access to UP
is not subsumed by k-Turing access to UP.
(2) Though fault-tolerant access (i.e., "1-helping" access) 
is known to be no more powerful than NP itself, 
we give both structural and relativized evidence that 
fault tolerant access to UP suffices to recognize even sets beyond UP.
Furthermore, we completely characterize, 
in terms of locally positive reductions, 
the sets that fault-tolerantly reduce to UP. 
(3) In guarded access, Grollmann and Selman's natural notion
of access to unambiguous computation, 
a deterministic polynomial-time Turing machine asks questions 
to a nondeterministic polynomial-time Turing machine
in such a way that the nondeterministic machine
never accepts ambiguously. In contrast to guarded access, 
the standard notion of access to unambiguous computation
is that of access to a set that is uniformly unambiguous--
even for queries that it never will be asked by its questioner,
it must be unambiguous. We show that these notions, 
though the same for nonadaptive reductions, 
differ for Turing and strong nondeterministic reductions.
%X 92.tr419.access_unambig_computation.ps.Z

%A E.P. Markatos 
%A T.J. LeBlanc 
%T Shared-Memory Multiprocessor Trends
and the Implications for Parallel Program Performance
%R TR 420 ($2.00; 28 pages; in pub/papers/systems)
%I URCSD 
%D May 1992 
%X The last decade has produced enormous improvements in
processor speeds without a corresponding improvement in
bus or interconnection network speeds.
As a result, the relative costs of communication and computation
in shared-memory multiprocessors have changed dramatically.
An important consequence of this trend is that many parallel applications,
which depend on a delicate balance between the cost of communication
and computation, do not execute efficiently on today's shared-memory
multiprocessors.
.pp
In this paper we quantify the effect of this trend
in multiprocessor architecture on parallel program performance.
Our experiments on bus-based,
cache-coherent machines like the Sequent Symmetry,
and large-scale distributed-memory machines like the BBN Butterfly,
demonstrate that applications scale much better on previous-generation
machines than on current machines.
In addition, we show that some scalable machines support
fine-grain, shared-memory programs better than some bus-based,
cache-coherent machines, without significantly greater programming effort.
>From our experiments we conclude that communication has become a
dominant source of inefficiency in shared-memory multiprocessors,
with serious consequences for system software involved in
scheduling and decomposition decisions.
In particular, we argue that shared-memory programming models
that could be implemented efficiently on the machines of yesterday
do not readily port to state-of-the-art machines,
and that current software trends in support of fine-grain
parallel programming are at odds with hardware trends.
%X 92.TR420.interaction_architecture_parallel.ps.Z

%A Marc Light
%T A Computational Theory of Lexical Relatedness
%R TR 421 ($2.00; 41 pages; in pub/papers/ai)
%I URCSD
%D July 1992
%K lexicon; word semantics; word formation; derivational affixation
%X Lexicon coverage is often the limiting factor in natural language 
processing systems. Recent work has attempted to remedy this situation
by extracting information from machine readable dictionaries.
Unfortunately, no NLP lexicon system or dictionary could possibly list
all the potential words of English. However, humans are often able
to interpret novel word forms (that is, words they have not seen before)
without difficulty. One way we do this, if the word is complex
(e.g., "undecidability"), is by using cues from the internal structure 
of the word. Relations in phonological form often correspond to
relations in meaning. For example, if someone knows what the verb
"open" means, a number of educated guesses can be made about the
meaning of "reopen". Exceptions abound in lexical data and any system
that attempts to use lexical generalizations must be able to handle
exceptions in a principled fashion. In this report, I will describe
the preliminary design of a system that uses relations in form
to derive relations in meaning. For a new word, the system will produce
meaning postulates that represent an educated guess about the meaning
of the new word. These meaning postulates will be written in Episodic
Logic, and the entire system will be a module of the TRAINS system.
%X 92.tr421.lexical_relatedness.ps.Z

%A Farid Ablayev
%T Lower Bounds for One-Way Probabilistic Communication Complexity
%R TR 422 ($2.00; 22 pages; in pub/papers/theory)
%I URCSD
%D May 1992
%K communication complexity; probabilistic communication complexity; 
lower bounds; probabilistic algorithms
%X We prove three different types of complexity lower bounds for one-way
unbounded-error and bounded-error error probabilistic communication
protocols for boolean functions. The lower bounds are proved
for arbitrary boolean functions in the common way in terms of the
deterministic communication complexity of functions and in terms of the
notion "probabilistic communication characteristic" that we define.
.pp
It is shown that for almost all boolean functions either Yao's
lower bound or the first or third lower bound are more precise
depending on the value of probability error.
.pp
We present boolean functions with different probabilistic
communication characteristics which demonstrates that each of these
lower bounds can be more precise than the others depending on the
probabilistic communication characteristics of a function.  The
examples of boolean functions show that the lower bounds of the paper
are precise and incomparable.
.pp
Our lower bounds are good enough for proving proper hierarchies for
various one-way probabilistic communication complexity classes (namely
for unbounded error probabilistic communication, for bounded error
probabilistic communication, and for errors of probabilistic
communication).
%X 92.tr422.probabilistic_commun_complexity.ps.Z 

%A Farid Ablayev
%T Lower Bounds for Probabilistic Space Complexity: Automata Approach
%R TR 423 ($2.00; 13 pages; in pub/papers/theory)
%I URCSD
%D May 1992
%K probabilistic space complexity; probabilistic algorithms; lower bounds
%X In this paper we investigate a well known sequential model of
computation: one-way LOG-SPACE Turing machines. We analyze a different
known method for constructing an effective probabilistic algorithm.
We prove a lower bound for probabilistic space complexity,
which is good enough for understanding the above problem
for the one-way LOG-SPACE Turing machine model of computation.
%X 92.tr423.probabilistic_space_complexity.ps.Z

%A David R. Traum
%A Elizabeth A. Hinkelman
%T Conversation Acts in Task-Oriented Spoken Dialogue
%R TR 425 ($2.00; 28 pages; in pub/papers/ai)
%I URCSD
%D June 1992
%K speech acts; conversation; literal meaning; discourse; grounding;
     turn taking
%X A linguistic form's compositional, timeless meaning can be surrounded
or even contradicted by various social, aesthetic,
or analogistic companion meanings.
This paper addresses a series of problems in the structure of
spoken language discourse, including turn-taking and grounding.
It views these processes as composed of fine-grained actions,
which resemble speech acts both in resulting from a computational
mechanism of planning and in having a rich relationship to the
specific linguistic features which serve to indicate their presence.
.pp
The resulting notion of Conversation Acts is more general than
speech act theory, encompassing not only the traditional speech acts
but turn-taking, grounding, and higher-level argumentation acts as well.
Furthermore, the traditional speech acts in this scheme become fully joint
actions, whose successful performance requires full listener participation.
.pp
This paper presents a detailed analysis of spoken language dialogue.
It shows the role of each class of conversation acts
in discourse structure, and discusses how members of each class
can be recognized in conversation. Conversation acts, it will be seen,
better account for the success of conversation than speech act theory alone.
%X 92.tr425.conversation_acts.ps.Z

%A Man-Wai Chu
%T Polhemus Coordinates and Polhemus-Puma Conversion
%R TR 427 ($2.00; 20 pages; in pub/papers/robotics)
%I URCSD
%D June 1992
%K Polhemus sensor; Polhemus source; VPL DataGlove
%X A Polhemus 3Space Isotrak sensor system is used on the
VPL Research DataGlove Model 2 to detect the glove's absolute
position and orientation. The sensor system has two components:
the Polhemus sensor and the Polhemus source.
The sensor is attached to the back of the DataGlove.
The sensor sends to the DataGlove Control Unit analog signals,
which are converted into the Polhemus data--six parameters that
represent the position and orientation of the sensor
relative to the source. This document describees how
the Polhemus devices work and how the Polhemus data should be interpreted.
It also describes the transformation of the Polhemus output
into the (X, Y, Z, O, A, T) space of the robot in the
University of Rochester Robotics Laboratory.
This transformation allows teleoperation of the robot
through the use of the Polhemus devices.
%X 92.tr427.Polhemus_coordinates.ps.Z

%A George M. Ferguson
%T Explicit Representation of Events, Actions and Plans for
     Assumption-Based Plan Reasoning
%R TR 428 ($2.00; 48 pages; in /pub/papers/ai)
%I URCSD
%D June 1992
%K knowledge representation; plans; temporal reasoning; defeasible reasoning
%X We propose a wide-ranging knowledge representation formalism
designed expressly to support many different forms of reasoning about plans.
We begin with an event-based language based on the interval
temporal logic. The language supports reasoning about action attempts
and composite actions, both of which are given axiomatic definitions.
We then define a representation for plans viewed as arguments
that a certain course of action under certain explicit conditions
will achieve certain goals. We can represent both correct
and incorrect plans, and reason about why they might or might not fail.
An important aspect of this work is the formal characterization of plan
reasoning as assumption-based reasoning, to make the non-deductive aspects
of plan reasoning explicit. A preliminary implementation of these ideas
has already been built as the plan reasoning component of the TRAINS system.
%X 92.tr428.assumption_based_plan_rsng.ps.Z

%A M.L. Scott
%A J.M. Mellor-Crummey
%T Fast, Contention-Free Combining Tree Barriers
%R TR 429 ($2.00; 29 pages; in /pub/papers/systems)
%I URCSD
%D June 1992
%K synchronization; adaptive combining tree; fuzzy barriers; multiprogramming;
     contention; scalability; local-only spinning; fetch-and-store
%X Counter-based algorithms for busy-wait barrier synchronization
execute in time linear in the number of synchronizing processes.
This time can be made logarithmic in the number of processes by
adopting algorithms based on trees or FFT-like synchronization patterns.
As an additional improvement, Gupta and Hill have proposed
an adaptive combining tree barrier that exploits non-uniformity in inter-
barrier computation times: processes begin to leave the barrier in time
logarithmic in the number of processes when all processes arrive at once, but
in constant time after the arrival of the last process when arrival times
are skewed.Building on earlier work, Gupta and Hill present both
regular and fuzzy versions of their barrier. The fuzzy version allows a
process to perform useful work between the point at which it notifies
other processes of its arrival at the barrier and the point at which
it waits for all other processes to arrive.
.pp
Unfortunately, like many forms of busy-wait synchronization, 
adaptive combining tree barriers as originally devised can induce
large amounts of memory and interconnect contention in
shared-memory multiprocessors, seriously degrading performance.
They also perform a comparatively large amount of work
at every tree node, raising the possibility that the constant factors in their
execution time may be unacceptably high on machines of reasonable size.
To address these problems, we present a new adaptive combining tree
barrier, with fuzzy variant, that achieves significant speed improvements
by spinning only on locally-accessible locations, and by using atomic
fetch_and_store operations to avoid explicit locking of tree nodes.
We also present a version of this barrier (again with fuzzy variant)
that employs breadth-first wakeup of processes to reduce context switching
when processors are multiprogrammed. We compare the performance
of these new algorithms to that of other fast barriers on a 64-node
BBN Butterfly 1 multiprocessor and on a 35-node BBN TC2000.
Results suggest that adaptation is of little benefit, but that the combination
of fuzziness with tree-style synchronization is of significant practical
importance: fuzzy combining tree barriers with local-only spinning
outperform all known alternatives on the TC2000 when the amount of
fuzzy computation exceeds about 10% of the time between barriers.
%X 92.tr429.fast_contention_free_combining_tree_barriers.ps.Z

%A Lane A. Hemachandra 
%A Sudhir K. Jha
%T Defying Upward and Downward Separation
%R TR 430 ($2.00; 28 pages; in /pub/papers/theory)
%I URCSD
%D June 1992
%K complexity theory; upward separation; downward separation; limited
     nondeterminism
%X Upward and downward separation results link the collapse
of small and large classes, and are a standard tool in complexity theory.
We study the limitations of upward and downward separation.
.pp
We show that the exponential-time limited nondeterminism hierarchy
does not robustly possess downward separation.
We show that probabilistic classes do not robustly possess
Hartmanis-Immerman-Sewelson upward separation.
Though NP is known to robustly possess Hartmanis-Immerman-Sewelson
upward separation, we show that NP does not robustly possess
Hartmanis-Immerman-Sewelson upward separation with respect to strong
(immunity) separation. On the other hand, we provide a
structural sufficient condition for upward separation.
%X 92.tr430.defying_upward_downward_separation.ps.Z

%A Lane A. Hemachandra
%A Riccardo Silvestri
%T Easily Checked Self-Reducibility
%R TR 431 ($2.00; 30 pages; in /pub/papers/theory)
%I URCSD
%D July 1992
%K computational complexity; checking; self-reducibility; sparse sets
%X This paper explores two generalizations, within NP, of self-reducibility:
kernel constructibility and committability. Informally stated,
kernel constructible sets have self-reductions that are easy to check
(though perhaps hard to compute), and committable sets are those sets
for which the potential correctness of a partial proof of set membership
can be checked via a query to the same set (that is, via a
self-reduction). We study these two notions of self-reducibility on
non-dense sets. We show that sparse kernel constructible sets
are of low complexity, we extend previous results showing that sparse
committable sets are of low complexity, and we provide
structural evidence of interest in its own right---namely that if all
sparse disjunctively self-reducible sets are in P then FewP \cap coFewP is
not P-bi-immune---that our extension is unlikely to be further extended.
We obtain density-based sufficient conditions for kernel-constructibility:
sets whose complements are captured by non-dense sets are perforce
kernel constructible. Using sparse languages and Kolmogorov complexity
theory as tools, we argue that kernel constructibility is
orthogonal to standard notions of complexity.
%X 92.tr431.easily_checked_self_reducibility.ps.Z

%A William J. Bolosky
%A Michael L. Scott
%T A Trace-Based Comparison of Shared Memory Multiprocessor Architectures
%R TR 432 ($2.00; 28 pages; in pub/papers/systems)
%I URCSD
%D July 1992
%K shared memory multiprocessor; software coherence; optimal analysis
%X There are three major classes of MIMD multiprocessors: 
cache-coherent machines, NUMA (non-uniform memory reference) machines
without cache coherence, and distributed-memory multicomputers.
All three classes can be used to run shared-memory applications,
though the third requires software support in order to do so,
and the second requires software support in order to do so well. 
We use trace-driven simulation to compare the performance of these classes,
in an attempt to determine the effect of various architectural features
and parameters on overall program performance.
For those systems whose hardware or software supports both
coherent caching (migration, replication) and remote reference,
we use optimal off-line analysis to make the correct decision in all cases.
This technique allows us to evaluate architectural alternatives
without worrying that the results may be biased by a poor data placement
policy. We find that the size of the unit of coherence (page or cache line)
is the dominant factor in performance; that NUMA systems can have
performance comparable to that of cache coherent machines; and that even
relatively expensive, software-implemented remote reference is beneficial
in distributed shared memory machines.
%X 92.tr432.trace_based_comparison_of_shared_memory_multiprocessors.ps.Z

%A Lata Narayanan
%T Selection, Sorting, and Routing on Mesh-Connected Processor Arrays
%R TR 433 and Ph.D. Thesis ($4.00; 83 pages; in pub/papers/theory)
%I URCSD
%D May 1992
%K selection; sorting; routing; mesh-connected processor arrays; median;
     grids; randomized; deterministic; algorithms; lower bounds;
     off-line routing; multi-packet selection; optimal selection
%X The mesh-connected processor array has been the object of a great deal
of attention in recent years, and several parallel computers
have configurations based on the mesh topology. This thesis
addresses the fundamental problems of selection, sorting, and routing
on mesh-like networks. Sorting and selection are prototype problems,
due both to their practical applications and to their role in
inter-processor communication. The routing problem isolates the issue
of communication between processors in an interconnection network.
.pp
We show efficient randomized algorithms for selection on mesh-like
networks. In particular, we show that there is a 1.22n step
randomized algorithm that selects the element of rank k at the
middle processor of the nxn mesh, and uses constant size queues,
with high probability. In the deterministic setting, we devise a
1.44n step algorithm for selection at the middle processor. For the case
when there are N elements distributed at the nodes of an nxn mesh
(N > n^2), we show a deterministic algorithm that works in
O(min{n^2 log (N/n^2), max{N/n^{4/3}, n}}) steps.
We show optimal algorithms for selection in a variety of restricted
settings: at specific locations in the mesh; when the inputs are 
chosen from a small domain; and for elements with specific ranks.
We are able to show that adding the toroidal and/or diagonal
connections to the mesh yields better algorithms for selection.
We exhibit improved randomized and deterministic algorithms for
selection in higher-dimensional meshes.
.pp
The bounds for sorting and selection on the mesh seem to be very
model-dependent. We define a general model of computation that
has the queue size and the ability to replicate packets as parameters.
We prove lower bounds for sorting and selection in some incarnations
of this model. The architectures we consider are meshes
and tori, with and without diagonal connections.
.pp
We examine the trade-off between time and queue size in algorithms for 
routing on the mesh. We show an elegant off-line algorithm to route
permutations that works in 2.2n+5 steps, and requires queues of size 14.
%X 92.tr433.selection_sorting_routing_mesh_connected_processor_arrays.ps.Z

%A Lambert E. Wixson
%T Exploiting World Structure to Efficiently Search for Objects
%R TR 434 ($3.00; 55 pages; in pub/papers/robotics)
%I URCSD
%D July 1992
%K object recognition; visual search; object search; knowledge-based vision;
     active vision
%X This paper studies the task of using a mobile camera platform to
search a region of space for a target object.
Our goal is to maximize the efficiency of such searches.
The problem is analyzed using a simple mathematical description of the factors
that affect search efficiency. This analysis suggests that one way to
improve efficiency is to take advantage of the spatial relationships
in which the target object commonly participates. Searches that do so, 
which we call indirect searches, are modeled as two-stage processes
that first find an intermediate object that commonly participates in
a spatial relationship for the target object, and then look for the target
in the restricted region specified by this relationship.
A mathematical model of search efficiency is then used to analyze
the efficiency of indirect search over a wide range of situations that vary
the spatial structure of the domain as well as
recognition performance. The model predicts that, for searches
that involve rotating a camera about a fixed location, indirect searches
improve efficiency by factors of 2 to 8. An implemented robot search system
substantiates these predictions. Finally, we highlight some areas 
in need of further research if these efficiencies are to be achieved.
%X 92.tr434.exploiting_world_structure.ps.Z









===========================================================================
Co-moderator:  Richard Golding, Computer & Information Sciences, UC Santa Cruz
	    compdoc-techreports-request@ftp.cse.ucsc.edu