Sign In

Communications of the ACM

Table of Contents


ACM President's Letter: reflections on petitions


An English language question answering system for a large relational database

By typing requests in English, casual users will be able to obtain explicit answers from a large relational database of aircraft flight and maintenance data using a system called PLANES. The design and implementation of thiscontext …

On the complexity of computing the measure of ∪[ai,bi]

The decision tree complexity of computing the measure of the union of n (possibly overlapping) intervals is shown to be &OHgr;(n log n), even if comparisons between linear functions of the interval endpoints are allowed. The existence …

An O(n) algorithm for determining a near-optimal computation order of matrix chain products

This paper discusses the computation of matrix chain products of the form M1 × M22 × ··· × Mn where Mi's are matrices. The order in which the matrices are computed affects the number of operations. A sufficient condition about …

Interpolation search—a log logN search

Interpolation search is a method of retrieving a desired record by key in an ordered file by using the value of the key and the statistical distribution of the keys. It is shown that on the average log logN file accesses areN …

Pseudochaining in hash tables

This paper presents pseudochaining as a new collision-resolution method. Pseudochaining is half way between open addressing and chaining. It owes its name to the fact that link fields are present in each cell of the hash table …

Time, clocks, and the ordering of events in a distributed system

The concept of one event happening before another in a distributed system is examined, and is shown to define a partial ordering of the events. A distributed algorithm is given for synchronizing a system of logical clocks which …

Shallow binding in Lisp 1.5

Shallow binding is a scheme which allows the value of a variable to be accessed in a bounded amount of computation. An elegant model for shallow binding in Lisp 1.5 is presented in which context-switching is an environment tree …

Proving the correctness of heuristically optimized code

A system for proving that programs written in a high level language are correctly translated to a low level language is described. A primary use of the system is as a postoptimization step in code generation. The low level language …

An algorithm for reasoning about equality

A simple technique for reasoning about equalities that is fast and complete for ground formulas with function symbols and equality is presented. A proof of correctness is given as well.

Analysis of the availability of computer systems using computer-aided algebra

Analytical results, related to the availability of a computer system constructed of unreliable processors, are presented in this paper. These results are obtained by using various computer-aided algebraic manipulation techniques …

Technical correspondence: Interlude on signals and semphores revisited. author's response


Technical correspondence: thoughtless programming


Technical correspondence: Interlude on signals and semephores revisited


On LRU stack model suitability


Technical corespondence: Thoughtless programming? author's response


Technical correspondence: on LRU stack model suitability. author's response


Technical correspondence: On B-trees re-examined


Technical correspondence: on B-trees re-examined. author's response


ACM forum