ACM DL

Journal of the ACM (JACM)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of the ACM (JACM), Volume 14 Issue 4, Oct. 1967

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....