July 1978 - Vol. 21 No. 7
Features
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…
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…
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…
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…
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…
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…
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…
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…
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…
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…
