**A Backtrack Procedure for Isomorphism of Directed Graphs**

A. T. Berztiss

Pages: 365-377

DOI: 10.1145/321765.321766

A reasonably efficient procedure for testing pairs of directed graphs for isomorphism is important in information retrieval and other application fields in which structured data have to be matched. One such procedure, a backtrack procedure based...

**A Path Entropy Function for Rooted Trees**

Christopher D. Green

Pages: 378-384

DOI: 10.1145/321765.321767

The class of rooted trees or arborescences used for modeling hierarchical classification and indexing procedures is considered. An entropy function measuring the complexity of the paths from the root to the terminal vertices is defined. Upper...

**A Note on Dijkstra's Shortest Path Algorithm**

Donald B. Johnson

Pages: 385-388

DOI: 10.1145/321765.321768

An assertion that Dijkstra's algorithm for shortest paths (adapted to allow arcs of negative weight) runs in O(n3) steps is disproved by showing a set of networks which take...

**A Note on Yen's Algorithm for Finding the Length of All Shortest Paths in N-Node Nonnegative-Distance Networks**

Thomas A. Williams, Gregory P. White

Pages: 389-390

DOI: 10.1145/321765.321769

An error in Yen's algorithm is pointed out, and an alternative is offered which will produce correct results.

**Reply to Williams and White's Note**

Jin Y. Yen

Page: 390

DOI: 10.1145/321765.321770

**On Local Roundoff Errors in Floating-Point Arithmetic**

Toyohisa Kaneko, Bede Liu

Pages: 391-398

DOI: 10.1145/321765.321771

A bound on the relative error in floating-point addition using a single-precision accumulator with guard digits is derived. It is shown that even with a single guard digit, the accuracy can be almost as good as that using a double-precision...

**Toward Abstract Numerical Analysis**

Webb Miller

Pages: 399-408

DOI: 10.1145/321765.321772

This paper deals with a technique for proving that certain problems of numerical analysis are numerically unsolvable. So that only methods which are natural for dealing with analytic problems may be presented, notions from recursive function...

**An Algorithm for the Inversion of Block Matrices of Toeplitz Form**

G. A. Watson

Pages: 409-415

DOI: 10.1145/321765.321773

An algorithm of W. F. Trench is generalized to apply to the inversion of block matrices of Toeplitz form.

**Cyclic Queues with Bulk Arrivals**

Igal Adiri

Pages: 416-428

DOI: 10.1145/321765.321774

This paper deals with a single-server station (a computer) where each customer's demand comprises an independent random number of jobs (programs). Under certain assumptions, two cyclic disciplines are mathematically analyzed: (a) continuous job...

**Placement of Records on a Secondary Storage Device to Minimize Access Time**

David D. Grossman, Harvey F. Silverman

Pages: 429-438

DOI: 10.1145/321765.321775

The problem considered is how to place records on a secondary storage device to minimize average retrieval time, based on a knowledge of the probability for accessing the records. Theorems are presented for two limiting cases. A numerical...

**Some Results in Computational Topology**

G. Tourlakis, J. Mylopoulos

Pages: 439-455

DOI: 10.1145/321765.321776

It is the object of this paper to study the topological properties of finite graphs that can be embedded in the n-dimensional integral lattice (denoted Nn). The basic notion of deletability...

**Generalized Feedback Shift Register Pseudorandom Number Algorithm**

T. G. Lewis, W. H. Payne

Pages: 456-468

DOI: 10.1145/321765.321777

The generalized feedback shift register pseudorandom number algorithm has several advantages over all other pseudorandom number generators. These advantages are: (1) it produces multidimensional pseudorandom numbers; (2) it has an arbitrarily...

**An Asymptotically Random Tausworthe Sequence**

J. P. R. Tootill, W. D. Robinson, D. J. Eagle

Pages: 469-481

DOI: 10.1145/321765.321778

The theoretical limitations on the orders of equidistribution attainable by Tausworthe sequences are derived from first principles and are stated in the form of a criterion to be achieved. A second criterion, extending these limitations to...

**Efficient Ordering of Set Expressions for Symbolic Expansion**

R. B. Worrell, B. L. Hulme

Pages: 482-488

DOI: 10.1145/321765.321779

This paper gives an algorithm for efficiently ordering the terms and factors of a set (or Boolean) expression so that the work required for the symbolic expansion of the expression according to the distributive law is minimized. Formulas are...

**Decidable Properties of Monadic Functional Schemas**

Edward Ashcroft, Zohar Manna, Amir Pnueli

Pages: 489-499

DOI: 10.1145/321765.321780

A class of (monadic) functional schemas which properly includes “Ianov” flowchart schemas is defined. It is shown that the termination, divergence, and freedom problems for functional schemas are decidable. Although it is possible to...

**Loopless Algorithms for Generating Permutations, Combinations, and Other Combinatorial Configurations**

Gideon Ehrlich

Pages: 500-513

DOI: 10.1145/321765.321781

The purpose of this work is to find a method for building loopless algorithms for listing combinatorial items, like partitions, permutations, combinations. Gray code, etc. Algorithms for the above sequence are detailed in full.

**Parallel Program Schemata and Maximal Parallelism I. Fundamental Results**

Robert M. Keller

Pages: 514-537

DOI: 10.1145/321765.321782

The phenomenon of maximal parallelism is investigated in the framework of a class of parallel program schemata. Part I presents the basic properties of this model. Two types of equivalence relation on computations are presented, to each of which...

**Erratum: “An axiomatic approach to code optimization for expressions”**

James C. Beatty

Page: 538

DOI: 10.1145/321765.321783