COMPUTER SCIENCE TECHNICAL REPORTS

1992 SERIES

SCHOOL OF COMPUTER SCIENCE

CARNEGIE MELLON UNIVERSITY

PITTSBURGH, PA  15213-3891

NOTE: Please read this Copyright notice before proceeding.

CMU-CS-92-100

Time Models for Protocol Security
Nevin Heintze, J. Doug Tygar
January 1992
26 pages

CMU-CS-92-101 (Text)

CMU-CS-92-101A (Title Page)

The Golem Go Program
Herbert D. Enderton
December 1991
13 pages

CMU-CS-92-102

Efficient Exploration in Reinforcement Learning
Sebastian B. Thrun
January 1992
44 pages

CMU-CS-92-103

NESL: A Nested Data-Parallel Language
Guy E. Blelloch
January 1992
36 pages

CMU-CS-92-104A (Preface)

CMU-CS-92-104B (Text)

CMU-CS-92-104C (Figures)

Shape and Motion from Image Streams: A Factorization Method 2. Full Report on the Orthographic Case [Parts 2,8,10]
Carlo Tomasi, Takeo Kanade
January 1992
36 pages

CMU-CS-92-105

On the Undecidability of Partial Polymorphic Type Reconstruction
Frank Pfenning
January 1992
15 pages

CMU-CS-92-106R [A revised version of CMU-CS-92-106.ps]

Nested Dissection: A Survey
Manpreet S. Khaira, Gary L. Miller, Thomas J. Sheffler
January 1992
26 pages

CMU-CS-92-107

Integrated Natural Language Generation Systems
Mark Kantrowitz, Joseph Bates
April 1992
16 pages

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

Vocabulary-Independent Speech Recognition: The VOCIND System
Hsiao-Wuen Hon
Ph.D. Thesis
March 1992

CMU-CS-92-109

Programming with Inductive and Co-Inductive Types
John Greiner
January 1992
34 pages

CMU-CS-92-110 (Unavailable via ftp)

Language for Higher-Order Explanation-Based Learning
Scott Dietzen
Ph.D. Thesis
January 1992

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

Automatic Acquisition of Task Theories for Robotic Manipulation
Alan D. Christiansen
Ph.D. Thesis
March 1992

CMU-CS-92-112

The SPHINX-II Speech Recognition System: An Overview
Xuedong Huang, Fileno Alleva, Hsiao-Wuen Hon, Mei-Yuh Hwang, Ronald Rosenfeld
January 1992
12 pages

CMU-CS-92-113

Survey on User Interface Programming
Brad A. Myers, Mary Beth Rosson
February 1992
**Contains embedded Macintosh postscript files, printing difficulties may occur on certain equipment.
14 pages

CMU-CS-92-114

State of the Art in User Interface Software Tools
Brad A. Myers
February 1992
**Contains embedded Macintosh postscript files; some figures will not appear.
37 pages

CMU-CS-92-115 (Unavailable via ftp)

Neural Network Perception for Mobile Robot Guidance
Dean A. Pomerleau
Ph.D. Thesis
February 1992

CMU-CS-92-116 (Unavailable via ftp)

Towards Task-Level Planning: Action-Based Sensor Design
Michael Erdmann
February 1992
[Also appears as Robotics Institute CMU-RI-TR-92-03]

CMU-CS-92-117

Analytica - A Theorem Prover for Mathematica
Edmund Clarke, Xudong Zhao
October 1992
45 pages

CMU-CS-92-118

Precision Imaging and Control for Machine Vision Research at Carnegie Mellon University
Reg. G. Willson, Steven A. Shafer
March 1992
23 pages

CMU-CS-92-119 (Titlepage)

CMU-CS-92-119A (Text)

MINDS-II Feedback Architecture: Detection and Correction of Speech Misrecognitions
Sheryl R. Young, Michael Matessa
March 1992
14 pages

CMU-CS-92-120 (Titlepage)

CMU-CS-92-120A (Text)

Using Pragmatic and Semantic Knowledge to Correct Parsing of Spoken Language Utterances
Sheryl R. Young, Michael Matessa
March 1992
9 pages

CMU-CS-92-121

Stable and Sequential Functions on Scott Domains
Stephen Brookes, Shai Geva
June 1992
46 pages

CMU-CS-92-122

Polymorphic Type Assignment and CPS Conversion
Robert Harper, Mark Lillibridge
April 1992
12 pages

CMU-CS-92-123

A Modular Implementation of Partial Evaluation
Christopher Colby, Peter Lee
March 1992
18 pages

CMU-CS-92-124 (compressed)

CMU-CS-92-124

DYNAMIC: A New Role for Training Problems in EBL
M. Alicia Perez, Oren Etzioni
March 1992
13 pages

CMU-CS-92-125

Unpublished

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

Deriving and Manipulating Module Interfaces
Robert Louis Nord
Ph.D. Thesis
May 1992

CMU-CS-92-127 (Unavailable via ftp)

Factored Arc Consistency for RETE Match
Mark Perlin
April 1992

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

Constraint-Directed Efficient Matching in PRODIGY
Xuemei Wang
April 1992

CMU-CS-92-129 (Unavailable via ftp)

Representation and Manipulation of Inductive Boolean Functions
Aarti Gupta, Allan L. Fisher
April 1992

CMU-CS-92-130 (Unavailable via ftp)

Parity Declustering for Continuous Operation in Redundant Disk Arrays
Mark Holland, Garth Gibson
April 1992

CMU-CS-92-131 (Unavailable via ftp)

Symbolic Model Checking: An Approach to the State Explosion Problem
Kenneth L. McMillan
Ph.D. Thesis
May 1992

CMU-CS-92-132

CMU-CS-92-132A (Title page)

Extensions to Standard ML to Support Transactions
Jeannette M. Wing, Manuel Faehndrich, J. Gregory Morrisett, Scott Nettles
April 1992
15 pages

CMU-CS-92-133R (Revised Version of CMU-CS-92-133.ps)

Type Evolution and Instance Adaptation
Stewart M. Clamen
June 1992
27 pages

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

TAQL: A Problem Space Tool for Expert System Development
Gregg R. Yost
Ph.D. Thesis
May 1992

CMU-CS-92-135

Thoughts on a Larch/ML and a New Application for LP
Jeannette M. Wing, Eugene Rollins, Amy Moormann Zaremski
May 1992
17 pages

CMU-CS-92-136

Unpublished

CMU-CS-92-137 (Unavailable via ftp)

Program Structure as a Basis for the Parallelization of Global
Compiler Optimizations
Angelika Zobel
Ph.D. Thesis
May 1992

CMU-CS-92-138

Memory Approaches to Reinforcement Learning in Non-Markovian Domains
Long-Ji Lin, Tom Mitchell
May 1992
28 pages

CMU-CS-92-139 (Unavailable via ftp)

Selective Perception for Robot Driving
Douglas A. Reece
Ph.D. Thesis
May 1992

CMU-CS-92-140

Unpublished

CMU-CS-92-141

Recent Developments in the NL-Soar Garden Path Theory
Richard L. Lewis
May 1992
30 pages

CMU-CS-92-142

Integrating Reactivity, Goals, and Emotion in a
Broad Agent
Joseph Bates, A. Bryan Loyall, W. Scott Reilly
May 1992
13 pages

CMU-CS-92-143

Building Emotional Agents
W. Scott Reilly, Joseph Bates
May 1992
13 pages

CMU-CS-92-144

An Architecture for Action, Emotion, and Social Behavior
Joseph Bates, A. Bryan Loyall, W. Scott Reilly
May 1992
14 pages

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

The Complexity of Real-Time Search
Sven Koenig
April 1992

CMU-CS-92-146 (Unavailable via ftp)

Planning Multiple Observations for Object Recognition
@\Keith D. Gremban, Katsushi Ikeuchi
December 1992

CMU-CS-92-147

Analytica - An Experiment in Combining Theorem Proving and Symbolic Computation
Edmund Clarke, Xudong Zhao
October 1992
19 pages

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

Implementation and Evaluation of a Three-Dimensional Photometric Sampler
Hideichi Sato, Shree K. Nayar, Katsushi Ikeuchi
July 1992

CMU-CS-92-149 (Unavailable via ftp)

Conference Registration Task for Neural Net Speech Recognition -
Data Collection and Labeling
Cindy A. Wood
December 1992

CMU-CS-92-150

Prodigy 4.0: The Manual and Tutorial
Jim Blythe, Jaime G. Carbonell, Oren Etzioni, Yolanda Gil, Robert Joseph, Dan Kahn, Craig Knoblock, Steven Minton, Alicia Perez, Scott Reilly, Manuela Veloso, Xuemei Wang
June 1992
60 pages

CMU-CS-92-151

Expert-System Development in Soar: A Tutorial
Erik Altmann, Gregg R. Yost
June 1992
58 pages

CMU-CS-92-152

On Statman's Finite Completeness Theorem
Richard Statman, Gilles Dowek
June 1992
17 pages

CMU-CS-92-153

Unpublished

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

An Axiomatic Treatment of Partial Correctness and Deadlock in a Shared Variable Parallel Language
Stephen Brookes
June 1992

CMU-CS-92-155

A Portable Multiprocessor Interface for Standard ML of New Jersey
J Gregory Morrisett, Andrew Tolmach
June 1992
31 pages

CMU-CS-92-156

Information Processing Rsearch
Allen Newell, Scott E. Fahlman Dale A. James, C. Roy Taylor (editors)
January 1992
155 pages

CMU-CS-92-157

Final Report on Speech Recognition Research
Jutta S. Denton, C. Roy Taylor (editors)
June 1992
70 pages

CMU-CS-92-158

The Match Cost of Adding a New Rule: A Clash of Views
Milind Tambe, Robert Doorenbos, Allen Newell
June 1992
10 pages

CMU-CS-92-159 (Unavailable via ftp)

Appearance-Based Vision and the Automatic Generation of Object Recognition Programs
Keith D. Gremban, Katsushi Ikeuchi
July 1992

CMU-CS-92-160

Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams
Randal E. Bryant
July 1992
35 pages

CMU-CS-92-161

CMU Common Lisp User's Manual
Robert A. MacLachlan (editor)
July 1992
142 pages

CMU-CS-92-162 (Unavailable via ftp)

Inner Product Mapping: Direct Localization and Ordering of DNA Probes Using Chromosome-Characterized Radiation Hybrids
Mark Perlin
June 1992

CMU-CS-92-163

Towards Formalized Software Architectures
Robert Allen, David Garlan
July 1992
23 pages

CMU-CS-92-164 (Unavailable via ftp)

Wait-Free Consensus
James Aspnes
Ph.D. Thesis
July 1992

CMU-CS-92-165

Dialogue Processing with Neural Networks
Ye-Yi Wang, Alex Waibel
June 1992
14 pages

CMU-CS-92-166 (Unavailable via ftp)

Compiling Prolog to Standard ML: Some Optimizations
Luke Hornof
Senior Thesis
September 1992

CMU-CS-92-167

Transactional Distributed Shared Memory
Andrew B. Hastings
Ph.D. Thesis
July 1992
176 pages

CMU-CS-92-168 (Unavailable via ftp)

Design and Implementation of Practical Constraint Logic Programming Systems
Spiro Michaylov
Ph.D. Thesis
August 1992

CMU-CS-92-169

A Specification of the Soar Cognitive Architecture in Z
Brian G. Milnes, et. al.
August 1992
242 pages

CMU-CS-92-170 (Compressed file)

Transparently Interposing User Code at the System Interface
Michael B. Jones
Ph.D. Thesis
September 1992
143 pages

CMU-CS-92-171

Unpublished

CMU-CS-92-172

Work Efficient Hashing on Parallel and Vector Computers
Thomas J. Sheffler, Randal E. Bryant
August 1992
13 pages

CMU-CS-92-173

Implementing the Multiprefix Operation on Parallel and Vector Computers
Thomas J. Sheffler
August 1992
23 pages

CMU-CS-92-174 (Unavailable via ftp)

Learning by Analogical Reasoning in General Problem Solving
Manuela M. Veloso
Ph.D. Thesis
August 1992

CMU-CS-92-175 (Unavailable via ftp)

Acquiring Domain Knowledge for Planning by Experimentation
Yolanda Gil
Ph.D. Thesis
August 1992

CMU-CS-92-176 (temporarily unavailable)

Experience With a Course on Architectures for Software Systems Part I: Course Description
David Garlan, Mary Shaw, Chris Okasaki, Curtis M. Scott, Roy F. Swonger
August 1992
30 pages

CMU-CS-92-177

Unpublished

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

Verbal Reasoning
Thad A. Polk
Ph.D. Thesis
August 1992

CMU-CS-92-179 (Unavailable via ftp)

Trace Algebra for Automatic Verification of Real-Time Concurrent Systems
Jerry R. Burch
Ph.D. Thesis
August 1992

CMU-CS-92-180

Ascent: Application-Specific Environment Transformer
David Garlan, Linxi Cai, Robert L. Nord, Robert Stockton
December 1992
67 pages

CMU-CS-92-181

Grammatical Trigrams: A Probabilistic Model of Link Grammar
John Lafferty, Daniel Sleator, Davy Temperley
September 1992
10 pages

CMU-CS-92-182

Consistency Management for Virtually Indexed Caches
Brian N. Bershad and Bob Wheeler
October 1992
14 pages

CMU-CS-92-183

Fast Mutual Exclusionn for Uniprocessors
Brian N. Bershad, David D. Redell, John R. Ellis
October 1992
15 pages

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

Paths in Graphs and Parallel Computing
Thomas R. Mathies
Ph.D. Thesis
September 1992

CMU-CS-92-185 (Unavailable via ftp)

Towards a Vision Algorithm Compiler for Recognition of Partially Occluded 3-D Objects
Mark D. Wheeler, Katsushi Ikeuchi
November 1992

CMU-CS-92-186

A Proof of the Church-Rosser Theorem and its Representation in a Logical Framework
Frank Pfenning
September 1992
46 pages

CMU-CS-92-187

Speech Recognition Using Dynamical Model of Speech Production
Ken-ichi Iso
September 1992
9 pages

CMU-CS-92-188 (Unavailable via ftp)

Knowledge Acquisition for Visually Oriented Planning
Robert Leo'nard' Joseph
Ph.D. Thesis
August 1992

CMU-CS-92-189

Optimal Online Scheduling of Parallel Jobs with Dependencies
Anja Feldmann, Ming-Yang Kao, Jiri Sgall, Shang-Hua Teng
September 1992
24 pages

CMU-CS-92-190

Fixed Points In Spectral Complexity
Sean W. Smith, Carl Sturtivant
October 1992
14 pages

CMU-CS-92-191 (Unavailable via ftp)

A Module System for a Programming Language Based on the LF Logical Framework
Robert Harper, Frank Pfenning
September 1992

CMU-CS-92-192 (Unavailable via ftp)

Using Knowledge About the Opponent in Game-Tree Search
Peter J. Jansen
Ph.D. Thesis
September 1992

CMU-CS-92-193

Human-Computer Interaction in the School of Computer Science
Edited by Bonnie E. John, Philip L. Miller, Brad A. Myers, Christine M. Neuwirth, Steven A. Shafer
October 1992
24 pages

CMU-CS-92-194 (Unavailable via ftp)

Fractal Surface Reconstruction with Uncertainty Estimation: Modeling Natural Terrain
Kenichi Arakawa, Eric Krotkov
October 1992

CMU-CS-92-195

Dramatic Presence
Margaret Thomas Kelso, Peter Weyhrauch, Joseph Bates
December 1992
17 pages

CMU-CS-92-196

A Massively Distributed Parallel Genetic Algorithm (mdpGA)
Shumeet Baluja
October 1992
20 pages

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

Conference Registration Task for Neural Net Speech Recognition - Data Collection and Labeling for a Speaker Independent System
Cindy A. Wood
December 1992

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

Conference Registration Task for Neural Net Speech Recognition - Data Collection and Labeling for a Speaker Independent System, Part II
Cindy A. Wood
December 1992

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

Conference Registration Task for Neural Net Speech Recognition - Data Collection and Labeling for a Spontaneous Speech System
Cindy A. Wood
December 1992

CMU-CS-92-200 (Unavailable via ftp)

The Nature of Characters in Interactive Worlds and The Oz Project
Joseph Bates
October 1992

CMU-CS-92-201 (Unavailable via ftp)

Set Based Program Analysis
Nevin Heintze
Ph.D. Thesis
October 1992

CMU-CS-92-202

Evicted Variables and the Interaction of Global Register Allocation and Symbolic Debugging
Ali-Reza Adl-Tabatabai, Thomas Gross
October 1992
16 pages

CMU-CS-92-203 (Unavailable via ftp)

Match and Move, an Approach to Data Parallel Computing
Thomas J. Sheffler
Ph.D. Thesis (Electrical and Computer Engineering)
October 1992

CMU-CS-92-204 (Unavailable via ftp)

Source-level Debugging of Automatically Parallelized Programs
Robert Cohn
Ph.D. Thesis
October 1992

CMU-CS-92-205

Soar-mode v5.0 User's Manual for Soar release 5.2 and 6.0
Frank E. Ritter, Michael Hucka, Thomas F. McGinnis
December 1992
24 pages

CMU-CS-92-206

Verification of the Futurebus+ Cache Coherence Protocol
Edmund Clarke, Orna Grumberg, Hiromi Hiraishi, Somesh Jha, David Long, Kenneth McMillan, Linda Ness
October 1992
15 pages

CMU-CS-92-207

Temporal-Color Space Analysis of Reflection
Yoichi Sato and Katsushi Ikeuchi
November 1992

CMU-CS-92-208

A Paraperspective Factorization Method for Shape and Motion Recovery
Conrad J. Poelman, Takeo Kanade
October 1992
30 pages

CMU-CS-92-209

Reflected Number Systems
Anuarag Acharya
November 1992
6 pages

CMU-CS-92-210

Explicit Polymorphism and CPS Conversion
October 1992
23 pages

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

Pattern Recognition Interacting with Search
Hans J. Berliner
October 1992

CMU-CS-92-212

Estimating Scene Properties fromm Color Histograms
Carol L. Novak, Steven A. Shafer
November 1992
30 pages

CMU-CS-92-213 (Unavailable via ftp)

The Quantified Design Space - A Tool for the Quantitative Analysis of Designs
Toru Asada, Roy F. Swonger, Nadine Bounds, Paul Duerig
November 1992

CMU-CS-92-214 (Unavailable via ftp)

Representation and Recognition of Free-Form Surfaces
Herve Delingette, Martial Hebert, Katsushi Ikeuchi
November 1992

CMU-CS-92-215

The Impact of Communication Style on Machine Resource Usage for the iWarp Parallel Processor
Thomas Gross, A. Hasegawa, Susan Hinrichs, David O'Hallaron, Thomas Stricker
November 1992
23 pages

CMU-CS-92-216

Unpublished

CMU-CS-92-217

Reactive Integration for Traditional Programming Languages
David Garlan, Curtis Scott
December 1992
14 pages

CMU-CS-92-218 (Unavailable via ftp)

Collection-oriented Match: Scaling Up the Data in Production Systems
Anurag Acharya, Milind Tambe
December 1992

CMU-CS-92-219

A Larch Specification of Copying Garbage Collection
Scott Nettles
December 1992

CMU-CS-92-220 (text)

CMU-CS-92-220A (figures)

CMU-CS-92-220B (figures)

Family Values: A Semantic Notion of Subtyping
Barbara Liskov, Jeannette M. Wing
December 1992
47 pages

CMU-CS-92-221

Nonresident and Endangered Variables: The Effects of Code Generation Optimizations on Symbolic Debugging
Ali-Reza Adl-Tabatabai
December 1992
33 pages