Browsing MAC Memos (1963 - 1974) by Title
Now showing items 29-48 of 57
-
Improved Bounds on the Costs of Optimal and Balanced Binary Search Trees
(1975-11)A binary search tree can be used to store data in a computer system for retrieval by name. Different elements in the tree may be referenced with different probabilities. If we define the cost of the tree as the average ... -
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 ... -
Interactive Design Coordination for the Building Industry
(1970-06)The problem of effective communication in the process of building design and construction is widely recognized. The involvement of several design disciplines combined with the tendency for designers to work in distinct ... -
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, ... -
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 ... -
The Macaims Data Management System
(1971-04)MacAIMS (MAC Advanced Interactive Management System) is a relatively small research project that was initiated in the summer of 1968 to investigate the feasibility of using some of the then existing computer facilities at ... -
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 ... -
A New List-tracing Algorithm
(1970-10)List-processing systems have each allowed use of only a single size and configuration of list cell. This paper describes a system which allows use of arbitrarily many different sizes and configurations of list cell, ... -
On Bateson's Logical Levels of Learning Theory
(1975-02) -
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. ... -
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, ... -
Pseudo-random Sequences
(1970-10)The purpose of this paper is to study some notions of randomnes for infinite sequences of 0's and 1's. -
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 ... -
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 ... -
The Relational Approach to the Management of Data Bases
(1971-04)The ultimate goal of Project MacAIMS (MAC Advanced Interactive Management System) is to build a computer facility which will be able to support non-trivial decision making processes. (See reference 4). In the early stages ... -
Research on Experts Systems
(1974-12) -
SIM360: A S/360 Simulator
(1972-05)Modern, large-scale computer systems typically operate under the control of an operating system or executive program, and reserve for the exclusive use of the operating system a set of privileged instructions, which the ... -
Steam-oriented Computation in Recursive Data Flow Schemas
(1975-10)In this thesis we present a parallel programming language based on a parallel computation model known as data flow schemas. Syntactically, the language resembles programming languages such as Algol 60, but does not have ...