MAC Memos (1963 - 1974)

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

Sat, 01 Nov 1975 00:00:00 GMT

Improved Bounds on the Costs of Optimal and Balanced Binary Search Trees Bayer, Paul J. 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 number of elements which must be examined in searching for an element, then different trees have different costs. We show that two particular types of trees, weight balanced trees and min-max trees, which are easily constructed from the probability distribution on the elements, are close to optimal. Specifically, we show that for any probability distribution with entropy H, H-log2H-(log2e-1)<=Copt<= Cwb ,+ H+2/Cmm,+H+2 where Copt, Cwb, and Cmm are the optimal, weigh balances, and min-max costs. We gain some added insight by deriving an expression for the expected value of the entropy of a random probability distribution.

Steam-oriented Computation in Recursive Data Flow Schemas

Wed, 01 Oct 1975 00:00:00 GMT

Steam-oriented Computation in Recursive Data Flow Schemas Weng, Kung-Song 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 GOTO's, WHILE-loops, and non-local variables. The attractiveness of this approach lies in the inherently determinate nature of data flow schemas and the possiblity of formalizing the semantics of the language within the formalism suggested by Scott and Strachey. The language provides programming features for stream-oriented computation and intercommunicating systems. We introduce the notions of proper initialization and termination of such systems. A subclass of determinate systems in which these properties can be easily checked is defined and a translation into recursive data flow schemas is given.

Computational Complexity of the Word Problem for Commutative Semigroups

Wed, 01 Oct 1975 00:00:00 GMT

Computational Complexity of the Word Problem for Commutative Semigroups Cardoza, Edward W. 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 for commutative semigroups requires storage space at least proportional to n/logn on a multitape Turing machine. This implies that the word problem is polynomia space hard (and in particular that it is at least NP-hard). We comment on the close relation of commutative semigroups to vector addition systems and Petri nets. We also show that the lower bound of space n/logn can be extended to certain other natural algorithmic problems for commutative semigroups. Finally we show that for several other algorithmic problems for commutative semigroups there exist polynomial time algorithms.

Formal Properties of Well-formed Data Flow Schemas

Sun, 01 Jun 1975 00:00:00 GMT

Formal Properties of Well-formed Data Flow Schemas Leung, Clement Kin Cho 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). Algorithms are given for translating a schema in each class into an equivalent schema in the other class. The propertiees of freedom, _-freedom, openness, and completeness are defined and studied. For every path P in a free flowchart schema S, there exists an interpretation under which the flow of controls through S is along P. _-freedom is a generalization of freedom and captures the notion of freedom for wfdfs's. An open schema is one in which no basic component is redundant and a complete schema contains no subschema which, whenever enabled, does not terminate. A comparison of the expressive power of subclasses of flowchart schemas and wfdfs's possessing various combinations of these properties is made. It is shown that the class of free flowchart schemas properly contains the classes of free and _-free wfdfs's , and that the class of open and complete flowchart schemas is equivalent in expressive power to the class of open and complete wfdfs's. Three undecidabilty results for open and complete program schemas are established: openness is undecidable for complete program schemas, completeness is undecidable for open program schemas, and equivalence is undecidable for open and complete program schemas.

The Complexity of Negotion-limited Networks: A Brief Survery

Sun, 01 Jun 1975 00:00:00 GMT

The Complexity of Negotion-limited Networks: A Brief Survery Fischer, Michael J.

Finding Isomorph Classes for Combinatorial Structures

Sun, 01 Jun 1975 00:00:00 GMT

Finding Isomorph Classes for Combinatorial Structures Weiss, Randell B. 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 with certain properties. In chemistry, it is used to count the number of structures with the same chemical formula. In computer science it is used in counting arguments in proofs in complexity theory. In coding theory, it is used to partition sets of vectors into easy to handle sets. This thesis presents three different algorithms for solving this type of problem and compares their timing and memory use. Some examples are given of how to apply the algorithms to graph theory and coding theory.

An Asynchronous Logic Array

Thu, 01 May 1975 00:00:00 GMT

An Asynchronous Logic Array Patil, Suhas S. 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 circuits even though they are implemented in a uniform diode array with appropriate terminating circuits. The logic array is particularly suited for implementing control structures and should help extend the field of micro-control to asynchronous and parallel computers.

First Version of a Data Flow Procedure Language

Thu, 01 May 1975 00:00:00 GMT

First Version of a Data Flow Procedure Language Dennis, Jack B. 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 operate on elementary and structured values, and always define functional transformations of values. The language is equivalent in expressive power to a block structured language with internal procedure variables and is a generalization of pure Lisp. The language is being used as a model for study of fundamental semantic constructs for programming, as a target language for evaluating translatability of programs expressed as the user-language level, and as a guide for research in advanced computer architecture.

CAMAC: Group Manipulation System

Sat, 01 Mar 1975 00:00:00 GMT

CAMAC: Group Manipulation System Weiss, Randell B. 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, stabilizers, orbits, conjugacy classes, and isomorph classes of combinatorial objects, etc.

Decision Problems for Petri Nets and Vector Addition Systems

Sat, 01 Mar 1975 00:00:00 GMT

Decision Problems for Petri Nets and Vector Addition Systems Hack, Michael 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 of boundedness (decidable) and inclusion (undecidable). Various forms of the Reachability Problem are shown to be recursively equivalent to the Liveness Problem for Petri Nets. The decideability of these questions is still open, and some arguments both for and against the decidability of Liveness are presented.

Decidability of Equivalence for a Class of Data Flow Schemas

Sat, 01 Mar 1975 00:00:00 GMT

Decidability of Equivalence for a Class of Data Flow Schemas Qualitz, Joseph E. 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 non-trivial class of unary operator data flow schemas, and consider the applicability of this result to the problem of deciding equivalence in related models of computation. The model described below is a restricted version of the data flow schema described by Dennie and Fosseen in [1]. The reader is referred to that source for a more complete discussion of the properties of data flow schemas.

On Bateson's Logical Levels of Learning Theory

Sat, 01 Feb 1975 00:00:00 GMT

On Bateson's Logical Levels of Learning Theory Levin, Michael

Research on Experts Systems

Sun, 01 Dec 1974 00:00:00 GMT

Research on Experts Systems Gorry, G. Anthony

A Class of Boolean Functions with Linear Combinatorial Complexity

Tue, 01 Oct 1974 00:00:00 GMT

A Class of Boolean Functions with Linear Combinatorial Complexity Hsieh, W. N.; Harper, L.H.; Savage, J.E. 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 way of restricting it to a subset of n-l variables. We show that the complexity of P^n3,5 function is no less than 7n-4/6, and this bound cannot be much improved. Further, we find that for each k, there are p^k,2^k functions with complexity linear in n.

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

Tue, 01 Oct 1974 00:00:00 GMT

The Inherent Computational Complexity of Theories of Ordered Sets: A Brief Survery Meyer, Albert R.

MDC-Programmer: A Muddle-to-datalanguage Translator for Information Retrieval

Tue, 01 Oct 1974 00:00:00 GMT

MDC-Programmer: A Muddle-to-datalanguage Translator for Information Retrieval Bengelloun, Safwan A. 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 environment. The application involves the design and implementation of a software facility that will permit users at MIT's Dynamic Modeling System to consider the retrieval component of the Datacomputer (developed and run by the Computer Corporation of America) as an extension of the Muddle environment. This facility generates efficient Datalanguage retrieval code, handles inter-process control of the Datacomputer, and manages all the necessary network connections.

Computing in Logarithmic Space

Sun, 01 Sep 1974 00:00:00 GMT

Computing in Logarithmic Space Lind, John C. 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 of recursive string functions containing concatenation and the equality function, and closed under explicit transformation, substitution of a function for a variable and two restricted types of recursion on notation. The first is called recursion of concatenation and only allows top level concetenation of the value of the recursive call. The second, called log bounded recursion on notation, will only define string functions whose length is bounded by 0(log n) on arguments of length n. Some additional closure properties of logspace are also described.

An Investigation of Current Language Support for the Data Requirements of Structured Programming

Sun, 01 Sep 1974 00:00:00 GMT

An Investigation of Current Language Support for the Data Requirements of Structured Programming Aiello, Jack M. 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 structures. With possibly some limitations and extensions, existing languages can support control structure refinement. On the other hand, it is the belief of many that the representation of data structure refinement cannot be satified by present-day languages. Before accepting this view, it is wise to explore its validity. Therefore this thesis will investigate whether existing languages with possibly slight modifications are adequate for supporting the data requirements of structured programming.

An Enciphering Module for Multics

Mon, 01 Jul 1974 00:00:00 GMT

An Enciphering Module for Multics Benedict, G. Gordon 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 implementation of Lucifer for Multics is described. A proof of the algorithm's reversibility for deciphering is provided. A special hand-coded (assembly language) version of Lucifer is described whose goal is to attain performance as close as possible to that of the hardward device. Performance measurements of this program are given. Questions addressed are: How complex is it to implement an algorithm in software designed primarily for digital hardware? Can such a program perform well enough for use in the I/O system of a large time-sharing system?

Complete Classification of (24,12) and (22,11) Self-dual Codes

Sat, 01 Jun 1974 00:00:00 GMT

Complete Classification of (24,12) and (22,11) Self-dual Codes Pless, Vera; Sloane, N.J.A. 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, 6] self-dual code. Several theorems on the enumeration of self-orthogonal codes are used, including forumlas for the number of such codes with minimum distance ≥ 4, and for the sum of the weight enumerators of all self-dual codes.

The Reduction Method for Establishing Lower Bounds on the Number of Additions

Sat, 01 Jun 1974 00:00:00 GMT

The Reduction Method for Establishing Lower Bounds on the Number of Additions Kedem, Zvi M. 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 and subtractions. The results obtained partially overlap those of Belaga, Winograd and Kirkpatrick.

Combining Dimensionality and Rate of Growth Arguments for Establishing Lower Bounds on Number of Multiplications

Sat, 01 Jun 1974 00:00:00 GMT

Combining Dimensionality and Rate of Growth Arguments for Establishing Lower Bounds on Number of Multiplications Kedem, Zvi M. 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.

Fast On-line Integer Multiplication

Wed, 01 May 1974 00:00:00 GMT

Fast On-line Integer Multiplication Fischer, Michael J.; Stockmeyer, Larry J. 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 method for converting any off-line multiplication algorithm which forms the product of two n-digit binary numbers in time F(n) into an on-line method which uses time only O(F(n) log n ), assuming that F is monotone and satisfies n F(n) F(2n)/2 ! kF(n) for some constant k.

Symmetry Codes and Their Invariant Subcodes

Fri, 01 Feb 1974 00:00:00 GMT

Symmetry Codes and Their Invariant Subcodes Pless, Vera We define and study the invariant subcodes of the symmetry codes in order to be able to determine the algebraic properties of these codes. An infinite family of self-orthogonal rate 1/2 codes over GF (3), called symmetry codes, were constructed in [3].

Super-exponential Complexity of Presburger Arithmetic

Fri, 01 Feb 1974 00:00:00 GMT

Super-exponential Complexity of Presburger Arithmetic Fischer, Michael J.; Rabin, Michael O. Lower bounds are established on the computational complexity of the decision problem and on the inherent lengths of proofs for two classical decidable theories of logic: the first order theory of the real numbers under addition, and Presburger arithmetic -- the first order theory of addition on the natural numbers. There is a fixed constant c > 0 such that for every (non-deterministic) decision procedure for determining the truth of sentences of real addition and for all sufficiently large n, there is a sentence of length n for which the decision procedure runs for more than 2 cn steps.

On the Complexity of the Theories of Weak Direct Products

Tue, 01 Jan 1974 00:00:00 GMT

On the Complexity of the Theories of Weak Direct Products Rackoff, Charles 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. We present here a more efficient procedure which operates within space 2 2 . As corollaries we obtain the same upper bound for the theory of finite abelian groups, the theory of finitely generated abelian groups, and the theory of the structure < N ,' > of positive ...

String-matching and Other Products

Tue, 01 Jan 1974 00:00:00 GMT

String-matching and Other Products Fischer, Michael J.; Paterson, Michael S. 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, Knuth and Pratt which has a running time proportional to the total length of the pattern and long string together. This time may be achieved even on a Turing machine. The more difficult case where either string may have "don't care" symbols which are deemed to match with all symbols is also considered. By exploiting the formal similarity of string-matching with integer multiplication, a new algorithm has been obtained with a running time which is only slightly worse than linear.

An Improved Overlap Argument for On-line Multiplication

Tue, 01 Jan 1974 00:00:00 GMT

An Improved Overlap Argument for On-line Multiplication Paterson, Michael S.; Fischer, Michael J.; Meyer, Albert R. 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 is cN1ogN. These bounds compare favorably with know upper bounds of the form cN(1ogN) k, and for some classes the upper and lower bounds coincide. The proofs are based on the "overlap" argument due to Cook and Aanderaa.

Discrete Computation: Theory and Open Problems

Tue, 01 Jan 1974 00:00:00 GMT

Discrete Computation: Theory and Open Problems Meyer, Albert R. 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.

Weak Monadic Second Order Theory of Successor is not Element-recurive

Sat, 01 Dec 1973 00:00:00 GMT

Weak Monadic Second Order Theory of Successor is not Element-recurive Meyer, Albert R. Let L SIS be the set of formulas expressible in a week monadic second order logic using only the predicates [x =y+1] and [x E z]. Bucci and Elgot [3,4] have shown that the truth of sentences in L SIS (under the standard interpretation < N, successor > with second order variables interpreted as ranging over finite sets) is decidable. We refer to the true sentences in L SIS as WSIS. We shall prove that WSIS is not elementary-recursive in the sense of Kalmar. In fact, we claim a stronger result:

Real-time Simulation of Multidimensional Turing Machines by Storage Modification Machines

Sat, 01 Dec 1973 00:00:00 GMT

Real-time Simulation of Multidimensional Turing Machines by Storage Modification Machines Schönage, A. 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 in particular -- in real time.

A User's Guide to the Macro Control Language

Sat, 01 Dec 1973 00:00:00 GMT

A User's Guide to the Macro Control Language Geiger, Steven P.

An Interactive Implementation of the ToddCoxeter Algorithm

Sat, 01 Dec 1973 00:00:00 GMT

An Interactive Implementation of the ToddCoxeter Algorithm Bonneau, Richard J. 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, and methods of accessing the program. Applications of this algorithm are also discussed.

Polynomial Exponentiation: The Fast Fourier Transform Revisited

Fri, 01 Jun 1973 00:00:00 GMT

Polynomial Exponentiation: The Fast Fourier Transform Revisited Bonneau, Richard J.

A Decision Procedure for the First Order Theory of Real Addition with Order

Tue, 01 May 1973 00:00:00 GMT

A Decision Procedure for the First Order Theory of Real Addition with Order Ferrante, Jeanne; Rackoff, Charles 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 analyse it to show that it takes at most time 2^2^cn, c a constant, to decide sentences of length n. Looking more closely at this procedure, we arrive at a second procedure by showing that a given sentence doesn't change in truth value when each of the quantifiers is limited to range over an appropriately chosen finite set of rationals. This fact leads to a decision procedure for S which takes space2^cn. We also remark that our methods lead to a decision procedure for Presburger arithmetic which operates in space 2^2^cn. These upper bounds should be compared with the results of Fischer and Rabin (Proceedings of AMS Symp. on Complexity of Real Computation Processes, to appear) that for some constant c, tim 2^cn for real addition, and time 2^2^cn for Presburger arithmetic, is required to decide some sentences of length n for infitely many n.

An Operator Embedding Theorem for Complexity Classes of Recursive Functions

Tue, 01 May 1973 00:00:00 GMT

An Operator Embedding Theorem for Complexity Classes of Recursive Functions Moll, Robert 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, then it is natural to ask how rich a structure is obtained. We show that this structure is very rich indeed. If R is any countable partial order and F is any total effective operator, then we show that there is a recursively enumerable sequence of...

A Class of Finite Computations Structures Supporting the Fast Fourier Transform

Thu, 01 Mar 1973 00:00:00 GMT

A Class of Finite Computations Structures Supporting the Fast Fourier Transform Bonneau, Richard J. 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.

SIM360: A S/360 Simulator

Mon, 01 May 1972 00:00:00 GMT

SIM360: A S/360 Simulator McCray, Wm. Arthur 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 normal users may not issue. This very necessary arrangement produces a problem of equipment availability for those who wish to develop or investigate operating systems programs, because such programs cannot be run as normal user jobs under an executive program. This thesis describes SIM360, a detailed simulator of the representative IBM S/360 computer, which was written to run student programs, programs assigned as machine problems for a course in operating systems. The simulator allows programs to issue all of the priveleged instructions of the S/360, and thus provides a readily available tool for the study of operating systems programs.

The Emptiness Problem for Automata on Infinite Trees

Thu, 01 Jun 1972 00:00:00 GMT

The Emptiness Problem for Automata on Infinite Trees Hossley, Robert; Rackoff, Charles 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 that for automata on finite trees, by showing that any automata definable set of infinite trees must contain a finitely-genarable trees.

Construction Heuristics for Geometry and a Vector Algebra Representation of Geometry

Thu, 01 Jun 1972 00:00:00 GMT

Construction Heuristics for Geometry and a Vector Algebra Representation of Geometry Wong, Richard 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 is discussed. The solution of these vector algebra geometry problems is analyzed. The use of algebraic constructions to help solve these vector problems is also discussed.

Economy of Descriptions and Minimal Indices

Sat, 01 Jan 1972 00:00:00 GMT

Economy of Descriptions and Minimal Indices Bagchi, Amitava

Helping People Think

Thu, 01 Apr 1971 00:00:00 GMT

Helping People Think Goldstein, Robert C. 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 of the machines that he has been able to command. Furthermore, since simple machines can be used to construct more complicated ones, this process, once begun, tends to advance at an accelerating rate.

The Macaims Data Management System

Thu, 01 Apr 1971 00:00:00 GMT

The Macaims Data Management System Goldstein, Robert C.; Strnad, Alois J. 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 M.I.T. to aid in the management of Project MAC. Several interesting and useful interactive programs were developed and are currently in use.

The Relational Approach to the Management of Data Bases

Thu, 01 Apr 1971 00:00:00 GMT

The Relational Approach to the Management of Data Bases Strnad, Alois J. 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 of our experiments we discovered that traditional approaches to the management of data bases do not satisfy our needs. We have determined the following requirements for the management of Large Data Bases (LDB) in a dynamically varying environment such as an interactive Management Information System.

Transmission of Information Between a Man-machine Decision System and its Environment

Thu, 01 Apr 1971 00:00:00 GMT

Transmission of Information Between a Man-machine Decision System and its Environment Wells, Douglas M.

The Substantive Use of Computers for Intellectual Activities

Thu, 01 Apr 1971 00:00:00 GMT

The Substantive Use of Computers for Intellectual Activities Goldstein, Robert C.

A Computer Model of Simple Forms of Learning

Fri, 01 Jan 1971 00:00:00 GMT

A Computer Model of Simple Forms of Learning Jones, Thomas L.

A New List-tracing Algorithm

Thu, 01 Oct 1970 00:00:00 GMT

A New List-tracing Algorithm Fenichel, Robert R. 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, possibly not specified until run time.

Automatic Code-generation from an Object-machine Description

Thu, 01 Oct 1970 00:00:00 GMT

Automatic Code-generation from an Object-machine Description Miller, Perry L. 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 to generate code for a particular machine from machine-dependent information given in descriptive form.

Complexity Measures for Programming Languages

Wed, 01 Sep 1971 00:00:00 GMT

Complexity Measures for Programming Languages Goodman, Leonard I. 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 particular resource used by a program in processing an input. Typical resources would be execution time, core, I/O devices, and channels

Pseudo-random Sequences

Thu, 01 Oct 1970 00:00:00 GMT

Pseudo-random Sequences Bruere-Dawson, Gerard The purpose of this paper is to study some notions of randomnes for infinite sequences of 0's and 1's.

An Expansion of the Data Structuring Capabilities of PAL

Thu, 01 Oct 1970 00:00:00 GMT

An Expansion of the Data Structuring Capabilities of PAL Zilles, Stephen N.

Suspension of Processes in a Multiprocessing Computer System

Tue, 01 Sep 1970 00:00:00 GMT

Suspension of Processes in a Multiprocessing Computer System Vogt, Carla M.

Use of High Level Languages for Sytems Programming

Tue, 01 Sep 1970 00:00:00 GMT

Use of High Level Languages for Sytems Programming Graham, Robert M. (This paper is a slightly edited version of a transcript so that it still contains the colloquial flavor of the oral presentation.) I'm going to talk about languages for systems programming what they can do for us, and what we might expect from them in the future. These comments are largely based on my experience with the Multics System and I'll quote a few figures from Multics as we go along. I'm concerned particularly with large complex system.

File Management and Related Topics, June 12, 1970

Tue, 01 Sep 1970 00:00:00 GMT

File Management and Related Topics, June 12, 1970 Graham, Robert M. 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 time-sharing system. We do this for two reasons. First, this environment imposes the most severe constraints. Other environments are obtained by relaxing these constraints. Secondly, large information and computing services will become more prevalent in the years to come. Let us first look briefly at those objectives of an information and computing service which are significant to this discussion.

Description and Flow Chart of the PDP-7/9 Communications Package

Wed, 01 Jul 1970 00:00:00 GMT

Description and Flow Chart of the PDP-7/9 Communications Package Ward, Philip W. 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 one of the displays (with a PDP-9 buffer controller) was to be operated remotely over q 50-kilobit line, and the only feasible access to the 7094 CTSS host computer was via the PDP-7 buffer controller of the other display, which is directly connected to CTSS channel D. For this connection, the PDP-7 could be looked upon as the "host" for the PDP-9, although it merely served as a message-handling intermediary for the real host, the 7094

Interactive Design Coordination for the Building Industry

Mon, 01 Jun 1970 00:00:00 GMT

Interactive Design Coordination for the Building Industry Jackson, James N. 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 offices results in little capacity for them to investigate the influence of their design decisions on other design areas. One of the responses to the need for effective Interaction in the use of computers for design project is the supersytem concept proposed for ICES, the Integrated Civil Engineering System. The supersystem is defined as the cooperative effort on the part of the designers of several problem oriented computer capabilities to implement project capabilities by allowing each of their problem oriented subsystem to reference a single file of project data. The supersystem would allow design interaction by having each of the problem oriented computer subsystem reference a single file of information specifying the project. Future work in the application of computers to interactive and project oriented design in the building industry will have to concentrate on the file structure to be used in the Implementation of a computer building design supersystem.