Browsing MAC Memos (1963 - 1974) by Title

Now showing items 9-28 of 57

    • The Complexity of Negotion-limited Networks: A Brief Survery 

      Fischer, Michael J. (1975-06)

    • Computational Complexity of the Word Problem for Commutative Semigroups 

      Cardoza, Edward W. (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 

      Jones, Thomas L. (1971-01)

    • Computing in Logarithmic Space 

      Lind, John C. (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 

      Wong, Richard (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 

      Qualitz, Joseph E. (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 

      Hack, Michael (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 

      Ferrante, Jeanne; Rackoff, Charles (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 

      Ward, Philip W. (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 

      Meyer, Albert R. (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 

      Bagchi, Amitava (1972-01)

    • The Emptiness Problem for Automata on Infinite Trees 

      Hossley, Robert; Rackoff, Charles (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 ...

    • An Enciphering Module for Multics 

      Benedict, G. Gordon (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 Expansion of the Data Structuring Capabilities of PAL 

      Zilles, Stephen N. (1970-10)

    • Fast On-line Integer Multiplication 

      Fischer, Michael J.; Stockmeyer, Larry J. (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 ...

    • File Management and Related Topics, June 12, 1970 

      Graham, Robert M. (1970-09)
      The subject of these notes is file management. We will develop the problems of file management within the environment of a large information and computing service, often called a computer utility or general purpose ...

    • Finding Isomorph Classes for Combinatorial Structures 

      Weiss, Randell B. (1975-06)
      A common problem in combinatorial analysis is finding isomorph classes of combinatorial objects. This process is sometimes known as isomorph rejection. In graph theory, it is used to count labelled and unlabelled graphs ...

    • First Version of a Data Flow Procedure Language 

      Dennis, Jack B. (1975-05)
      A language for representing computational procedures based on the concept of data flow is presented in terms of a semantic model that permits concurrent execution of noninterfering program parts. Procedures in the language ...

    • Formal Properties of Well-formed Data Flow Schemas 

      Leung, Clement Kin Cho (1975-06)
      This thesis presents some results in comparative schematology and some undecidability results for two models of computer programs: the class of flowchart schemas and the class of well-formed data flow schemas (wfdfs's). ...

    • Helping People Think 

      Goldstein, Robert C. (1971-04)
      Everyone, today, is familiar with the use of machines to ease physical burdens. Since the dawn of civilization, man's progress in gaining control over his environment has been largely determined by the power and sophistication ...