Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 15 Issue 3, July 1968

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