Search
Now showing items 11-17 of 17
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, ...
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 ...
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 ...
Computing in Logarithmic Space
(1974-09)
The set logspace, of logarithmic space computable string functions is defined. It is easily seen that logspace ≤ polytime, the set of polynomial time computable functions. ogspace is shown to equal L, the smallest class ...
A Class of Boolean Functions with Linear Combinatorial Complexity
(1974-10)
In this paper we investigate the combinatorial complexity of Boolean functions satisfying a certain property, P^nk,m. A function of n variable has the P^nk,m property if there are at least m functions obtainable from each ...
MDC-Programmer: A Muddle-to-datalanguage Translator for Information Retrieval
(1974-10)
This memo describes a practical application within the framework of the ARPA computer network of the philosophy that a fully developed computer network should appear as a virtual extensino of the user's own software ...