Robert L. Ashenhurst
Pages 1-3
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
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
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 to
s …
Edward H. Sussenguth
Pages 17-20
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
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
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
Robert Morris
Pages 39-42
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
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
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
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
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
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
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
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
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 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
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
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
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
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
