**A Formalism for Program Translation**

J. Slansky, M. Finkelstein

Pages: 165-175

DOI: 10.1145/321450.321451

A formalism for representing sequences or networks of program translations and compiler translations is described. The formalism is shown to be capable of (a) concisely and clearly representing the overall tasks of assemblers and preprocessors,...

**Structuring of Parallel Algorithms**

P. A. Gilmore

Pages: 176-192

DOI: 10.1145/321450.321452

The structuring of algorithms suitable for execution on parallel processors is discussed. Two examples of such algorithms are given. The first example exhibits a restructuring of Bellman's dynamic programming technique; the second presents a...

**The Perspective Representation of Functions of Two Variables**

B. Kubert, J. Szabo, S. Giulieri

Pages: 193-204

DOI: 10.1145/321450.321453

A perspective transformation is developed whereby an object in space as viewed from an arbitrary point can be projected into a plane and plotted. Families of curves which can be used to define such an object are discussed and examples are given....

**A Mathematical Model for the Analysis of Contour-Line Data**

Stephen P. Morse

Pages: 205-220

DOI: 10.1145/321450.321454

This paper describes a mathematical model for the study of contour-line data. Formal definitions are given for the various classes of contour lines found on a contour map. The concept of cliff lines is introduced and the properties of both...

**A Bidirectional Simplex Algorithm**

A. Orden, V. Nalbandian

Pages: 221-235

DOI: 10.1145/321450.321455

A simplex type algorithm is presented which deals uniformly with (a) ordinary linear programming problems, (b) problems with upper bounded variables, and (c) problems with convex piecewise linear objective functions, e.g., absolute value terms....

**Mechanical Theorem-Proving by Model Elimination**

Donald W. Loveland

Pages: 236-251

DOI: 10.1145/321450.321456

A proof procedure based on a theorem of Herbrand and utilizing the matching technique of Prawitz is presented. In general, Herbrand-type proof procedures proceed by generating over increasing numbers of candidates for the truth-functionally...

**An Adaptation of the Fast Fourier Transform for Parallel Processing**

Marshall C. Pease

Pages: 252-264

DOI: 10.1145/321450.321457

A modified version of the Fast Fourier Transform is developed and described. This version is well adapted for use in a special-purpose computer designed for the purpose. It is shown that only three operators are needed. One operator replaces...

**Quasi- Newton Methods for Nonlinear Equations**

Frank J. Zeleznik

Pages: 265-271

DOI: 10.1145/321450.321458

A unified derivation is presented of the quasi-Newton methods for solving systems of nonlinear equations. The general algorithm contains, as special cases, all of the previously proposed quasi-Newton methods.

**Common Solutions for n Matrix Equations With Applications**

Gerald L. Morris, Patrick L. Odell

Pages: 272-274

DOI: 10.1145/321450.321459

A solution of n matrix equations is formulated by using existing theory of pseudo inverses of matrices. Techniques for solving recursively such systems, techniques for determining the rank of matrices, techniques for testing...

**Analysis in the Computable Number Field**

Oliver Aberth

Pages: 275-299

DOI: 10.1145/321450.321460

It is well known that real variable analysis is nonconstructive. For example, although it is asserted that every bounded monotone sequence converges to a limit, there is no algorithm for obtaining this limit.
This paper presents a...

**A Remark on Acceptable Sets of Numbers**

Marcel Paul Schutzenberger

Pages: 300-303

DOI: 10.1145/321450.321461

Two negative results concerning the so-called acceptable sets of numbers are extended to the case or arbitrary context-free languages with the help of conventional analytic techniques.

**Generalized Pair Algebra With Applications to Automata Theory**

Raymond T. Yeh

Pages: 304-316

DOI: 10.1145/321450.321462

The concept of a pair algebra is extended so that it can be defined between similar relational systems. It is shown that when the relational systems under consideration are lattices a generalized pair algebra specializes to a pair algebra....

**Decidable and Undecidable Questions About Automata**

J. E. Hopcroft, J. D. Ullman

Pages: 317-324

DOI: 10.1145/321450.321463

Four types of balloon automata (defined by one- or two-way input and deterministic or nondeterministic finite control) and closed classes of balloon automata were previously defined by the authors. A set of closed classes, one for each of the...

**Computational Complexity of One-Tape Turing Machine Computations**

J. Hartmanis

Pages: 325-339

DOI: 10.1145/321450.321464

The quantitative aspects of one-tape Turing machine computations are considered. It is shown, for instance, that there exists a sharp time bound which must be reached for the recognition of nonregular sets of sequences. It is shown that the...

**Corrigendum: `` A Permutation Network''**

Abraham Waksman

Page: 340

DOI: 10.1145/321450.321465