Search
Now showing items 1-8 of 8
Weak Monadic Second Order Theory of Successor is not Element-recurive
(1973-12)
Let L SIS be the set of formulas expressible in a week monadic second order logic using only the predicates [x =y+1] and [x E z]. Bucci and Elgot [3,4] have shown that the truth of sentences in L SIS (under the standard ...
A Class of Finite Computations Structures Supporting the Fast Fourier Transform
(1973-03)
The Fast Fourier Transform (FFT) and modular arithmetic are two distinct techniques which recently have been employed to increase the efficiency of numerous algorithms in the area of symbolic and algebraic manipulation.
An Operator Embedding Theorem for Complexity Classes of Recursive Functions
(1973-05)
Let F (t) be the set of functions computable by some machine using no more than t(x) machine steps on all but finitely many arguments x. If we order the - classes under set inclusion as t varies over the recursive functions, ...
An Interactive Implementation of the ToddCoxeter Algorithm
(1973-12)
The Todd-Coxeter algorithm provides a systematic approach to the enumeration of cosets of a finitely presented group. This memo describes an interactive implementation of algorithm, including a manual on its use, examples, ...
A Decision Procedure for the First Order Theory of Real Addition with Order
(1973-05)
Consider the first order theory of the real numbers with the predicates + (plus) and < (less than). Let S be the set of true sentences. We first present an elimination of quantifiers decision procedure for S, and then ...
Real-time Simulation of Multidimensional Turing Machines by Storage Modification Machines
(1973-12)
In [1] the author introduced a new machine model, now called the Storage Modification Machine (SMM). It was claimed, but not proved, that SMM's can simulate all sorts of Turing machines-- those with multidimensional worktapes ...