1991 Technical Reports | SCS | UW
[Please remove <h1>]
| 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 |
|
|
Adobe
PDF |
Compressed
Latex |
| 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
|
|
Adobe
PDF |
Compressed
Latex |
| 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 |
|
|
Adobe
PDF |
Compressed
Latex |
| 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
|
|
Adobe
PDF |
Compressed
Latex |
| 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 di1culty 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: |
Intro,
Algebra, Concurrency,
SQO, Storage, Types |
PDF Reports: |
Intro,
Algebra, Concurrency,
SQO, Storage, Types |
| 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 su1ciently 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 |
|
|
Adobe
PDF |
Compressed
Latex |
| 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 |
|
|
Adobe
PDF |
Compressed
Latex |
| 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 |
|
|
Adobe
PDF |
Compressed
Latex |
| 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 |
|
|
Adobe
PDF |
Compressed
Latex |
| 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 |
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 |
|
|
Adobe
PDF |
Compressed
Latex |
| CS-91-32 |
| Title |
Numeration Systems, Linear
Recurrences, and Regular Sets |
| Authors |
J. O. Shallit |
| Abstract |
PDF
Abstract |
| Date |
July 1991 (Revised November
1991) |
| Report |
|
|
Adobe
PDF |
Compressed
Latex |
| 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 |
|
|
Adobe
PDF |
Compressed
Latex |
| 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 flavor 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 modeling 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
|
|
Adobe
PDF |
Compressed
Latex |
| 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 |
|
|
Adobe
PDF |
Compressed
Latex |
| 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 |
|
|
Adobe
PDF |
Compressed
Latex |