| 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 | Applying Database Dependency Theory to Software Engineering (PDF) |
Compressed
PostScript: Applying Database Dependency Theory to Software Engineering (PS.Z) | ||
| 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 | Partitioning a Chordal Graph Into Transitive Subgraphs for Parallel Sparse Triangular Solution (PDF) |
Compressed
PostScript: Partitioning a Chordal Graph Into Transitive Subgraphs for Parallel Sparse Triangular Solution (PS.Z) | |
| 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 | A Small-Domain Lower Bound for Parallel Maximum Computation (PDF) |
Compressed
PostScript: A Small-Domain Lower Bound for Parallel Maximum Computation (GZIP) | ||
| 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 | The Stability of the Partitioned Inverse Approach to Parallel Sparse Triangular (PDF) |
Compressed
PostScript: The Stability of the Partitioned Inverse Approach to Parallel Sparse Triangular (PS.Z) | |
| CS-92-51 | ||||
|---|---|---|---|---|
| Title | Highly Parallel Sparse Triangular Solution | |||
| Authors | A. Pothen, F.L. Alvarado and R.S. Schreiber | |||
| Date | October 1992 | |||
| Report | README | Highly Parallel Sparse Triangular Solution (PDF) |
Compressed
PostScript: Highly Parallel Sparse Triangular Solution (PS.Z) | |
| 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 | Solving Partial Constraint Satisfaction Problems Using Local Search and Abstraction (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 | Speech Acts and Pragmatics in Sentence Generation Masters Thesis (PDF) |
Compressed
PostScript: Speech Acts and Pragmatics in Sentence Generation Masters Thesis (GZIP) | ||
| 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 | Downward Refinement and the Efficiency of Hierarchical Problem Solving (PDF) | |||
| CS-92-44 | ||||
|---|---|---|---|---|
| Title | Anisotropic Mesh Transformations and Optimal Error Control | |||
| Authors | R. B. Simpson | |||
| Date | August 1992 | |||
| Report | Anisotropic Mesh Transformations and Optimal Error Control (PDF) |
Compressed
PostScript: Anisotropic Mesh Transformations and Optimal Error Control (PS.Z) | ||
| 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 | Justified Plans and Ordered Hierarchies (PDF) |
Compressed
PostScript: Justified Plans and Ordered Hierarchies (PS.Z) | ||
| 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 | An Evaluation of the Temporal Coherence Heuristic for Nonlinear Planning (PDF) |
Compressed
PostScript: An Evaluation of the Temporal Coherence Heuristic for Nonlinear Planning (GZIP) | ||
| 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 | A Sublinear Space, Polynomial Time Algorithm for Directed $s$-$t$ Connectivity (PDF) | A Sublinear Space, Polynomial Time Algorithm for Directed $s$-$t$ Connectivity (PS.Z) | ||