Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 15 Issue 2, April 1968

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