**Sufficient Conditions for the Success of GPS**

George W. Ernst

Pages: 517-533

DOI: 10.1145/321541.321542

A formal model of a problem is developed and its relationship to the General Problem Solver (GPS) is discussed. Before GPS can work on a problem it must be given differences, a difference-ordering, and a table of connections, in addition to the...

**Continuous Skeletons from Digitized Images**

Ugo Montanari

Pages: 534-549

DOI: 10.1145/321541.321543

An algorithm for the determination of the skeleton of a polygonal figure is presented. The propagation of the figure contour is simulated analytically. All skeleton branch points are obtained, in an order which depends on their distance from the...

**Halting Stack Automata**

J. D. Ullman

Pages: 550-563

DOI: 10.1145/321541.321544

It is shown that every two-way (deterministic) stack automaton language is accepted by a two-way (deterministic) stack automaton which for each input has a bound on the length of a valid computation. As a consequence, two-way deterministic stack...

**A Cycle Generation Algorithm for Finite Undirected Linear Graphs**

Norman E. Gibbs

Pages: 564-568

DOI: 10.1145/321541.321545

When the algorithms of J. T. Welch, Jr. were implemented it was discovered that they did not perform as described. The generation of all cycles from a basis is faulty. The generation of the basis is apparently correct. A modified version of...

**File Organization: On the Selection of Random Access Index Points for Sequential Files**

S. P. Ghosh, M. E. Senko

Pages: 569-579

DOI: 10.1145/321541.321546

The construction of a hierarchy of indexes (the indexed sequential access method) is one means of providing rapid random access to sequential files. An examination is made of the consequences of partially or completely replacing one or more...

**Nonnormality and Jordan Condition Numbers of Matrices**

Georghios Loizou

Pages: 580-584

DOI: 10.1145/321541.321547

A lower bound for the departure from normality of an n X n matrix A is given. Furthermore, various inequalities are obtained for certain condition numbers associated with the reduction of...

**Finite Difference Scheme for a Third Boundary Value Problem**

A. Zafarullah

Pages: 585-591

DOI: 10.1145/321541.321548

A finite difference scheme for a linear, second-order third boundary value problem in ordinary differential equations is described. The discretization error is found to be O(h4).

**Toeplitz Matrix Inversion: The Algorithm of W. F. Trench**

Shalhav Zohar

Pages: 592-601

DOI: 10.1145/321541.321549

The algorithm of W. F. Trench for the inversion of Toeplitz matrices is presented with a detailed proof for the case of non-Hermitian matrices. The only condition necessary to insure the validity of the algorithm is that all principal minors be...

**Analysis and Optimization of Disk Storage Devices for Time-Sharing Systems**

H. Frank

Pages: 602-620

DOI: 10.1145/321541.321550

A major limitation for time-sharing systems is the time delay encountered in transferring records between central “fast” memory and peripheral memory devices. In this paper the transfer characteristics of disk storage devices are...

**Random Sets in Subrecursive Hierarchies**

Robert A. Di Paola

Pages: 621-630

DOI: 10.1145/321541.321551

Successive modifications of Church's definition of a random sequence are considered in terms of their relative position in the Ritchie hierarchy of Kalmar elementary functions. A general result is derived governing the classification of Church...

**Computer Time-Sharing Queues with Priorities**

Igal Adiri

Pages: 631-645

DOI: 10.1145/321541.321552

The paper deals with computer time-sharing disciplines in which external priorities are introduced. For a computer system under a time-sharing discipline, the following priority disciplines are discussed: (a) head-of-the-line; (b) preemptive...

**Erratum: `` Analysis of a Drum Input/Output Queue Under Scheduled Operation in a Paged Computer System''**

E. G. Coffman, Jr.

Page: 646

DOI: 10.1145/321541.321553

**Erratum: “Automorphisms of polyadic automata”**

Jerzy W. Grzymala-Busse

Page: 646

DOI: 10.1145/321541.331603

**Erratum: “Mechanical theorem-proving by model elimination”**

Donald W. Loveland

Page: 646

DOI: 10.1145/321541.331604