An algorithm is described that will recognize, and fully analyze, strings of unbounded length, using the rewriting rules of any context-free grammar. It uses a finite random access store, three pushdown tapes, and a counter. It imposes no restrictions on the grammar defined by the rewriting rules, excepting only that it be a context-free phrase structure grammar. The analysis printed out is a linearized form of the structural description tree (or trees, in an ambiguous case) of the input string. A proof that the analyzer will always stop in a finite time is provided. The upper bound on the running time increases exponentially with input string length.

An error analysis of direct methods (i.e., Gaussian elimination or triangular factorization) of solving simultaneous linear algebraic equations is performed in the backward mode, in which the computational errors are expressed as perturbations on the data. Bounds are found for perturbations on the coefficients of the equations, leaving the right-hand sides unchanged. These bounds can be evaluated concurrently with the computation itself, with only a small increase in computing effort. Because they use information obtained during the solution process, these bounds avoid exaggerating the magnitude of the error, and so are also useful as error estimates.

Recent developments in computer design and error analysis have made feasible the use of variable precision arithmetic and the preparation of programs that automatically determine their own precision requirements. Such programs enable the user to specify the accuracy he wants, and yield answers guaranteed to lie within the bounds prescribed. A class of such programs, called “contracting error programs,” is defined in which the precision is determined by prescribing error bounds on the data. A variant of interval arithmetic is defined which enables a limited class of algorithms to be programmed as contracting error programs. A contracting error program for the solution of simultaneous linear equations is described, demonstrating the application of the idea to a wider class of problems.

The Jacobi method for diagonalizing symmetric matrices requires, in its usual form, that the matrix be held in a random-access store. Two variations of the method are described which make it suitable for matrices held on a serial-access store, such as a magnetic tape. Techniques are described for applying these methods to computers with from one to six magnetic-tape units.