Browsing MAC Memos (1963 - 1974) by Title

Now showing items 15-34 of 57

    • 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 ...

    • Improved Bounds on the Costs of Optimal and Balanced Binary Search Trees 

      Bayer, Paul J. (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 

      Paterson, Michael S.; Fischer, Michael J.; Meyer, Albert R. (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 ...

    • The Inherent Computational Complexity of Theories of Ordered Sets: A Brief Survery 

      Meyer, Albert R. (1974-10)

    • Interactive Design Coordination for the Building Industry 

      Jackson, James N. (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 

      Bonneau, Richard J. (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 

      Aiello, Jack M. (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 ...