Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 13 Issue 1, Jan. 1966

Program and Addressing Structure in a Time-Sharing Environment
B. W. Arden, B. A. Galler, T. C. O'Brien, F. H. Westervelt
Pages: 1-16
DOI: 10.1145/321312.321313
The problem studied is the effect of a time-sharing environment on the structure of programs and on the addressing strategies which may be employed in the hardware. An account is given of some very recent developments toward reduction in the...

ALPHA—An Automatic Programming System of High Efficiency
A. P. Yershov
Pages: 17-24
DOI: 10.1145/321312.321314
An automatic programming system for the M-20 computer at the Computing Centre of the Siberian Division of the USSR Academy of Sciences has been developed. The translator is a compiler which accepts source programs written in ALPHA language...

Large Parallel Computers
J. Schwartz
Pages: 25-32
DOI: 10.1145/321312.321315
Various classes of machines incorporating parallelism are considered. A general class of large-scale multiprocessors is outlined, and some problems of hardware and software implementation for computers of this class are discussed....

Realization of Input-Output Relations by Sequential Machines
A. Gill
Pages: 33-42
DOI: 10.1145/321312.321316
This paper deals with the synthesis of sequential machines (without a distinguished initial state) which satisfies a specified list of input sequences and corresponding output sequences. Readily testable necessary and sufficient conditions are...

Index Register Allocation
L. P. Horwitz, R. M. Karp, R. E. Miller, S. Winograd
Pages: 43-61
DOI: 10.1145/321312.321317
A procedure for index register allocation is described. The rules of this procedure are shown to yield an optimal allocation for “straight line” programs....

Ambiguity in context free languages
Seymour Ginsburg, Joseph Ullian
Pages: 62-89
DOI: 10.1145/321312.321318
Four principal results about ambiguity in languages (i.e., context free languages) are proved. It is first shown that the problem of determining whether an arbitrary language is inherently ambiguous is recursively unsolvable. Then a decision...

On the Syntax of Algorithmic Languages
Philip Gilbert
Pages: 90-107
DOI: 10.1145/321312.321319
The analytic grammar (a model which provides a rigorous description of syntactic analysis) is presented, and some of its fundamental properties are shown. Various submodels are discussed and equivalences among these are...

Convergence Problems in Maehly's Second Method: Part II
Charles B. Dunham
Pages: 108-113
DOI: 10.1145/321312.321320
Maehly's second method is a general algorithm for finding the best Chebyshev approximation to a continuous function on a finite interval. This paper examines the convergence properties of Maehly's second method, a modification, and the more...

Pseudo-Runge-Kutta Methods Involving Two Points
George D. Byrne, Robert J. Lambert
Pages: 114-123
DOI: 10.1145/321312.321321
A third order two step method and a fourth order two step method for the numerical solution of the vector initial value problem dy ÷ dx=F(y), y(a) = n can be defined by making evaluations...

A Procedure for Nonlinear Least Squares Refinement in Adverse Practical Conditions
R. N. Maddison
Pages: 124-134
DOI: 10.1145/321312.321322
An iterative method is described for computing optimum values of a set of parameters for the best agreement in a least squares between a given set of (experimental) values and corresponding calculated (theoretical) values where these may be...

A Method for the Solution of Roots of a Nonlinear Equation and for Solution of the General Eigenvalue Problem
C. A. Barlow, Jr., E. L. Jones
Pages: 135-142
DOI: 10.1145/321312.321323
A simple and yet powerful method of solving two of the more common numerical problems is heuristically derived and briefly discussed. The method makes possible the efficient solution of the zeros of a complex function, either transcendental or...

A Note on Linear Extrapolation of Multivariable Functions by the Monte Carlo Method
Takao Tsuda, Hiroshi Matsumoto
Pages: 143-150
DOI: 10.1145/321312.321324
The feasibility of Monte Carlo linear extrapolation of multivariable functions is discussed. The method considered is a modified version of the Monte Carlo method for linear interpolation. An effective truncation procedure is introduced, which...

On Asymptotic Estimates in Switching and Automata Theory
Michael A. Harrison
Pages: 151-157
DOI: 10.1145/321312.321325
Formulas and algorithms have recently been given for calculating the number of symmetry types of functions, networks and automata under various transformation groups. In almost all cases, the computations involved are quite difficult and require...

Two Complete Axiom Systems for the Algebra of Regular Events
Arto Salomaa
Pages: 158-169
DOI: 10.1145/321312.321326
The theory of finite automata is closely linked with the theory of Kleene's regular expressions. In this paper, two formal systems for the algebraic transformation of regular expressions are developed. Both systems are consistent and complete;...

Group-Type Automata
Charles A. Trauth, Jr.
Pages: 170-175
DOI: 10.1145/321312.321327
The purpose is to investigate the input structure of automata which have a group-like character. The class of perfect automata investigated by Fleck in [2] and Weeg in [6] is a proper subclass of those considered here....