**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 = {aibici ∣ i,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...