**Programming Language for Automata**

Donald E. Knuth, Richard H. Bigelow

Pages: 615-635

DOI: 10.1145/321420.321421

The techniques of automatic programming are useful for constructive proofs in automata theory. A formal definition of an elementary programming language for a stack automaton is given, and it is shown how this may be readily adapted to other...

**Nondeterministic Algorithms**

Robert W. Floyd

Pages: 636-644

DOI: 10.1145/321420.321422

Programs to solve combinatorial search problems may often be simply written by using multiple-valued functions. Such programs, although impossible to execute directly on conventional computers, may be converted in a mechanical way into...

**Real-Time Definable Languages**

Arnold L. Rosenberg

Pages: 645-662

DOI: 10.1145/321420.321423

The closure properties of the class of languages defined by real-time, online, multi-tape Turing machines are proved. The results obtained are, for the most part, negative and, as one would expect, asymmetric. It is shown that the results remain...

**On Memory Requirements for Context-Free Language Recognition**

J. Hartmanis

Pages: 663-665

DOI: 10.1145/321420.321424

The purpose of this note is to show that it is recursively undecidable how much tape is required by a Turing machine to recognize nonregular context-free languages.

**Periodic Decomposition of Sequential Machines**

Arthur Gill, J. Robert Flexer

Pages: 666-676

DOI: 10.1145/321420.321425

Given a minimal sequential machine M and a positive integer T, it is desired to partition the state set of M into T classes, say S0,...

**The Solvability of the Halting Problem for 2-State Post Machines**

Stål Aanderaa, Patrick C. Fischer

Pages: 677-682

DOI: 10.1145/321420.321426

A Post machine is a Turing machine which cannot both write and move on the same machine step. It is shown that the halting problem for the class of 2-state Post machines is solvable. Thus, there can be no universal 2-state Post machine. This is...

**Minimal Experiments for Input-Independent Machines**

Bruce H. Barnes, John M. Fitzgerald

Pages: 683-686

DOI: 10.1145/321420.321427

If, in a sequential machine, the output upon application of an input character depends only upon the current state of the machine and not upon the input character, the machine is called input-independent. Two states, p and...

**Automatic Theorem Proving With Renamable and Semantic Resolution**

James R. Slagle

Pages: 687-697

DOI: 10.1145/321420.321428

The theory of J. A. Robinson's resolution principle, an inference rule for first-order predicate calculus, is unified and extended. A theorem-proving computer program based on the new theory is proposed and the proposed semantic resolution...

**The Concept of Demodulation in Theorem Proving**

Lawrence Wos, George A. Robinson, Daniel F. Carson, Leon Shalla

Pages: 698-709

DOI: 10.1145/321420.321429

In many fields of mathematics the richness of the underlying axiom set leads to the establishment of a number of very general equalities. For example, it is easy to prove that in groups...

**Morphology of ``Information Flow''**

Robert A. Fairthorne

Pages: 710-719

DOI: 10.1145/321420.321430

Such phrases as “information flow” may be purely metaphorical, or may refer to porterage and storage of physical documents, transmission of signals, power required for signaling, Shannon's Selective Information, changes in the state...

**An Algorithm for Reconstructing Protein and RNA Sequences**

Marvin B. Shapiro

Pages: 720-731

DOI: 10.1145/321420.321431

An algorithm for deriving the primary sequence of a protein or RNA is presented. The data is in the form of short sequences of letters which must be fitted together to form the unknown complete sequence. A computer program for carrying out the...

**On a Continuous Method of Approximating Solutions of the Heat Equation**

V. G. Sigillito

Pages: 732-741

DOI: 10.1145/321420.321432

Theoretical methods, based on a priori pointwise bounds, for approximating solutions of many elliptic and parabolic initial and/or boundary value problems, have been developed in recent years. These methods, however, are relatively unknown to...

**Conversion of Limited-Entry Decision Tables to Optimal Computer Programs II**: minimum storage requirement

Lewis T. Reinwald, Richard M. Soland

Pages: 742-756

DOI: 10.1145/321420.321433

Given the number of words of computer storage required by the individual tests in a limited-entry decision table, it is sometimes desirable to find an equivalent computer program with minimum total storage requirement. In this paper an algorithm...

**Matrix Inversion Using Parallel Processing**

Marshall C. Pease

Pages: 757-764

DOI: 10.1145/321420.321434

Two general methods of matrix inversion, Gauss's algorithm and the method of bordering, are analyzed from the viewpoint of their adaptability for parallel computation. The analysis is not based on any specific type of parallel processor; its...

**On Computing the Fixed-Point Probability Vector of Ergodic Transition Matrices**

P. L. Odell, E. P. Decell

Pages: 765-768

DOI: 10.1145/321420.321435

A technique for computing the fixed-point probability vector of an orgodic (cyclic) transition matrix P is developed. The technique utilizes generalized matrix inversion in a scheme which only necessitates calculation of the...

**Solution of Ordinary Differential Equations Using Two ``Off-Step'' Points**

D. G. Brush, J. J. Kohfeld, G. T. Thompson

Pages: 769-784

DOI: 10.1145/321420.321436

In a previous paper the authors suggested that the accurate correctors proposed by Gragg and Stetter for solving ordinary differential equations should be accompanied by similar predictors. In each method in that paper the corrector and one of...

**Some New Results in Pseudo-Random Number Generation**

A. Van Gelder

Pages: 785-792

DOI: 10.1145/321420.321437

Pseudo-random number generators of the power residue (sometimes called congruential or multiplicative) type are discussed and results of statistical tests performed on specific examples of this type are presented. Tests were patterned after the...

**On the Time Required to Perform Multiplication**

S. Winograd

Pages: 793-802

DOI: 10.1145/321420.321438

The time required to perform multiplication is investigated. A lower bound on the time required to perform multiplication, as well as multiplication modulo N, is derived and it is shown that these lower bounds can be approached....