| CS-91-72 | ||||
|---|---|---|---|---|
| Title | Characteristic Words as Fixed Points of Homomorphisms | |||
| Authors | J. O. Shallit | |||
| Abstract | Abstract (PDF) | |||
| Date | December 1991 | |||
| Report | Characteristic Words as Fixed Points of Homomorphisms (PDF) |
Compressed
DVI: Characteristic Words as Fixed Points of Homomorphisms (DVI.Z) | ||
| CS-91-67 | ||||
|---|---|---|---|---|
| Title | Comparative Stylistics in an Integrated Machine Translation System | |||
| Authors | K. Mah | |||
| Abstract |
Comparative
stylistics
is
a
subfield
of
stylistics
that
attempts
to
account
for
the
differences
in
style
between
languages.
Rules
of
comparative
stylistics
are
commonly
presented,
in
textbooks
of
translation,
as
"rules-of-thumb",
but
if
we
hope
to
incorporate
a
knowledge
of
comparative
stylistics
into
natural
language
understanding
systems,
we
must
take
a
more
formal
approach.
In
particular,
we
will
develop
a
computational
model
of
comparative
stylistics
for
machine
translation
that
could
be
used
to
guide
translation
and
thereby
improve
the
quality
of
the
translated
output.
An
implementation
of
this
model
would
provide
additional
information
to
the
machine
translation
system
about
the
potential
modulations
to
the
translated
text
and
their
effects,
enabling
it
to
make
a
more
informed
decision. In this thesis, we develop a set of formal rules of syntactic French-English comparative stylistics to be used as a component of a model of comparative stylistics. As the foundation for the formal rules, we adapt theoretical rules of syntactic French-English comparative stylis- tics compiled by Guillemin-Flescher [1981] and the formal representation of syntactic style developed by DiMarco [1990]. A corpus of French sentences and their English translations is analyzed to convert the theoretical rules to a set of formal rules that builds on DiMarco's grammars of syntactic style. Thus, we present a formal grammar of French-English compara- tive stylistics. We also suggest a method for incorporating these rules into an existing machine translation system. | |||
| Date | October 1991 | |||
| Report | Comparative Stylistics in an Integrated Machine Translation System (PDF) |
Compressed
DVI: Comparative Stylistics in an Integrated Machine Translation System (DVI.Z) | ||
| CS-91-65 | ||||
|---|---|---|---|---|
| Title | Abstraction in Nonlinear Planning | |||
| Authors | Qiang Yang, Josh D. Tenenberg, & Steve Woods | |||
| Abstract | We extend the hierarchical, precondition-elimination abstraction of Abstrips to nonlinear, least-commitment planners such as Tweak. Specifically, we show that the combined planning system, AbTweak, satisfies the monotonic property, whereby the existence of a lowest level solution the implies the existence of a highest level solution that is structurally similar to II. This property enables one to prune a considerable amount of the search space without loss of completeness. In addition, we develop a criteria for good abstraction hierarchies, and develop a novel, complete search strategy called Left,Wedge that is optimized for good abstraction hierarchies. We demonstrate the utility of both the monotonic property and the Left-Wedge strategy through a series of empirical tests. | |||
| Date | December 1991 | |||
| Report | Abstraction in Nonlinear Planning (PDF) |
Compressed
PostScript: Abstraction in Nonlinear Planning (PS.Z) | ||
| CS-91-62 | ||||
|---|---|---|---|---|
| Title | On Specialization Constraints Over Complex Objects | |||
| Authors | M. Ito, G. Weddell and N. Coburn | |||
| Abstract |
Most
semantic
data
models
and
object-oriented
data
models
allow
entity
and
object
classes
to
be
organized
according
to
a
generalization
taxonomy.
In
addition,
range
restrictions
(or
property
typing)
may
be
specified
not
only
on
properties
associated
with
a
given
class,
but
also
on
properties
inherited
from
superclasses.
In
this
paper,
we
consider
a
more
general
form
of
specialization
constraint
in
which
range
restrictions
are
associated
with
property
value
paths,
instead
of
with
the
properties
themselves.
One
consequence
is
that
the
constraints
enable
a
form
of
molecular
abstraction,
in
which
the
internals
of
more
complicated
objects
can
be
defined
in
terms
of
a
collection
of
more
primitive
classes. We consider the problem for two models. The first imposes no constraints on class membership for an object beyond those implied by sub- classing constraints. In this case, we present a sound and complete axiomatization for arbitrary specialization constraints, and e1cient decision procedures for the corresponding membership problems. The second model is more typical and requires that each object is created with respect to a particular class. Membership problems in this case are shown to be NP-hard, and NP-complete if class schema include a "bottom" class. We exhibit polynomial-time decision procedures when a bottom class does exist and antecedent specialization constraints satisfy a bounded path length condition. We also consider a case concerning the second model in which class schema satisfy a lower semi-lattice condition. A sound and complete axiomatization for well-formed specialization constraints is presented, together with e1cient decision procedures for the membership problem for well-formed constraints, and for determining if an arbitrary constraint is well-formed. We prove that the membership problem for arbitrary specialization constraints remains NP-complete, however, even for class schema satisfying the lower semi-lattice condition. | |||
| Date | December 1991 | |||
| Report | On Specialization Constraints Over Complex Objects (PDF) |
Compressed
DVI: On Specialization Constraints Over Complex Objects (DVI.Z) | ||
| CS-91-56 | ||||
|---|---|---|---|---|
| Title | The Maximal Path Length of Binary Trees | |||
| Authors | Helen Cameron & Derick Wood | |||
| Abstract | We further refine the bounds on the path length of binary trees of a given size by considering not only the size of a binary tree, but also its height and fringe thickness (the difference between the length of a shortest root-to-leaf path and the height). We characterize the maximum path length binary trees of a given height, size, and fringe thickness. Using this characterization, we give an algorithm to find the maximum path length binary trees of a given size and fringe thickness. | |||
| Date | October 1991 | |||
| Report | The Maximal Path Length of Binary Trees (PDF) |
Compressed
DVI: The Maximal Path Length of Binary Trees (DVI.Z) | ||
| CS-91-55 | ||||
|---|---|---|---|---|
| Title | A Constraint-Based Approach to Dynamic Colour Management for Windowing Interfaces | |||
| Authors | Blair MacIntyre | |||
| Abstract | Selecting harmonious colours for traditional window systems can be a difficult and frustrating endeavor. At the root of this problem is the fact that typical window systems do not allow abstract properties of colours to be specified. Instead, they insist that users specify individual colour values exactly. When many colours are used, the value of each colour must be chosen to satisfy any relationships that exist between it and previously chosen colours. Unfortunately, the difficulty of colour selection often prevents users from taking full advantage of the functional benefits of colour, particularly that of resolving context. A more desirable approach is to allow the aesthetic and functional properties of colours to be specified and to allow users to select values for the colours they wish. The window system can choose the remaining colours using these properties. Another failing of typical window systems is that once a colour value has been determined it will not change without explicit direction from the user. When windows open or close the factors which motivated a choice of colour value may change. Unfortunately, if the user wishes the chosen colour value to change as the environment changes, he or she must typically perform the modifications. A dynamic window system assists the user in making these choices. By specifying colour properties as constraints, a dynamic window system can adjust colour values as the environment changes, to satisfy these constraints. The potential problems with dynamic window systems incorporating colour constraints are investigated in this thesis. An implementation that uses a distributed, jostling, constraint-solver based on a simple dynamical system shows that this approach is possible. | |||
| Date | October 1991 | |||
| Report | A Constraint-Based Approach to Dynamic Colour Management for Windowing Interfaces (PDF) |
Compressed
PostScript: A Constraint-Based Approach to Dynamic Colour Management for Windowing Interfaces (PS.Z) | ||
| CS-91-53 | ||||
|---|---|---|---|---|
| Title | uC++ Annotated Reference Manual (Preliminary Draft) | |||
| Authors | P. A. Buhr and R. A. Stroobosscher | |||
| Abstract | The goal of this work is to introduce concurrency into the object-oriented language C++ [Str91]. To achieve this goal a set of important programming language abstractions were adapted to C++, producing a new dialect called {mu}C++. These abstractions were derived from a set of design requirements and combinations of elementary execution properties, different combinations of which categorized existing programming language abstractions and suggested new ones. The set of important abstractions contains those needed to express concurrency, as well as some that are not directly related to concurrency. Therefore, while the focus of this work is on concurrency, all the abstractions produced from the elementary properties are discussed. While we are implementing our ideas as an extension to C++, the requirements and elementary properties are generally applicable to other object-oriented languages such as Eiffel [Mey88], Simula [Sta87] and Smalltalk [GR83]. This manual does not discuss how to use the new constructs to build complex concurrent systems. The manual is strictly a reference manual for {mu}C++. A reader should have an intermediate knowledge of control 0ow and concurrency issues to understand the ideas presented in this manual as well as some experience programming in C++. | |||
| Date | October 1991 | |||
| Report | uC++ Annotated Reference Manual (Preliminary Draft) (PDF) |
Compressed
DVI: uC++ Annotated Reference Manual (Preliminary Draft) (DVI.Z) | ||
| CS-91-52 | ||||
|---|---|---|---|---|
| Title | uSystem Annotated Reference Manual Version 4.4 | |||
| Authors | P. A. Buhr, H. I. Macdonald, & R. A. Stroobosscher | |||
| Abstract | The goal of this work was to introduce concurrency into the language C. To achieve this goal a set of library routines and definitions were created in C. The set of routines and definitions contains those needed to express concurrency, as well as some that are not directly related to concurrency. Therefore, while the focus of this work is on concurrency, all the abstractions produced from the routines and definitions are considered important. This manual does not discuss how to use the new constructs to build complex concurrent systems. The manual is strictly a reference manual for the {mu}System definitions. A reader should have an intermediate knowledge of control 0ow and concurrency issues to understand the ideas presented in this manual as well as some experience programming in C. This manual contains annotations set off from the normal discussion in the following way: | |||
| Date | October 1991 | |||
| Report | uSystem Annotated Reference Manual Version 4.4 (PDF) |
Compressed
PostScript: uSystem Annotated Reference Manual Version 4.4 (DVI.Z) | ||
| CS-91-47 | ||||||
|---|---|---|---|---|---|---|
| Title | Pm Numbers, Ambiguity, and Regularity | |||||
| Authors | Helen Cameron & Derick Wood | |||||
| Abstract | Abstract (PDF) | |||||
| Date | September 1991 | |||||
| Report | Pm Numbers, Ambiguity, and Regularity (PDF) |
Compressed
DVI: Pm Numbers, Ambiguity, and Regularity (DVI.Z) | ||||
| CS-91-46 | ||||
|---|---|---|---|---|
| Title | The Technology of Object-Oriented Databases | |||
| Authors | G. Weddell | |||
| Abstract |
There
is
now
a
reasonable
consensus
on
what
an
object-oriented
(OODBMS)
database
system
must
have
in
the
way
of
features.
Roughly,
one
obtains
an
OODBMS
by
adding
a
"non-procedural"
query
language,
secondary
storage
management
and
support
for
concurrency
and
recovery
to
an
object-oriented
programming
language,
such
as
C++
or
Eiffel. Unfortunately, this cannot be accomplished by a straightforward marriage of existing database and compiler technology. From the point of view of relational database technology, new problems are introduced and most existing problems are made more complicated in some way problems on topics relating to query languages, constraint theory, storage management and object indexing, object clustering, query optimization, transaction processing, and so on, are all affected. During the summer of 1991, I had the opportunity of working with thirteen of our graduate students in attempting to gain some appreciation for the present state of OODBMS technology. The students divided into five groups, consisting of two or three people each, for the purpose of surveying five of these topics as they relate to an OODBMS. This document is the result of their efforts. There are five individual reports in the document|one for each of the groups. The first is a survey of proposals for complex object algebras and for query languages based on extensions to SQL; the second is a survey of typing in an OODBMS. The third report is a survey of recent proposals for concurrency control in cases where transactions are long duration, and where they also access complex object structures. The remaining two reports concern storage management and semantic query optimization respectively. The order of presentation is not accidental; reports on topics relating more to conceptual issues are located prior to those on topics relating to internal issues. However, the reader should have no difficulty in understanding the contents of any of the reports in isolation|each has been written independently of the others. My thanks to all the students for their interest and enthusiasm for their help in making the course such a success. Particular thanks also to Glenn Paulley for preparing the final draft of this document. | |||
| Date | September 1991 | |||
| Report |
DVI Reports: |
PDF Reports: | ||
| CS-91-44 | ||||
|---|---|---|---|---|
| Title | Description of Generalized Continued Fractions by Finite Automata | |||
| Authors | J. O. Shallit | |||
| Abstract | A generalized continued fraction algorithm associates with every real number x a sequence of integers; x is rational iff the sequence is finite. For a fixed algorithm, call a sequence of integers valid if it is the result of that algorithm on some input x0. We show that, if the algorithm is sufficiently well-behaved, then the set of all valid sequences is accepted by a finite automaton. | |||
| Date | September 1991 | |||
| Comments | Use "table.roff" to get the table. | |||
| Report | Description of Generalized Continued Fractions by Finite Automata (PDF) |
Compressed
DVI: Description of Generalized Continued Fractions by Finite Automata (DVI.Z) | ||
| CS-91-43 | ||||
|---|---|---|---|---|
| Title | Communication Abstractions for Distributed Systems | |||
| Authors | James W. Hong | |||
| Abstract |
This
thesis
presents
techniques
for
reducing
the
complexity
of
communication
in
distributed
systems.
It
presents
a
set
of
simple
standards
and
tools
that
provide
an
eficient
and
consistent
programming
interface
that
can
be
used
to
implement
a
great
variety
of
communication
interactions
both
within
and
between
various
types
of
paradigms,
abstractions,
and
entities.
It
also
provides
a
framework
based
on
these
standards
and
tools,
with
which
arbitrary
communication
systems
can
be
constructed. Various communication paradigms and issues are examined in order to identify and categorize the fundamental aspects of communication. These fundamental as- pects are then redefined and organized into a set of communication abstractions which is simple and general, rigorous and flexible, low-level and extensible. The generic communication model based on this set provides a framework for arbitrary communication systems. Further, the model utilizes the eficiencies of a single mem- ory domain while providing a universal interface between various types of paradigms, abstractions, and entities across a wide spectrum of environments. The framework provided in the generic communication model is used to develop a specific model called the Buffer and Queue Model which provides a single eficient and consistent communications programming interface. The Buffer-Queue proto- col extends this consistent programming interface transparently to a distributed environment. Finally, a few examples are presented using Buffers and Queues that illustrate how various complex communication facilities may easily be developed and how the use of a common fundamental base makes intermixing of locally defined user interfaces and conversion between higher-level protocols a relatively straightforward task. | |||
| Date | September 1991 | |||
| Report | Communication Abstractions for Distributed Systems (PDF) |
Compressed
DVI: Communication Abstractions for Distributed Systems (DVI.Z) | ||
| CS-91-39 | ||||
|---|---|---|---|---|
| Title | Drop Tolerance Preconditiong for Incompressible Viscous Flow | |||
| Authors | E.F. D'Azevedo, P.A. Forsyth, W.-P. Tang | |||
| Date | August 1991 | |||
| Report | Only available in printed format | |||
| CS-91-35 | ||||
|---|---|---|---|---|
| Title | Implication Problems for Functional Constraints on Databases Supporting Complex Objects | |||
| Authors | Minoru ITO, Grant E. WEDDELL | |||
| Abstract | Virtually all semantic or object-oriented data models assume objects have an identity separate from any of their parts, and allow users to define complex object types in which part values may be any other objects. A more general form of functional dependency is proposed for such models in which component attributes may correspond to descriptions of property paths, called path functional dependencies. The main contribution of the reference is a sound and complete axiomatization for PFDs, when interpretations may be infinite. However, a number of issues were left open which are resolved in this paper. First, we prove that the same axiomatization remains complete if PFDs are permitted empty left-hand sides, and that the implication problem for arbitrary PFDs is decidable. A proof of the latter suggests a means of characterizing an important function closure. Based on this idea, we derive an effective procedure for constructing a deterministic finite state automaton representing the closure. The procedure is further refined to efficient polynomial time algorithms for the implication problem for cases in which antecedent PFDs satisfy a `prefix' condition. This class of PFDs includes as a proper subset the class of key PFDs. Finally, we prove that the axiomatization is not complete if logical consequence is defined with respect to finite interpretations only. | |||
| Report | Implication Problems for Functional Constraints on Databases Supporting Complex Objects (PDF) |
Compressed
DVI: Implication Problems for Functional Constraints on Databases Supporting Complex Objects (DVI.Z) | ||
| CS-91-34 | ||||
|---|---|---|---|---|
| Title | A Generic Paradigm for Efficient Distributed Communication | |||
| Authors | James W. Hong and James P. Black | |||
| Abstract | In our work, we seek to reduce the complexity of communication in distributed systems. We present the Buffer and Queue Model, which consists of a set of simple standards and tools that provide an effcient and consistent programming interface that can be used to implement a great variety of communication interactions both within and among various types of paradigms, abstractions, and entities. The Buffer-Queue protocol extends this consistent programming interface transparently to a distributed environment. We give examples of how various complex communication facilities may be developed using the Buffer and Queue paradigm. | |||
| Date | July 1991 | |||
| Report | A Generic Paradigm for Efficient Distributed Communication (PDF) |
Compressed
DVI: A Generic Paradigm for Efficient Distributed Communication (PDF) (DVI.Z) | ||
| CS-91-33 | ||||
|---|---|---|---|---|
| Title | Adaptive Linear Equation Solvers in Codes for Large Stiff Systems of Odes | |||
| Authors | K. R. Jackson and W. L. Seward | |||
| Abstract |
Iterative
linear
equation
solvers
have
been
shown
to
be
effective
in
codes
for
large
systems
of
stiff
initial-value
problems
for
ordinary
differential
equations
(ODEs).
While
preconditioned
iterative
methods
are
required
in
general
for
effciency
and
robustness,
unpreconditioned
methods
may
be
cheaper
over
some
ranges
of
the
interval
of
integration.
In
this
paper,
we
develop
a
strategy
for
switching
between
unpreconditioned
and
preconditioned
iterative
methods
depending
on
the
amount
of
work
being
done
in
the
iterative
solver
and
properties
of
the
matrix
being
solved.
This
strategy
is
combined
with
a
"type-insensitive"
approach
to
the
choice
of
formula
used
in
the
ODE
code
to
develop
a
method
that
makes
a
smooth
transition
between
nonstiff
and
stiff
regimes
in
the
interval
of
integration.
We
find
that,
as
expected,
for
some
large
systems
of
ODEs,
there
may
be
a
considerable
saving
in
execution
time
when
the
type-insensitive
approach
is
used.
If
there
is
a
region
of
the
integration
that
is
"mildly"
stiff,
switching
between
unpreconditioned
and
preconditioned
iterative
methods
also
increases
the
effciency
of
the
code
significantly. Key words:type-insensitive ODE code, iterative linear solver, preconditioning. AMS(MOS) subject classifications:65L05, 65F10. | |||
| Date | July 1991 | |||
| Report | Adaptive Linear Equation Solvers in Codes for Large Stiff Systems of Odes (PDF) |
Compressed
DVI: Adaptive Linear Equation Solvers in Codes for Large Stiff Systems of Odes (DVI.Z) | ||
| CS-91-32 | ||||
|---|---|---|---|---|
| Title | Numeration Systems, Linear Recurrences, and Regular Sets | |||
| Authors | J. O. Shallit | |||
| Abstract | Abstract (PDF) | |||
| Date | July 1991 (Revised November 1991) | |||
| Report | Numeration Systems, Linear Recurrences, and Regular Sets (PDF) |
Compressed
DVI: Numeration Systems, Linear Recurrences, and Regular Sets (DVI.Z) | ||
| CS-91-30 | ||||
|---|---|---|---|---|
| Title | Some Facts About Continued Fractions That Should Be Better Known | |||
| Authors | J. O. Shallit | |||
| Abstract |
In
this
report
I
will
give
proofs
of
some
simple
theorems
concerning
continued
fractions
that
are
known
to
the
cognoscenti,
but
for
which
proofs
in
the
literature
seem
to
be
missing,
incomplete,
or
hard
to
locate.
In
particular,
I
will
give
two
proofs
of
the
following
"folk
theorem":
if
5
is
an
irrational
number
whose
continued
fraction
has
bounded
partial
quotients,
then
any
non-trivial
linear
fractional
transformation
of
5
also
has
bounded
partial
quotients.
The
second
proof
is
of
interest
because
it
uses
the
connection
between
continued
fractions
and
finite
automata
first
enunciated
by
G.
N.
Raney
[R].
I
will
assume
that
the
reader
knows
basic
facts
about
continued
fractions,
at
the
level
of
[HW,
Chapter
X]. Note to the reader: It is intended that this report will eventually form a part of a longer article with the same name, written in collaboration with A. J. van der Poorten. | |||
| Date | July 1991 | |||
| Report | Some Facts About Continued Fractions That Should Be Better Known (PDF) |
Compressed
DVI: Some Facts About Continued Fractions That Should Be Better Known (DVI.Z) | ||
| CS-91-27 | ||||
|---|---|---|---|---|
| Title | Numerical Solution of a Turning Point Problem | |||
| Authors | W.-P. Tang | |||
| Abstract | Abstract (PDF) | |||
| Date | July 1991 | |||
| Report | Numerical Solution of a Turning Point Problem (PDF) |
Compressed
DVI: Numerical Solution of a Turning Point Problem (DVI.Z) | ||
| CS-91-17 | ||||
|---|---|---|---|---|
| Title | An Implementation and Evaluation of a Hierarchical Nonlinear Planner | |||
| Authors | Steven G. Woods | |||
| Abstract |
Planning
is
the
process
of
generating
sequences
of
actions
in
order
to
provide
a
method
for
agents
to
modify
the
state
of
the
world
in
which
they
exist.
It
is
well
known
that
the
application
of
abstraction
can
greatly
reduce
the
search
involved
in
creating
plans.
In
this
talk,
an
empirical
evaluation
of
several
different
approaches
to
reducing
search
in
AbTweak,
an
abstract
nonlinear
planning
system,
are
presented. To solve a complex problem using abstraction, one would like to protect parts of the abstract solution that have already been completed during the abstract plan refinement. However, it has not been well understood how this protection can be done profitably; some subgoal protection may indeed result in a decrease in efficiency. The Monotonic Property has been proposed as a form of goal protection in abstract planning. Different versions of this property are investigated with respect to their effect on planning performance in several domains. Furthermore, a series of empirical tests of the utility of the properties are presented, along with an evaluation of different search strategies for abstract planning. In addition, we present a novel abstract planning control strategy known as LeftWedge. This strategy adds a depth-first flavour to a complete search strategy by taking advantage of the fact that less abstract solutions are generally closer to a concrete level solution than more abstract ones. The relative benefit of this approach under various criticality assignments is demonstrated through comparisons with breadth-first strategy. Furthermore, two subgoal selection strategies are presented and compared empirically. | |||
| Date | May 1991 | |||
| Report | An Implementation and Evaluation of a Hierarchical Nonlinear Planner (PDF) |
Compressed
PostScript: An Implementation and Evaluation of a Hierarchical Nonlinear Planner (PS.Z) | ||
| CS-91-14 | ||||
|---|---|---|---|---|
| Title | Introducing a Multi-Dimensional User Model to Tailor Natural Language Generation | |||
| Authors | J. Chu | |||
| Abstract |
Previous
work
has
shown
that
it
is
important
to
include
user
modelling
in
question
answering
systems
in
order
to
tailor
the
output.
In
this
thesis,
we
develop
a
natural
language
response
generation
model
that
handles
both
definitional
and
procedural
questions,
and
employs
a
multi-dimensional
user
model.
The
various
attributes
of
the
user
recorded
in
the
user
model
include
the
user's
role,
domain
knowledge,
preferences,
interests,
receptivity
and
memory
capability.
We
also
address
how
to
represent
the
user's
view
of
a
knowledge
base
to
then
tailor
generation
to
that
user's
view,
and
introduce
a
representation
for
knowledge
bases
with
property
inheritance
based
on
the
Telos
system. We further specify how this multi-dimensional user model influences different stages of McKeown style generation, on determining question type, deciding relevant knowledge, selecting schema, instantiating predicates, and selecting predicates. An algorithm is proposed to describe how the generation process can be tailored according to these influences, and some examples are presented to show that the output is desirable. We also address the problem of conflicts arising from the variation in response generation suggested by different user model attributes and use various weighting schemes to resolve them. Furthermore, we include a procedure for updating the user model after each interaction which also enables the algorithm to be used over multiple sessions, with up-to-date information about the users. | |||
| Date | April 1991 | |||
| Report | Introducing a Multi-Dimensional User Model to Tailor Natural Language Generation (PDF) |
Compressed
PostScript: Introducing a Multi-Dimensional User Model to Tailor Natural Language Generation (PS.Z) | ||
| CS-91-11 | ||||
|---|---|---|---|---|
| Title | Probabilistic Complexity Classes | |||
| Authors | A. Lopez-Ortiz | |||
| Abstract | The purpose of this work is to present an overview of the class of problems solvable in probabilistic polynomial time with double sided error (PP). We explore the relationship of PP to other complexity classes, in particular NP and the polynomial hierarchy, and discuss closure under some standard operations such as intersection and complementation. New proofs are given of some results from the literature using techniques developed by the author. | |||
| Date | March 1991 | |||
| Report | Probabilistic Complexity Classes (PDF) |
Compressed
DVI: Probabilistic Complexity Classes (DVI.Z) | ||
| CS-91-09 | ||||
|---|---|---|---|---|
| Title | Reducing Communication to a Buffer and Queue Model | |||
| Authors | James W. Hong and James P. Black | |||
| Abstract | In our work, we seek to reduce the communication problem to its critical concepts and build a simple, effcient, and general commu- nication paradigm based on these concepts. We present the Buffer and Queue Model, which contains a set of communication abstrac- tions and primitives which is simple and general, rigorous and flexi- ble, low-level and extensible. We show how this model seeks to utilize the effciencies of shared memory communication while providing a universal communications interface between various types of entities across a wide spectrum of environments. We give examples of how various complex communication facilities may be developed from this low-level communication system. | |||
| Date | March 1991 | |||
| Report | Reducing Communication to a Buffer and Queue Model (PDF) |
Compressed
DVI: Reducing Communication to a Buffer and Queue Model (DVI.Z) | ||
| CS-91-04 | ||||
|---|---|---|---|---|
| Title | Preconditioned Conjugate Gradient Methods for Incompressible Navier-Stokes Equations | |||
| Authors | P. Chin, E. F. D'Azevedo, P. A. Forsyth, & W.-P. Tang | |||
| Abstract | A robust technique for solving primitive-variable formulations of the incompressible Navier-Stokes equations is to use Newton iteration for the fully-implicit nonlinear equations. A direct sparse matrix method can be used to solve the Jacobian but is costly for large problems; an alternative is to use an iterative matrix method. This paper investigates effective ways of using a conjugate gradient type method with an incomplete LU factorization preconditioner for two-dimensional incompressible viscous 0ow problems. Special attention is paid to the ordering of unknowns, with emphasis on a minimum updating matrix (MUM) ordering. Numerical results are given for several test problems. | |||
| Date | January 1991 | |||
| Report | Preconditioned Conjugate Gradient Methods for Incompressible Navier-Stokes Equations (PDF) |
Compressed
DVI: Preconditioned Conjugate Gradient Methods for Incompressible Navier-Stokes Equations (DVI.Z) | ||