Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 20 Issue 1, Jan. 1973

Upper Bounds for the Total Path Length of Binary Trees
C. K. Wong, J. Nievergelt
Pages: 1-6
DOI: 10.1145/321738.321739
Two upper bounds for the total path length of binary trees are obtained. One is for node-trees, and bounds the internal (or root-to-node) path length; the other is for leaf-trees, and bounds the external (or root-to-leaf) path length. These...

A-Stable Composite Multistep Methods
Harry M. Sloate, Theodore A. Bickart
Pages: 7-26
DOI: 10.1145/321738.321740
Consider the set of multistep formulas ∑l-1jmn-k...

An Efficient Parallel Algorithm for the Solution of a Tridiagonal Linear System of Equations
Harold S. Stone
Pages: 27-38
DOI: 10.1145/321738.321741
Tridiagonal linear systems of equations can be solved on conventional serial machines in a time proportional to N, where N is the number of equations. The conventional algorithms do not lend themselves directly...

A Combinatorial Problem Related to Interleaved Memory Systems
G. J. Burnett, E. G. Coffman, Jr.
Pages: 39-45
DOI: 10.1145/321738.321742
A combinatorial problem arising from the analysis of a model of interleaved memory systems is studied. The performance measure whose calculation defines this problem is based on the distribution of the number of modules in operation during a...

Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment
C. L. Liu, James W. Layland
Pages: 46-61
DOI: 10.1145/321738.321743
The problem of multiprogram scheduling on a single processor is studied from the viewpoint of the characteristics peculiar to the program functions that need guaranteed service. It is shown that an optimum fixed priority scheduler possesses an...

Mathematical Models for Automatic Line Detection
Arnold K. Griffith
Pages: 62-80
DOI: 10.1145/321738.321744
A particular decision-theoretic approach to the problem of detecting straight edges and lines in pictures is discussed. A model is proposed of the appearance of scenes consisting of prismatic solids, taking into account blurring, noise, and...

Arcs and Curves in Digital Pictures
Azriel Rosenfeld
Pages: 81-87
DOI: 10.1145/321738.321745
Characterizations of digital “simple arcs” and “simple closed curves” are given. In particular, it is shown that the following are equivalent for sets S having more than four points: (1)...

Efficient Exercising of Switching Elements in Nets of Identical Gates
Donald L. Richards
Pages: 88-111
DOI: 10.1145/321738.321746
The problem of finding a minimum number of patterns to exercise the logic elements of a combinational switching net is investigated. Throughout, the word “testing” refers to exercising of this kind; or, equivalently, to fault...

The Solvability of the Decision Problem for Classes of Proper Formulas and Related Results
Robert A. Di Paola
Pages: 112-126
DOI: 10.1145/321738.321747
In connection with the development of an actual question-answering system, the Relational Data File of The Rand Corporation, a class of formulas of the predicate calculus, the definite formulas of Kuhns, was proposed as the class of symbolic...

Z-Resolution: Theorem-Proving with Compiled Axioms
John K. Dixon
Pages: 127-147
DOI: 10.1145/321738.321748
An improved procedure for resolution theorem proving, called Z-resolution, is described. The basic idea of Z-resolution is to “compile” some of the axioms in a deductive problem. This means to automatically transform the selected...

A Class of Merging Algorithms
F. K. Hwang, D. N. Deutsch
Pages: 148-159
DOI: 10.1145/321738.321749
Suppose we are given two disjoint linearly ordered subsets A and B of a linearly ordered set C, say A = {a1 <...

Tree-Manipulating Systems and Church-Rosser Theorems
Barry K. Rosen
Pages: 160-187
DOI: 10.1145/321738.321750
Subtree replacement systems form a broad class of tree-manipulating systems. Systems with the “Church-Rosser property” are appropriate for evaluation or translation processes: the end result of a complete sequence of applications of...

Errata: “An axiomatic approach to code optimization for Expressions”
James C. Beatty
Page: 188
DOI: 10.1145/321738.321751