usenet@ucbvax.BERKELEY.EDU (USENET News Administration) (02/13/86)
Technical Report Series as of 10/07/85
Department of Comptuer Science
NEW YORK UNIVERSITY
COURANT INSTITUTE OF MATHEMATICAL SCIENCES
251 Mercer Street
New York, NY 10012
(212) 460-7226
To order, please indicate the report number(s) you wish to
receive and mail your request to:
Mary Conway
Department of Computer Science
New York University
251 Mercer Street
New York, NY 10012
If you prefer, you can forward your request to me via electronic mail.
My arpanet address is CONWAY@NYU .
All our reports are free of charge except reports 84 and 85.
-----------------------------------------------------------------
Report
No. Title Author(s) Date
-----------------------------------------------------------------
001 A Survey of Program Proof J. Schwartz Sep 1978
Technology
002 Two Approaches to Inter- M. Sharir & Sep 1978
procedural Data Flow A. Pnueli
Analysis
003 Security in Operating E. Weyuker Oct 1978
Systems; Separating the
Roles of Rights
004 Probabilistic Algorithms J. Schwartz Oct 1978
for Verification of
Polynomial Identities
005 A Note and a Dialog On R. Dewar Oct 1978
Aspects of the DOD
Com-Language (Ironman)
006 Translatability and E. Weyuker Oct 1978
Decidability Questions
for Restricted Classes of
Program Schemas
007 Automatic Discovery of S. Stolfo & Jan 1979
Heuristics M. Harrison
for Non-deterministic
programs
008 Theories of Program E. Weyuker & Feb 1979
Testing and the Application T. Ostrand
of Revealing Domains
009 Micro-Balm - A Programming M. Harrison Jan 1979
Language for Microcomputers
010 Compile-Time Analysis of P. Abrahams & Feb 1979
Data List-Format List L. Clarke
Correspondences
011 Micro Spitbol R. Dewar, Oct 1979
M. Golumbic &
C. Goss
012 The Language REFAL: The V. Turchin Jan 1980
Theory of Compilation and
Metasystem Analysis
013 CIMS PL/I P. Abrahams Apr 1980
014 A Strong-Connectivity M. Sharir May 1979
Algorithm And Its Applications
in Data Flow Analysis
015 Structural Analysis: A New M. Sharir Oct 1979
Approach To Flow
Analysis in Optimizing Compilers
016 Some Observations Concerning M. Sharir Jan 1980
Differentiation of
Set-Theoretic Expressions
017 Application of the M. Sharir Jan 1980
Use-Definition Chaining
to Attribute-Flow Analysis
018 A Worst Case Analysis of C. Kruskal & Nov 1979
Heapsort E. Weixelbaum
019 Algorithmic Aspects of M. Golumbic Jul 1980
Perfect Graphs (OUT OF PRINT)
020 Internal, external, and J. Schwartz Jul 1980
pragmatic influences: technical
perspectives in the development
of programming languages
021 Algorithm Derivation M. Sharir Oct 1979
by Transformations
022 Criteria for the Adequacy of E. Weyuker May 1980
Test Data
023 Data Flow Analysis Techniques S. Rapps & Dec 1981
for Program Test Data E. Weyuker
Generation (REVISED)
024 Supersaturated Ultracomputer A. Gottlieb & Sep 1980
U11 Algorithms C. Kruskal
025 On Testing Nontestable E. Weyuker Oct 1980
Problems
026 Some Modified Algorithms for R. Dewar, Oct 1980
Dijkstra's Longest Upsequence S. Merritt &
Problem M. Sharir
027 Error-Based Testing Strategy E. Weyuker Jan 1981
028 Basic Techniques for the A. Gottlieb, Dec 1980
U16 Efficienct Coordination of B. Lubachevsky &
Sequential Processors L. Rudolph
029 Washcloth - The Logical A. Gottlieb Dec 1980
U12 Successor To Soapsuds
030 Networks and Algorithms for A. Gottlieb & Mar 1981
U25 Very Large Scale Parallel J. Schwartz
Computation
031 Supersaturated Paracomputer C. Kruskal May 1981
U26 Algorithms
032 Lower Bounds on VLSI M. Snir May 1981
U29 Implementations of
Communication Networks
033 Balancing is Not Always Good M. Snir Jun 1981
034 Syllog: A Knowledge Based A. Walker Jun 1981
Data Management Systems
035 A Quadratically Convergent M. Overton May 1981
Method for Minimizing a Sum
of Euclidean Norms
036 Verification of Several B. Lubachevsky Jul 1981
U33 Parallel Coordination Programs
Based on Descriptions of their
Reachability Sets
037 A New Real-Time Algorithm for E. Schonberg & Sep 1981
the Two-Dimensional Convex Z. Zhou
Hull Problem
038 Convergence of a Two-Stage G. Golub & Sep 1981
Richardson Iterative M. Overton
Procedure for Solving Systems
of Linear Equations
039 On the Piano-Movers Problem, J. Schwartz & Oct 1981
R1 I. Case of a Two-Dimensional M. Sharir
Rigid Polygonal Body Moving
Amidst Polygonal Barriers
040 The NYU Ultracomputer - A A. Gottlieb, Jul 1981
U42 General Purpose R. Grishman,
Parallel Computer C. Kruskal,
K. McAuliffe,
L. Rudolphe,
M. Snir
041 On the Piano Movers Problem, J.T. Schwartz & Feb 1982
R2 II. General Techniques for M. Sharir
Computing Topological
Properties of Real Algebraic
Manifolds
042 Practical Method for M. Burke & Apr 1982
Syntatic Error Diagnosis and G. Fisher
Recovery
043 A Preliminary Evaluation of R. Grishman & May 1982
Trace Scheduling for S. Bugong
Global Microcode Compaction
044 The NYU Ultracomputer - A. Gottlieb, Jul 1981
U40 Designing a MIMD Shared R. Grishman,
Memory C. Kruskal,
K. McAuliffe,
L. Rudolphe,
M. Snir
045 On Parallel Searching M. Snir Jun 1982
U44
046 On The Partitioning of M. Snir Jul 1982
Regular Networks
047 Collecting and Categorizing T. Ostrand & Aug 1982
Software Error Data in An E. Weyuker
Industrial Enviornment
049 The Effect of Restrictions on P. Spirakis Aug 1982
Relative Processor Speeds to
Differences in Efficiency between
Synchronous and Asynchronous Systems
050 A Formal Notion of M. Davis & Oct 1982
Program-Based Test Data E. Weyuker
051 Some Results on Multistage C. Kruskal & May 1982
U41 Interconnection Networks M. Snir
052 On the Piano Movers Problem J. Schwartz & Sep 1982
R3 III. Coordinating the Motion M. Sharir
of Several Independent Bodies:
The Special Case of Circular Bodies
Moving Amidst Polygonal Barriers
053 The Vornoi Diagram Method of C. O'Dunlaing & Mar 1982
R4 Motion-Planning: I. The Case C. Yap
of A Disc
054 Concurrency Control O. Shmueli & Nov 1982
Performance Evaluation P. Spirakis
(A Methodology and an
Application to Two Phase
Locking)
055 On the Shadow CPU P. Spirakis Jan 1983
Approximation for
Modelling Priority Scheduling
in Computer Systems
056 Intersecting and Closest-Pair M. Sharir Feb 1983
R5 Problems for a Set of
Planar Objects
057 Efficient Implementation Y. Perl & Feb 1983
of a Shifting Algorithm U. Vishkin
058 On the Piano Movers Problem M. Sharir & Feb 1983
R6 IV Various Decomposable E. Azriel-Sheffi
Two-Dimensional
Motion Planning Problems
059 Efficient Detection of J. Hopcroft, Feb 1983
R7 Intersections Among J. Schwartz &
Spheres M. Sharir
060 An Approach to Automating The B. Lubachevsky Feb 1983
U45 Verification of Compact Parallel
Coordination Programs, I
061 On Choice of A Model of U. Vishkin Feb 1983
U50 Parallel Computation
062 Optimal Distributed J. Reif & Feb 1983
Resource Allocation P. Spirakis
063 Isomorphism of Strongly R. Cole Feb 1983
Regular Graphs
064 An Approach to Automating the B. Lubachevsky Feb 1983
U49 Verification of Compact Parallel
Coordination Programs, II.
065 Structured Light Sensors for J. Schwartz Mar 1983
R8 3-D Robot Vision
066 A Gradient Projection R. Hummel & Mar 1983
R9 Algorithm for Relaxation S. Zucker
Methods
067 Precise Implementation of CAD S. Ocken & Mar 1983
R10 Primitives Using Rational J. Schwartz
Parametrizations of Standard
Surfaces
068 A Design Method for Relaxation R. Hummel Mar 1983
R11 Labeling Applications
069 O(log n) and Optimal Parallel U. Vishkin & Apr 1983
U51 Biconnectivity Algorithms R. Tarjan
070 Parallel Computation on 2-3 W. Paul, Apr 1983
U52 Trees U. Vishkin &
H. Wagner
071 Synchronous Parallel U. Vishkin Apr 1983
U53 Computation
072 Dynamic Parallel Memories H. Wigderson Apr 1983
U54 U. Vishkin
074 Numerical Methods for J. Nocedal & Apr 1983
Solving Inverse Eigenvalue M. Overton
Problems
075 A Linear-Time Algorithm C. Bleich & Apr 1983
for the Weighted Median M. Overton
Problem
076 On the Combinatorial P. Spirakis & Apr 1983
R12 Complexity of Motion C. Yap
Coordination
077 Washcloth Simulation of Korn &
U55 Three-Dimensional Rushfield
Weather
078 Trade-Offs Between U. Vishkin Apr 1983
U56 Depth and Width in Parallel
Computation
079 An Accelerated Bisection H. Bernstein Jul 1983
Method for the Calculation of
Eigenvalues of a Symmetric Tri-
diagonal Matrix
080 The AMPOS Multiprocessor M. Harrison & Jul 1983
System: A Computer System O. Smith
for Laboratory Use
081 Lucid Boxes vs. Black Boxes U. Vishkin Jul 1983
082 On the Depth of a Random J. Reif & Jul 1983
Graph P. Spirakis
083 On the Piano Movers Problem: J. Schwartz & Jul 1983
R13 V. The Case of a Rod Moving M. Sharir
in Three-Dimensional Space
Amidst Polyhedral Obstacles
084 The Executable Semantics NYU Ada Project
Ada of Ada
085 The Static Semantics of Ada NYU Ada Project
Ada
087 Geometric Retrieval Problems R. Cole & Oct 1983
C. Yap
088 Searching and Storing Similar R. Cole Oct 1983
Lists
089 Granularity of Parallel U. Vishkin & Oct 1983
U59 Memories K. Mehlhorn
090 Optimal Parallel Generation of I. Bar-On & Oct 1983
U61 a Computation Tree Form U. Vishkin
091 Expected Parallel Time and J. Reif & Oct 1983
Sequential Space Complexity P. Spirakis
of Graph and Digraph
Problems
092 Strong NP-Hardness of Moving P. Spirakis & Oct 1983
R20 Many Discs C. Yap
093 Moving Many Pebbles in a Graph P. Spirakis & Oct 1983
R21 is Polynomial Time C. Yap
094 Buffered Versus Unbuffered P. Spirakis Oct 1983
Tree Networks Accessing
a Critical Resource
095 Projected Hessian Updating J. Nocedal & Nov 1983
Algorithms for Nonlinearly M. Overton
Constrained Optimization
096 A Parallel-Design U. Vishkin Jun 1983
U58 Distributed-Implementation
(PDDI) General-Purpose Computer
097 Stability of Hyperbolic L. Trefethen Nov 1983
Finite-Difference Models
With One Or Two Boundaries
098 Very Fast Algorithms for the P. Spirakis Dec 1983
R22 Area of the Union of Many
Circles
099 Axiomatizing Software Test E. Weyuker Jan 1984
Data Adequacy
100 Numerical Solution of a Model M. Overton Feb 1984
Problem from Collapse Load
Analysis
101 Iterative Methods for Elliptic O. Widlund Feb 1984
Problems on Regions Partitioned
into Substructures and the
Biharmonic Dirichlet Problem
102 Probabilistic techniques for P. Spirakis & Oct 1983
two phase locking in database J. Reif
systems
103 On the complexity of motion J. Hopcroft & Feb 1984
R14 planning for multiple J. Schwartz
independent objects; PSPACE
hardness of the "warehouseman's
problem"
104 Shape from probing R. Cole & Dec 1983
R15 C. Yap
105 Coordinating the Motion of C. Yap Feb 1984
R16 Several Discs
106 An Optimal Parallel Algorithm U. Vishkin Dec 1983
U64 for Selection
107 Randomized Speed-Ups in U. Vishkin Feb 1984
U66 Parallel Computation
108 On k-hulls and Related Problems R. Cole, Feb 1984
R17 M. Sharir &
C. Yap
109 An efficient parallel strong U. Vishkin Feb 1984
U67 orientation
110 Square blocks and L. Trefethen Mar 1984
equioscillation
in the Pade, Walsh and CF Tables
111 Zero crossings and the heat R. Hummel & Mar 1984
R18 equation B. Gidas
112 Analysis and design of poly- L. Trefethen Mar 1984
gonal resistors by conformal
mapping
113 VSH Users guide: A software D. Clark & Mar 1984
R19 environment for image R. Hummel
processing
114 Queuing delay modeling for P. Spirakis Mar 1984
U68 multistage interconnection
multiprocessor networks
115 Deblurring Gaussian blurr R. Hummel & Apr 1984
R23 B. Kimia
p-
116 On l instability and L. Trefethen Apr 1984
oscillation at discontinuities
in finite difference schemes
117 Slowing down sorting networks R. Cole Apr 1984
to obtain faster sorting
algorithms
118 Probabalistic biddings gives J. Reif & Apr 1984
R24 optimal distributed resource P. Spirakis
allocation
119 Some remarks on robot vision J. Schwartz & Apr 1984
R25 M. Sharir
120 Servol preliminary proposals H. Bernstein, Apr 1984
R26 for a programming language P.G. Lowney &
for real-time servo control J. Schwartz
121 Coordinating pebble motion D. Kornhauser, May 1984
R27 on graphs, the diameter of G. Miller &
permuatation groups and P. Spirakis
applications
122 Tight area bounds and provably A. Siegel Jun 1984
2
good AT bounds for sorting
circuits
123 An ontology of physical actions E. Davis Jun 1984
124 Preliminary implementation of C. Bastuscheck& Jun 1984
R28 a ratio image depth sensor J. Schwartz
125 Determining the shape of a H. Bernstein Jun 1984
R29 convex n-sided polygon by using
2n+k tactile probes
126 A parallel median algorithm R. Cole & Jul 1984
C. Yap
127 Conformal mapping solution of L. Trefethen & Jul 1984
Laplace's equation on a polygon R. Williams
with oblique derivative boundary
conditions
128 Counting digraphs and hyper- C. O'Dunlaing & Jul 1984
graphs C. Yap
129 Parallel implementation of H. Bernstein & Jul 1984
bisection for the calculation M. Goldstein
of eigenvalues of tridiagonal
symmetric matrices
130 A semantic approach to A. Tuzhilin & Jul 1984
correctness of concurrent P. Spirakis
executions
131 Decision procedures for D. Cantone, Aug 1984
elementary sublanguages of A. Ferro &
set theory. V. Multi-level J. Schwartz
syllogistic extended by the
general union operator.
132 The rectilinear convex skull D. Wood & Aug 1984
R30 problem C. Yap
133 The volume of the union of many P. Spirakis Aug 1984
R35 spheres and point inclusion
problems (Revised)
134 Finding Euler tours in parallel M. Atallah Sep 1984
U73 U. Vishkin
135 Optimal parallel pattern U. Vishkin Sep 1984
U74 matching in strings
136 Iterative methods for the P. Bjorstad & Sep 1984
solution of elliptic problems O. Widlund
on regions partitioned into
substructures
137 Shape and function of solid E. Davis Oct 1984
objects: some examples
138 On shortest paths in polyhedral M. Sharir Oct 1984
R31 spaces
139 Generalized Vornoi diagrams for C. O'Dunlaing Nov 1984
R32 moving a ladder: I Topological M. Sharir
analysis C. Yap
140 Generalized Vornoi diagrams for C. O. Dunlaing Nov 1984
R33 moving a ladder: II Efficient M. Sharir
construction of the diagram C. Yap
141 Look up table computation for a M. Bastuscheck Nov 1984
R34 ratio image depth sensor
142 Partitioning point sets in 4 R. Cole Nov 1984
dimensions
143 Byzantine agreement by J. Reif Oct 1984
distributed randomization in P. Spirakis
0(log n) rounds (Revised)
144 Fast probabilistic techniques P. Spirakis Nov 1984
U80 for dynamic parallel addition,
parallel counting and the
processor identification problem
145 A high level real-time E. Davis Dec 1984
R36 programming language
146 A time-independent definition S. Weiss Jan 1985
of software reliability E. Weyuker
147 A self-organizing database G. Piatetsky- Jan 1985
system - A different approach Shapiro
to query optimization
148 ASSET: A systen to select and P. Frankl Jan 1985
evaluate tests S. Weiss
E. Weyuker
149 Evaluating software complexity E. Weyuker Jan 1985
150 On the conditioning of pole J. Demmel Jan 1985
assignment
151 Dynamic grid embedding: J. Ellis Jan 1985
optimizing the compression F. Makedon
of partial grids P. Spirakis
S. Zachos
152 The design and analysis of a A. Green Feb 1985
Distributed System
153 On intersection of planar R. Livne Feb 1985
R37 Jordan curves M. Sharir
154 An efficient algorithm for J. Schwartz Feb 1985
R38 finding connected components M. Sharir
in a binary image A. Siegel
155 Polynomial minimum root J. Schwartz Feb 1985
R39 separation (Note to a paper
of S.M. Rump)
156 Decision procedures for D. Cantone Feb 1985
elementary sublanguages A. Ferro
of set theory. VI. Multi-level J. Schwartz
syllogistic extended by the
powerset operator
157 A video camera interface for E. Kishon Feb 1985
R40 high speed region boundary X.D. Yang
locations
158 Join processing in a symmetric D. Shasha Mar 1985
parallel environment P. Spirakis
159 Finding minimal convex A. Aggarwal Mar 1985
R41 nested polygons H. Booth
J. O'Rourke
S. Suri
C. Yap
160 Minimum area circumscribing C. Yap May 1985
R42 polygons
161 An 0(nlogn) algorithm for the C. Yap May 1985
R43 Vornoi diagram of a set of simple
curve segments
162 Two-dimensional model-based A. Kalvin May 1985
R44 boundary matching E. Schonberg
using footprints J. Schwartz
M. Sharir
163 Computing stable J. Demmel May 1985
eigendecompositions of B. Kagstrom
of matrix pencils
164 Efficint motion planning J. Schwartz June 1985
R45 algorithms in environments M. Sharir
of bounded local complexity
165 Identification of partially J. Schwartz June 1985
R46 obscured objects in 2 and 3 M. Sharir
dimensions by matching of
noisy "characteristic curves"
166 Bird - A high-level A. Cimino June 1985
R47 interpreter for plotting
curves in 3 dimensions using
NCAR
167 Efficient string matching G. Landau June 1985
with k mismatches U. Vishkin
168 An efficient string matching G. Landau July 1985
algorithm with k differences U. Vishkin
for nuceotide and amino acid
sequences
169 A polynomial solution for J. Chang July 1985
R48 potato-peeling problem C. Yap
170 From prototype to efficient E. Schonberg July 1985
implementation: A case study D. Shields
using SETL and C
171 Iterative methods for over- R. Chan Aug 1985
flow queueing models
172 Optimal VLSI circuits for R. Cole Aug 1985
U86 sorting A. Siegel
173 Connected component labelling R. Hummel Sep 1985
U87 in image processing with MIMD A. Rojer
R49 architectures
174 Constrained total least J. Demmel Sep 1985
squares problems and the
smallest perturbation of a
submatrix which lowers the rank
175 Deterministic coin tossing R. Cole Sep 1985
U87 with applications to optimal U. Vishkin
parallel list ranking
176 Receptive fields and the R. Hummel Sep 1985
R50 reconstruction of visual S. Zucker
information
177 A brief survey of knowledge R. Hummel Sep 1985
R51 aggregation methods M. Landy
178 When does non-linear text D. Shasha Sep 1985
help?
179 The formulation and analysis S. Friedland Sep 1985
of numerical methods for J. Nocedal
inverse eigenvalue problems M. Overton
180 On shortest paths between two A. Baltsam Sep 1985
R52 convex polyhedra M. Sharir
181 On shortest paths amidst M. Sharir Sep 1985
R53 convex polyhedra
182 Input sensitive optimal P. Spirakis Jul 1985
parallel randomized
algorithms for addition and
identification
183 A Lagrangian functional step C. Borgers Oct 1985
method for the incompressible
Navier-Stokes equations
184 Partitioning point sets in R. Cole Oct 1985
arbitrary dimension
-------