Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 16 Issue 2, April 1969

Experiments With Some Programs That Search Game Trees
James R. Slagle, John E. Dixon
Pages: 189-207
DOI: 10.1145/321510.321511
Many problems in artificial intelligence involve the searching of large trees of alternative possibilities—for example, game-playing and theorem-proving. The problem of efficiently searching large trees is discussed. A new method called...

Automorphisms of Polyadic Automata
Jerzy W. Grzymala-Busse
Pages: 208-219
DOI: 10.1145/321510.321512
This paper is a continuation of the studies of Fleck, Weeg, and others concerning the theory of automorphisms of ordinary automata and of the work of Gil pertaining to time varying automata. A certain restricted class of time-varying automata,...

A Note on Star-Free Events
Albert R. Meyer
Pages: 220-225
DOI: 10.1145/321510.321513
It is shown that a short proof of the equivalence of star-free and group-free regular events is possible if one is willing to appeal to the Krohn-Rhodes machine decomposition theorem.

Synchronizations and General Repetitive Machines, with Applications to Ultimate Definite Automata
R. G. Reynolds, W. F. Cutlip
Pages: 226-234
DOI: 10.1145/321510.321514
Let s and t be states of a finite (deterministic) automaton A. t can be reached from s if there is a tape x such that, if A is...

The Time Required for Group Multiplication
Philip M. Spira
Pages: 235-243
DOI: 10.1145/321510.321515
Winograd has considered the time necessary to perform numerical addition and multiplication and to perform group multiplication by means of logical circuits consisting of elements each having a limited number of input lines and unit delay in...

Properties of Programs and the First-Order Predicate Calculus
Zohar Manna
Pages: 244-255
DOI: 10.1145/321510.321516
This paper is concerned with the relationship of the termination problem for programs and abstract programs to the validity of certain formulas in the first-order predicate calculus. By exploiting this relationship, subclasses of abstract...

A Direct Proof of the Inherent Ambiguity of a Simple Context-Free Language
Herman A. Maurer
Pages: 256-260
DOI: 10.1145/321510.321517
A direct and self-contained proof is given of the inherent ambiguity of the context-free language L = {aibicii,j > 1}...

Translation Networks and Function Composition
Peter Wegner
Pages: 261-263
DOI: 10.1145/321510.321518
A notation for specifying translation networks is analyzed and shown to be a special case of a notation for specifying functions. Cancellation of domains and ranges and associativity is derived more simply than in a previous paper by Sklansky,...

New Methods in Automatic Extracting
H. P. Edmundson
Pages: 264-285
DOI: 10.1145/321510.321519
This paper describes new methods of automatically extracting documents for screening purposes, i.e. the computer selection of sentences having the greatest potential for conveying to the reader the substance of the document. While previous work...

Lattice Approximations to the Minima of Functions of Several Variables
Gerald Berman
Pages: 286-294
DOI: 10.1145/321510.321520
A computer-oriented method is developed for determining relative minima of functions of several variables. No derivatives (or approximations) are required and the process always converges to a relative minimum no matter which initial point is...

Linear Multistep Methods for Volterra Integro-Differential Equations
Peter Linz
Pages: 295-301
DOI: 10.1145/321510.321521
The Dahlquist stability analysis for ordinary differential equations is extended to the case of Volterra integro-differential equations. Thus the standard multistep methods can be generalized to furnish algorithms for solving...

Inversion of Matrices by Partitioning
Marshall C. Pease
Pages: 302-314
DOI: 10.1145/321510.321522
The inversion of nonsingular matrices is considered. A method is developed which starts with an arbitrary partitioning of the given matrix. The separate submatrices are grouped into sets determined by the nonzero entries of some appropriate...

A Time-Sharing Queue with a Finite Number of Customers
I. Adiri, B. Avi-Itzhak
Pages: 315-323
DOI: 10.1145/321510.321523
A time-sharing queue serving a finite number of customers is described. It is assumed that both the service time and the time elapsing between termination of service and the next arrival of the same customer at the queue (service station) are...

The Recursive Unsolvability of the Decision Problem for the Class of Definite Formulas
Robert A. Di Paola
Pages: 324-327
DOI: 10.1145/321510.321524
A class of formulas of the first-order predicate calculus, the definite formulas has recently been proposed as the formal representation of the “reasonable” questions to put to a computer in the context of an actual data retrieval...

Toward a Theory of Enumerations
Paul R. Young
Pages: 328-348
DOI: 10.1145/321510.321525
An attempt is made to show that there is much work in pure recursion theory which implicitly treats computational complexity of algorithmic devices which enumerate sets. The emphasis is on obtaining results which are independent of the...