Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 14 Issue 3, July 1967

Probability Models for Multiprogramming Computer Systems
D. P. Gaver, Jr.
Pages: 423-438
DOI: 10.1145/321406.321407
A probabilistic model is developed for a multiprogramming computer configuration, i.e., one in which several program segments are simultaneously in main memory (core). The model relates speed and number of input-output devices, core size, and...

Production and Stabilization of Real-Time Task Schedules
G. K. Manacher
Pages: 439-465
DOI: 10.1145/321406.321408
A model for multiprocessor control is considered in which jobs are broken into various pieces, called tasks. Tasks are executed by single processing units. In this paper the structure controlling the assignment of tasks to...

Roots of Star Events
J. A. Brzozowski
Pages: 466-477
DOI: 10.1145/321406.321409
A regular event W is a star event if there exists another event V such that W = V*. In that case, V is called a root of W....

Some Bounds on the Storage Requirements of Sequential Machines and Turing Machines
Richard M. Karp
Pages: 478-489
DOI: 10.1145/321406.321410
Any sequential machine M represents a function fM from input sequences to output symbols. A function f is representable if some finite-state sequential...

Parenthesis Grammars
Robert McNaughton
Pages: 490-500
DOI: 10.1145/321406.321411
A decision procedure is given which determines whether the languages defined by two parenthesis grammars are equal.

Matrix Equations and Normal Forms for Context-Free Grammars
Daniel J. Rosenkrantz
Pages: 501-507
DOI: 10.1145/321406.321412
The relationship between the set of productions of a context-free grammar and the corresponding set of defining equations is first pointed out. The closure operation on a matrix of strings is defined and this concept is used to formalize the...

Analysis of Factorial Experiments Using Generalized Matrix Operations
I. Oliver
Pages: 508-519
DOI: 10.1145/321406.321413
The computer analysis of factorial experiments is discussed in terms of a new generalized matrix notation which highlights the special properties of factorial designs. A method of calculating an analysis of a variance suitable for programming as...

A Method for Constructing Circuit Codes
Victor Klee
Pages: 520-528
DOI: 10.1145/321406.321414
A d-dimensional circuit code of spread s (also called SIBs, code or circuit code of minimum distance s) is a simple circuit Q in the graph...

An Algorithm for Generating Stable Feedback Shift Registers of Order n
Frederic J. Mowle
Pages: 529-542
DOI: 10.1145/321406.321415
It is shown in this paper that the stable feedback shift registers, when classified according to Hamming weight (the number of fundamental product terms in expanded sum of products form), are binomially distributed, i.e., are...

On the Compatibility of a Given Solution With the Data of a Linear System
J. L. Rigal, J. Gaches
Pages: 543-548
DOI: 10.1145/321406.321416
Some new theorems generalizing a result of Oettli and Prager are applied to the a posteriori analysis of the compatibility of a computed solution to the uncertain data of a linear system (or of a polynomial equation).

Numerical Solution of Parabolic Partial Differential Equations With Two-Point Boundary Conditions by Use of the Method of Lines
J. S. Hicks, J. Wei
Pages: 549-562
DOI: 10.1145/321406.321417
The Method of Lines, a numerical technique commonly used for solving partial differential equations on analog computers, is used to attain digital computer solutions of such equations. An extensive theoretical development is presented that...

The Organization of Computations for Uniform Recurrence Equations
Richard M. Karp, Raymond E. Miller, Shmuel Winograd
Pages: 563-590
DOI: 10.1145/321406.321418
A set equations in the quantities ai(p), where i = 1, 2, · · ·, m and p ranges over a set R of...

Application of Parallel Processing to Numerical Weather Prediction
A. B. Carroll, R. T. Wetherald
Pages: 591-614
DOI: 10.1145/321406.321419
The purpose of this study is to illustrate the application of a parallel network processing computing system to an important class of problems in hydrodynamics. The computing system selected for this study is a prototype of the SOLOMON parallel...