Communications of the ACM

ACM President's Letter: reflections on petitions

Daniel D. McCracken
Page 525

---

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 … David L. Waltz
Pages 526-539

---

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 … Francis Y. Chin
Pages 544-549

---

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 … Constantine Halatsis, George Philokyprou
Pages 554-557

---

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 … Leslie Lamport
Pages 558-565

---

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 … Henry G. Baker
Pages 565-569

---

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 … Hanan Samet
Pages 570-582

---

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. Robert E. Shostak
Pages 583-585

---

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 … Rahul Chattergy, Udo W. Pooch
Pages 586-591

---

Technical correspondence: thoughtless programming

Duane Sand
Pages 592-593

---

Technical correspondence: Interlude on signals and semephores revisited

Arne Maus
Page 592

---

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

Niklaus Wirth
Page 592

---

On LRU stack model suitability

Percy Tzelnic
Page 593

---

Technical corespondence: Thoughtless programming? author's response

M. A. Auslander
Page 593

---

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

Rollins Turner
Page 594

---

Technical correspondence: On B-trees re-examined

Lawrence Snyder
Page 594

---

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

Gerald Held, Michael Stonebraker
Page 594

---

ACM forum

Robert L. Ashenhurst
Page 601

---

On the complexity of computing the measure of ∪[a_i,b_i]

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 … Michael L. Fredman, Bruce Weide
Pages 540-544

---

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 … Yehoshua Perl, Alon Itai, Haim Avni
Pages 550-553

---