Sign In

Communications of the ACM

Table of Contents


ACM President's Letter: where would ACM be without volunteers?


An algorithm using symbolic techniques for the Bel-Petrov classification of gravitational fields

In this note, an algorithm is presented for the symbolic calculation of certain algebraic invariants of the Weyl tensor which permits the determination of the Bel-Petrov types of a gravitational field. This algorithm, although …

Hybrid simulation models of computer systems

This paper describes the structure and operation of a hybrid simulation model in which both discrete-event simulation and analytic techniques are combined to produce efficient yet accurate system models. In an example based on …

A practical interprocedural data flow analysis algorithm

A new interprocedural data flow analysis algorithm is presented and analyzed. The algorithm associates with each procedure in a program information about which variables may be modified, which may be used, and which are possibly …

A model for verification of data security in operating systems

Program verification applied to kernel architectures forms a promising method for providing uncircumventably secure, shared computer systems. A precise definition of data security is developed here in terms of a general model …

Generalized working sets for segment reference strings

The working-set concept is extended for programs that reference segments of different sizes. The generalized working-set policy (GWS) keeps as its resident set those segments whose retention costs do not exceed their retrieval …

A controlled experiment in program testing and code walkthroughs/inspections

This paper describes an experiment in program testing, employing 59 highly experienced data processing professionals using seven methods to test a small PL/I program. The results show that the popular code walkthrough/inspection …

Right brother trees

Insertion and deletion algorithms are provided for the class of right (or one-sided) brother trees which have O (log n) performance. The importance of these results stems from the close relationship of right brother trees to2 …

Event manipulation for discrete simulations requiring large numbers of events

The event-manipulation system presented here consists of two major parts. The first part addresses the familiar problem of event scheduling efficiency when the number of scheduled events grows large. The second part deals with …

A note on virtual memory indexes

In [4] Maruyama and Smith analyzed design alternatives for virtual memory indexes. The indexes investigated were those modeled on the structure of VSAM [5] which are closely related to B-trees [1]. Maruyama and Smith presented …

Real time plotting of approximate contour maps


Simulations of dynamic sequential search algorithms

In [3], R.L. Rivest presents a set of methods for dynamically reordering a sequential list containing N records in order to increase search efficiency. The method Ai (for i between 1 and N) performs the following operation each …

ACM forum