1992 technical reports

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)