January 1983 Table of Contents | Communications of the ACM

advertisement

Home → Magazine Archive → January 1983 (Vol. 26, No. 1)

Table of Contents

The first quarter century

Robert L. Ashenhurst

Pages 1-3

Sequential formula translation

The syntax of an algorithmic language such as ALGOL is conveniently described as a sequence of states indicated by an element called cellar. Transitions are controlled by admissible state-symbol pairs which may be represented …

K. Samelson, F. L. Bauer

Pages 9-13

A syntax directed compiler for ALGOL 60

Although one generally thinks of a compiler as a program for a computer which translates some object language into a target language, in fact this program also serves to define the object language in terms of the target language …

Edgar T. Irons

Pages 14-16

Use of tree structures for processing files

In data processing problems, files are frequently used which must both be searched and altered. Binary search techniques are efficient for searching large files, but the associated file organization is not readily adapted tos …

Edward H. Sussenguth

Pages 17-20

Solution of a problem in concurrent programming control

A number of mainly independent sequential-cyclic processes with restricted means of communication with each other can be made in such a way that at any moment one and only one of them is engaged in the “critical section” of its …

E. W. Dijkstra

Pages 21-22

ELIZA — a computer program for the study of natural language communication between man and machine

ELIZA is a program operating within the MAC time-sharing system of MIT which makes certain kinds of natural language conversation between man and computer possible. Input sentences are analyzed on the basis of decomposition rules …

Joseph Weizenbaum

Pages 23-28

Programming semantics for multiprogrammed computations

The semantics are defined for a number of meta-instructions which perform operations essential to the writing of programs in multiprogrammed computer systems. These meta-instructions relate to parallel processing, protection …

Jack B. Dennis, Earl C. Van Horn

Pages 29-35

An improved hash code for scatter storage

Introduced is a hash coding method based on fixed-point division rather than multiplication or logical operations. This new method allows the hash table to have almost any length. Also a new method of handling collisions is discussed …

W. D. Maurer

Pages 36-38

Scatter storage techniques

Robert Morris

Pages 39-42

The working set model for program behavior

Probably the most basic reason behind the absence of a general treatment of resource allocation in modern computer systems is an adequate model for program behavior. In this paper a new model, the “working set model,” is developed …

Peter J. Denning

Pages 43-48

The structure of “THE”-multiprogramming system

A multiprogramming system is described in which all activities are divided over a number of sequential processes. These sequential processes are placed at various hierarchical levels, in each of which one or more independent …

Edsger W. Dijkstra

Pages 49-52

An axiomatic basis for computer programming

In this paper an attempt is made to explore the logical foundations of computer programming by use of techniques which were first applied in the study of geometry and have later been extended to other branches of mathematics. …

C. A. R. Hoare

Pages 53-56

An efficient context-free parsing algorithm

A parsing algorithm which seems to be the most efficient general context-free algorithm known is described. It is similar to both Knuth's LR(k) algorithm and the familiar top-down algorithm. It has a time bound proportional to …

Jay Earley

Pages 57-61

The quadratic quotient method: a hash code eliminating secondary clustering

Secondary clustering as a cause of hash code inefficiency is discussed, and a new hashing method based on its elimination is presented. Comparisons with previous methods are made both analytically and empirically.

James R. Bell

Pages 62-63

A relational model of data for large shared data banks

Future users of large data banks must be protected from having to know how the data is organized in the machine (the internal representation). A prompting service which supplies such information is not a satisfactory solution …

E. F. Codd

Pages 64-69

Program development by stepwise refinement

The creative activity of programming—to be distinguished from coding—is usually taught by examples serving to exhibit certain techniques. It is here considered as a sequence of design decisions concerning the decomposition of …

Niklaus Wirth

Pages 70-74

A technique for software module specification with examples

This paper presents an approach to writing specifications for parts of software systems. The main goal is to provide specifications sufficiently precise and complete that other pieces of software can be written to interact with …

D. L. Parnas

Pages 75-78

A statistical study of the accuracy of floating point number systems

This paper presents the statistical results of tests of the accuracy of certain arithmetic systems in evaluating sums, products and inner products, and analytic error estimates for some of the computations. The arithmetic systems …

H. Kuki, W. J. Cody

Pages 79-83

The UNIX time-sharing system

UNIX is a general-purpose, multi-user, interactive operating system for the Digital Equipment Corporation PDP-11/40 and 11/45 computers. It offers a number of features seldom found even in a larger operating systems, including …

Dennis M. Ritchie, Ken Thompson

Pages 84-89

Ethernet: distributed packet switching for local computer networks

Ethernet is a branching broadcast communication system for carrying digital data packets among locally distributed computing stations. The packet transport mechanism provided by Ethernet has been used to build systems which can …

Robert M. Metcalfe, David R. Boggs

Pages 90-95

A method for obtaining digital signatures and public-key cryptosystems

An encryption method is presented with the novel property that publicly revealing an encryption key does not thereby reveal the corresponding decryption key. This has two important consequences: Couriers or other secure means …

R. L. Rivest, A. Shamir, L. Adleman

Pages 96-99

Communicating sequential processes

This paper suggests that input and output are basic primitives of programming and that parallel composition of communicating sequential processes is a fundamental program structuring method. When combined with a development of …

C. A. R. Hoare

Pages 100-106