COMPUTER SCIENCE TECHNICAL REPORTS

1993 SERIES

SCHOOL OF COMPUTER SCIENCE

CARNEGIE MELLON UNIVERSITY

PITTSBURGH, PA   15213-3891

NOTE: Please read this Copyright notice before proceeding.

CMU-CS-93-100 (Unavailable via ftp)

Uncertainty in Object Pose Determination with Three Light-Stripe Range Measurements
Keiichi Kemmotsu, Takeo Kanade
January 1993

CMU-CS-93-101 (Unavailable via ftp)

A Methodology and Software Environment for Testing Process Model's Sequential Predictions with Protocols
Frank E. Ritter
Ph.D. Thesis (Psychology)
December 1992

CMU-CS-93-102 (Unavailable via ftp)

Experiments in Multiple-Baseline Stereo
Tomoharu Nakahara, Takeo Kanade
August 1992

CMU-CS-93-103 (Unavailable via ftp)

Reinforcement Learning for Robots Using Neural Networks
Long-Ji Lin
Ph.D. Thesis
January 1993

CMU-CS-93-104 (Unavailable via ftp)

YARF: An Open-Ended Framework for Robot Road Following
Karl Kluge
Ph.D. Thesis
February 1993

CMU-CS-93-105 (Unavailable via ftp)

ACM SIGPLAN Workshop on ML and its Applications
Peter Lee, Editor
June 1992

CMU-CS-93-106

Complexity Analysis of Real-Time Reinforcement Learning Applied to Finding Shortest Paths in Deterministic Domains
Sven Koenig, Reid G. Simmons
December 1992
99 pages

CMU-CS-93-107 (Compressed File)

Cryptography: It's Not Just For Electronic Mail Anymore
J.D. Tygar, Bennet Yee
March 1993
21 pages

CMU-CS-93-108 (Unavailable via ftp)

The Second Garnet Compendium: Collected Papers 1990-1992
Brad A. Myers, Editor
February 1993

CMU-CS-93-109

Efficient Compilation of Array Statements for Private Memory Multicomputers
James M. Stichnoth
February 1993
49 pages

CMU-CS-93-110

Unpublished

CMU-CS-93-111 (Unavailable via ftp)

Applying High-Level Language Paradigms to Communications Software for Distributed Systems
Ellen H. Siegel
Ph.D. Thesis
January 1993

CMU-CS-93-112

Implementation of a Portable Nested Data-Parallel Language
Guy E. Blelloch, Siddhartha Chatterjee, Jonathan C. Hardwick, Jay Sipelstein, Marco Zagha
February 1993
28 pages

CMU-CS-93-113

A Status Report on Research in Transparent Informed Prefetching
R. Hugo Patterson, Garth A. Gibson, Mahadev Satyanarayanan
February 1993
14 pages

CMU-CS-93-114

CVL: A C Vector Library Manual: Version 2
Guy E. Blelloch, Siddhartha Chatterjee, Jonathan C. Hardwick, Margaret Reid-Miller, Jay Sipelstein, Marco Zagha
February 1993
15 pages

CMU-CS-93-115

Class Notes: Programming Parallel Algorithms CS 15-840 (Fall 1992)
Guy E. Blelloch, Jonathan C. Hardwick
February 1993
141 pages

CMU-CS-93-116

Signed Vector Timestamps: A Secure Protocol for Partial Order Time
Sean W. Smith, J. Doug Tygar
October 1991; version of February 1993
15 pages

CMU-CS-93-117

CMU-CS-93-117A (figure 5)

CMU-CS-93-117B (figure 7)

Neural Representation of Space Using Sinusoidal Arrays
David S. Touretzky, A. David Redish, Hank S. Wan
March 1993
13 pages

CMU-CS-93-118

Unpublished

CMU-CS-93-119

The Midway Distributed Shared Memory System
Brian N. Bershad, Matthew J. Zekauskas, Wayne A. Sawdon
March 1993
10 pages

CMU-CS-93-120 (Unavailable via ftp)

A Quantitative Model of Expert Transcription Typing
Bonnie E. John
March 1993

CMU-CS-93-121

Using the Mach Communication Primitives in X11
Michael Ginsberg, Robert V. Baron, Brian N. Bershad
March 1993
8 pages

CMU-CS-93-122

What is the Center of the Image?
Reg. G. Willson, Steven A. Shafer
April 1993
21 pages

CMU-CS-93-123 (Figures located in files CMU-CS-93-123A to 123G.ps)

Venari/ML Interfaces and Examples
Jeannette M. Wing, Manuel Faehndrich, Nick Haines, Karen Kietzke, Darrell Kindred, J. Gregory Morrisett, Scott Nettles
March 1993
52 pages

CMU-CS-93-124

Fail-safe PVM: A Portable Package for Distributed Programming with Transparent Recovery
Juan Leon, Allan L. Fisher, Peter Steenkiste
February 1993
22 pages

CMU-CS-93-125

The Priority Inversion Problem and Real-Time Symbolic Model Checking
Sergio V. Campos
April 1993
22 pages

CMU-CS-93-126 (Unavailable via ftp)

Software Architectures for Shared Information Systems
Mary Shaw
March 1993

CMU-CS-93-127

Efficient Transparent Optimistic Rollback Recovery for Distributed Application Programs
David B. Johnson
March 1993
17 pages

CMU-CS-93-128

Mobile Host Internetworking Using IP Loose Source Routing
David B. Johnson
February 1993
14 pages

CMU-CS-93-129

NESL: A Nested Data-Parallel Language (Version 2.6)
April 1993
54 pages
[Revised version of CMU-CS-92-103, January 1992]

CMU-CS-93-130

Solving Integer Programs from Dependence and Synchronization Problems
Jaspal Subhlok
March 1993
18 pages

CMU-CS-93-131

Protocol Service Decomposition for High-Performance Networking
Chris Maeda, Brian N. Bershad
March 1993
14 pages

CMU-CS-93-132

Simple Protocol Processing for High-Bandwidth Low-Latency Networking
Jose C. Brustoloni, Brian N. Bershad
March 1993
17 pages

CMU-CS-93-133

Visual Representations as Feedback in a Programmable Visual Shell
Francesmary Modugno, Brad A. Myers
March 1993
8 pages

CMU-CS-93-134

Typed Output and Programming in the Interface
Francesmary Modugno, Brad A. Myers
March 1993
10 pages

CMU-CS-93-135

Replication-Based Incremental Copying Collection
Scott Nettles, James O'Toole, David Pierce, Nicholas Haines
April 1993
8 pages

CMU-CS-93-136

Unpublished

CMU-CS-93-137

Concurrent Garbage Collection of Persistent Heaps
Scott Nettles, James O'Toole, David Gifford
April 1993
22 pages

CMU-CS-93-138

Concurrent Replication Garbage Collection: An Implementation Report
James O'Toole, Scott Nettles
April 1993
15 pages
[Also appears as MIT-LCS-TR-570]

CMU-CS-93-139

Predicting Unseen Triphones with Senones
Mei-Yuh Hwang, Xuedong Huang, Fileno Alleva
April 1993
13 pages

CMU-CS-93-140

Monads and Comonads in Intensional Semantics
Stephen Brookes, Kathryn Van Stone
April 1993
41 pages

CMU-CS-93-141

Full Abstraction for a Shared Variable Parallel Language
Stephen Brookes
April 1993
19 pages

CMU-CS-93-142

Automated Acquisition of Control Knowledge to Improve the Quality of Plans
M. Alicia Perez, Jaime G. Carbonell
April 1993
33 pages

CMU-CS-93-143 (Unavailable via ftp)

Lightweight Recoverable Virtual Memory
Mahadev Satyanarayanan, Henry H. Mashburn, Puneet Kumar, David C. Steere, James J. Kistler
August 1993

CMU-CS-93-144

Service without Servers
Chris Maeda, Brian N. Bershad
August 1993
6 pages

CMU-CS-93-145 (Unavailable via ftp)

Avoidance and Suppression of Compensation Code in a Trace Scheduling Compiler
Stefan M. Freudenberger, Thomas R. Gross, P. Geoffrey Lowney
April 1993

CMU-CS-93-146

Connectionist Models and Linguistic Theory: Investigations of Stress Systems in Languages
Prahlad Gupta, David S. Touretzky
April 1993
31 pages

CMU-CS-93-147 (Unavailable via ftp)

Using Interactive Sketch Interpretation to Design Solid Objects
David Pugh
Ph.D. Thesis
April 1993

CMU-CS-93-148 (Unavailable via ftp)

sing Multiple Adaptively-Weighted Strategies for the Resolution of Demonstratives
Ralf D. Brown
Ph.D. Thesis
May 1993

CMU-CS-93-149 (This report has been superceded by CMU-CS-93-187)

A New Definition of the Subtype Relation
Barbara Liskov, Jeannette M. Wing
April 1993
20 pages

CMU-CS-93-150 (Unavailable via ftp)

Temporal Segmentation of Tasks from Human Hand Motion
Sing Bing Kang, Katsushi Ikeuchi
April 1993

CMU-CS-93-151

Signature Matching: A Key to Reuse
Amy Moormann Zaremski, Jeannette M. Wing
15 pages

CMU-CS-93-152

Fast Interrupt Priority Management in Operating System Kernels
Daniel Stodolsky, J. Bradley Chen, Brian N. Bershad
May 1993
6 pages

CMU-CS-93-153

Unpublished

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

Constrained Objects
Bruce Horn
Ph.D. Thesis
November 1993

CMU-CS-93-155

Integrating Reactive and Deliberative Planning for Agents
Jim Blythe, W. Scott Reilly
May 1993
25 pages

CMU-CS-93-156 (Unavailable via ftp)

Disconnected Operation in a Distributed File System
James J. Kistler
Ph.D. Thesis
May 1993

CMU-CS-93-157

Processor Capacity Reserves for Multimedia Operating Systems
Clifford W. Mercer, Stefan Savage, Hideyuki Tokuda
May 1993
15 pages

CMU-CS-93-158

Modelling and Specifying Name Visibiity and Binding Semantics
Scott A. Vorthmann
July 1993
12 pages

CMU-CS-93-159

Formalizing Properties of Agents
Richard Goodwin
May 1993
52 pages

CMU-CS-93-160R

Standard ML Weak Polymorphism Can Be Sound
John Greiner
May 1993
20 pages
[This report is a revision of CMU-CS-93-160.ps.]

CMU-CS-93-161 (Unavailable via ftp)

Generating Knight's Tours Without Backtracking from Errors
Jefferey A. Shufelt, Hans J. Berliner
May 1993

CMU-CS-93-162

A Scientific Basis for Computational Science
Raul E. Valdes-Perez
May 1993
18 pages

CMU-CS-93-163

Sequential Functions on Indexed Domains and Full Abstraction for a
Sub-language of PCF
Stephen Brookes, Shai Geva
April 1993
15 pages

CMU-CS-93-164

Xab: A Tool for Monitoring PVM Programs
Adam L. Beguelin
June 1993
8 pages

CMU-CS-93-165

A Distributed Reinforcement Learning Scheme for Network Routing
Michael Littman, Justin Boyan
July 1993
6 pages

CMU-CS-93-166

Visual Parallel Programming and Determinacy: A Language Specification, an Analysis Technique, and a Programming Tool
Adam Beguelin, Gary Nutt
June 1993
33 pages

CMU-CS-93-167

Causality-Preserving Timestamps in Distributed Programs
Adam Beguelin, Erik Seligman
June 1993
9 pages

CMU-CS-93-168

Experience with Disconnected Operation in a Mobile Computing Environment
Mahadev Satyanarayanan, James J. Kistler, Lily B. Mummert, Maria R. Ebling, Puneet Kumar, Qi Lu
June 1993
18 pages

CMU-CS-93-169 (Unavailable via ftp)

A Simplified Account of Polymorphic References
Robert Harper
June 1993

CMU-CS-93-170

Standard ML Signatures for a Protocol Stack
Edoardo Biagioni, Robert Harper, Peter
October 1993
16 pages
(Also appears as CMU-CS-FOX-93-01)

CMU-CS-93-171 (Unavailable via ftp)

Optimistic Parallelization
Greg Morrisett, Maurice Herlihy
October 1993

CMU-CS-93-172

Note on Conditional Compilation in Standard ML
Nicholas Haines, Edoardo Biagioni, Robert Harper, Brian G. Milnes
June 1993
7 pages
(Also appears as CMU-CS-FOX-93-02)

CMU-CS-93-173 (Compressed File)

Segmented Operations for Sparse Matrix Computation on Vector Multiprocessors
Guy E. Blelloch, Michael A. Heroux, Marco Zagha
August 1993
23 pages

CMU-CS-93-174

Computing the Pipelined Phase-Rotation FFT
Langhorne P. Withers, Jr., John E. Whelchel, David R. O'Hallaron, Peter J. Lieu
July 1993
16 pages

CMU-CS-93-175

Dialog-Based Learning (DBL) for Adaptive Interface Agents and Programming-By-Demonstration Systems
Siegfried Bocionek, Michael Sassin
July 1993
51 pages

CMU-CS-93-176

CMU-CS-93-176A

Portable Parallel Ray Tracing Algorithms
Michael J. Garland
Senior Honors Thesis
May 1993
21 pages

CMU-CS-93-177 (Unavailable via ftp)

A Method for Estimating Scene Parameters from Color Histograms
Carol L. Novak, Steven A. Shafer
July 1993

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

Model Checking, Abstraction, and Compositional Verification
David E. Long
Ph.D. Thesis
July 1993

CMU-CS-93-179

CMU Very Fast Range-Imaging System
Shigeyuki Tada, Andrew Gruss, Takeo Kanade
October 1993
41 pages

CMU-CS-93-180

The CMU Master in Software Engineering Core Curriculum
David Garlan, Alan Brown, Daniel Jackson, Jim Tomayko, Jeannette Wing
August 1993
19 pages

CMU-CS-93-181

Tap-D: A Model for Developing Specialization Tracks in Graduate Software Engineering Education
Carol L. Hoover
July 1993
37 pages

CMU-CS-93-182

How To Stop a Cheater: Secret Sharing with Dishonest Participation
Erik W. Selberg
Senior Honors Thesis
July 1993
16 pages

CMU-CS-93-183

Why are Human-Computer Interfaces Difficult to Design and Implement?
Brad A. Myers
July 1993
15 pages

CMU-CS-93-184 (Unavailable via ftp)

Multilist Scheduling: A New Parallel Programming Model
I-Chen Wu
Ph.D. Thesis
July 1993

CMU-CS-93-185

Unpublished

CMU-CS-93-186

Unpublished

CMU-CS-93-187

Family Values: A Behavioral Notion of Subtyping
Barbara Liskov, Jeannette M. Wing
July 1993
34 pages

CMU-CS-93-188

Software Methods for System Address Tracing
J. Bradley Chen
August 1993
9 pages

CMU-CS-93-189

Unpublished

CMU-CS-93-190

A Methodology for Formal Hardware Verification, with Application to Microprocessors
Derek L. Beatty
Ph.D. Thesis
August 1993

CMU-CS-93-191

A Comparison of Data-Parallel Algorithms for Connected Components
John Greiner
August 1993
17 pages

CMU-CS-93-192

Unpublished

CMU-CS-93-193

Set Based Analysis of ML Program
Nevin Heintze
July 1993
20 pages
[Also appears as Fox Memorandum CMU-CS-FOX-93-03]

CMU-CS-93-194

Unpublished

CMU-CS-93-195 (Unavailable via ftp)

Experiments in Knowledge Refinement for a Large Rule-Based System
Wilson A. Harvey, Jr., Milind Tambe
August 1993

CMU-CS-93-196

An MS-DOS File System for UNIX
Alessandro Forin, Gerald R. Malan
September 1993
24 pages

CMU-CS-93-197

A Type-Theoretic Approach to Higher-Order Modules with Sharing
Robert Harper, Mark Lillibridge
October 1993

CMU-CS-93-198 (Unavailable via ftp)

Simulating User's Preferences: Towards Automated Artificial Evolution for Computer Generated Images
Shumeet Baluja, Dean Pomerleau, Todd Jochem
October 1993

CMU-CS-93-199

Dialog Structure and Plan Recognition in Spontaneous Spoken Dialog
Sheryl R. Young
June 1993
14 pages

CMU-CS-93-200

A Redundant Disk Array Architecture for Efficient Small Writes
Daniel Stodolsky, Mark Holand, William V. Courtright II, Garth A. Gibson
October 1993
68 pages

CMU-CS-93-201

Analyzing the Properties of User Interface Software
Rick Kazman, Len Bass, Gregory Abowd, Mike Webb
October 1993
26 pages

CMU-CS-93-202

Tinkertoy Transactions
Nicholas Haines, Darrell Kindred, J. Gregory Morrisett, Scott M. Nettles, Jeannette M. Wing
December 1993
21 pages

CMU-CS-93-203

Unpublished

CMU-CS-93-204

Rational Handling of Multiple Goals for Mobile Robots
Richard Goodwin, Reid Simmons
November 1993
16 pages

CMU-CS-93-205

Performance Measurements of the Multimedia Testbed on Mach 3.0: Experience Writing Real-Time Device Drivers, Servers, and Applications
Roger B. Dannenberg, David B. Anderson, Tom Neuendorffer, Dean Rubine, Jim Zelenka
July 1993
22 pages

CMU-CS-93-206 (Unavailable via ftp)

Program Derivation by Proof Transformation
Penny Anderson
Ph.D. Thesis
October 1993

CMU-CS-93-207

A Usage Profile and Evaluation of a Wide-Area Distributed File System
Mirjana Spasojevic, Mahadev Satyanarayanan
October 1993
17 pages

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

Electronic Mail and Organizational Knowledge: Media Use in a Global Corporation
Robert E. Kraut, Paul Attewell
December 1993

CMU-CS-93-209a

CMU-CS-93-209b

Optimizing Ray Tracing with Visual Coherence
Nathan Loofbourrow, Steven A. Shafer
December 1993
20 pages

CMU-CS-93-210

Memory Sybsystem Performance of Programs Using Copying Garbage Collection
Amer Diwan, David Tarditi, Eliot Moss
December 1993
20 pages

CMU-CS-93-211

Symbolic Model Checking for Sequential Circuit Verification
Jerry R. Burch, Edmund M. Clarke, David E. Long, Kenneth L. McMillan, David L. Dill
July 1993
50 pages

CMU-CS-93-212

Automatic Mapping of Task and Data Parallel Programs for Efficient Execution on Multicomputers
Jaspal Subhlok
November 1993

CMU-CS-93-213 (text) (Compressed File)

CMU-CS-93-213A (title)

Principal Component Analysis with Missing Data and Its Application to Object Modeling
Heung-yeung Shum, Katsushi Ikeuchi, Raj Reddy
December 1993
40 pages

CMU-CS-93-214 (Compressed File)

Building 3-D Models From Unregistered Range Images
Kazunori Higuchi, Martial Hebert, Katsushi Ikeuchi
November 1993
18 pages

CMU-CS-93-215 (Compressed File)

Combining Shape and Color Information For 3D Object Recognition
Kazunori Higuchi, Martial Hebert, Katsushi Ikeuchi
December 1993
19 pages

CMU-CS-93-216

Bibliography of Research in Natural Language Generation
Mark Kantrowitz
November 1993
49 pages

CMU-CS-93-217 (Unavailable via ftp)

Compiler Techniques for Managing Data Motion
John S. Pieper
Ph.D. Thesis
December 1993

CMU-CS-93-218

An Analysis of Instruction-Cached SIMD Computer Architecture
Todd E. Rockoff
PH.D. Thesis
December 1993

CMU-CS-93-219 (Compressed File)

A Paraperspective Factorization method for Shape and Motion Recovery
Conrad J. Poelman, Takeo Kanade
December 1993
36 pages

CMU-CS-93-220 (Compressed File)

DigitEyes: Vision-Based Human Hand Tracking
James M. Rehg, Takeo Kanade
December 1993

CMU-CS-93-221

Set Based Analysis of Arithmetic
Nevin Heintze
December 1993
15 pages
[Also appears as Fox Memorandum CMU-CS-FOX-93-06]

CMU-CS-93-222 (Unavailable via ftp)

Utility-Based Planning
Sven Koenig, Reid G. Simmons
November 1993

CMU-CS-93-223

Learning New Words from Spontaneous Speech: A Project Summary
Sheryl R. Young
July 1993
29 pages

CMU-CS-93-224

Unpublished

CMU-CS-93-225

Deferred Compilation: The Automation of Run-Time Code Generation
Mark Leone, Peter Lee
December 1993
17 pages

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

An Architecturally-based Theory of Human Sentence Comprehension
Richard Lawrence Lewis
Ph.D. Thesis
December 1993

CMU-CS-93-227

Memory Subsystem Performance of Programs with Intensive Heap Allocation
Amer Diwan David Tarditi, Eliot Moss
December 1993
43 pages
[Also appears as Fox Memorandum CMU-CS-FOX-93-07]

CMU-CS-93-228

A Cognitive Model of Decision Making: Chunking and the Radar Detection Task
Constantine P. Papageorgiou, Kathleen Carley
December 1993
27 pages

CMU-CS-93-229

Basic Research in Computer Science Final Report: 1990-1993
Dale A. James, C. Roy Taylor (Editors)
December 1993
152 pages

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

Subphonetic Acoustic Modeling for Speaker-Independent Continuous Speech Recognition
Mei-Yuh Hwang
Ph.D. Thesis
December 1993

CMU-CS-93-231 (Unavailable via ftp)

A Theory of Distributed Time
Sean W. Smith
December 1993