**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.