Browsing MAC Memos (1963 - 1974) by Title
Now showing items 1-20 of 57
-
An Asynchronous Logic Array
(1975-05)A new asynchronous logic array for the general synthesis of asynchronous digital circuits is presented. The parallel and asynchronous nature of the array gives the realized systems the speed and characteristics of hardwired ... -
Automatic Code-generation from an Object-machine Description
(1970-10)This memo outlines the basic elements of a macro code-generating system, and develops an informal machine-independent model of a code generator. Then the memo discusses how an implementation of this model could be set up ... -
CAMAC: Group Manipulation System
(1975-03)CAMAC is a collection of group manipulation progams with an easy to use interface. With groups defined by either generating permutations or generators and relations the system can find coset tables, normalizers, centralizers, ... -
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 ... -
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. -
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, ... -
Complexity Measures for Programming Languages
(1971-09)A theory of complexity is developed for algorithms implemented in typical programming languages. The complexity of a measuring a specific type of complexity is a complexity measure -- some function of the amount of a ... -
Computational Complexity of the Word Problem for Commutative Semigroups
(1975-10)We analyze the computational complexity of some decision problems for commutative semigroups in terms of time and space on a Turing machine. The main result we present is that any decision procedure for the word problemm ... -
A Computer Model of Simple Forms of Learning
(1971-01) -
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 ... -
Construction Heuristics for Geometry and a Vector Algebra Representation of Geometry
(1972-06)Heuristics for generating constructions to help solve high school geometry problems are given. Many examples of the use of these heuristics are given. A method of translating geometry problems into vector algebra problems ... -
Decidability of Equivalence for a Class of Data Flow Schemas
(1975-03)In this paper we examine a class of computation schemas and consider the problem of deciding when pairs of elements in this class represent equivalent programs. We are able to show that equivalence is decidable for a ... -
Decision Problems for Petri Nets and Vector Addition Systems
(1975-03)Petri Nets, Generalized Petri Nets, and Vector Addition Systems can represent each other and thus have common decideability problems. The graphical appeal of Petri Nets is used in a new presentation of the classical problems ... -
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 ... -
Description and Flow Chart of the PDP-7/9 Communications Package
(1970-07)The PDP-7/9 Communications Package was written to provide data transfers between the buffer controller (PDP-7 or PDP-9) of an ESL Display Console and a host computer via a 50-kilobit serial Dataphone link. Initially, only ... -
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. -
Economy of Descriptions and Minimal Indices
(1972-01) -
The Emptiness Problem for Automata on Infinite Trees
(1972-06)The purpose of this paper is to give an alternative proof to the decidability of the emptiness problem for tree automata, as shown in Rabin [4]. The proof reduces the emptiness problem for automata on infinite trees to ...