Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 16 Issue 4, Oct. 1969

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