1992 Technical Reports | SCS | UW
[Please remove <h1>]
| CS-92-56 |
| Title |
Applying Database Dependency
Theory to Software Engineering |
| Authors |
D. Raymond and F.W. Tompa |
| Abstract |
We describe the use of
database dependency theory for investigating software designs. Dependency
theory cap- tures some of the essential constraints implicit in a sys- tem,
and focuses attention on its update properties. The fundamental choice between
redundancy and normalization is directly related to the issue of reuse.
We show how depen- dency theory can be applied to the design of text editors
and spreadsheet systems, and discuss its implications for object-oriented
programming.
|
| Date |
December 1992 |
| Report |
|
|
Adobe
PDF |
Compressed
PostScript |
| CS-92-55 |
| Title |
Partitioning a Chordal
Graph Into Transitive Subgraphs for Parallel Sparse Triangular Solution |
| Authors |
A. Pothen, B.W. Peyton
and X. Yuan |
| Date |
December 1992 |
| Report |
README |
|
Adobe
PDF |
Compressed
PostScript |
| CS-92-53 |
| Title |
A Small-Domain Lower Bound
for Parallel Maximum Computation |
| Authors |
P. Ragde |
| Abstract |
Recent work has shown
that parallel algorithms that are sensitive to the size of the input domain
can improve on more general parallel algorithms. A paper by Berkman et al
in FOCS 1990 demonstrates an O(log log log s)-step algorithm on an n-processor
CRCW PRAM for finding the prefix-maxima of n numbers in the range [1..s].
This paper proves a lower bound demonstrating that no algorithm is asymptotically
faster as a function of s. |
| Date |
November 1992 |
| Report |
|
|
Adobe
PDF |
Compressed
PostScript |
| CS-92-52 |
| Title |
The Stability of the Partitioned
Inverse Approach to Parallel Sparse Triangular |
| Authors |
A. Pothen and N.J. Higham |
| Date |
October 1992 |
| Report |
README |
|
Adobe
PDF |
Compressed
PostScript |
| CS-92-50 |
| Title |
Solving Partial Constraint
Satisfaction Problems Using Local Search and Abstraction |
| Authors |
Qiang Yang and Philip
W.L. Fong |
| Abstract |
Partial constraint satisfaction
problems (PCSPs) were proposed by Freuder and Wallace to address some of
the representational difficulties with traditional constraint satisfaction
techniques. However, the reasoning method of their proposal was limited
to traditional backtracking based algorithms. In this paper, we extend the
PCSP model by associating it with a local search algorithm, which has found
great successes in solving many large scale problems in the past. Furthermore,
we extend the combined model to incorporate abstract problem solving, and
show that the extended model has not only the advantages of both PCSP and
local search, but also a number of new features useful for scheduling applications.
We demonstrate the feasibility of our approach by an application to a university
course scheduling domain. |
| Date |
September 1992 |
| Report |
|
|
Adobe
PDF |
|
| CS-92-49 |
| Title |
Speech Acts and Pragmatics
in Sentence Generation Masters Thesis |
| Authors |
Cameron Shelley |
| Abstract |
A fundamental advance
in recent theories about natural language pragmatics involves the realization
that people use language not just to describe propositions, but also to
perform actions. This idea can be taken as a given starting point for investigating
the questions: how are linguistic actions, or {\it speech acts}, performed
and understood? How far can descriptions, as locutions, be used as speech
acts? What role does inference play in the performance and understanding
of speech acts?
Many previous theories of speech acts have taken speech acts to be independent
and primitive units of communication, implicit in, but separate from, description
and inference. In this thesis, I argue for an alternative model of speech
acts. I propose that speech acts can be explained by a combination of description
and inference, without the requirement of separate conventions. This explanation
relies instead on an account of explicit linguistic units, including clausal
moods and performative verbs, in addition to the inferential mechanism provided
by Gricean conversational implicature.
In addition to outlining a model for the description and comparison of speech
acts, I present a small sentence generator that partially implements the
model, and discuss how it can be enhanced in future. Also, I illustrate
the relevance of this model for a current computational theory of syntactic
style. My model of speech acts suggests how this computational stylistic
theory can be extended into the areas of semantic style and lexical style. |
| Date |
September 1992 |
| Report |
|
|
Adobe
PDF |
Compressed
PostScript |
| CS-92-45 |
| Title |
Downward Refinement and
the Efficiency of Hierarchical Problem Solving |
| Authors |
Fahiem Bacchus and Qiang
Yang |
| Abstract |
Analysis and experiments
have shown that hierarchical problem-solving is most effective when the
hierarchy satisfies the downward refinement property “DRP”, whereby every
abstract solution can be refined to a concrete-level solution without backtracking
across abstraction levels. However, the DRP is a strong requirement that
is not often met in practice. In this paper we examine the case when the
DRP fails, and provide an analytical model of search complexity parameterized
by the probability of an abstract solution being refinable. Our model provides
a more accurate picture of the effectiveness of hierarchical problemfisolving.
We then formalize the DRP in Abstripsfistyle hierarchies, providing a syntactic
test that can be applied to determine if a hierarchy satisfies the DRP.
Finally, we describe an algorithm called Highpoint that we have developed.
This algorithm builds on the Alpine algorithm of Knoblock in that it automatically
generates abstraction hierarchies. However, it uses the theoretical tools
we have developed to generate hierarchies superior to those generated by
Alpine. This superiority is demonstrated empirically |
| Date |
September 1992 |
| Report |
|
|
Adobe
PDF |
|
| CS-92-44 |
| Title |
Anisotropic Mesh Transformations
and Optimal Error Control |
| Authors |
R. B. Simpson |
| Date |
August 1992 |
| Report |
|
|
Adobe
PDF |
Compressed
PostScript |
| CS-92-42 |
| Title |
Justified Plans and Ordered
Hierarchies |
| Authors |
Eugene Fink |
| Abstract |
The use of abstraction
in problem solving is an effective approach to reducing search, but finding
good abstractions is a di cult problem. The first attempt to automatically
gen erate a hierarchy of abstraction spaces was made by Sacerdoti in 1974.
In 1990 Knoblock built the system ALPINE, which completely automates the
formation of a hierarchy by abstracting preconditions of operators. To formalize
his method, Knoblock introduced the notion of ordered abstraction hierarchies,
in attempt to capture the intuition behind "good" hierarchies.
In this thesis we continue the work started by Knoblock. We present further
formalization of several important notions of abstract planning and describe
methods to increase the number of abstraction levels without violating the
ordered property of a hierarchy. We start by defining the justification
of a non linear plan. Justification captures the intuition behind "good"
plans, which do not contain useless actions. We introduce several kinds
of justification, and describe algorithms that find different justifications
of a given plan by removing useless operators. We prove that the task to
find the "best possible" justification is NP complete.
The notion of justified plans leads us to define several kinds of semi,ordered
abstraction hierarchies, which preserve the "good" properties of Knoblock's
ordered hierarchies, but may have more abstraction levels. Finally, we present
an algorithm for automatically abstracting not only preconditions but also
effects of operators. This algorithm generates hierarchies with more levels
of abstraction than ALPINE, and may increase the e ciency of planning in
many problem domains. The algorithm may generate both problem independent
and problem specific hierarchies. |
| Date |
August 1992 |
| Report |
|
|
Adobe
PDF |
Compressed
PostScript |
| CS-92-34 |
| Title |
An Evaluation of the Temporal
Coherence Heuristic for Nonlinear Planning |
| Authors |
Cheryl Murray and Qiang
Yang |
| Abstract |
This paper presents an
evaluation of a heuristic for partial-order planning, known as temporal
coherence. The temporal coherence heuristic was proposed by Drummond and
Currie as a method to improve the effciency of partial-order planning without
losing the ability to fnd a solution (i.e. completeness). It works by using
a set of domain constraints to prune away plans that do not "make sense,"
or temporally inco- herent. Our analysis shows that, while intuitively appealing,
temporal coherence can only be applied to a very specific implementation
of a partial-order planner and still maintain completeness. Furthermore,
the heuristic does not always improve planning effciency in some cases,
its application can actually degrade the effciency of planning dramatically.
To understand when the heuristic will work well, we conducted complex- ity
analysis and empirical tests. Our results show that temporal coherence works
well when strong domain constraints exist that significantly reduce the
search space, when the number of subgoals is small, when the plan size is
not too large and when it is inexpensive to check each domain constraint. |
| Date |
June 1992 |
| Report |
|
|
Adobe
PDF |
Compressed
PostScript |
| CS-92-18 |
| Title |
A Sublinear Space, Polynomial
Time Algorithm for Directed $s$-$t$ Connectivity |
| Authors |
Greg Barnes, Jonathon
F. Buss, Walter L. Ruzzo and Baruch Schieber |
| Abstract |
Directed $s$-$t$ connectivity
is the problem of detecting whether there is a path from vertex $s$ to vertex
$t$ in a directed graph. We present the first known deterministic sublinear
space, polynomial time algorithm for directed $s$-$t$ connectivity. For
$n$-vertex graphs, the algorithm can use as little as $n/2^{\Theta(\sqrt{\log
n})}$ space while still running in polynomial time. |
| Date |
September 1993 |
| Report |
|
|
Adobe
PDF |
Compressed
PostScript |