Search
Now showing items 21-30 of 35
Backup and Recovery of On-line Information in a Computer Utility
(1974-01)
This thesis describes a design for an automatic backup mechanism to be incorporated in a computer utility for the protection of on-line information against accidental or malicious destruction. This protection is achieved ...
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, ...
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 ...
Analysis of Asynchronous Concurrent Systems by Timed Petri Nets
(1974-02)
This thesis is concerned with the modeling and performance analysis of systems which consist of concurrently acting components, an example of which is an asynchronous pipelined processor. The work is divided into two ...
Introduction to Multics
(1974-02)
The Multics project was begun in 1964 by the Computer Systems Research group of M.I.T. Project MAC. The goal was to create a prototype of a computer utility. In 1965, the project became a cooperative venture of M.I.T. ...