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