1985 Technical Reports

YALEU/DCS/TR355 * Relational Queries Computable in Polynomial Time
Neil Immerman
January 1985

YALEU/DCS/TR356 [.pdf] Fast Algorithms for Bipartite flow
Daniel Gusfield
Charles Martel
David Fernandez
January 1985

YALEU/DCS/TR357 [.pdf] An Incremental Multigrid Strategy for the Fluid Dynamics Equations
Michele Napolitano
January 1985

YALEU/DCS/TR358 [.pdf] High Re Separated Flow Solutions Using the Navier-Strokes and Approximate Equations
Michele Napolitano
January 1985

YALEU/DCS/TR359 * Parallel Programming in Linda
David Gelernter
January 1985

YALEU/DCS/TR360 [.pdf] Future High performance Computation: The Megaflop per Dollar Alternative’
Lennart Johnsson
January 1985

YALEU/DCS/TR361 [.pdf] Communication Efficient Matrix Operations on a Torus and a Boolean Cube
Lennart Johnsson
January 1985

YALEU/DCS/TR362 [.pdf] A New List Compaction Method
Kai Li
Paul Hudak
February 1985

YALEU/DCS/TR363 [.pdf] Multiple Array Processors for Ocean Acoustic Problems
Martin Schultz
February 1985

YALEU/DCS/TR364 [.pdf] Bulldog: A compiler for VLIW Architectures
John Ellis
February 1985

YALEU/DCS/TR365 [.pdf] A Stability Analysis of Incomplete LU Factorizations
Howard Elman
February 1985

YALEU/DCS/TR366 [.pdf] On the dependence of the covergence of Gummel’s Algorithm on the Regularity of the Solution
Thomas Kerkhoven
February 1985

YALEU/DCS/TR367 [.pdf] Data Permutations and Basic Linear Alegebra Computations on Ensemble Architectures
Lennart Johnsson
February 1985

YALEU/DCS/TR368 [.pdf] Multigrid Algorithms on the Hypercube Multiprocessor
Tony Chan
Youcef Saad
February 1985

YALEU/DCS/TR369 * Reasoning About Access to Equipment
Erik Urdang
February 1985

YALEU/DCS/TR370 [.pdf] Efficient Systolic Arrays for the Solution of Toeplitz Systems: An Illustration of a Methodology for the Construction of Systolic Architectures in VLSI
Jean-Marc Delosme
Ilse Ipsen
February 1985

YALEU/DCS/TR371 * Parallel Programming and Algorithm Synthesis Using Recursion Equations and First Order
Marina Chen
March 1985

YALEU/DCS/TR372 [.pdf] Fairing of Biased Coins in Bounded Time
Josh Cohen
March 1985

YALEU/DCS/TR373 [.pdf] Solving Eliptic Partial Differential Equations on the Hypercube Multiprocessor
Tony Chan
Faisal Saied
Martin Schultz
March 1985

YALEU/DCS/TR374 * Synthesizing Systolic Designs
Marina Chen
March 1985

YALEU/DCS/TR375 [.pdf] Parallelism, Memory Anti-Aiasing and Correctness for Trace Scheduling Compilers
Alex Nicolau
March 1985

YALEU/DCS/TR376 [.pdf] Inductive Inference by Refinement
Philip Laird
November 1985

YALEU/DCS/TR377 * Dense Matrix Operations on a Torus and a Boolean Cube
Lennart Johnsson
March 1985

YALEU/DCS/TR378 [.pdf] Generation of Layouts from Circuit Schematics A Graph Theoretic Approach
Tak NG
Lennart Johnsson
March 1985

YALEU/DCS/TR379 * Banded Systems Solvers for Ensemble Architectures
Lennart Johnsson
March 1985

YALEU/DCS/TR380 [.pdf] Polynomial Interation for Nonsymmetric Indefinite Linear Systems
Howard Elman
Roy Streit
March 1985

YALEU/DCS/TR381 [.pdf] Alternating Direction Methods on Multiprocessors
Lennnart Johnsson
Youcef Saad
Martin Schultz
April 1985

YALEU/DCS/TR382 [.pdf] Alternating Direction on Multiprocessors: An Extended Abstract
Youcef Saad
Martin Schultz
April 1985

YALEU/DCS/TR383 The S/NET’s Linda Kernel
Nicholas Carriero
David Gelernter
March 1985

YALEU/DCS/TR384 Explanation: A Second Pass
Roger C. Schank
Christopher Riesbeck
April 1985

YALEU/DCS/TR385 Questions and Thought
Roger C. Schank
April 1985

YALEU/DCS/TR386 Bug Catalogue 2,3,4.
James Spohrer
Edgar Pope
Michael Lipman
Warren Sack
Scott Freiman
David Littman
W. Lewis Johnson
Elliot Soloway
May 1985

YALEU/DCS/TR387 [.pdf] Parallel Direct Methods for Solving Banded Linear
Youcef Saad
Martin H. Schultz
August 1985

YALEU/DCS/TR388 * Band Matrix Systems Solvers on Ensemble Architecture.
Lennart Johnson
May 1985

YALEU/DCS/TR389 [.pdf] Topological Properties of Hyercubes
Youcef Saad
Martin H. Schultz
April 1985

YALEU/DCS/TR390 [.pdf] Para-Functional Programming: A Paradigm for Programming Multiprocessor Systems
Paul Hudak
Lauren Smith
May 1985

YALEU/DCS/TR391 [.pdf] A Set-Theoretic Characterization of Function Strictness in the Lambda Calculus.
Pual Hudak
Jonathan Young
May 1985

YALEU/DCS/TR392 A Goal/Plan Analysis of Buggy Pascal Programs
James Spohrer
Elliot Soloway
Edgar Pope
May 1985

YALEU/DCS/TR393 [.pdf] Relational Quirie Computable in Polynomial Time
Neil Immerman
May 1985

YALEU/DCS/TR394 [.pdf] Primality and Cryptography
Evangelos Kranakis
May 1985

YALEU/DCS/TR395 Intention-Based Diagnosis of Errors in Novice Programs
William Lewis Johnson
May 1985

YALEU/DCS/TR396 On the Lanczos Method for Solving Symmetric Linear Systems w/ Several Right Hand Slides
Youcef Saad
June 1985

YALEU/DCS/TR397 [.pdf] Partial Eigen-Solutions of Large Nonsemetric Matrices
Youcef Saad
June 1985

YALEU/DCS/TR398 [.pdf] Rank revealing QR-Factorizations
Tony Chan
June 1985

YALEU/DCS/TR399 [.pdf] The DUCK Manual
Drew McDermott
June 1985

YALEU/DCS/TR400 [.pdf] Probabilistic Inductive Inference
Leonard Pitt
June 1985

YALEU/DCS/TR401 [.pdf] On the Solution of Circulant Linear Systems
Mingkui Chen
June 1985

YALEU/DCS/TR402 * Micro-Proust
W. Lewis Johnson
Elliot Soloway
June 1985

YALEU/DCS/TR403 [.pdf] Deflated Decomposition by the Lanczos Process
Tony Chan
Youcef Saad
June 1985

YALEU/DCS/TR404 [.pdf] A Simple Probabilistic Approximation Algorithm for Vertex Cover
Leonard Pitt
June 1985

YALEU/DCS/TR405 [.pdf] Easy Impossibility Proofs for Distributed Consensus Problems
Michael Fischer
Nancy Lynch
Michael Merritt
June 1985

YALEU/DCS/TR406 * An Approach to the Design of Highly Parallel Algorithms in VLSI
Marina Chen
July 1985

YALEU/DCS/TR407 [.pdf] Three Fast Algorithms for Four Problems in Stable Marriage
Dan Gusfield
July 1985

YALEU/DCS/TR408 [.pdf] Analysis of Preconditioners for Domain Decomposition
Tony Chan
July 1985

YALEU/DCS/TR409 [.pdf] A Domain Decomposed Fast Poisson Solver on a Rectangle
Tony Chan
Diana Resasco
July 1985

YALEU/DCS/TR410 * Fourier Analysis of Preconditional Interactive Methods
Tony Chan
Howard Elman
July 1985

YALEU/DCS/TR411 [.pdf] An Explicit Scheme for the Prediction of Ocean Acoustic Propagation in Three Dimensions
Tony Chan
Long-jun Shen
Ding Lee
July 1985

YALEU/DCS/TR412 [.pdf] A Parallel Language and its Compilation to Multiprocessor Machines or VLSI
Marina Chen
July 1985

YALEU/DCS/TR413 [.pdf] Stability Analysis of Difference Schemes for Variable Cofficient Schrodinger Type Equations
Tony Chan
Long-jun Shen
August 1985

YALEU/DCS/TR414 [.pdf] A Survey of Preconditioners for Domain Decomposition
Tony Chan
Diana Resasco
August 1985

YALEU/DCS/TR415 [.pdf] Dynamic Monotone Priorities on Planer Sets (Extended Abstract)
Michael Fischer
Michael Paterson
August 1985

YALEU/DCS/TR416 [.pdf] A Robust and Varifiable Cryptographically Secure Election Scheme (Extended Abstract)
Josh Cohen
Michael Fischer
August 1985

YALEU/DCS/TR417 [.pdf] On the Solution of a class of Toeplitz Systems
Mingkui Chen
August 1985

YALEU/DCS/TR418 [.pdf] Solving Narrow Banded Systems on Ensemble Architectures
Lennart Johnsson
August 1985

YALEU/DCS/TR419 [.pdf] Probabilistic Analysis of a Network Resource Allocation Algorithm.
Michael Fischer
Nancy A. Lynch
Nancy D. Griffeth
Leonidas J. Guibas
August 1985

YALEU/DCS/TR420 Why Kids Should Learn to Program
Elliot Soloway
August 1985

YALEU/DCS/TR421 [.pdf] Distributed FIFO Allocation of Identical Resources Using Small Shared Space
Michael Fischer
Nancy A. Lynch
Allan Borodin
James E.Burns
August 1985

YALEU/DCS/TR422 [.pdf] Interconnection Networks and Parallel Memory Organizations for Array Processing
Abhiram G. Ranade
September 1985

YALEU/DCS/TR423 [.pdf] Planning by Search through Simulations
David Miller
September 1985

YALEU/DCS/TR424 [.pdf] Complex Shift and Invert Strategies for Real Matrices
Youcef Saad
Breseford Parlett
September 1985

YALEU/DCS/TR425 [.pdf] Parallel Implementations of Preconditioned Conjugate Gradien Methods
Martin Schultz
Youcef Saad
September 1985

YALEU/DCS/TR426 [.pdf] Foundations of Knowledge for Distributed Systems
Michael Fischer
Neil Immerman
October 1985

YALEU/DCS/TR427 Automatic Generation of VLSI Architectures: Synthesis by Agorithym Transformation
Marina Chen
October 1985

YALEU/DCS/TR428 [.pdf] Data Communications in Hypercubes
Martin Schultz
Youcef Saad
October 1985

YALEU/DCS/TR429 Coupled and lecoupled Algorithms for Semiconductors Simulation
Thomas Kerkhoven
October 1985

YALEU/DCS/TR430 Temporal Reasoning & Default Logics
Drew McDermott
Steven Hanks
October 1985

YALEU/DCS/TR431 Education and Computers: An AI Perspective
Roger Schank
Stephen Slade
October 1985

YALEU/DCS/TR432 Revised: A Systolic Design for the Problem of Partitions of an Integer
Marina Chen
October 1985

YALEU/DCS/TR433 Temporal Imagery: An Approach to Reasoning about Time for Planning and Problem Solving
Thomas Dean
October 1985

YALEU/DCS/TR434 [.pdf] Every Finite Distributive Lattice is a Set of Stable Matchings for a Small Stable Marriage Instance
Daniel Gusfield
R. Irving
P. Leather
M. Saks
October 1985

YALEU/DCS/TR435 [.pdf] The Structure of the Solvable Stable Roommates Problem: It’s the Stable Marriage Problem.
Daniel Gusfield
October 1985

YALEU/DCS/TR436 [.pdf] Solving Tridiagonal Systems on Ensemble Architectures.
Lennart Johnsson
October 1985

YALEU/DCS/TR437 [.pdf] Cyclic Reduction on a Binary Tree.
Lennart Johnsson
October 1985

YALEU/DCS/TR438 Distributed Dated Structures in Linda
David Gelernter
Nicholas Carriero
Jerold Leichter
October 1985

YALEU/DCS/TR439 [.pdf] Combining Parallel and Sequential Sorting on a Boolean Cube
Lennart Johnsson
October 1985

YALEU/DCS/TR440 [.pdf] Rapid Solution of Integral Equations of Scattering Theory in Two Dimensions
Vladimir Rokhlin
November 1985

YALEU/DCS/TR441 [.pdf] End-point Corrected Trapezoidal Quadrature Rules for Singluar Function
Vladimir Rokhlin
November 1985

YALEU/DCS/TR442 * The Generation of a Class of Multipliers: A Synthesis Approach to the Design of Highly Parallel Algorithms in VLSI
Marina Chen
December 1985

YALEU/DCS/TR443 [.pdf] How to Embed lrees into Hypercubes. Supported in part by the Office of Naval Research under contracts Supported by N00014-85-K-0461
Sandeep Bhatt
Ilse Ipsen
December 1985

YALEU/DCS/TR444 [.pdf] The Impact of Parallel Architectures on the Solution of the Eigenvalue Problems.
Ilse Ipsen
Youcef Saad
December 1985

YALEU/DCS/TR445 [.pdf] Orbit: An Optimizing Compiler for Scheme
David Kranz
Richard Kelsey
Paul Hudak
James Philbin
Norman Adams
December 1985

YALEU/DCS/TR446 [.pdf] A Proof-Stream Semantics for Lazy Narrowing
Juan Guzman
Paul Hudak
December 1985

YALEU/DCS/TR447 * Functional Programming on Multiprocessor Architectures
Paul Hudak
December 1985

YALEU/DCS/TR448 [.pdf] Comparison of Domain Decomposition Techniques for Elliptic Partial Differential Equations and their Parallel Implementation
David Keyes
William Gropp
December 1985

YALEU/DCS/TR449 [.pdf] A Projection Method for Partial Pole Assignment in Linear State Feedback
Youcef Saad
December 1985