**Analysis of Two Time-Sharing Algorithms Designed for Limited Swapping**

E. G. Coffman, Jr.

Pages: 341-353

DOI: 10.1145/321466.321467

The necessity for swapping in the operation of modern time-sharing systems constitutes the major reason for the latter's inefficiency compared to batch-processing systems. Time-sharing algorithms are discussed which are designed primarily for...

**A Procedure for Detecting Intersections of Three-Dimensional Objects**

Paul G. Comba

Pages: 354-366

DOI: 10.1145/321466.321468

As a step toward the solution of the placement problem in engineering design, a procedure has been developed for detecting intersections of convex regions in 3-space by means of a pseudocharacteristic function. The mathematical techniques...

**Resolution With Merging**

Peter B. Andrews

Pages: 367-381

DOI: 10.1145/321466.321469

A refinement of the resolution method for mechanical theorem proving is presented. A resolvent C of clauses A and B is called a merge if literals from A and...

**On the Recognition of Primes by Automata**

J. Hartmanis, H. Shank

Pages: 382-389

DOI: 10.1145/321466.321470

A study of the problem of recognizing the set of primes by automata is presented. A simple algebraic condition is derived which shows that neither the set of primes nor any infinite subset of the set of primes can be accepted by a pushdown or...

**A Modification of Nordsieck's Method Using an ``Off-Step'' Point**

J. J. Kohfeld, G. T. Thompson

Pages: 390-401

DOI: 10.1145/321466.321471

In 1962, Nordsieck presented a series of numerical methods for solving ordinary differential equations which rely on Taylor's series, but which are equivalent to the correctors in the Adams methods. In a method of Nordsieck, simplifications,...

**Inversion of Modified Symmetric Matrices**

Gerhard Zielke

Pages: 402-408

DOI: 10.1145/321466.321472

The problem to be solved is the computation of the inverse of a modified symmetric matrix if the inverse of the original symmetric matrix is already known. By “modified” it is meant that the two symmetric matrices differ from each...

**The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines**

T. V. Griffiths

Pages: 409-413

DOI: 10.1145/321466.321473

It is shown that the equivalence problem for A-free nondeterministic generalized machines is unsolvable, and it is observed that this result implies the unsolvability of the equality problem for c-finite languages.

**Relations Between Time and Tape Complexities**

John E. Hopcroft, Jeffrey D. Ullman

Pages: 414-427

DOI: 10.1145/321466.321474

It is shown that if a language L is recognized by a (nondeterministic) single-tape Turing machine of time complexity T(n), then L is recognized by a (nondeterministic) offline...

**One-way nondeterministic real-time list-storage languages**

Seymour Ginsburg, Michael A. Harrison

Pages: 428-446

DOI: 10.1145/321466.321475

A device is presented which has its memory organized as a linear list, a type of storage equivalent to having two pushdown stores. Attention is then focused on the nondeterministic automaton (called an lsa) which results when...

**A Universal Syntax-Directed Top-Down Analyzer**

B. A. Chartres, J. J. Florentin

Pages: 447-464

DOI: 10.1145/321466.321476

An algorithm is described that will recognize, and fully analyze, strings of unbounded length, using the rewriting rules of any context-free grammar. It uses a finite random access store, three pushdown tapes, and a counter. It imposes no...

**Syntax-Directed Transduction**

P. M. Lewis, II, R. E. Stearns

Pages: 465-488

DOI: 10.1145/321466.321477

A transduction is a mapping from one set of sequences to another. A syntax-directed transduction is a particular type of transduction which is defined on the grammar of a context-free language and which is meant to be a model of part of the...

**Corrigendum: `` PL360, a Programming Language for the 360 Computers''**

Niklaus Wirth

Page: 489

DOI: 10.1145/321466.321478