**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