COMPUTER SCIENCE TECHNICAL REPORTS

1990 SERIES

SCHOOL OF COMPUTER SCIENCE

CARNEGIE MELLON UNIVERSITY

PITTSBURGH, PA  15213-3891

NOTE: Please read this Copyright notice before proceeding.

CMU-CS-90-100

The Cascade-Correlation Learning Architecture
Scott E. Fahlman, Christian Lebiere
February 1990
13 pages

CMU-CS-90-101

User Interface Software Structures
Thomas G. Lane
Ph.D. Thesis
May 1990
[Also appears as Software Engineering Technical Report SEI-90-TR-13.

CMU-CS-90-102

Extensible Records Without Subsumption
Robert W. Harper, Benjamin C. Pierce
February 1990

CMU-CS-90-103

Fast Animation and Control of Nonrigid Structures
Andrew Witkin, William Welch
January 1990

CMU-CS-90-104

Deductive Assistance for Elucidation of Chemical Reaction Pathways
Raul E. Valdes-Perez
January 1990

CMU-CS-90-105

Foundations of A Computational Theory of Catecholamine Effects
Harry Printz, David Servan-Schreiber
May 1990

CMU-CS-90-106

Determining Reflectance Parameters Using Range and Brightness Images
Katsushi Ikeuchi and Kosuke Sato
February 1990

CMU-CS-90-107

Multiprocessing in a Network of Workstations
David A. Nichols
Ph.D. Thesis
February 1990

CMU-CS-90-108

Large Scale Parallelization of Alpha-Beta Search: An Algorithmic and Architectural Study with Computer Chess
Feng-hsiung Hsu
Ph.D. Thesis
February 1990

CMU-CS-90-109

Self-improving Reactive Agents: Case Studies of Reinforcement Learning Frameworks
Long-Ji Lin
August 1990

CMU-CS-90-110

Distributed Hartstone Real-Time Benchmark Suite
Clifford W. Mercer, Yutaka Ishikawa, Hideyuki Tokuda
March 1990

CMU-CS-90-111

Object-Oriented Real-Time Language Design: Constructs for Timing Constraints
Yutaka Ishikawa, Hideyuki Tokuda, Clifford W. Mercer
March 1990

CMU-CS-90-112

Rules and Maps II: Recent Progress in Connectionist Symbol Processing
David S. Touretzky, Deirdre W. Wheeler, Gillette Elvgren III
March 1990

CMU-CS-90-113

A Taste of Category Theory for Computer Scientists
Benjamin C. Pierce
March 1990 - Revised version of CMU-CS-88-203

CMU-CS-90-114

Scoping, Inheritance, and Frames
Mark W. Perlin
February 1990

CMU-CS-90-115

Data-Flow Analysis and Type Recovery in Scheme
Olin Shivers
March 1990

CMU-CS-90-116

Description of Acoustic Variations by Hidden Markov Models with Tree Structure
Satoru Hayamizu, Kai-Fu Lee, Hsiao-Wuen Hon
March 1990

CMU-CS-90-117

The Garnet Toolkit Reference Manuals: Support for Highly-Interactive Graphical User Interfaces in Lisp
Brad A. Myers, Dario Giuse, Roger B. Dannenberg, Brad Vander Zanden, David Kosbie, Philippe Marchal, Ed Pervin, Andrew Mickish, John A. Kolojejchick
March 1990
[Revised version of CMU-CS-89-196]

CMU-CS-90-118

The Design of Spoken Language Interfaces
Alexander I. Rudnicky
March 1990

CMU-CS-90-119

Concurrent Garbage Collection for C++
David L. Detlefs
May 1990

CMU-CS-90-120

A Stereo Matching Algorithm with an Adaptive Window: Theory and Experiment
Takeo Kanade, Masatoshi Okutomi
April 1990

CMU-CS-90-121

Programming Language Support for Multicast Communication in Distributed Systems
Eric C. Cooper
May 1990

CMU-CS-90-122

A Methodology for Hardware Verification Based on Logic Simulation
Randal E. Bryant
March 1990

CMU-CS-90-123

The NAVLAB System for Mobile Robot Navigation
Anthony Stentz
Ph.D. Thesis
March 1990

CMU-CS-90-124

Minimum Cost Aspect Classification: A Module of a Vision Algorithm Compiler
Ki Sang Hong, Katsushi Ikeuchi, Keith D. Gremban
April 1990

CMU-CS-90-125

Scheduling Support for Concurrency and Parallelism in the Mach Operating System
David L. Black
April 1990

CMU-CS-90-126

Efficient User-Level File Cache Management on the Sun Vnode Interface
David C. Steere, James J. Kistler, Mahadev Satyanarayanan
April 1990

CMU-CS-90-127

Collection-Oriented Languages
Jay M. Sipelstein, Guy E. Blelloch
September 1990

CMU-CS-90-128

Shape and Motion Without Depth
Carlo Tomasi, Takeo Kanade
May 1990

CMU-CS-90-129

Two Levels of Filesystem Hierarchy on One Disk
Vince Cate
May 1990

CMU-CS-90-130

The Impact of Domain Dynamics on Intelligent Robot Design
Douglas A. Reece, Steven Shafer
May 1990

CMU-CS-90-131

Formal Verification of Digital Circuits Using Symbolic Ternary System Models
Randal E. Bryant, Carl-Johan Seger
May 1990

CMU-CS-90-132

Progress in Call-Graph Caching
Mark W. Perlin
May 1990

CMU-CS-90-133

A Practical Approach to Replication of Abstract Data Objects
Joshua J. Bloch
Ph.D. Thesis
May 1990

CMU-CS-90-134

Extensions and Applications of Higher-Order Unification
Conal M. Elliott
Ph.D. Thesis
May 1990

CMU-CS-90-135

The Deliberative Integration of Planning, Execution, and Learning
Daniel R. Kuokka
Ph.D. Thesis
May 1990

CMU-CS-90-136

A Specifier's Introduction to Formal Methods
Jeannete M. Wing
May 1990

CMU-CS-90-137

On the Type Structure of Standard ML
Robert Harper, John C. Mitchell
May 1990

CMU-CS-90-138

Rules and Maps III: Further Progress in Connectionist Phonology
David S. Touretzky, Deirdre W. Wheeler, Gillette Elvgren III
June 1990

CMU-CS-90-139

Inheritance Theory and Networks with Roles
Richmond H. Thomason, David S. Touretzky
June 1990

CMU-CS-90-140

Supervised Color Constancy Using a Color Chart
Carol L. Novak, Steven A. Shafer
June 1990

CMU-CS-90-141

An Introduction to Circuit Complexity and A Guide to Harstad's Proof
Allan Heydon
June 1990

CMU-CS-90-142

Informatics for a New Century: Computing Education for the 1990s and Beyond
Mary Shaw
July 1990
[Also appears as SEI Report CMU/SEI-90-TR-15, ESD-TR-90-142]

CMU-CS-90-143

Automatic Generation of Systolic Programs from Nested Loops
Hudson B. Ribas
Ph.D. Thesis (Electrical and Computer Engineering)
June 1990

CMU-CS-90-144

Systems of Polymorphic Type Assignment in LF
Robert Harper
June 1990

CMU-CS-90-145

A Computational Study of Job-Shop Scheduling
David Applegate, William Cook
November 1990

CMU-CS-90-146

VCODE Reference Manual (Version 1.1)
Guy E. Blelloch, Siddhartha Chatterjee, Fritz Knabe, Jay Sipelstein, Marco Zagha
July 1990

CMU-CS-90-147

On Functors Expressible in the Polymorphic Typed Lambda Calculus
John C. Reynolds, Gordon D. Plotkin
July 1990
[An earlier vision appeared as CMU-CS-88-125]

CMU-CS-90-148

A Parallel Algorithm for Constructing Binary Decision Diagrams
Shinji Kimura, Edmund M. Clarke
July 1990

CMU-CS-90-149

The Architecture of PRL: A Mathematical Medium
Joseph Bates
July 1990

CMU-CS-90-150

A Simulator for Concurrent Objects
Jeannette M. Wing, Chun Gong
July 1990
26 pages

CMU-CS-90-151

A Library of Concurrent Objects and Their Proofs of Correctness
Jeannette M. Wing, Chun Gong
July 1990
30 pages

CMU-CS-90-152

Scheduling and Resource Management Techniques for Multiprocessors
David L. Black
Ph.D. Thesis
July 1990

CMU-CS-90-153

Protocol Implementation on the Nectar Communication Processor
Eric C. Cooper, Peter A. Steenkiste, Robert D. Sansom, Brian D. Zill
September 1990

CMU-CS-90-154

The Garnet Compendium: Collected Papers, 1989-1990
Brad A. Myers, ed.
August 1990

CMU-CS-90-155

Scheduling Dependent Real-Time Activities
Raymond Keith Clark
Ph.D. Thesis
August 1990

CMU-CS-90-156

Visual Tracking with Deformation Models
James M. Rehg, Andrew P. Witkin
August 1990

CMU-CS-90-157

A Record Calculus Based on Symmetric Concatenation
Robert Harper, Benjamin Pierce
August 1990

CMU-CS-90-158

GLINDA: Natural Language Text Generation in the OZ Interactive Fiction Project
Mark Kantrowitz
July 1990
22 pages

CMU-CS-90-159

Specifications as Search Keys for Software Libraries: A Case Study Using Lambda Prolog
Eugene J. Rollins, Jeannette M. Wing
September 1990

CMU-CS-90-160

Finitely Stratified Polymorphism
Daniel Leivant
August 1990

CMU-CS-90-161

Stochastic Plans for Robotic Manipulation
Kenneth Yigael Goldberg
Ph.D. Thesis
August 1990

CMU-CS-90-162

Demonstrational Interfaces: A Step Beyond Direct Manipulation
Brad A. Myers
August 1990

CMU-CS-90-163

The Computation of Grobner Bases on a Shared Memory Multiprocessor
Jean-Philippe Vidal
August 1990

CMU-CS-90-164

Snap Together Mathematics
Michael Gleicher, Andrew Witkin
August 1990

CMU-CS-90-165

Prospects for an Engineering Discipline of Software
Mary Shaw
September 1990

CMU-CS-90-166

Shape and Motion from Image Streams: A Factorization Method 1. Planar Motion
Carlo Tomasi, Takeo Kanade
September 1990

CMU-CS-90-167

From Physiology to Behavior: Computational Models of Catecholamine Modulation of Information Processing
David Servan-Schreiber
Ph.D. Thesis
September 1990

CMU-CS-90-168

Maximization of Mutual Information in a Context Sensitive Neural Network
Gordon J. Goetsch
Ph.D. Thesis
September 1990

CMU-CS-90-169

Semantic Characterizations of Number Theories
Daniel Leivant
August 1990

CMU-CS-90-170

Towards a Theory of Parallel Algorithms on Concrete Data Structures
Stephen Brookes, Shai Geva
September 1990

CMU-CS-90-171

Unpublished

CMU-CS-90-172

A Linear-Programming Reformulation of Chemical Stoichiometry and Catalysis
Raul Valdes-Perez
September 1990

CMU-CS-90-173

A Statistical Study of Selective Min-Max Search in Computer Chess
Thomas S. Anantharaman
Ph.D. Thesis
May 1990

CMU-CS-90-174

Hybridizing Nonmonotonic Inheritance with Theorem Proving
Richmond H. Thomason, John M. Aronis
October 1990

CMU-CS-90-175

Studying Software Architecture through Design Spaces and Rules
Thomas G. Lane
October 1990
[Also appears CMU/SEI-90-TR-18]

CMU-CS-90-176

A Design Space and Design Rules for User Interface Software Architecture
Thomas G. Lane
October 1990
[Also appears as CMU/SEI-90-TR-22]

CMU-CS-90-177

Concurrent, Atomic Garbage Collection
David L. Detlefs
Ph.D. Thesis
October 1990

CMU-CS-90-178

A Locally Adaptive Window for Signal Matching
Masatoshi Okutomi, Takeo Kanade
October 1990

CMU-CS-90-179

Soar User's Manual: Version 5.2
John Laird, Clare Bates Congdon, Erik Altmann, Kathy Swedlow
October 1990
[Also appears Electrical Engineering and Computer Science Department, The University of Michigan as Technical Report CSE-TR-72-90.]

CMU-CS-90-180

BEE: A Basis for Distributed Event Environments (Reference Manual
Bernd Bruegge
November 1990

CMU-CS-90-181

The CLP (R) Language and System
Joxan Jaffar, Spiro Michaylov, Peter J. Stuckey, Roland H.C. Yap
October 1990

CMU-CS-90-182

Parallel Symbolic Computation Algorithms
Edmund M. Clarke, David E. Long, Spiro Michaylov, Stephen A. Schwab,
Jean-Philippe Vidal, Shinji Kimura
October 1990

CMU-CS-90-183

Learning AC^0 Functions Sampled Under Mutually Independent Distributions
Merrick Furst, Jeffrey Jackson, Sean Smith
October 1990

CMU-CS-90-184

Typing First-Class Continuations in ML
Bruce F. Duba, Robert Harper, David MacQueen
October 1990

CMU-CS-90-185

A Structural Theory of Explanation-Based Learning
Oren Etzioni
Ph.D. Thesis
December 1990

CMU-CS-90-186

Adding Threads to Standard ML
Eric C. Cooper, J. Gregory Morrisett
December 1990

CMU-CS-90-187

No Assembly Required: Compiling Standard ML to C
David Tarditi, Anurag Acharya, Peter Lee
November 1990

CMU-CS-90-188

Persistent Long-term Transactions for Software Development
Charles W. Krueger
November 1990

CMU-CS-90-189

A Multiple-Baseline Stereo
Masatoshi Okutomi, Takeo Kanade
November 1990

CMU-CS-90-190

Prefix Sums and Their Applications
Guy E. Blelloch
November 1990

CMU-CS-90-191

Machine Discovery of Chemical Reaction Pathways
Raul E. Valdes-Perez
Ph.D. Thesis
December 1990

CMU-CS-90-192

Fixed Point under the Fourier Transform of Boolean Functions
Sean W. Smith, Carl Sturtivant
November 1990

CMU-CS-90-193

Performance Evaluation of Scene Registration and Stereo Matching for Cartographic Feature Extraction
Yuan C. Hsieh, David M. McKeown, Jr., Frederic P. Perlant
November 1990

CMU-CS-90-194

Fusion of Monocular Cues to Detect Man-Made Structures in Aerial Imagery
Jefferey A. Shufelt, David M. McKeown, Jr.
September 1990

CMU-CS-90-195

Towards Real-Time GOMS
Bonnie E. John, Alonso H. Vera, Allen Newell
December 1990

CMU-CS-90-196

Dynamic Recurrent Neural Networks
Barak A. Pearlmutter
December 1990
[Supersedes CMU-CS-88-191]

CMU-CS-90-197

Supporting Systolic and Memory Communication in iWarp
Shekhar Borkar, Robert Cohn, George Cox, Thomas Gross, H.T. Kung, Monica Lam, Margie Levine, Brian Moore, Wire Moore, Craig Peterson, Jim Susman, Jim Sutton, John Urbanski, Jon Webb
September 1990