ACM DL

Journal of the ACM (JACM)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of the ACM (JACM), Volume 15 Issue 4, Oct. 1968

Semantic Clustering of Index Terms
S. Kumar
Pages: 493-513
DOI: 10.1145/321479.321480

PATRICIA—Practical Algorithm To Retrieve Information Coded in Alphanumeric
Donald R. Morrison
Pages: 514-534
DOI: 10.1145/321479.321481
PATRICIA is an algorithm which provides a flexible means of storing, indexing, and retrieving information in a large file, which is economical of index space and of reindexing time. It does not require rearrangement of text or index as new...

The Influence of Data Base Characteristics and Usage on Direct Access File Organization
Thomas C. Lowe
Pages: 535-548
DOI: 10.1145/321479.321482
Memory utilization and retrieval time from direct access inverted files are investigated as a function of the data base, the demands on it, and a parameter which the system designer may control. An analysis of the effects of data base...

Feedback Queueing Models for Time-Shared Systems
Edward G. Coffman, Leonard Kleinrock
Pages: 549-576
DOI: 10.1145/321479.321483
Time-shared processing systems (e.g. communication or computer systems) are studied by considering priority disciplines operating in a stochastic queueing environment. Results are obtained for the average time spent in the system, conditioned on...

Queueing Analysis of the IBM 2314 Disk Storage Facility
Joseph Abate, Harvey Dubner, Sheldon B. Weinberg
Pages: 577-589
DOI: 10.1145/321479.321484
In this paper the use of the techniques of queueing theory in analyzing the performance of a mass storage device in a real-time environment is demonstrated; concern is with the tradeoff experienced in practice between throughput of a stochastic...

Scheduling Parallel Computations
Raymond Reiter
Pages: 590-599
DOI: 10.1145/321479.321485
A model for parallel computations is given as a directed graph in which nodes represent elementary operations, and branches, data channels. The problem considered is the determination of an admissible schedule for such a computation; i.e. for...

A Method for Obtaining Skeletons Using a Quasi-Euclidean Distance
U. Montanari
Pages: 600-624
DOI: 10.1145/321479.321486
The problem of obtaining the skeleton of a digitized figure is reduced to an optimal policy problem. A hierarchy of methods of defining the skeleton is proposed; in the more complicated ones, the skeleton is relatively invariant under rotation....

A Formal Deductive Problem-Solving System
J. R. Quinlan, E. B. Hunt
Pages: 625-646
DOI: 10.1145/321479.321487
A formalism is defined in which solutions to theorem-proving and similar problems take the form of a sequence of transformations of states into other states. The data used to solve a problem then consists of a set of rewriting rules which...

Indexed Grammars—An Extension of Context-Free Grammars
Alfred V. Aho
Pages: 647-671
DOI: 10.1145/321479.321488
A new type of grammar for generating formal languages, called an indexed grammar, is presented. An indexed grammar is an extension of a context-free grammar, and the class of languages generated by indexed grammars has closure properties and...

On the Independence of Real-Time Definability and Certain Structural Properties of Context-Free Languages
Arnold L. Rosenberg
Pages: 672-679
DOI: 10.1145/321479.321489
An operator precedence language which is not real-time definable by any multitple Turing machine is constructed. This strengthens previous results about the existence of unambiguous context-free languages (CFL's) which are not real-time...

Degrees of Unsolvability in Formal Grammars
Dennis F. Cudia, Wilson E. Singletary
Pages: 680-692
DOI: 10.1145/321479.321490
The following theorem is a refinement of an unsolvability result due to E. Post: For any recursively enumerable degree D of recursive unsolvability there is a recursive class of sequences (of the same length)...

Representation of Events in the von Neumann Cellular Model
Amar Mukhopadhyay
Pages: 693-705
DOI: 10.1145/321479.321491
In this paper it is proved that regular events are representable in the cellular model proposed by John von Neumann, and a construction of a finite-state cellular automaton is presented. The procedure was motivated primarily by McNaughton's...

A Theorem for the Stability of General Predictor-Corrector Methods for the Solution of Systems of Differential Equations
Abbas I. Abdel Karim
Pages: 706-711
DOI: 10.1145/321479.321492
Practically, predictor-corrector methods for the solution of differential equations are widely used. In these numerical methods, the question of stability is most important. For a single differential equation Crane and Lambert (1962) studies the...

Generalized Multistep Methods in Satellite Orbit Computation
James Dyer
Pages: 712-719
DOI: 10.1145/321479.321493
The theory of generalized multistep methods using an off-grid point is extended to the special second-order equation y″ = f(x, y). New high-order methods for solving this...

A Correction Concerning Resolution
Peter B. Andrews
Page: 720
DOI: 10.1145/321479.321494