COMPUTER SCIENCE TECHNICAL REPORTS

1994 SERIES

SCHOOL OF COMPUTER SCIENCE

CARNEGIE MELLON UNIVERSITY

PITTSBURGH, PA  15213-3891

NOTE: Please read this Copyright notice before proceeding.

CMU-CS-94-100

Large Granularity Cache Coherence for Intermittent Connectivity
Lily Mummert, Mahadev Satyanarayanan
April 1994

CMU-CS-94-101

List Ranking and List Scan on the Cray C-90
Margaret Reid-Miller, Guy E. Blelloch
February 1994
37 pages

CMU-CS-94-102

Non-Intrusive Gaze Tracking Using Artificial Neural Networks
Shumeet Baluja, Dean Pomerleau
January 1994
16 pages

CMU-CS-94-103

Combining Symbolic Computation and Theorem Proving: Some Problems of Ramanujan
Edmund Clarke, Xudong Zhao
January 1994

CMU-CS-94-104

Advanced Languages for Systems Software: The Fox Project in 1994
Robert Harper, Peter Lee
January 1994
29 pages
(Also appears as CMU-CS-FOX-94-01)

CMU-CS-94-105

Symbolic Debugging of Globally Optimized Code: Data Value Problems and Their Solutions
Ali-Reza Adl-Tabatabai, Thomas Gross
January 1994

CMU-CS-94-106

Communication and Memory Requirements as the Basis for Mapping Task and Data Parallel Programs
Jaspal Subhlok, David R. O'Hallaron, Thomas Gross, Peter A. Dinda, Jon Webb
January 1994

CMU-CS-94-106R (REVISED VERSION OF CMU-CS-94-106.ps)

Communication and Memory Requirements as the Basis for Mapping Task and Data Parallel Programs
Jaspal Subhlok, David R. O'Hallaron, Thomas Gross, Peter A. Dinda, Jon Webb
August 1994

CMU-CS-94-107 (text)

CMU-CS-94-107A (titlepage)

Procedure Calls are the Assembly Language of Software Interconnection: Connectors Deserve First-Class Status
January 1994
18 pages

CMU-CS-94-108

A Compile Time Model for Composing Parallel Programs
Susan Hinrichs
April 1994

CMU-CS-94-109

Pursuit: Visual Programming in a Visual Domain
Francesmary Modugno, Brad A. Myers
January 1994
25 pages

CMU-CS-94-110

Refinement Types for ML
Tim Freeman
March 1994
Ph.D. Thesis

CMU-CS-94-111

Unpublished (will not appear)

CMU-CS-94-112

Task Parallel Programming in Fx
Jaspal Subhlok, David R. O'Hallaron, Thomas Gross
August 1994
10 pages

CMU-CS-94-113 (Unavailable via ftp)

O(Log^2 n) Time Efficient Parallel Factorization of Desne, Sparse Separable, and Banded Matrices
John H. Reif
April 1994
31 pages

CMU-CS-94-114

Another Look at LTL Model Checking
Edmund Clarke, Orna Grumberg, Kiyoharu Hamaguchi
February 1994
22 pages

CMU-CS-94-115

Formal Connectors
Robert Allen, David Garlan
March 1994
26 pages

CMU-CS-94-116

Incremental Recompilation for Standard ML of New Jersey
Robert Harper, Peter Lee, Frank Pfenning, Eugene Rollins
February 1994
14 pages
(Also appears as CMU-CS-FOX-94-02)

CMU-CS-94-117

iwmeter: A Real-Time and Interactive Parallel Software Monitor for iWarp
Ming-Jen Chan, Eka N. Ginting
February 1994
20 pages

CMU-CS-94-118 (Unavailable via ftp)

Projective and Object Space Geometry for Monocular Building Extraction
J. Chris McGlone, Jefferey A. Shufelt
March 1994
28 pages

CMU-CS-94-119

Synrgen: An Extensible File Reference Generator
Maria R. Ebling, Mahadev Satyanarayanan
February 1994
18 pages

CMU-CS-94-120

An Empirical Study of a Highly Avaiable File System
Brian D. Noble, Mahadev Satyanarayanan
February 1994
14 pages

CMU-CS-94-121

The Breakdown of Operators when Interacting with the External World
Garrett A. Pelton, Jill Fain Lehman
February 1994

CMU-CS-94-122

Compiling with Non-Parametric Polymorphism (Preliminary Version)
Robert Harper and Greg Morrisett
February 1994
28 pages

CMU-CS-94-123

Prodigy Planning Algorithm
Eugene Fink, Manuela Veloso
March 1994

CMU-CS-94-124

A Comparison of Streams and Time Advance As Paradigms for Multimedia Systems
Roger B. Dannenberg, Dean Rubine
March 1994
20 pages

CMU-CS-94-125 (Technical Report)

CMU-CS-94-125A (Collection of instructional slides)

CMU-CS-94-125 (Compressed)

CMU-CS-94-125 (Erratum - Ascii Format)

An Introduction to the Conjugate Gradient Method Without the Agonizing Pain
Jonathan R. Shewchuk
March 1994
61 pages

CMU-CS-94-126 [See CMU-CS-94-126R.ps]

Structuring Z Specifications with Views
Daniel Jackson
March 1994
27 pages

CMU-CS-94-126 [Supercedes CMU-CS-94-126.ps.Z]

Structuring Z Specifications with Views
Daniel Jackson
June 1995
29 pages

CMU-CS-94-127

A Database for Analyzing Sequential Behavioral Data and Their Associated Cognitive Models
Bonnie E. John
May 1994
24 pages
(Also appears as CMU-HCII-94-101)

CMU-CS-94-128 (Unavailable via ftp)

Architectures and Algorithms for On-Line Failure Recovery in Redundant Disk Arrays
Mark Holland, Garth A. Gibson, Daniel P. Siewiorek
March 1994

CMU-CS-94-129

ML Partial Evaluation using Set-Based Analysis
Karoline Malmkjaer, Nevin Heintze, Olivier Danvy
February 1994
(Also appears as CMU-CS-FOX-94-04)

CMU-CS-94-130

Asynchronous Optimistic Rollback Recovery Using Secure Distributed Time
Sean W. Smith, David B. Johnson, J. Doug Tygar
March 1994

CMU-CS-94-131

The CMU Task Parallel Program Suite
Peter Dinda, Thomas Gross, David O'Hallaron, Edwared Segall, James Stichnoth,
Jaspal Subhlok, Jon Webb, Bwolen Yang
March 1994

CMU-CS-94-132

Combining Left and Right Unlinking for Matching a Large Number of Learned Rules
Robert B. Doorenbos
April 1994

CMU-CS-94-133

Performance Debugging Based on Scalability Analysis
Takashi Suzuoka, Jaspal Subhlok, Thomas Gross
June 1994
31 pages

CMU-CS-94-134 (Unavailable via ftp)

Collected Papers of the Soar/IFOR Project: Spring 1994
W. Lewis Johnson, Randolph M. Jones, David Keirsey, Frank V. Koss, John E. Laird, Jill F. Lehman, Paul E. Neilsen, Paul S. Rosenbloom, Robert Rubinoff, Karl B. Schwamb, Milind Tambe, Michael van Lent, Robert Wray
April 1994
107 pages

CMU-CS-94-135

Security and Privacy for Partial Order Time
Sean W. Smith, J. Doug Tygar
April 1994

CMU-CS-94-136 (Unavailable for ftp)

The Role of Emotion in Believable Agents
Joseph Bates
April 1994

CMU-CS-94-137

Adaptable Binary Programs
Robert Wahbe, Steven Lucco, Susan L. Graham
April 1994
18 pages

CMU-CS-94-138

Adaptive Statistical Language Modeling: A Maximum Entropy Approach
Ronald Rosenfeld
April 1994
Ph.D. Thesis
116 pages

CMU-CS-94-139

Unpublished (will not appear)

CMU-CS-94-140

An Architecture for Optimal All-to-All Personalized Communication
Susan Hinrichs, Corey Kosak, David R. O'Hallaron, Thomas M. Stricker, Riichiro Take
September 1994
32 pages

CMU-CS-94-141

Performance Measurements of the Multimedia Testbed on Real-Time Mach
Roger B. Dannenberg, David B. Anderson, Tom Neuendorffer, Dean Rubine
April 1994
20 pages

CMU-CS-94-142 (Unavailable via ftp)

Control Transfer in Operating System Kernels
Richard P. Draves
May 1994
Ph.D. Thesis
150 pages

CMU-CS-94-143

Linear Congruential Generators Over Elliptic Curves
Sean Hallgren
Senior Honors Thesis
May 1994
12 pages

CMU-CS-94-144 (Unavailable via ftp)

On-Line Scheduling on Parallel Machines
Jiri Sgall
Ph.D. Thesis
May 1994

CMU-CS-94-145

The Impact of Software Structure and Policy on CPU and Memory System
Performance
J. Bradley Chen
Ph.D. Thesis
May 1994
172 pages

CMU-CS-94-146

Real-Time Symbolic Model Checking for Discrete Time Models
Sergio V. Campos, Edmund M. Clarke
May 1994
19 pages

CMU-CS-94-147

Computing Quantitative Characteristics of Finite-State Real-Time Systems
Sergio Campos, Edmund Clarke, Wilfredo Marrero, Marius Minea, Hiromi Hiraishi
May 1994
23 pages

CMU-CS-94-148

Measuring Software Dependability by Robustness Benchmarking
Arup Mukherjee, Daniel P. Siewiorek
May 1994
26 pages

CMU-CS-94-149

Using Secure Coprocessors
Bennet Yee
May 1994
Ph.D. Thesis
106 pages

CMU-CS-94-150

Making Structured Graphics and Constraints Practical for Large-Scale Applications
Brad A. Myers, Dario A. Giuse, Andrew Mickish, David S. Kosbie
26 pages
(Also appears as CMU-HCII-94-100)

CMU-CS-94-151

Using Belief to Reason About Cache Coherence
Lily Mummert, Jeannette M. Wing, Mahadev Satyanarayanan
May 1994
17 pages

CMU-CS-94-152

Sensor Placement Design for Object Pose Determination with Three Light-Stripe Range Finders
Keiichi Kemmotsu, Takeo Kanade
May 1994
27 pages

CMU-CS-94-153

Dome: Distributed Object Migration Environment
Adam Beguelin, Erik Seligman, Michael Starkey
May 1994
27 pages

CMU-CS-94-154 (Unavailable via ftp)

Beyond Objects: A Software Design Paradigm Based on Process Control
Mary Shaw
January 1994
18 pages
(Also appears as CMU/SEI-94-TR-15)

CMU-CS-94-155

Locating and Tracking of Human Faces with Neural Networks
H. Martin Hunke
August 1994
84 pages

CMU-CS-94-156

Extending Programming by Demonstration with Hierarchical Event Histories
David S. Kosbie, Brad A. Muers
May 1994
20 pages

CMU-CS-94-157

Recognition Confidence Measures: Detection of Misrecognitions and Out-Of-Vocabulary Words
Sheryl R. Young
May 1994
18 pages

CMU-CS-94-158

A Sequential Factorization Method for Recovering Shape and Motion from Image Streams
Toshihiko Morita, Takeo Kanade
May 1994
29 pages

CMU-CS-94-159

Solving Recursive Domain Equations with Enriched Categories
Kim Ritter Wagner
Ph.D. Thesis
July 1994
106 pages

CMU-CS-94-160

Verification of Arithmetic Functions with Binary Moment Diagrams
Randy E. Bryant, Yirng-An Chen
May 1994
41 pages

CMU-CS-94-161

A Practical Approach to Drawing Undirected Graphs
Daniel Tunkelang
June 1994
30 pages

CMU-CS-94-162

Assessment of the ACSE Science Learning Environment and the Impact of Movies and Simulations
John F. Pane
June 1994
20 pages

CMU-CS-94-163

Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning
Shumeet Baluja
June 1994
41 pages

CMU-CS-94-164

On-Line Data Reconstruction in Redundant Disk Arrays
Mark Holland
Ph.D. Thesis (Electrical and Computer Engineering)
May 1994
254 pages

CMU-CS-94-165

On Predictable Operating System Protocol Processing
Clifford W. Mercer, Jim Zelenka, Ragunathan Rajkumar
May 1994
20 pages

CMU-CS-94-166

An Introduction to Software Architecture
David Garlan, Mary Shaw
January 1994
50 pages
(Also appears as CMU/SEI-94-TR-21)

CMU-CS-94-167

An Active Multibaseline Stereo System with Real-Time Image Acquisition
Sing Bing Kang, Jon Webb, C. Lawrence Zitnick, Takeo Kanade
September 1994
31 pages

CMU-CS-94-168 (Unavailable for ftp)

B* Probability Based Search
Hans J. Berliner, Chris McConnell
June 1994
54 pages

CMU-CS-94-169

Chopping: A Generalization of Slicing
Daniel Jackson, Eugene J. Rollins
July 1994
21 pages

CMU-CS-94-170

A Redundant Disk Array Architecture for Efficient Small Writes
Daniel Stodolsky, Mark Holland, William V. Courtright II, Garth Gibson
July 1994
27 pages

CMU-CS-94-171

A Structured TCP in Standard ML
Edoardo S. Biagioni
July 1994
(Also appears as CMU-CS-FOX-94-105)
19 pages

CMU-CS-94-172

Program Verification for Optimized Byte Copy
Edoardo S. Biagioni
July 1994
21 pages

CMU-CS-94-173

Improved Approximation Guarantees for Minimum-Weight k-trees and Prize-collecting Salesmen
Baruch Awerbuch, Yossi Azar, Avrim Blum, Santosh Vempala
August 1994
11 pages

CMU-CS-94-174

CMU-CS-94-174R (a revised version - October 1994)

Representing and Reformulating Diagonalization Methods
Erica Melis
July 1994
22 pages

CMU-CS-94-175

Integrating Human Factors with Software Engineering Practices
William E. Hefley, Elizabeth A. Buie, Gene F. Lynch, Michael J. Muller, Douglas G. Hoecker, Jim Carter, J. Thomas Roth
July 1994
11 pages
(Also appears as CMU-HCII-94-103)

CMU-CS-94-176

Interactive Sketching for the Early Stages of User Interface Design
James A. Landay, Brad A. Myers
July 1994
19 pages
(Also appears as CMU-HCII-94-104)

CMU-CS-94-177 (Unavailable for ftp)

Secure Distributed Time for Secure Distributed Protocols
Sean W. Smith
Ph.D. Thesis
September 1994
189 pages

CMU-CS-94-178 (Unavailable via ftp)

Experience with a Course on Architectures for Software Systems, Part II: Educational Materials
David Garlan, Mary Shaw, Jose Galmes
August 1994
483 pages
[Also appears as CMU/SEI-94-TR-20, ESC-TR-94-020]

CMU-CS-94-179

Online Performance-Improvement Algorithms
Prasad Chalasani
Ph.D. Thesis
August 1994
112 pages

CMU-CS-94-180

Research in Parallel Computing Final Report: 1987-90
Jutta Denton, C. Roy Taylor, Editors
August 1994
56 pages

CMU-CS-94-181

The GOMS Family of Analysis Techniques: Tools for Design and Evaluation
Bonnie E. John, David E. Kieras
August 1994
54 pages
(Also appears as CMU-HCII-94-106)

CMU-CS-94-182

User Interface Software Tools
Brad A. Myers
(Also appears as CMU-HCII-94-106)
46 pages

CMU-CS-94-183

Application-Aware Adaptation for Mobile Computing
Mahadev Satyanarayanan, Brian Noble, Puneet Kumar, Morgan Price
July 1994
7 pages

CMU-CS-94-184

Learning One More Thing
Sebastian Thrun, Tom M. Mitchell
September 1994
22 pages

CMU-CS-94-185

Compiling Polymorphism Using Intensional Type Analysis
Robert Harper, Greg Morrisett
September 1994
(Also appears as CMU-CS-FOX-94-07)
26 pages

CMU-CS-94-186 (Unavailable for ftp)

The Assembly Tower and Some Categorical and Algebraic Aspects of Frame Theory
J. Todd Wilson
Ph.D. Thesis
May 1994
141 pages

CMU-CS-94-187

The Effect of Context on Training: Is Learning Situated?
Lynne Reder, Roberta L. Klatzky
September 1994
(Also appears as CMU-HCII-94-108)
32 pages

CMU-CS-94-188

Inference and Estimation of a Long-Range Trigram Model
Stephen Della Pietra, Vincent Della Pietra, John Gillett, John Lafferty, Harry Printz, Lubos Ures
September 1994
19 pages

CMU-CS-94-189

A Tabular Interface for Automated Verification of Event-Based Dialogs
Hung-Ming Wang, Gregory Abowd
July 1994
38 pages

CMU-CS-94-190

Learning DNF over the Uniform Distribution Using a Quantum Example Oracle
Nader H. Bshouty, Jeffrey Jackson
September 1994
18 pages

CMU-CS-94-191

Client-Server Interactions in Multi-Server Operating Systems: The Mach-US Approach
J. Mark Stevenson, Daniel P. Julin
September 1994
17 pages

CMU-CS-94-192

A Scalable Video Rate Camera Interface
Jon A. Webb, Thomas Warfel, Sing Bing Kang
September 1994
16 pages

CMU-CS-94-193

Backward Error Recovery in Redundant Disk Arrays
William V. Courtright II, Garth A. Gibson
September 1994
18 pages

CMU-CS-94-194

CMU-CS-94-194A

Specifying Weak Sets
Jeannette M. Wing, David C. Steere
September 1994
20 pages

CMU-CS-94-195

Unpublished (will not appear)

CMU-CS-94-196

A Parallel Complexity Model for Functional Languages
Guy Blelloch, John Greiner
October 1994
26 pages

CMU-CS-94-197 (Unavailable via ftp)

Research in the Automated Analysis of Remotely Sensed Imagery: 1993-1994
David M. McKeown, Jr., Steven Douglas Cochran, Stephen J. Ford, Stephen J. Gifford, Wilson A. Harvey, Yuan C. Hsieh, J. Chris McGlone, Michael F. Polis, Michel Roux, Jefferey A. Shufelt
October 1994

CMU-CS-94-198

Modal Event Calculus in Lolli
Iliano Cervesato, Luca Chittaro, Angelo Montanari
October 1994
23 pages

CMU-CS-94-199 (Unavailable via ftp)

Automating the Construction of Large Scale Virtual Worlds
Michael F. Polis, Stephen J. Gifford, David M. McKeown
October 1994

CMU-CS-94-200

Porting a Vector Library: A Comparison of MPI, Paris, CMMD, and PVM (or, "I'll never have to port CVL again")
Jonathan C. Hardwick
November 1994
18 pages

CMU-CS-94-201

Measuring the Cost of Storage Management
David Tarditi, Amer Diwan
May 1995
(Also appears as CMU-CS-FOX-94-08)
15 pages

CMU-CS-94-202 (Unavailable via ftp)

Adaptive Vergence for the Stereo Matching of Oblique Imagery
Steven Douglas Cochran
October 1994

CMU-CS-94-203

Unavailable to date

CMU-CS-94-204

Efficient Generation of Counterexamples and Witnesses in Symbolic Model Checking
Edmund Clarke, Orna Grumberg, Kenneth McMillan, Xudong Zhao
October 1994
19 pages

CMU-CS-94-205

Performance Evaluation of a New Parallel Preconditioner
Keith D. Gremban, Gary L. Miller, Marco Zagha
October 1994
33 pages

CMU-CS-94-206

Automatically Selecting and Using Primary Effects in Planning:
Theory and Experiments
Eugene Fink, Qiang Yane
October 1994
40 pages

CMU-CS-94-207

Problems in Rewriting Applied to Categorical Concepts by the Example of a Computational Comonad
Wolfgang Gehrke
October 1994
16 pages

CMU-CS-94-208 (Unavailable via ftp)

Inductive Boolean Function Manipulation: A Hardware Verification Methodology for Automatic Induction
Aarti Gupta
Ph.D. Thesis
October 1994

CMU-CS-94-209

Reducing Network Depth in the Cascade-Correlation Learning Architecture
Shumeet Baluja, Scott E. Fahlman
October 1994
11 pages

CMU-CS-94-210

Characteristics of Higher-level Languages for Software Architecture
Mary Shaw, David Garlan
December 1994
19 pages

CMU-CS-94-211 (Unavailable via ftp)

Scalability in Production System Programs
Anurag Acharya
Ph.D. Thesis
November 1994
366 pages

CMU-CS-94-212

Operating System Support for Coexistence of Real-Time and Conventional Scheduling
David B. Golub
November 1994
12 pages

CMU-CS-94-213

Long Term Distributed File Reference Tracing: Implementation and Experience
Lily Mummert, Mahadev Satyanarayanan
November 1994
30 pages

CMU-CS-94-214

Flexible and Safe Resolution of File Conflicts
Puneet Kumar, Mahadev Satyanarayanan
November 1994
15 pages

CMU-CS-94-215

Mitigating the Effects of Optimistic Replication in a Distributed File System
Puneet Kumar
Ph.D. Thesis
December 1994
187 pages

CMU-CS-94-216

A Case for Dynamic Sets in Operating Systems
David Steere, Mahadev Satyanarayanan
November 1994
18 pages

CMU-CS-94-217

A Differential Approach to Graphical Interaction
Michael L. Gleicher
Ph.D. Thesis
November 1994

CMU-CS-94-218

A structural Proof of Cut Elimination and Its Representation in
a Logical Framework
Frank Pfenning
November 1994
67 pages

CMU-CS-94-219

Exploiting Symmetry in the Model Checking of Relational Specifications
Daniel Jackson
December 1994
22 pages

CMU-CS-94-220

A Multi-body Factorization Methods for Motion Analysis
Joao Costeira, Takeo Kanade
September 1994
25 pages

CMU-CS-94-221 CMU-CS-94-221A.ps, CMU-CS-94-221B.ps

Reflectance Analysis Under Solar Illumination
Yoichi Sato, Katsushi Ikeuchi
December 1994
43 pages

CMU-CS-94-222

Structural Cut Elimination in Linear Logic
Frank Pfenning
December 1994
64 pages

CMU-CS-94-223

High-Level Fault Tolerance in Distributed Programs
Erik Seligman, Adam Beguelin
December 1994
12 pages

CMU-CS-94-224

Visual Tracking of Self-Occulding Articulated Objects
James M. Rehg, Takeo Kanade
December 1994
43 pages

CMU-CS-94-225

Unpublished (will not appear)

CMU-CS-94-226 (Unavailable via ftp)

An Architectural Design of A Toolkit for Synchronous Groupware Applications
Nobuhisa Yoda, Brad A. Myers
December 1994
38 pages
[Also appears as CMU-HCII-94-109 and CMU-INI-TR-1994-7]

CMU-CS-94-227

Control-Flow Analysis and Type Systems
Nevin Heintze
December 1994
18 pages
[Also appears as CMU-CS-FOX-94-09]

CMU-CS-94-228

On the Performance of Spectral Graph Partitioning Methods
Stephen Guattery, Gary L. Miller
December 1994
33 pages

CMU-CS-94-229

Unpublished (will not appear)

CMU-CS-94-230 (Unavailable via ftp)

Wax: A Wide Area Computation System
Peter D. Stout
Ph.D. Thesis
December 1994