Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 21 Issue 2, April 1974

Some Binary Derivation Systems
E. E. Sibert, D. Michie
Pages: 175-190
DOI: 10.1145/321812.321813
Previous studies of heuristic search techniques have usually considered situations for which the search space could be represented as a tree, which limits the applicability of the results obtained. Here Kowalski is followed and a more general...

A New Class of Automated Theorem-Proving Algorithms
Ross A. Overbeek
Pages: 191-200
DOI: 10.1145/321812.321814
A procedure is defined for deriving from any statement S an infinite sequence of statements S0, S1, S2,...

The Parallel Evaluation of General Arithmetic Expressions
Richard P. Brent
Pages: 201-206
DOI: 10.1145/321812.321815
It is shown that arithmetic expressions with n ≥ 1 variables and constants; operations of addition, multiplication, and division; and any depth of parenthesis nesting can be evaluated in time 4...

Further Results on the Problem of Finding Minimal Length Programs for Decision Tables
David Pager
Pages: 207-212
DOI: 10.1145/321812.321816
In this paper it is shown that whatever the length function employed, the problem of finding the shortest program for a decision table with two (or more) entries is not recursively solvable (whereas for decision tables with a single entry the...

Grammar Schemata
Armin Gabrielian, Seymour Ginsburg
Pages: 213-226
DOI: 10.1145/321812.321817
A solution is presented for the following problem: Determine a procedure that produces, for each full trio L of context-free languages (more generally, each trio of r.e. languages), a family of context-free (phrase structure) grammars which (a)...

A Modified List Technique Allowing Binary Search
G. Berman, A. W. Collin
Pages: 227-232
DOI: 10.1145/321812.321818
A modification of linked lists is presented which permits searching almost as efficiently as a pure binary search. The method depends on using consecutive memory locations for consecutive list elements whenever possible.

A Document Storage Method Based on Polarized Distance
R. T. Chien, E. A. Mark
Pages: 233-245
DOI: 10.1145/321812.321819
Some elementary mathematical properties of term matching document retrieval systems are developed. These properties are used as a basis for a new file organization technique. Some of the advantages of this new method are (1) the key-to-address...

Efficient Storage and Retrieval by Content and Address of Static Files
Peter Elias
Pages: 246-260
DOI: 10.1145/321812.321820
We consider a set of static files or inventories, each consisting of the same number of entries, each entry a binary word of the same fixed length selected (with replacement) from the set of all binary sequences of that length, and the entries...

Calculating the Eigenvectors of Diagonally Dominant Matrices
M. M. Blevins, G. W. Stewart
Pages: 261-271
DOI: 10.1145/321812.321821
An algorithm is proposed for calculating the eigenvectors of a diagonally dominant matrix all of whose elements are known to high relative accuracy. Eigenvectors corresponding to pathologically close eigenvalues are treated by computing the...

The Solution of a Toeplitz Set of Linear Equations
Shalhav Zohar
Pages: 272-276
DOI: 10.1145/321812.321822
The solution of a set of m linear equations with a non-Hermitian Toeplitz associated matrix is considered. Presently available fast algorithms solve this set with 4m2...

Computing Partitions with Applications to the Knapsack Problem
Ellis Horowitz, Sartaj Sahni
Pages: 277-292
DOI: 10.1145/321812.321823
Given r numbers s1, ···, sr, algorithms are investigated for finding all possible combinations of these numbers which sum to...

Bernstein-Bézier Methods for the Computer-Aided Design of Free-Form Curves and Surfaces
William J. Gordon, Richard F. Riesenfeld
Pages: 293-310
DOI: 10.1145/321812.321824
The mth degree Bernstein polynomial approximation to a function ƒ defined over [0, 1] is ∑m&mgr;=0...

Efficiency of Chebyshev Approximation on Finite Subsets
Charles B. Dunham
Pages: 311-313
DOI: 10.1145/321812.321825
Chebyshev approximation on an interval and closed subsets by a Haar subspace are considered. The closeness of best approximations on subsets to the best approximation on the interval is examined. It is shown that under favorable conditions the...

Comments on a Paper by Gaver
E. Balkovich, W. Chiu, L. Presser, R. Wood
Pages: 314-315
DOI: 10.1145/321812.321826
In a 1967 publication, D. P. Gaver studied a probabilistic model of a multiprogramming computer system. His results have been utilized recently by a number of authors. However, we have observed that Gaver's results contain inconsistencies. These...

Application of the Diffusion Approximation to Queueing Networks I: Equilibrium Queue Distributions
Hisashi Kobayashi
Pages: 316-328
DOI: 10.1145/321812.321827
The practical value of queueing theory in engineering applications such as in computer modeling has been limited, since the interest in mathematical tractability has almost always led to an oversimplified model. The diffusion process...

Synthesis of a Feedback Queueing Discipline for Computer Operation
J. A. Michel, E. G. Coffman, Jr.
Pages: 329-339
DOI: 10.1145/321812.321828
Considerable effort has been invested in devising and analyzing sequencing rules for multiprogrammed or time-shared systems. A much studied discipline of this kind is the so-called system with feedback to lower priority queues. This discipline...

Priority Disciplines in a Loop System
Steven Katz, Alan G. Konheim
Pages: 340-349
DOI: 10.1145/321812.321829
A loop system with N buffered terminals sharing a common time-multiplexed channel is studied. The service discipline is prescribed by a permutation &phgr; = (&phgr;(1), ···, &phgr;(N)) which...

Corrigendum: "Some Topics in Code Optimization"
Christopher Earnest
Page: 350
DOI: 10.1145/321812.323471

Erratum: `` A Local Visual Operator Which Recognizes Edges and Lines''
Manfred H. Hueckel
Page: 350
DOI: 10.1145/321812.321830