Browsing LCS Technical Memos (1974 - 2003) by Issue Date
Now showing items 21-40 of 492
-
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, ... -
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 ... -
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 User's Guide to the Macro Control Language
(1973-12) -
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, ... -
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 ... -
On the Complexity of the Theories of Weak Direct Products
(1974-01)Let N be the set of nonnegative integers and let < N ,+> be the weak direct product of < N,+> with itself. Mostowski[ 9 ] shows that the theory of < N ,*> is decidable, but his decision procedure isn't elementary recursive. ... -
Discrete Computation: Theory and Open Problems
(1974-01)Complexity 1. Borodin, A. Computational Complexity: Theory and Practice, in Currents in the Theory of Computing, A. Aho, ed., Prentice-Hall, Englewood Cliff, N.J., 1973,pp.32-89. -
An Improved Overlap Argument for On-line Multiplication
(1974-01)A lower bound of cN1ogN is proved for the mean time complexity of an on-line multitape Turing machine performing the multiplication of N-digit binary integers. For a more general class of machines the corresponding bound ... -
String-matching and Other Products
(1974-01)The string-matching problem considered here is to find all occurrences of a given pattern as a substring of another longer string. When the pattern is simply a given string of symbols, there is an algorithm due to Morris, ... -
Super-exponential Complexity of Presburger Arithmetic
(1974-02)Lower bounds are established on the computational complexity of the decision problem and on the inherent lengths of proofs for two classical decidable theories of logic: the first order theory of the real numbers under ... -
Symmetry Codes and Their Invariant Subcodes
(1974-02)We define and study the invariant subcodes of the symmetry codes in order to be able to determine the algebraic properties of these codes. An infinite family of self-orthogonal rate 1/2 codes over GF (3), called symmetry ... -
Fast On-line Integer Multiplication
(1974-05)A Turing machine multiplies binary integers on-line if it receives its inputs low-order digits first and produces the jth digit of the product before reading in the (j+l)st digits of the two inputs. We present a general ... -
Combining Dimensionality and Rate of Growth Arguments for Establishing Lower Bounds on Number of Multiplications
(1974-06)In this paper we describe a new method for establishing lower bounds for the number of multiplications and divisions required to compute rational functions. We shall start by reminding the reader of some standard notations. -
Complete Classification of (24,12) and (22,11) Self-dual Codes
(1974-06)A complete classification is given of all [22, 11] and [24, 12] self-dual codes. For each code we give the order of its group, the number of codes equivalent to it, and its weight distribution. There is a unique [24, 12, ... -
The Reduction Method for Establishing Lower Bounds on the Number of Additions
(1974-06)A method for establishing lower bounds on the number of multiplications and divisions has been developed by Pan, Winograd and Strassen. A similar method is developed for establishing lower bounds on the number of additions ... -
An Enciphering Module for Multics
(1974-07)Recently IBM Corporation has declassified an algorithm for encryption usable for computer-to-computer or computer-to-terminal communications. Their algorithm was implemented in a hardware device called Lucifer. A software ... -
An Investigation of Current Language Support for the Data Requirements of Structured Programming
(1974-09)Structured programming is a new method for constructing reliable programs. Structured programming relies upon a systematic technique of top-down development which involves the refinement of both control structures and data ...