New York University Courant Institute of Mathematical Sciences Department of Computer Science Technical Report Repository Following is a listing of all technical reports currently available in /pub/tech-reports. Please contact christie@cs.nyu.edu with any questions. TR 086-U100 A. Gottlieb. An Overview of the NYU Ultracomputer Project (Oct. 1987, Revised) TR 221-U101 G. Landau, U. Vishkin. Efficient Parallel and Serial Approximate String Matching. (Feb. 1986) TR 222-U102 Y. Maon, B. Schieber, U. Vishkin. Parallel Ear Decomposition Search (EDS) and ST-Numbering in Graphs. (Feb. 1986) TR 223-U103 Y. Azar, U. Vishkin. Tight Comparison Bounds on the Complexity of Parallel Sorting. (Feb. 1986) TR 242-U108 R. Cole, U. Vishkin. The Accelerated Centroid Decomposition Technique for Optimal Parallel Tree Evaulation in Logarithmic Time. (Sep. 1986) TR 243-U109 R. Cole, C. O'Dunlaing. Note on the AKS Sorting Network. (Sep. 1986) TR 485 D. Szyld, O. Widlund. Variational Analysis of Some Conjugate Gradient Methods. (Dec. 1989) TR 486-U167 M. Dryja, O. Widlund. Towards a Unified Theory of Domain Decomposition Algorithms for Elliptic Problems. (Dec. 1989) TR 489 D. Rennels, E. Schonberg. A Program Analysis Tool for Evaluating the ADA Compiler Validation Suite. (Jan. 1990) TR 498 K. Donovan. Performance of Shared Memory in a Parallel Computer. (Mar. 1990) TR 502 E. Weyuker, B. Jeng. Analyzing Partition Testing Strategies. (Apr. 1990) TR 503 V. Lanin, D. Shasha. Tree Locking on Changing Trees. (Apr. 1990) TR 504-R230 M. Pellegrini. Stabbing and Ray Shooting in 3-Dimensional Space. (May 1990) TR 505 M. Overton. Large-Scale Optimization of Eigenvalues. (May 1990) TR 506 X. Cai, O. Widlund. Domain Decomposition Algorithms for Indefinite Elliptic Problems. (May 1990) TR 507 M. Dryja, O. Widlund. Multilevel Additive Methods for Elliptic Finite Element Problems. (May 1990) TR 510 S. Cox, M. Overton. On the Optimal Design of Columns Against Buckling. (Jun. 1990) TR 512 R. Cole, Tight Bounds on the Complexity of the Bover-Moore Pattern Matching Algorithm. (Jun. 1990) TR 514 D. Shasha, J. Turek. Beyond Fail-Stop: Wait-Free Serializability and Resiliency in the Presence of Slow-Down Failures. (Sep. 1990) TR 518 K. Li. Dag Representation and Optimization of Rewriting. (Sep. 1990) TR 517 B. Smith. Domain Decomposition Algorithms for the Partial Differential Equations of Linear Elasticity. (Sep. 1990) TR 519 B. Smith. A Domain Decomposition Algorithm for Elliptic Problems in Three Dimensions. (Oct. 1990) TR 520 J. Burke. Stable Perturbations of Nonsymmetric. (Oct. 1990) TR 523 P. Ouyang. Execution of Regular DO Loops on Asynchronous Multiprocessors. (Oct. 1990) TR 529 M. Dryja. Substructuring Methods for Parabolic Problems. (Nov. 1990) TR 531 W. Jockush, N. Prabhu. Cutting a Polytype. (Nov. 1990) TR 532 G. Bohus, W. Jockush, C. Lee, N. Prabhu. On Triangulations of the 3-Ball and the Solid Torus. (Nov. 1990) TR 533 N. Prabhu. On a Conjecture of Micha Perles. (Nov. 1990) TR 534 E. Davis. Physical Idealization as Plausible Inference. (Nov. 1990) TR 536-R241 M. Pellegrini. Combinatorial and Algorithmic Analysis of Stabbing and Visibility Problems in 3-Dimensional Space. (Dec. 1990) TR 539 R. Cole, O. Zajicek. The APRAM - The Rounds Complexity Measure and the Explicit Costs of Synchronization. (Jan. 1991) TR 541 E. Davis. The Kinematics of Cutting Solid Objects. (Jan. 1991) TR 542-U170 R. Cytron, J. Lipkis, E. Schonberg. A Computer-Assisted Approach to SPMD Execution. (Jul. 1990) TR 546 R. Cole, O. Zajicek. An Asynchronous Parallel Algorithm for Undirected Graph Connectivity. (Feb. 1991) TR 547-R244 G. Gallo, B. Mishra. Some Constructions in Rings of Differential Polynomials. (Mar. 1991) TR 548 K. L. Clarkson, R. Cole, R. E. Tarjan. Randomized Parallel Algorithms for Trapezoidal Diagrams. (Mar. 1991) TR 549-R245 S. Mallat, W. L. Hwang. Singularity Detection and Processing with Wavelets. (Mar. 1991) TR 552 P. Charles. A Practical Method for Constructing Efficient LALR(k) Parsers with Automatic Error Recovery. (Mar. 1991) TR 553 I. Rigoutsos, R. Hummel. Scalable Parallel Geometric Hashing for Hypercube SIMD Architectures. (Jan. 1991) TR 554 I. Rigoutsos, R. Hummel. On a Parallel Implementation of Geometric Hashing on the Connection Machine. (Apr. 1991) TR 555 K. Laufer. Comparing Three Approaches to Transformational Programming. (Apr. 1991) TR 556 F. Henglein, K. Laufer. Programming with Structures, Functions, and Objects. (Apr. 1991) TR 557 R. Cole, U. Vishkin. On the Detection of Robust Curves. (Apr. 1991) TR 558-R246 G. Koren, B. Mishra, A. Raghunathan, D. Shasha. On-Line Schedulers for Overloaded Real-Time Systems. (May 1991) TR 561 R. Sundar. Amortized Complexity of Data Structures. (May 1991) TR 562 S. Nepomnyaschikh. Decomposition and Fictitious Domains Methods for Elliptic Boundary Value Problems. (May 1991) TR 565 E. Davis. Lucid Representations. (Jun. 1991) TR 566 M. Overton, R. Womersley. Optimality Conditions and Duality Thoery for Minimizing Sums of the Largest Eigenvalues of Symmetric Matrices. (Jun. 1991) TR 567 J. Burke, M. Overton. On the Subdifferentiability of a Matrix Spectrum I: Mathematical Foundations. (Jun. 1991) TR 568 J. Burke, M. Overton. On the Subdifferentiability of a Matrix Spectrum II: Subdifferential Formulas. (Jun. 1991) TR 569-R250 P. Tetali. Applications and Analysis of Probablistic Techniques. (Jun. 1991) TR 570 M. Dryja, O. Widlund. Additive Schwarz Methods for Elliptic Finite Element Problems in Three Dimensions. (Jun. 1991) TR 571 F. Gasperoni, U. Schweigelshohn. Efficient Algorithms for Cyclic Scheduling. (Jul. 1991) TR 572 G. Koren, D. Shasha. An Optimal Scheduling Algorithm with a Competitive Factor for Real-Time Systems. (Jul. 1991) TR 573 R. Cole, A. Raghunathan. Online Algorithms for Finger Searching. (Aug. 1991) TR 574 R. Cole, O. Zajicek. The Expected Advantage of Asynchrony. (Sep. 1991) TR 579 J. Burke, M. Overton. Differential Properties of Eigenvalues. (Sep. 1991) TR 580 L. Pavarino. An Additive Schwarz Method for the P-Version Finite Element Method. (Sep. 1991) TR 581 O. Widlund. Some Schwarz Methods for Symmetric and Nonsymmetric Elliptic Problems. (Sep. 1991) TR 582 X. Zhang. Multilevel Additive Schwarz Methods. (Sep. 1991) TR 583 X. Zhang. Domain Decompositioin Algorithms for the Biharmonic Dirichlet Problem. (Sep. 1991) TR 584 X. Zhang. Studies in Domain Decomposition: Multilevel Methods and the Biharmonic Dirichlet Problem. (Sep. 1991) TR 585 M. Hind. Efficient Loop-Level Parallelism in ADA. (Sep. 1991) TR 586 J. Haeberly. On Shape Optimizing the Ratio of the First Two Eigenvalues of the Laplacian. (Oct. 1991) TR 587 C. Chang, R. Paige. New Theoretical and Computational Results for Regular Languages. (Oct. 1991) TR 588-R255 B. Bederson, R. Wallace, E. Schwartz. A Miniaturized Active Vision System. (Nov. 1991) TR 589-R256 R. Wallace, P. Ong, B. Bederson, E. Schwartz. Space-Variant Image Processing. (Nov. 1991) TR 590 E. Davis. Axiomating Qualitative Process Theory. (Nov. 1991) TR 594 G. Koren, D. Shasha. An Optimal On-Line Scheduling Algorithm for Overloaded Real-Time Systems. (Jan. 1992) TR 595 X.-C. Cai, O. Widlund. Multiplicative Schwarz Algorithms for Some Nonsymmetric and Indefinite Problems. (Feb. 1992) TR 597 G. Park. Semantic Analyses for Storage Management Optimizations in Functional Language Implementations. (Feb. 1992) TR 599 E. Davis. Infinite Loops in Finite Time: Some Observations. (Feb. 1992) TR 601-R264 B. Bederson, R. Wallace, E. Schwartz. A Miniature Pan-Tilt Actuator: The Spherical Pointing Motor. (Apr. 1992) TR 602 J. Cai, X. Han, R. Tarjan. An $O(m$log$n)$-Time Algorithm for the Maximal Planar Subgraph Problem. (Apr. 1992) TR 603 J. Cai. Counting Embeddings of Planar Graphs Using DFS Trees. (Apr. 1992) TR 604 J. Cai, R. Paige, R. Tarjan. More Efficient Bottom-Up Multi-Pattern Matching in Trees. (Apr. 1992) TR 606 M. Dryja, O. Widlund. Domain Deomposition Algorithms with Small Overlap. (May 1992) TR 607 A. Greenbaum, L. Trefethen. GMRES/CR and Arnoldi/Lanczos as Matrix Approximations Problems. (May 1992) TR 608 A. Greenbaum, Z. Strakos. Matrices that Generate the Same Krylov Residual Spaces. (May 1992) TR 609 J. Cai, R. Paige. Multiset Discrimination -- A Method for Implementing Programming Language Systems Without Hashing. (Jun. 1992) TR 610 V. Averbukh, S. Figueroa, T. Schlick. HESFCN -- A FORTRAN Package of Hessian Subroutines for Testing Nonlinear Optimization Software. (Jun. 1992) TR 611-R266 B. Bederson. Miniature Space-Variant Active Vision System: Cortex-I. (Jul. 1992) TR 612-R267 D. Karron, J. Cox, B. Mishra. The Spiderweb Algorithm for Surface Construction from Medical Volume Data: Geometric Properties of its Surface. (Jul. 1992) TR 614 L. Pavarino. Some Schwarz Algorithms for the P-Version Finite Element Method. (Sep. 1992) TR 615 M. Dryja, O. Widlund. Some Recent Results on Schwarz Type Domain Decomposition Algorithms. (Sep. 1992) TR 616 L. Pavarino. Domain Decomposition Algorithms for the P-Version Finite Element Method for Elliptic Problems. (Sep. 1992) TR 619 S. Mallat, Z. Zhang. Matching Pursuits with Time-Frequency Dictionaries. (Revised Aug. 1993) TR 620 T.-R. Chuang, B. Goldberg. Backward Analysis for Higher-Order Functions Using Inverse Images. (Nov. 1992) TR 621 F. Tsai. Statistical Approach to Affine Invariant Matching with Line Features. (Nov. 1992) TR 622 K. Laufer. Polymorphic Type Inference and Abstract Data Types. (Dec. 1992) TR 623 J. Cullum, A. Greenbaum. Residual Relationships Within Three Pairs of Iterative Algorithms for Solving $Ax = b$. (Feb. 1993) TR 624 J. Haeberly, M. Overton. A Hybrid Algorithm for Optimizing Eigenvalues of Symmetric Definite Pencils. (Feb. 1993) TR 625 F. Tsai. Using Line Invariants for Object Recognition by Geometric Hashign. (Feb. 1993) TR 626 M. Dryja, O. Widlund. Schwarz Methods of Neumann-Neumann Type for Three-Dimensional Elliptic Finite Element Problems. (Mar. 1993) TR 627 M. Overton, R. Womersley. Second Derivatives for Optimizing Eigenvalues of Symmetric Matrices. (Mar. 1993) TR 628 G. Gallo, B. Mishra. The Complexity of Resolvent Resolved. (Mar. 1993) TR 629 M. Sarkis. Two-Level Schwarz Methods for Nonconforming Finite Elements and Discontinous Coefficients. (Mar. 1993) TR 630 P. Agarwal. The Cell Programming Language. (Mar. 1993) TR 631 M. Overton, X. Ye. Towards Second-Order Methods for Structured Nonsmooth Optimization. (Apr. 1993) TR 632 Muthukrishnan, K. Palem. Highly Efficient Dictionary Matching in Parallel. (Apr. 1993) TR 633 R. Wallace, P. Ong, B. Bederson, E. Schwartz. Space Variant Image Processing. (Apr. 1993) TR 634 R. Wallace. Miniature Direct Drive Rotary Actuators. (Apr. 1993) TR 635 J. Cai. A Language for Semantic Analysis. (May 1993) TR 636 R. Wallace, B. Bederson, E. Schwartz. Voice-Bandwidth Visual Communication Through Logmaps: The Telecortex. (May 1993) TR 637 E. Davis. Knowledge Preconditions for Plans. (May 1993) TR 638 M. Dryja, B. Smith, O. Widlund. Schwarz Analysis of Iterative Substructuring Algorithms for Elliptic Problems in Three Dimensions. (May 1993) TR 639 G. Koren, D. Shasha. Competitive Algorithms and Lower Bounds for On-line Scheduling of Multiprocessor Real-time Systems. (Jun. 1993) TR 640 F. Tsai. A Probabilistic Approach to Geometric Hashing Using Line Features. (Jun. 1993) TR 641 H. Hwang, S. Mallat. Characterization of Self-Similar with Wavelet Maxima. (Aug. 1993) TR 642 N. Silver. Control of a Dextrous Robot Hand: Theory, Implementation, and Experiment. (Aug. 1993; not avail. via FTP; email mishra@cs.nyu.edu) TR 643 B. Mishra, M. Antoniotti. ED I: NYU Educational Robot Design and Evaluation. (Aug. 1993) TR 644 T.-R. Chuang. New Techniques for the Analysis and Implementation of Functional Programs. (Aug. 1993) TR 645 A. Greenbaum. Norms of Functions of Matrices. (Aug. 1993) TR 646 B. Mishra. Bidirectional Edges Problem: Part I, a Simple Algorithm. (Sep. 1993) TR 647 B. Mishra. Bidirectional Edges Problem: Part II, an Efficient Algorithm. (Sep. 1993) TR 648 L. Pavarino, O. Widlund. Iterative Substructuring Methods for Special Elements in Three Dimensions. (Sep. 1993) TR 649 H. Cheng. Iterative Solution of Elliptic Finite Element Problems on Partially Refined Meshes and the Effect of Using Inexact Solvers. (Oct. 1993) TR 650 B. Mishra. A Survey of Computational Differential Algebra. (Oct. 1993) TR 651 R. Wallace. Miniature Direct Drive Rotary Actuators II: Eye, Finger, and Leg. (Nov. 1993) TR 652 D. Max, R. Wallace. Feedback Control of Miniature Direct Drive Devices. (Nov. 1993) TR 653 B. Mishra, M. Antoniotti, F. Hansen, R. Wallace. NYU Educational Robotics Project: A Pedagogic Overview. (Nov. 1993) TR 654 H. Chen. Multilevel Schwarz Methods with Partial Refinement. (Mar. 1994) TR 655 C. Yao, B. Goldberg. Pscheme: Extending Continuations to Express Control and Synchronization in a Parallel LISP. (Mar. 1994) TR 657 G. Davis, S. Mallat, Z. Zhang. Adaptive Time-Frequency Approximations with Matching Pursuits. (Mar. 1994) TR 658 J. Maddocks, M. Overton. Stability Theory for Dissipatively Perturbed Hamiltonian Systems. (Mar. 1994) TR 659 F. Alizadeh, J.P. Haeberly, M. Overton. A New Primal-Dual Interior-Point Method for Semidefinite Programming. (Mar. 1994) TR 660 J.P. Haeberly, M. Overton. Optimizing Eigenvalues of Symmetric Definite Pencils. (Mar. 1994) TR 661 L. Pavarino, O. Widlund. A Polylogarithmic Bound for an Iterative Substructuring Method for Spectal Elements in Three Dimensions. (Mar. 1994) TR 662 M. Dryja, M. Sarkis, O. Widlung. Multilevel Schwarz Methods for Elliptic Problems with Discontinuous Coefficients in Three Dimensions. (Mar. 1994) TR 663 L. Pavarino, O. Widlund. Iterative Substructuring Methods for Spectral Elements: Problems in Three Dimensions Based on Numerical Quadrature. (May 1994) TR 664 M. Antoniotti. Conceptual and Pragmatic Tools for Design and Control of Manufacturing Systems (Petrinets and Ramadge-Wonham Discrete Event Systems). (Jul. 1993) TR 665 S. Gomory, R. Wallace. Cursor Stereo. (May 1994) TR 666 E. Davis. Branching Continuous Time and the Semantics of Continuous Action. (Jul 1994) TR 667 C. Yao. Representing Control in Parallel Applicative Programming. (Sep 1994) TR 668 M. Ebner, R. Wallace. A Direct--Drive Hand: Design, Modeling and Control. (Jun 1994) TR 669 R. Wallace, J. Selig. Scaling Direct Drive Robots. (Sep 1994) TR 670 J. Choi, J. Sellen, C.K. Yap. Approximate Euclidean Shortest Path in 3-Space. TR 671 M.S. Martins, Schwarz Preconditioners for Elliptic Problems with Discontinuous Coefficients Using Conforming and Non-Conforming Elements.