Project MAC

Decidability Questions for Petri Nets

Tue, 01 Jun 1976 00:00:00 GMT

Decidability Questions for Petri Nets Hack, Michel Henri Théodore An understanding of the mathematical properties of Petri Nets is essential when one wishes to use Petri Nets as an abstract model for concurrent systems. The decidability of various problems which arise in this context is an important aspect of this question. The fact that these problems also arise in the context of other mathematical theories, such as commutative, closure under linear relations, Matrix Context-Free grammars, or Weak Counter Automata, provides further motivation.

Petri Net Language

Mon, 01 Mar 1976 00:00:00 GMT

Petri Net Language Hack, Michel Henri Théodore In a labeled Petri Net we assign symbols from an alphabet to some or all the transitions of a Petri Net. To each firing sequence of such a Labeled Petri Net corresponds to a string over the alphabet. We study the languages obtained in this way by all firing sequences of a Petri Net, or by all firing sequences which reach a given final marking.

Some Data Base Applications of Constraint Expressions

Sun, 01 Feb 1976 00:00:00 GMT

Some Data Base Applications of Constraint Expressions Grossman, Richard Weaver This report presents a novel network-like representation for information, called "constraint expressions" (CE). CE makes use of some of the knowledge-representation techniques developed by Artificial Intelligence research.

A Preliminary Study in Computer-aided Legal Analysis

Sat, 01 Nov 1975 00:00:00 GMT

A Preliminary Study in Computer-aided Legal Analysis Meldman, Jeffrey A. This paper describes the prototype for a computer system that can perform a simple kind of legal analysis. The system user, who is presumed to be a lawyer, describes to the system a hypothetical set of facts. The system determines the extent to which these facts fall within certain legal doctrines (by syllogism), or near to these doctrines (by analogy).

Minimizing the Naming Facilities Requiring Protection in a Computing Utility

Mon, 01 Sep 1975 00:00:00 GMT

Minimizing the Naming Facilities Requiring Protection in a Computing Utility Bratt, Richard Glenn This thesis examines the various mechanisms for naming the information objects stored in a general-purpose computing utility, and isolates a basic set of naming facilities that must be protected to assure complete control over user interaction and that allow desired interactions among users to occur in a natural way. Minimizing the protected naming facilities consistent with functional objective of controlled, but natural, user interaction contribute to defining a security kernel for a general-purpose computing utility.

Mechanization of Temporal Knowledge

Mon, 01 Sep 1975 00:00:00 GMT

Mechanization of Temporal Knowledge Kahn, Kenneth M. The design and implementation of a collection of computer programs knowledgeable about time "in general," called the time specialist, is described. The thesis that this time specialist can be placed in the service of larger more general problem solvers is demonstrated for two examples, medical diagnosis and the understanding of a time-travel story.

Strategy Selection in Medical Diagnosis

Mon, 01 Sep 1975 00:00:00 GMT

Strategy Selection in Medical Diagnosis Miller, Peter B. The recorded, verbal problem-solving behavior of doctors performing the diagnostic task of taking a present illness was analyzed in this research. The goal of the analysis was to discover that data-acquisition strategies were used by the doctors to accomplish the task. A model called the strategy frame model was created to describe the strategies that were found and to provide a mechanism for the selection of a strategy.

Equivalence Problems for Monadic Schemas

Sun, 01 Jun 1975 00:00:00 GMT

Equivalence Problems for Monadic Schemas Qualitz, Joseph E. A class of monadic program schemas is defined. This class, called iteration schemas, consists of schemas whose programs comprise assignment statements, conditional statements, and iteration statements. These schemas are shown to correspond to program schemas which are structured, and are shown to be strictly less "powerful" than monadic program schemas.

Automatic Test, Configuration and Repair of Cellular Arrays

Sun, 01 Jun 1975 00:00:00 GMT

Automatic Test, Configuration and Repair of Cellular Arrays Manning, Frank B. A cellular array is an iterative array of identical information processing machines, cells. The arrays discussed are rectangular arrays of programmable logic, in which information stored in a working cell tells the cell how to behave. No signal line connects more than a few cells. A loading mechanism in each cell allows a computer directly connected to one cell to load any good cell that is not walled off by flawed cells.

A Portable Compiler for the Language C

Thu, 01 May 1975 00:00:00 GMT

A Portable Compiler for the Language C Snyder, Alan This paper describes the implementation of a compiler for the language C. The compiler has been designed to be able to be capable of producing assembly-language code for most register-oriented machines with only minor recoding.

Program Restructuring for Virtual Memory Systems

Sat, 01 Mar 1975 00:00:00 GMT

Program Restructuring for Virtual Memory Systems Johnson, Jerry William The problem area addressed in this report is program restructuring, a method of reordering the relocatable sectors of a program in its address space to increase the locality of the programs reference behavior, thereby reducing the number of page fetches require for execution in a virtual memory system.

A Formalization and Correctness Proof of the CGOL Language System

Sat, 01 Mar 1975 00:00:00 GMT

A Formalization and Correctness Proof of the CGOL Language System VanDeVanter, Michael Lee In many important ways the design and implementation of programming languages are hindered rather than helped by BNF. We present an alternative meta-language based on the work of Pratt which retains much of the effective power of BNF but is more convenient for designer, implementer, and user alike. Its amenability to formal treatment is demonstrated by a rigorous correctness proof of a simple implementation.

The Computational Complexity of Some Logical Theories

Sat, 01 Feb 1975 00:00:00 GMT

The Computational Complexity of Some Logical Theories Rackoff, Charles Weill Upper and lower bounds on the inherent computational complexity of the decision problem for a number of logical theories are established. A general form of Ehrenfeucht game technique for deciding theories is developed which involves analyzing the expressive power of formulas with given quantifier depth. The method allows one to decide the truth of sentences by limiting quantifiers to range over finite sets.

A Digitalis Therapy Advisory

Wed, 01 Jan 1975 00:00:00 GMT

A Digitalis Therapy Advisory Silverman, Howard The physician administering digitalis makes use of the full richness of the clinical setting to form his/her impressions and decide on a therapeutic program. The weakness of existing programs which formulate digitalis dosage regimens lies in their inability to use all of the clinical data available-both quantitative. and qualitative. This report describes the construction of a computer system which formulates digitalis dosage regimens and which adjusts this regimen by interpreting the patient's response to the original dosage regimen.

Some Problems in German in English Machine Translation

Sun, 01 Dec 1974 00:00:00 GMT

Some Problems in German in English Machine Translation Brown, Gretchen P. This paper discusses some problems in the machine translation of natural language, in particular, for translation from German into English. An implementation of some parts of the translating process has been built. The system consists of a German interpretive grammar, to take in German text and output a set of semantic representation, and a generator, to produce English sentences from single semantic representations.

Naming and Protection in Extendable Operating Systems

Fri, 01 Nov 1974 00:00:00 GMT

Naming and Protection in Extendable Operating Systems Redell, David D. The properties of capability-based extendible operating systems are described, and various aspects of such systems are discussed, with emphasis on the conflict between free distribution of access privileges and later revocation of those privileges.

Nondeterministic Time and Space Complexity Classes

Sun, 01 Sep 1974 00:00:00 GMT

Nondeterministic Time and Space Complexity Classes Seiferas, Joel Irvin The marginal utility of the Turing machine computational resources running time and storage space are studied. A technique is developed which, unlike diagonalization, applies equally well to nondeterministic and deterministic automata. For f, g time or space bounding functions with f (n+1) small compared to g(n), it is shown that, in terms of word length n, there are languages which are accepted by Turing machines operating within time or space g(n) but which are accepted by no Turing machine operating within time or space f(n). The proof involves use of the recursion theorem together with "padding" or "translational" techniques of formal language theory.

Functional Domains of Applicative Languages

Sun, 01 Sep 1974 00:00:00 GMT

Functional Domains of Applicative Languages Ward, Stephen A. The expressive power of a particular applicative language may be characterized by the set of abstract functions directly representable in that language. The common FUNARG and applicative order problems are scrutinized in this way, and the effects of these weaknesses are related to the inexpressibility of classes of functions.

Semantics of Data Structures and References

Thu, 01 Aug 1974 00:00:00 GMT

Semantics of Data Structures and References Ellis, David J. Each programming language that handles data structures has its own set of rules for working with them. Notions such as assignment and construction of structures values appear in a huge number of different and complicated versions. This thesis presents a methodology which provides a common basis for describing ways in which programming languages deal with data structures and reference to them.

Removing the Dynamic Linker from the Security Kernel of a Computing Utility

Sat, 01 Jun 1974 00:00:00 GMT

Removing the Dynamic Linker from the Security Kernel of a Computing Utility Jason, Philippe Arnaud In order to enforce the security of the information stored in a computing utility, it is necessary to certify that the protection mechanism is correctly implemented so that there exist no uncontrolled access path to the stored information.

Mathematical Logic for Computer Scientists

Sat, 01 Jun 1974 00:00:00 GMT

Mathematical Logic for Computer Scientists Levin, Michael This book is an introductory course in mathematical logic covering basic topics in quantification theory and recursive function theory, and is intended for the reader who is interested in artificial intelligence, computer linguistics, and other related areas. The text is theoretical, but organized with implementation in mind.

Using Interactive Graphics in Simulating the Hospital Emergency Room

Wed, 01 May 1974 00:00:00 GMT

Using Interactive Graphics in Simulating the Hospital Emergency Room Weissberg, Richard W. The hospital emergency room is a complex system having many interrelated factors contributing to its operation. The emergency room administrator has limited control over certain of these factors: numbers of beds, nurses, doctors, x-ray units; for example. Other factors such as patient arrival rates and demands made upon available resources are largely uncontrollable.

The Computer Utility as a Marketplace for Computer Service

Wed, 01 May 1974 00:00:00 GMT

The Computer Utility as a Marketplace for Computer Service Frankston, Robert Mm. Computers are unique in their ability to be programmed for a wide variety of applications. This is in contrast with hardware dedicated to specific tasks such as the telephone system. Because of its flexibility, a computer system can support, concurrently, many diverse services that do not require dedicated hardware.

An Experimental Analysis of Program Reference Patterns in the Multics Virtual Memory

Wed, 01 May 1974 00:00:00 GMT

An Experimental Analysis of Program Reference Patterns in the Multics Virtual Memory Greenberg, Bernard Stewart This thesis reports the design, conducting, and results of an experiment intended to measure the paging rate of a virtual memory computer system as a function of paging memory size. This experiment, conducted on the Multics computer system at MIT, a large interactive computer utility serving an academic community, sought to predict paging rates for paging memory sizes larger than existing memory at the time.

A Model-debugging System

Tue, 01 Jan 1974 00:00:00 GMT

A Model-debugging System Mark, William S.

Verification of Programs Operating on Structured Data

Fri, 01 Mar 1974 00:00:00 GMT

Verification of Programs Operating on Structured Data Laventhal, Mark Steven The major method for verifying the correctness of computer program is the inductive assertion approach. This approach has been limited in the past by the lack of techniques for handling data structures. In particular, there has been a need for concepts with which to describe structured data during intermediate and final stages of a computation.

Introduction to Multics

Fri, 01 Feb 1974 00:00:00 GMT

Introduction to Multics Saltzer, Jerome H. The Multics project was begun in 1964 by the Computer Systems Research group of M.I.T. Project MAC. The goal was to create a prototype of a computer utility. In 1965, the project became a cooperative venture of M.I.T. Project MAC, the General Electric Company Computer Department (now Honeywell Information Systems Inc. ) and Bell Telephone Laboratories. In 1969, at the end of the research phase of the project, Bell Telephone Laboratories ended its active involvement.

On Lower Bounds for Selection Problems

Fri, 01 Mar 1974 00:00:00 GMT

On Lower Bounds for Selection Problems Yao, Foong Frances Let V i (n) be the minimum number of binary comparisons that are required to determine the i-th largest of n elements drawn from a totally ordered set. In this thesis we use adversary strategies to prove lower bounds on V i (n). For i = 3, our lower bounds determine V 3(n) precisely for infinitely many values of n,and determine V 3(n) to within 2 for all n.

Analysis of Asynchronous Concurrent Systems by Timed Petri Nets

Fri, 01 Feb 1974 00:00:00 GMT

Analysis of Asynchronous Concurrent Systems by Timed Petri Nets Ramchandani, Chander This thesis is concerned with the modeling and performance analysis of systems which consist of concurrently acting components, an example of which is an asynchronous pipelined processor. The work is divided into two parts. In the first part, a suitable model is developed for describing the structure of asynchronous concurrent systems. In conventional automata theory, the finite-state machine model is used to describe the behavior of systems; the problem with this is that a large number of states results when practical systems are modelled.

An Abstract Model of a Research Institute: Simple Automatic Programming Approach

Fri, 01 Mar 1974 00:00:00 GMT

An Abstract Model of a Research Institute: Simple Automatic Programming Approach Briabrin, Victor A problem of knowledge representation is considered in terms of designing a model for a simple sociological structure. A version of the access language is proposed which is based on three kind of expressions accepted by the system - constructors, specificators and requests. In addition, some topics concerned with model implementation and extension are discussed.

An Input/Output Architecture for Virtual Memory Computer Systems

Tue, 01 Jan 1974 00:00:00 GMT

An Input/Output Architecture for Virtual Memory Computer Systems Clark, David D In many large systems today, input/output is not performed directly by the user, but is done interpretively by the system for him, which causes additional overhead and also restricts the user to whatever algorithms the system has implemented. Many causes contribute to this involvement of the system in user input/output, including the need to enforce protection requirements, the inability to provide adequate response to control signals from devices, and the difficulty of running devices in a virtual environment, especially a virtual memory.

Backup and Recovery of On-line Information in a Computer Utility

Tue, 01 Jan 1974 00:00:00 GMT

Backup and Recovery of On-line Information in a Computer Utility Stern, Jerry A. This thesis describes a design for an automatic backup mechanism to be incorporated in a computer utility for the protection of on-line information against accidental or malicious destruction. This protection is achieved by preserving on magnetic tape recent copies of all items of information known to the online system. In the event of a system failure, file system damage is automatically assessed and missing information is recovered from backup storage.

On Reducibility Among Combinatorial Problems

Sat, 01 Dec 1973 00:00:00 GMT

On Reducibility Among Combinatorial Problems Herrmann, Paul Peter A large class of combinatorial problems have been shown by Cook and Karp to be computationally equivalent to within a polynomial. We exhibit some new problems in this class, and provide simpler proofs for some of the known reductions.

Productivity in Parallel Computational Schemata

Sat, 01 Dec 1973 00:00:00 GMT

Productivity in Parallel Computational Schemata Linderman, John P. A general model for parallel computation is developed in three parts. One part, the data flow graph, describes how actors which transform and test values are connected to the locations in a finite memory. Another part, an interpretation, supplies information about the contents of memory and the detailed nature of the transformations and tests.

Complexity Classes of Recursive Functions

Fri, 01 Jun 1973 00:00:00 GMT

Complexity Classes of Recursive Functions Moll, Robert An honest function is one whose size honestly reflects its computation time. In 1969 Meyer and McCreight proved the "honesty theorem," which says that for every t, the t-computable functions are the same as the t'computable functions for some honest honest t'.

The Emptiness and Complementation Problems for Automata on Infinite Trees

Mon, 01 Jan 1973 00:00:00 GMT

The Emptiness and Complementation Problems for Automata on Infinite Trees Rackoff, Charles Weill In [6] Rabin defines Automata on Infinite Trees, and the body of that paper is concerned with proving two theorems about these automata. The result we consider in the first chapter says that there exists an effective procedure to determine, given an automaton on infinite trees, whether or not it accepts anything at all. We present a new decision procedure which is much simpler than Rabin's since we do not use an induction argument as he does.

An Analysis of Sorting Networks

Sun, 01 Oct 1972 00:00:00 GMT

An Analysis of Sorting Networks Smith, Burton J. Comparators which sort two numbers can be interconnected to form networks which sort n numbers for any n. The input and output characteristics of comparator networks are analyzed from several different points of view.

Cooperation of Mutually Suspicious Subsystems in a Computer Utility

Fri, 01 Sep 1972 00:00:00 GMT

Cooperation of Mutually Suspicious Subsystems in a Computer Utility Schroeder, Michael D. This thesis describes practical protection mechanisms that allow mutually suspicious subsystems to cooperate in a single computation and still be protected from one another. The mechanisms are based on the division of a computation into independent domains of access privilege, each of which may encapsulate a protected subsystem. The central component of the mechanisms is a hardware processor that automatically enforces the access constraints associated with a multidomain computation implemented as a single execution point in a segmented virtual memory.

Finite Tree Automata and W-Automata

Fri, 01 Sep 1972 00:00:00 GMT

Finite Tree Automata and W-Automata Hossley, Robert Chapter I is a survey of finite automata as acceptors of finite labeled trees. Chapter II is a survey of finite automata as acceptors of infinite strings on a finite alphabet. Among the automata models considered in Chapter II are those used by McNaughton, Buchi, and Landweber. In Chapter II we also consider several new automata models based on a notion of a run of a finite automataton on an infinite string suggested by Professor A.R. Meyer in private communication. We show that these new models are all equivalent to various previously formulated models.

Relativization of the Theory of Computational Complexity

Thu, 01 Jun 1972 00:00:00 GMT

Relativization of the Theory of Computational Complexity Lynch, Nancy A. Blum's machine-independent treatment of the complexity of partial recursive functions is extended to relative algorithms (as represented by Turing machines with oracles). We prove relativizations of several results of Blum complexity theory, such as the compression theorem. A recursive relatedness theorem is proved, showing that any two relative complexity measures are related by fixed recursive function. This theorem allows us to obtain proofs of results for all measures from proofs for a particular measure.

The Complexity of Finite Functions

Wed, 01 Mar 1972 00:00:00 GMT

The Complexity of Finite Functions Vilfan, Bostjan Lower bounds on the length of formulas for finite functions are obtained from a generalization of a theorem of Specker. Let f: (0,1,...,d-1) [0,1,...,d-1] be a function which can be represented by a formula of length < c.n. For any m, if n is sufficiently large, there is a restriction f': {0,1,...,d-1}m > {0,...,d-1} of f which, is representable by special class of formulas called homogeneous e-complexes.

Autonomous, Synchronous Counters Constructed Only of J-K Flip-flops

Mon, 01 May 1972 00:00:00 GMT

Autonomous, Synchronous Counters Constructed Only of J-K Flip-flops Manning, Frank This report describes research into some properties of autonomous, synchronous counters constructed with only the simplest form of J-K Flip-Flop. The research revolved around a system with a special-purpose digital machine and a general-purpose computer. The special-purpose searched through all the possible counters constructed of five or fewer J-K Flip-Flops for all counters with a period equal to that specified by th input to the system.

Essays in Algebraic Simplification

Sat, 01 Apr 1972 00:00:00 GMT

Essays in Algebraic Simplification Fateman, Richard J. This thesis consists of essays on several aspects of the problem of algebraic simplification by computer. Since simplification is at the core of most algebraic manipulations, efficient and effective simplification procedures are essential to building useful computer systems for non-numerical mathematics. Efficiency is attained through carefully designed and engineered algorithms, heuristics,and data types, while effectiveness is assured through theoretical considerations.

Analysis of Production Schemata by Petri Nets

Tue, 01 Feb 1972 00:00:00 GMT

Analysis of Production Schemata by Petri Nets Hack, Michel Henri Théodore Petri nets provide a powerful graphical tool for representing and analyzing complex concurrent systems. Properties such as hang-up freeness, determinacy, conflict, concurrency and dependency, can be represented and studied. The precise relationship between structural and behavioral properties, and between local and global properties is not well-understood for the most general class of Petri Nets.

Induction in Proofs about Programs

Tue, 01 Feb 1972 00:00:00 GMT

Induction in Proofs about Programs Greif, Irene Gloria Four methods for proving equivalence of programs by induction are described and compared. They are recursion induction, structural induction, mu-rule induction, and truncation induction. McCarthy's formalism for conditional expressions as function definitions is used and reinterpreted in view of Park's work on results on results in lattice theory as related to proofs about programs. The possible application of this work to automatic program verification is commented upon.

Evaluation of Definite Integrals by Symbolic Manipulation

Wed, 01 Sep 1971 00:00:00 GMT

Evaluation of Definite Integrals by Symbolic Manipulation Wang, Paul S. A heuristic computer program for the evaluation of real definite integrals of elementary functions is described. This program, called WANDERER (WANg's DEfinite integRal EvaluatoR), evaluates many proper and improper integrals. The improper integrals may have a finite or infinite range of integration. Evaluation by contour integration and residue theory is among the methods used. A program called DELIMITER (DEfinitive LIMITEvaluatoR) is used for the limit computations needed in evaluating some definite integrals.

Cost Analysis of Debugging Systems

Wed, 01 Sep 1971 00:00:00 GMT

Cost Analysis of Debugging Systems Lester, Bruce P. A general method is presented for performing cost analysis of interactive debugging systems. The method is based on an abstract model of program execution. This model is derived from the interpreter used in the Vienna method of semantic definition of PL/I. A brief discussion of the overall operation and significance of Vienna interpreter is included.

Primary Access Control in Large-scale Time-shared Decision Systems

Thu, 01 Jul 1971 00:00:00 GMT

Primary Access Control in Large-scale Time-shared Decision Systems Owens, Richard C., Jr. The computer differs from other tools in that it presently does not provide its users with a working environment transparent to their desires; in particular, current computer systems do not support adequate mechanisms for controlled sharing of sensitive information. Four primary dimensions of the access control problem are identified. They are: 1) the physical level at which to apply control; 2) the fineness of distinction applied to the term ""access"" 3) the meaning of the term "user identification",and 4) the degree of sophistication employed in automatically assigned restrictions to new data files.

Bounds on Information Retrieval Efficiency in Static File Structures

Tue, 01 Jun 1971 00:00:00 GMT

Bounds on Information Retrieval Efficiency in Static File Structures Welch, Terry A. This research addresses the problem of file organization for efficient information retrieval when each file item may be accessed through any one of a large number of identification keys. The emphasis is on library problems, namely large, low-update, directory-oriented files, but other types of files are discussed.

Dynamic Reconfiguration in a Modular Computer System

Tue, 01 Jun 1971 00:00:00 GMT

Dynamic Reconfiguration in a Modular Computer System Schell, Roger R. This thesis presents an orderly design approach for dynamically changing the configuration of constituent physical units in a modular computer system. Dynamic reconfiguration contributes to high system availability by allowing preventative maintenance, development of new operating systems, and changes in system capacity on a non-interference basis.

Automatic Creation of a Code Generator from a Machine Description

Sat, 01 May 1971 00:00:00 GMT

Automatic Creation of a Code Generator from a Machine Description Miller, Perry L. This paper studies some of the problems involved in attaining machine independence for a code generator, similar to the language independence and the token independence attained by automatic parsing and automatic lexical systems. In particular, the paper examines the logic involved in two areas of code generation: computation and data reference.

Computer Analysis of Visual Properties of Curved Objects

Sat, 01 May 1971 00:00:00 GMT

Computer Analysis of Visual Properties of Curved Objects Krakauer, Lawrence J. A method is presented for the visual analysis of objects by computer. It is particularly well suited for opaque objects with smoothly curved surfaces. The method extracts information about the object's surface properties, including measures of its specularity, texture, and regularity. It also aids in determining the object's shape.

Design Strategies for File Systems

Thu, 01 Oct 1970 00:00:00 GMT

Design Strategies for File Systems Madnick, S.E. This thesis describes a methodology for the analysis and synthesis of modern general purpose file systems. The two basic concepts developed are (1) establishment of a uniform representation of a file's structure in the form of virtual memory or segmentation and (2) determination of a hierarchy of logical transformations within a file system.

Complexity Measures for Language Recognition by Canonic Systems

Thu, 01 Oct 1970 00:00:00 GMT

Complexity Measures for Language Recognition by Canonic Systems Haggerty, Joseph P. A canonic system C is a specification of a recursively enumerable set, such as a set of strings over a finite alphabet. From this description C, it is possible to generate a system C , called a proof measure function, which is an indication of the complexity of the language defined. For certain simple but important classes of canonic system, algebraic bounds on these functions can be derived from the structure of the system.

Deadlock-free Sharing of Resources in Asynchornous Systems

Tue, 01 Sep 1970 00:00:00 GMT

Deadlock-free Sharing of Resources in Asynchornous Systems Hebalkar, Prakash G. Whenever resources are shared among several activities that hoard resources, the activities can attain a state of deadlock in which, for lack of resources, none of the activities can proceed. Deadlocks can be prevented by coordination of the sharing. efficient running of the activities under such coordination requires knowledge of the patterns of use of resources by the activities.

Integral Convex Polyhedra and an Approach to Integralization

Sat, 01 Aug 1970 00:00:00 GMT

Integral Convex Polyhedra and an Approach to Integralization Edelberg, Murray Many combinatorial optimization problems may be formulated as integer linear programming problems - that is, problems of the form: given a convex polyhedron P contained in the non-negative orthant of n-dimensional space, find a integer point in P which maximizes (or minimizes) a given linear objective function. Well known linear programming methods would suffice to solve such a problem if: (i) P is an integral convex polyhedron, or (ii) P is transformed into the integral convex polyhedron that is the convex hull of the set of integer points in P, a process which is called integralization.

Computer Recognition of Prismatic Solids

Sat, 01 Aug 1970 00:00:00 GMT

Computer Recognition of Prismatic Solids Griffith, Arnold Koons An investigation is made into the problem of constructing a model of the appearance to an optical input device of scenes consisting of plane-faced geometric solids. The goal is to study algorithms which find the real straight edges in the scenes, taking into account smooth variations in intensity over faces of the solids, blurring of edges and noise.

Coordination of Asynchronous Event

Mon, 01 Jun 1970 00:00:00 GMT

Coordination of Asynchronous Event Patil, Suhas Shrikrishna The way activity in a system proceeds is that events occur as a result of some conditions and lead to some new conditions which make other events possible. Often it is necessary to coordinate such events to ensure proper behavior. Coordination nets for representing such coordinations and physically realizable structures for enforcing such coordinations are presented. These structures are modular and can be mechanically derived from the coordination nets. Coordination involved in concurrent management of resources are also discussed.

A Computer-controlled Graphical Display Processor

Mon, 01 Jun 1970 00:00:00 GMT

A Computer-controlled Graphical Display Processor Fiasconaro, James Gerard A cathode-ray tube, (CRT), is frequently employed to display text and drawings generated by a digital computer. Unfortunately, all of the commercially available CRT display systems are either very expensive or have limited dynamic capability resulting from the use of some form of storage-type CRT. A need exists to develop a low-cost, relatively sophisticated display compute-generated pictures.

Generalized Organization of Large Data Bases: A Set-theoretic Approach to Relations

Mon, 01 Jun 1970 00:00:00 GMT

Generalized Organization of Large Data Bases: A Set-theoretic Approach to Relations Fillat, Andrew Irwin; Kraning, Leslie Alan Problems inherent in representation and manipulation of large data bases are discussed. Data management is considered as the manipulation of relationships among elements of a data base. A detailed analogy introduces concepts embodied in a data management system. Set theory is used to describe a model for data-bases, and operations suitable for manipulation of relations are defined.

Economies of Scale in Computer Use: Initial Test and Implication A for the Computer Utility

Mon, 01 Jun 1970 00:00:00 GMT

Economies of Scale in Computer Use: Initial Test and Implication A for the Computer Utility Selwyn, Lee L. This study is concerned with the existence of economies of scale in the production of data processing and other computing services, and the possible regulatory and public policy implications of such economies. The rapid development of the technology of computation since the Second World War has raised many questions as to the supervision by public authorities of the use and progress of this technology.

Controlled Information Sharing in a Computer Utility

Wed, 01 Oct 1969 00:00:00 GMT

Controlled Information Sharing in a Computer Utility Vanderbilt, Dean H. A computer utility is envisioned as a large, multi-access computer system providing its users with the ability to store information and share its use with other system users. This thesis considers the nature of information sharing and how a computer utility can provide facilities allowing such sharing to take place in a controlled manner.

Recognition of Translators Invariants* By Iterative Arrays

Wed, 01 Oct 1969 00:00:00 GMT

Recognition of Translators Invariants* By Iterative Arrays Beyer, Wendel Terry A study is made of the recognition and transformation of figures by iterative arrays of finite state automata. A figure is a finite rectangular two-dimensional array of symbols. The iterative arrays considered are also finite, rectangular and two-dimensional.

Practical Translators for LR(k) Languages

Wed, 01 Oct 1969 00:00:00 GMT

Practical Translators for LR(k) Languages Deremer, Franklin Lewis A context-free syntactical translator (CFST) is a machine which defines a translation from one context-free language to another. A transduction grammar is a formal system based on a context-free grammar and it specifies a context-free syntactical translation. A simple suffix transduction grammar based on a context-free grammar which is LR(k) specifies a translation which can be defined by a deterministic push-down automation (DPDA).

A Graph Model for Parallel Computations

Mon, 01 Sep 1969 00:00:00 GMT

A Graph Model for Parallel Computations Rodrigues, Jorge E. This report presents a computational model called program graphs which makes possible a precise description of parallel computations of arbitrary complexity on non-structured data. In the model, the computation steps are represented by the nodes of a directed graph whose links represent elements of storage and transmission of data and /or control information.

Case Study in Interactive Graphics Programming: A Circuit Drawing and Editing Program for Use with A Storage-tube Display Terminal

Wed, 01 Oct 1969 00:00:00 GMT

Case Study in Interactive Graphics Programming: A Circuit Drawing and Editing Program for Use with A Storage-tube Display Terminal Brackett, J.; Hammer, M.M.; Thornhill, D. The concepts involved in building and manipulating a data structure through graphical interaction are presented, using the drawing and editing of electrical circuits as a vehicle. The circuit drawings program was designed to operate on an ARDS storage-tube display terminal attached to the M.I.T. Project MAC IBM 7094 Compatible Time-Sharing System.

EPS: An Interactive System for Solving Elliptic Boundary-Value Problems with Facilities for Data Manipulation

Sun, 01 Jun 1969 00:00:00 GMT

EPS: An Interactive System for Solving Elliptic Boundary-Value Problems with Facilities for Data Manipulation Tillman, Coyt C., Jr. This appendix for the author's forthcoming thesis, "On-Line Solution of Elliptic Boundary-Value Problems," is a user's guide for EPS. EPS solves two-dimensional boundary-value problems for elliptic systems of second-order partial differential equations. It also has general-purpose capabilities which permit the on-line definition and execution of arbitrary numerical procedures.

Interactive Computer-mediated Animation

Sun, 01 Jun 1969 00:00:00 GMT

Interactive Computer-mediated Animation Baeker, Ronald M. The use of interactive computer graphics in the construction of animated visual displays is investigated. The dissertation presents a process called interactive computer-mediated animation, in which dynamic displays are constructed by utilizing direct console commands, algorithms, free-hand sketches, and real-time actions. The resulting "movie" can then be immediately viewed and altered.

A Formal System for Defining the Syntax and Semantics of Computer Languages

Tue, 01 Apr 1969 00:00:00 GMT

A Formal System for Defining the Syntax and Semantics of Computer Languages Ledgard, Henry Francis The thesis of this dissertation is that formal definitions of the syntax and semantics of computer languages are needed. This dissertation investigates two candidates for formally defining computer languages: (1) the formalism of canonical systems for defining the syntax of a computer language and its translation into a target language for defining the semantics of a computer language.

Computer Recognition of Three-Dimensional Objects in a Visual Scene

Sun, 01 Dec 1968 00:00:00 GMT

Computer Recognition of Three-Dimensional Objects in a Visual Scene Guzman-Arenas, Aldolfo Methods are presented 1) to partition or decompose a visual scene into the bodies forming it; (2) to position these bodies in three-dimensional space, by combining two scenes that make a stereoscopic pair; 3) to find the regions or zones of a visual scene that belong to its background, (4) to carry out the isolation of objects in (1) when the input has inaccuracies.

A Simulator of Multiple Interactive Users to Drive a Time-shared Computer System

Wed, 01 Jan 1969 00:00:00 GMT

A Simulator of Multiple Interactive Users to Drive a Time-shared Computer System Greenbaum, Howard Jacques In the construction and maintenance of a time-shared computer system the need arises for a tool which can provide a controlled, repeatable environment for the purpose of making performance measurements. This thesis describes the use of a small second computer to simulate the actions of multiple interactive users over individual communication lines. Each simulated user exhibits responses similar to those of a "normal" interactive user.

Lambda Calculus Models of Programming Languages

Sun, 01 Dec 1968 00:00:00 GMT

Lambda Calculus Models of Programming Languages Morris, James H. Two aspects of programming languages, recursive definitions and type declarations are analyzed in detail. Church's -calculus is used as a model of a programming language for purposes of the analysis. The main result on recursion is an analogue to Kleene's first recursion theorem: If A= FA for any A-expressions A and F, then A is an extension of YF in the sense that if E[YE], any expressions containing YF, has a normal form then E[F] =E {A]. Y is Curry's paradoxical combinator. The result is shown to be invariant for many different versions of Y.

An Integrated Hardware-software Systems for Computer Graphics in Time-sharing

Sun, 01 Dec 1968 00:00:00 GMT

An Integrated Hardware-software Systems for Computer Graphics in Time-sharing Thornhill, D.E.; Stotz, R.H.; Ross, D.T.; Ward, J.E. This report describes the ESL Display Console and its associated user-oriented software systems developed by the M.I.T. Computer-Aided Design Project with Project MAC. Console facilities include hardware projection of three-dimensional line drawings, automatic light pen tracking, and a flexible set of knob, switch, and push-button inputs. The console is attached to the Project MAC IBM 7094 Compatible Time-Sharing System either directly or through a PDP-7 Computer.

Implementing Multi-process Primitives in a Multiplexed Computer System

Fri, 01 Nov 1968 00:00:00 GMT

Implementing Multi-process Primitives in a Multiplexed Computer System Rappaport, Robert Lee In any computer system primitive functions are needed to control the actions of processes in the system. This thesis discusses a set of six such process control primitives which are sufficient to solve many of the problems involved in parallel processing as well as in the efficient multiplexing of system resources among the many processes in a system.

Resource Allocation in Multiprocess Computer Systems

Wed, 01 May 1968 00:00:00 GMT

Resource Allocation in Multiprocess Computer Systems Denning, Peter James The dynamic allocation for limited processor and main memory resources among members of a user community is investigated as a supply-and-demand problem. The work is divided into four phases. First phase is the construction of the working set model for program behavior. This model is based on locality, the concept that, during any interval of execution, a program favors a subset of its information; a computation's working set is a dynamic measure of this set of favored information. A working set storage management policy is one that allocates processors to a computation if and only if there is enough uncommitted space in main memory to contain its working set.

Incremental Simulation on a Time-shared Computer

Mon, 01 Jan 1968 00:00:00 GMT

Incremental Simulation on a Time-shared Computer Jones, Malcolm Murray This thesis describes a system which allows simulation models to be built and tested incrementally. It is called OPS-4 and is specifically designed to operate in the environment of the Multics system. It represents a major expansion and improvement of the OPS-3 system implemented in CTSS and also includes many features adapted from other current simulation systems.

Symbolic Integration

Fri, 01 Dec 1967 00:00:00 GMT

Symbolic Integration Moses, Joel SIN and SOLDIER are heuristic programs written in LISP which solve symbolic integration problems. SIN (Symbolic INtegrator) solves indefinite integration problems at the difficulty approaching those in the larger integral tables. SIN contains several more methods than are used in the previous symbolic integration program SAINT, and solves most of the problems attempted by SAINT in less than one second. SOLDIER (SOLution of Ordinary Differential Equations Routine) solves first order, first degree ordinary differential equations at the level of a good college sophomore and at an average of about five seconds per problem attempted.

A Canonic Translator

Wed, 01 Nov 1967 00:00:00 GMT

A Canonic Translator Alsop, Joseph Wright An algorithm to recognize and translate sets of character strings specified by canonic system is presented. The ability of canonic systems to define the context sensitive features of strings and to specify their translation allows the algorithm to recognize and translate real computer languages. It is also applicable in other languages systems.

A System for Computer-aided Diagnosis

Fri, 01 Sep 1967 00:00:00 GMT

A System for Computer-aided Diagnosis Gorry, Gregory Anthony This thesis describes a model diagnostic problem and a computer program designed to deal with this problem. The model diagnostic problem is an abstract problem. A major contention of this thesis, however, is that this problem subsumes the principal feature of a number of ostensibly different real diagnostic problems including certain problems of medical diagnosis and the diagnosis of machine failures. A second major contention of this thesis is that strategies for the solution of the model diagnostic problem can be formulated in terms sufficiently explicit to permit their incorporation in a computer program.

Program Analysis by Digital Computer

Tue, 01 Aug 1967 00:00:00 GMT

Program Analysis by Digital Computer Wilde, Daniel Underwood A comparison of the properties of non-modifying and self-modifying programs leads to the definition of independent and dependent instructions. Because non-modifying programs contain only independent instructions, such programs can be analyzed by a straight forward, two -step analysis procedure. First, the program control flow is detected; second, that control flow is used to determine the program data flow or data processing. However, self-modifying programs can also contain dependent instructions, and the program control flows and data flows exhibit cyclic interaction.

Design and Implementation of a Table-Driven Compiler System

Sat, 01 Jul 1967 00:00:00 GMT

Design and Implementation of a Table-Driven Compiler System Liu, Chung L.; Change, Gabriel D.; Marks, Richard E. Our goal is to provide users of the table-driven compiler system with an environment within which they can freely design and produce their compilers. The primary design criterion is generality so that the users can define a large class of input languages oriented toward any kind of problem-solving purposes, and can also define a large class of object programs to be executed on different computer systems. Therefore, in our system we do not limit the users to specific ways of doing syntactic analysis, or doing storage allocation, or producing binary programs of a specific format for a particular computer system. What we provide are mechanisms that are general enough for whichever way a user desires to build his compiler.

Surfaces for Computer-aided Design of Space Forms

Thu, 01 Jun 1967 00:00:00 GMT

Surfaces for Computer-aided Design of Space Forms Coons, Steven A. The design of airplanes, ships, automobiles, and so-called ""sculptured parts"" involves the design, delineation, and mathematical description of bounding surfaces. A method is described which makes possible the description of free-form doubly curved surfaces of a very general kind. An extension of these ideas to hyper-surfaces in higher dimensional spaces is also indicated.

On-line Analysis for Social Scientists

Mon, 01 May 1967 00:00:00 GMT

On-line Analysis for Social Scientists Miller, James R. A library of computer routines has been compiled to facilitate the analysis of social science research data. Many of these routines are designed to test statistical hypotheses. All routines are operated on-line and permit conversational interaction between the user and a time-shared computer. Input data are typed directly into the computer through a teletype console. Explicit typing directions and error diagnostics, where appropriate, are printed out by each routine to guide the input process. Analyses are executed immediately, and computed results are printed out in typical publication language.

Syntax-based Analytic Reading of Musical Scores

Sat, 01 Apr 1967 00:00:00 GMT

Syntax-based Analytic Reading of Musical Scores Forte, Allen As part of a larger research project in musical structure, a program has been written which ""reads"" scores encoded in an input language isomorphic to music notation. The program is believed to be the first of its kind. From a small number of parsing rules the program derives complex configurations, each of which is associated with a set of reference points in a numerical representation of a time-comtinuum. The logical structure of the program is such that all and only the defined classes of events are represented in the output.

A Low-cost Output Terminal for Time-shared Computers

Wed, 01 Mar 1967 00:00:00 GMT

A Low-cost Output Terminal for Time-shared Computers Rosenburg, Ronald C.; Kennedy, Daniel W.; Humphrey, Roger A. This report describes a low-cost remote terminal to provide switch-form output from a time-shared digital computer. The terminal consists of a modified model 35 KSR teletype and a local memory unit. The unit is independent of any particular computer, and is easy to test and maintain. The states of the memory control and memory words are observable directly by indicator lights.

Some Aspects of Pattrn Recognition by Computer

Wed, 01 Feb 1967 00:00:00 GMT

Some Aspects of Pattrn Recognition by Computer Guzman-Arenas, Adolfo A computer may gather a lot of information from its environment in an optical or graphical manner. A scene, as seen for instance from a TV camera or a picture, can be transformed into a symbolic description of points and lines or surfaces. This thesis describes several programs, written in the language CONVERT, for the analysis of such descriptions in order to recognize, differentiate and identify desired objects or classes of objects in the scene. Examples are given in each case.

An On-line System for Algebraic Manipulation

Thu, 01 Dec 1966 00:00:00 GMT

An On-line System for Algebraic Manipulation Fenichel, Robert R. This thesis describes an approach to the problem of programming a computer for algebraic manipulation. The motivating threads of the work are first picked up in Chapter I. To test the descriptive intuitions urged normatively in Chapter I, an experimental system was actually implemented. This system is described in Chapter II and in the Appendices.

Computer Design for Asynchronously Reproducible Multiprocessing

Tue, 01 Nov 1966 00:00:00 GMT

Computer Design for Asynchronously Reproducible Multiprocessing Van Horn, Earl C. A concept is presented for designing either a computing system, or a programming language system, so that the following problem is avoided: during a multiprocess computation in which several processes communicate, and in which the relative timing of the processes is arbitrary, the output produced by the computation might not be a function of only the initial computation state, i.e., of only the inputs and initial program of the computation.

ADEPT: A Heuristic Program for Proving Theorems of Group Theory

Sat, 01 Oct 1966 00:00:00 GMT

ADEPT: A Heuristic Program for Proving Theorems of Group Theory Norton, Lewis Mark A computer program, named ADEPT (A Distinctly Empirical Prover of Theorems), has been written which proves theorems taken from the abstract theory of groups. Its organization is basically heuristic, incorporating many of the techniques of the human mathematician in a "natural" way. This program has proved almost 100 theorems, as well as serving as a vehicle for testing and evaluating special-purpose heuristics.

Pilot: A Step Towards Man-Computer Symbiosis

Thu, 01 Sep 1966 00:00:00 GMT

Pilot: A Step Towards Man-Computer Symbiosis Teitelman, Warren PILOT is a programming system constructed in LISP. It is designed to facilitate the development of programs by easing the familiar sequence: write some code, run the program, make some changes, write some more code, run the program again, etc. As a program becomes more complex, making theses changes becomes harder and harder because the implications of changes are harder to anticipate.

Models and Data Structures for Digital Logic Simulation

Mon, 01 Aug 1966 00:00:00 GMT

Models and Data Structures for Digital Logic Simulation Smith, Donald Leigh A digital logic simulation system is proposed for design verification. Logic to be simulated is specified with a high level register transfer design language, and the simulation system operates on-line on a large time-shared computer. The problem of selecting adequate circuit and signal models for this purpose is considered. models are proposed with sufficient timing detail to allow the simulation system to detect timing errors which currently are found by manual checking or prototype.

Traffic Control in a Multiplexed Computer System

Fri, 01 Jul 1966 00:00:00 GMT

Traffic Control in a Multiplexed Computer System Saltzer, Jerome H. This thesis describes a scheme for processor multiplexing in a multiple user, multiple processor computer system. The scheme is based upon a distributed supervisor which may be different for different users. The processor multiplexing method provides smooth inter-process communication, treatment of input/output control as a special case of inter-process communication, and provision for a user to specify parallel processing or simultaneous input/output without interrupt logic.

Search Procedures Based on Measures of Relatedness Between Documents

Wed, 01 Jun 1966 00:00:00 GMT

Search Procedures Based on Measures of Relatedness Between Documents Ivie, Evan Leon In this thesis a new type of information retrieval system is suggested which utilizes data of the type generated by the users of the system instead of data generated by indexers. The theoretical model on which the system is based consists of three basic elements. The first element is measure of the relatedness between document-pairs. It is derived from information theory.

Input/Output in Time-shared, Segmented, Multiprocessor Systems

Wed, 01 Jun 1966 00:00:00 GMT

Input/Output in Time-shared, Segmented, Multiprocessor Systems Smith, Arthur Anshel After introducing and defining the concepts of time-sharing, segmentation, and multiprocessing, two classes of systems incorporating these are introduced. Both classes use associative memories, as 'look behind' devices to speed the operation of addressing the segment memory, with the distinction between classes being the location of the associative memory.

Design of a Low-cost Character Generator for Remote Computer Displays

Tue, 01 Mar 1966 00:00:00 GMT

Design of a Low-cost Character Generator for Remote Computer Displays Cheek, Thomas Burrell A requirement exists for a low-cost remote display terminal with alphanumeric and line-drawing capabilities for use with time-shared computer systems. This thesis, conducted as part of the overall remote display design project, was undertaken to investigate novel approaches to character generation, with the goal of drastically reducing present-day costs for such devices. A survey of existing devices and character generation techniques was carried out, and a design approach was chosen which takes advantage of mass-fabrication techniques. This includes using a five-by-seven dot matrix raster and a resistor array "read-only" character memory for the 96 printable symbols of the Revised Proposed ASCII Code. Circuits designed, included a dot matrix generator and a register array memory with selection logic sense amplifiers, and a shift register output buffer. An experimental character generator with an eight-word memory was built, largely using integrated circuits and was found to work as desired. It is concluded that the design approach will yield a character generator that is of low enough cost to find wide use in remote computer terminals.

Investigation of an Analog Technique to Decrease Pentracking Time in Computer Display

Tue, 01 Mar 1966 00:00:00 GMT

Investigation of an Analog Technique to Decrease Pentracking Time in Computer Display Stratton, William David Many modern digital computer systems contain cathode-ray tube display equipment to facilitate man-machine communications. Through the use of a display and a light-sensitive pen, graphical material can be directly inserted into the computer by using the pen to control the position of the electron beam at the face of the CRT-a process called pen tracking. Beam position is continually sampled by the computer, permitting continuous display of the material being sketched. In present digital pen-tracking techniques, a tracking pattern (usually a cross) with a substantial number of points is generated on the face of the CRT and the binary response of the pen to the individual points of the pattern is employed to calculate pen position. The large number of pattern points, and the phosphor decay time associated with each, yield a typical tracking cycle of 500 to 1000 microseconds. Since the cycle must be repeated about 100 times per second, 5 to 10 percent of display time is consumed. To reduce the time required by the tracking operation, an analog technique employing a four-point tracking pattern is proposed in this study, in which the amplitude response of the pen to corresponding pairs of points is used to determine the position of the pen relative to the center of the pattern. To study the method, one channel of the proposed two-channel analog tracking system was designed, constructed, and coupled to the horizontal channel of a high-speed computer display console. To avoid the phosphor-decay limitation, an experimental "Beam" pen capable of detecting the electron beam rather than the phosphor luminescence is employed. The system included a pattern generator, sample-and-hold gates, difference amplifier, envelope detector and noise filter, and a threshold-logic analog-to-digital converter. The time required to generate the tracking pattern and develop the binary equivalent of the horizontal distance separating pen and pattern center is only 25 microseconds. Tracking is generally satisfactory, but some anomalies were noted, apparently due to the characteristics of the experimental pen being used. It is concluded that the analog technique is feasible for improving the speed of pen tracking, but recommended that further studies be made of the limitations inherent in the method.

MAP: A System for On-line Mathematical Analysis

Sat, 01 Jan 1966 00:00:00 GMT

MAP: A System for On-line Mathematical Analysis Kaplow, Roy; Strong, Stephen; Brackett, John This manual describes a computer suitable for use on the time-sharing facility at the M.I.T. Computation Center or at Project MAC. Designated for direct computer access through a remote console, the system replaces the normal procedures of programming with a question and answer interchange between the user (hereinafter called U) and the computer (hereinafter called C). The system is intended for the solution of mathematical problems. It should be usable by a person with no knowledge of computers or programming and little knowledge of numerical analysis. Within its range of capabilities, it should be as efficient as are the normal means of computer access for the more sophisticated user. The system establishes a "conversation" between U and C with an electric typewriter as the means of communication. U can give information to C and can ask it certain questions. C can answer those questions if it is given enough information. C can also ask questions and can therefore request any missing information. In addition, C can explain procedures to U in order to help the latter transmit the required information in a proper form. U, therefore, only needs to know a few basic rules, such as how to phrase his questions and how to name and tabulate his data.

Programming Semantics for Multiprogrammed Computations

Wed, 01 Dec 1965 00:00:00 GMT

Programming Semantics for Multiprogrammed Computations Dennis, Jack B.; Van Jhorn, Earl C. The semantics are defined for a number of meta-instructions which perform operations essential to the writing of programs in multiprogrammed computer systems. These meta-instructions relate to parallel procession, protection of separate computations, program debugging, and the sharing among users of memory segments and other computing objects, the names of which are hierarchically structured. The language sophistication contemplated is midway between an assembly language and an advanced algebraic language.

The Priority Problem

Mon, 01 Nov 1965 00:00:00 GMT

The Priority Problem Greenberger, Martin Priority decisions arise whenever limited facilities must be apportioned among competitive demands for service. Broadly viewed, even the familiar first-come-first served discipline is a priority rule. It favors the longest-waiting user, and guards against excessive delays. Other priority rules, such as shortest-job-next, are keyed instead to considerations of operating efficiency. Urgency of request is still another common consideration. Since these considerations often conflict, the priority rule serves as mediator. Use of a common cost measure can help effect this mediation, as results from recent job-shop simulations illustrate. A priority operation of contemporary interest is scheduling a time-shared computer among its concurrent users. Service requirements are not known in advance of execution. To keep response times short for small requests, service intervals are partitioned and segments are served separately in round-robin fashion. A mathematical analysis pinpoints the tradeoff between overhead and discrimination implicit in this procedure, and allows alternate strategies to be costed. Extensions of the simple round-robin procedure are suggested, the objectives of time-sharing are reviewed, and implications are drawn for the design of future priority and pricing systems.

Queueing Models for File Memory Operation

Fri, 01 Oct 1965 00:00:00 GMT

Queueing Models for File Memory Operation Denning, Peter James A model for the auxiliary memory function of a segmented, multiprocessor, time-shared computer system is set up. A drum system in particular is discussed, although no loss of generality is implied by limiting the discussion to drums. Particular attention is given to the queue of requests waiting for drum use. It is shown that a shortest access time first queue discipline is the most efficient, with the access time being defined as the time required for the drum to be positioned, and is measured from the finish of service of the last request to the beginning of the data transfer for the present request. A detailed study of the shortest access time queue is made, giving the minimum access time probability distribution, equations for the number in the queue, and equations for the wait in the queue. Simulations were used to verify these equations; the results are discussed. Finally, a general Markov Model for Queues is discussed in an Appendix.

Calculaid: An On-line System for Algebraic Computation and Analysis

Wed, 01 Sep 1965 00:00:00 GMT

Calculaid: An On-line System for Algebraic Computation and Analysis Wantman, Mayer Elihu OPS is an on-line system developed by M. Greenberger et al. at Project MAC. The present work provides a powerful and simple way to perform numerical manipulations and calculations within OPS. The program package is called CALCULAID. A method of executing algebraic assignment statements, of which MAD and FORTRAN assignments are a subset, is provided. When this assignment-statement ability is coupled with other features of the OPS system, such as unconditional transfers, general conditionals, and array and function declarations, most of the ability of a compiler language is provided. Because the programs written in OPS are executed interpretively, OPS-3 programs can be changed and re-run immediately, without being compiled. The other elements of CALCULAID are a program for creating multiple linear regression models, rank-ordering and counting data, and finding roots to polynomial equations in one unknown. The applications of CALCULAID to the analysis of a round-robin scheduling model and to a process-control problem are discussed, and conclusions regarding the suitability of running computational programs in an interpretive mode are drawn.

A Heuristic Approach to Alternate Routing in a Job Shop

Tue, 01 Jun 1965 00:00:00 GMT

A Heuristic Approach to Alternate Routing in a Job Shop Russo, F.J. The research reported here investigates the use of heuristics for selecting from several alternate routes resulting from partially ordered tasks in a job shop order file. The experimental vehicle employed was digital simulation. The concept of the "Alternate string" has been developed to generalize the existence of partially ordered operations. That term is defined as a concatenation of operations that can be performed in any order, with the additional specification that all within the string can be attempted. The presence of alternate strings with two or more member gives rise to the alternate routing problem, whose solution is approached by heuristic methods. Choosing from among several alternate routes constitutes a three level decision problem. At the lowest level, routes can be chosen when the order enters the shop. This is equivalent to fixed routing. At a higher level, alternates can be selected at the time of transition from one work station to another. The third decision level occurs at operation time, when one of the alternate operations is placed on a machine. Heuristics were tested at the latter two levels. There were two prior assertions that this thesis set out to prove. The first was that alternate routing at the highest decision level would produce significant reductions in the mean tardiness of orders completed past their designated due dates, the improvement being both relative to fixed routing and to alternate routing heuristics implemented at lower decision levels. Secondly, the contention was made that the improvement would be as such a magnitude that on-line, real-time systems become economically justifiable as a means of mitigating the attendant control problems caused by non-deterministic paths through the queuing network. The methodology employed here was to conduct two passes of simulated shop runs. The first, with two artificially high levels of alternate incidence, tested the efficiency of five different alternate routing heuristics in reducing mean tardiness. The second pass consisted of runs with the best heuristic developed during the first experimental phase applied to a realistic length and frequency of alternate strings. The results of the experiments strongly support the assertions made at the outset of the thesis. The performance characteristics of the different heuristics are discussed at length. In addition, some implications are drawn of the computational nature of alternate routing and the difficulties encountered in implementing alternate routing heuristics at operation time.

An Analysis of Time-Shared Computer Systems

Tue, 01 Jun 1965 00:00:00 GMT

An Analysis of Time-Shared Computer Systems Scherr, Allan Lee Some of the aspects of the operation of time-shared, interactive computer systems are analyzed. The emphasis is on the reaction of hardware systems to the demands that its users make upon it. Simply shared systems and their users in order to be able to predict the performance of the two operating together. Portions of this problem include the specification and measurement of user characteristics, the development and verification of both simulation and mathematical models for time-shared systems, and the specification and measurement of performance metrics for such systems. The user and some of the performance measurements were made on Project MAC's "Compatible Time-Sharing System" (CTSS). First, simulation models are used to study the effects of changing small details in the operation of CTS-like systems. Then, a continuous-time Markov process model is derived to predict the performance of a broad class of systems. Throughout, the CTSS data are used as a basis for comparison with model predictions. In order to be able to take measurements and to build models, many definitions of commonly used time-shared system terminology are made precise.

Time Sharing on a Multiconsole Computer

Mon, 01 Mar 1965 00:00:00 GMT

Time Sharing on a Multiconsole Computer Samuel, Arthur L. After a brief historical review and a description of the three basic types for time-sharing systems, the general purpose time-sharing system as exemplified by the M.I.T. CTSS system is described in general terms, with particular attention to the way the system looks to the user.

CTSS Technical Notes

Mon, 01 Mar 1965 00:00:00 GMT

CTSS Technical Notes Saltzer, Jerome H. This report is a technical description of the 7094 Compatible Time-Sharing System in use at Project MAC and the M.I.T. Computation Center. It is designed to acquaint a system programmer with the techniques of construction which were used in this particular time-sharing system. Separate chapters discuss the overall supervisor program flow: console message input and output: the scheduling and storage algorithms: and a thumbnail sketch is given of each of the subroutines which make up the supervisor program. This report was prepared with the aid of the compatible time-sharing system and the TYPSET and RUNOFF commands.

Use of CTSS in a Teaching Environment

Sun, 01 Nov 1964 00:00:00 GMT

Use of CTSS in a Teaching Environment Roos, Daniel Computer time-sharing offers many interesting possibilities for use in teaching computer technology. It might be expected that with proper hardware and software, students using time-sharing as a teaching machine could acquire proficiency in the fundamentals of programming more easily than using batch-processing. To test this hypothesis, the M.I.T. Department of Civil Engineering divided a freshman programming class so that half the students used batch-processing methods, and half used the Project MAC time-sharing system to do the same work. This paper describes the experiment and its tentative results.

A New Methodology for Computer Simulation

Thu, 01 Oct 1964 00:00:00 GMT

A New Methodology for Computer Simulation Greenberger, Martin Computer simulation is a cooperative venture between researcher and information processor, but the processor's role customarily begins too late. The researcher can benefit substantially by bringing the computer up into the earlier, creative phases of the simulation process. An on-line computer system that makes this possible is described.

The MAC System: A Progress Report

Thu, 01 Oct 1964 00:00:00 GMT

The MAC System: A Progress Report Fano, Robert M. The notion of machine-aided cognition implies an intimate collaboration between a human user and a computer in a real-time dialogue on the solution of a problem, in which the two parties contribute their best capabilities. In order for this intimate collaboration to be possible, a computer system is needed that can serve simultaneously a large number of people, and that is easily accessible to them, both physically and intellectually. The present MAC System is a first step toward this goal. The purpose of this paper is to present a brief description of the current system, to report on the experience gained from its operation, and to indicate directions along which future developments are like to proceed.

Program Structure in a Multi-access Computer

Fri, 01 May 1964 00:00:00 GMT

Program Structure in a Multi-access Computer Dennis, Jack B. A multi-access computer (MAC) system consists of processing units and directly addressable main memory in which procedure information is interpreted as sequences of operations on data, a system of terminal devices through which users may communicate with procedures operating for them, and mass memory where procedures and data may be held when not required for immediate reference. One fundamental attraction of the MAC concept is the increased productivity of "computer catalyzed research" that results from close man-machine interaction. Another attraction is wealth of data and procedures that are accessible to a large user community through the file memory of a MAC system. In this report thoughts are developed which form an adequate model of program structure. These concepts have grown out of many discussions with colleges in Project MAC, and our experience to date in the design and operation of multi-access computer systems.

The OPS-1 Manual

Fri, 01 May 1964 00:00:00 GMT

The OPS-1 Manual Greenberger, Martin The recent attainment and continuing development of personally accessible computer facilities have opened another chapter in the use of machines by man. A number of current research efforts, including Project MAC at M.I.T., are designing new conceptual systems to adapt the emerging technology to a wide range of human activity. Activities relating to management are the concern of a trial system at Project MAC called OPS-1. The OPS-1 system and the experiment that launched it are described in this manual. {AD 604-681}

OPL-I An Open Ended Programming System Within CTSS

Wed, 01 Jan 1964 00:00:00 GMT

OPL-I An Open Ended Programming System Within CTSS Weizenbaum, Joseph OPL-1, an incremental programming system presently operating with CTSS, permits the user to augment both his program and his data base during widely separated successive sessions at his terminal. Facilities are provided which make it possible for the user to operate on his already established data base both by means of built-in operators and in terms of operators (functions) which the user has previously defined in the language of the system. Underlying the system is a powerful list processing scheme embedded in FORTRAN (SLIP). The machinery of this fundamental language drives the system and is also largely available to the user. The data base generated by the user is therefore a set of list structures (trees), and most of the operators available to him are list processing operators. Data structures with considerably complex inter-relational properties may therefore be treated quite directly.

Stress: A Problem-oriented Language for Structural Engineering

Fri, 01 Jul 1966 00:00:00 GMT

Stress: A Problem-oriented Language for Structural Engineering Biggs, John M.; Logcher, Robert D. STRESS is a general purpose programming system for the analysis of structures. Compared to most other structural programs it has three distinguishing characteristics: (1) The input language is that of the structural engineer which makes possible direct communication between the engineer and the machine; (2) The system is capable of analyzing a wide variety of structural types and loading conditions thus permitting industrial use on a routine basis; and (3) The design process is expedited by the fact that modifications of the original structure for alternate designs can be easily executed. This last capability is most effective when STRESS is used in the time-sharing mode. These features combine to provide a system which not only reduces the effort required for structural analysis but, more significantly, enhances the designer's ability to evolve an efficient structure.

CARPS, A Program Which Solves Calculus Word Problems

CARPS, A Program Which Solves Calculus Word Problems Charniak, Eugene

Verbal and Graphical Language for the AED System: A Progress Report

Fri, 01 May 1964 00:00:00 GMT

Verbal and Graphical Language for the AED System: A Progress Report Ross, Douglas T.; Feldman, Clarence G. For Computer-Aided Design, use of time-sharing a single language which can take either verbal or graphical form is required. This paper describes how a single language processing technique, which is in turn a special application of more general concepts concerning the step-by-step growth and processing of large structures of interrelated elements, can efficiently process both language forms in the same manner. Illustrations of the concepts involved are also drawn from the methods used in the AED-O Compiler, an efficient ALGOL-60-based compiler used in Computer-Aided Design work, which is available as a public command in the Project MAC CTSS.

System Requirements for Multiple -Access, Time-shared Computers

Fri, 01 May 1964 00:00:00 GMT

System Requirements for Multiple -Access, Time-shared Computers Corbató, Fernando J. It is now clear that it is possible to create a general-purpose time-shared multiple access system on most contemporary computers. However, it is equally clear that none of the existent computers are well designed for multiple access systems. At present, good service to a few dozen simultaneous users is considered state-of-the-art. Discussions include: clocks, memory protection and supervisor mode, program relocation and common subroutines which expose the reader to the difficulties encountered with contemporary machines when multiple user multiple-processor systems are considered.

SIR: A Computer Program for Semantic Information Retrieval

Mon, 01 Jun 1964 00:00:00 GMT

SIR: A Computer Program for Semantic Information Retrieval Raphael, Bertram SIR is a computer system, programmed in the LISP language, which accepts information and answers questions expressed in a restricted form of English. This system demonstrates what can reasonably be called an ability to "understand" semantic information. SIR's semantic and deductive ability is based on the construction of an internal model, which uses word associations and property lists, for the relational information normally conveyed in conversational statements. A format-matching procedure extracts semantic content from English sentences. If an input sentence is declarative, the system adds appropriate information to the model. If an input sentence is a question, the system searches the model until it either finds the answer or determines why it cannot find the answer. In all cases SIR reports its conclusions. The system has some capacity to recognize exceptions to general rules, resolve certain semantic ambiguities, and modify its model structure in order to save computer memory space. Judging from its conversational ability, SIR is more "intelligent" than any existing question-answering system. The author describes how this ability was developed and how the basic features of SIR compare with those of other systems. The working system, SIR , is a first step toward intelligent machine communication. The author proposes a next step by describing how to construct a more general system which is less complex and yet more powerful than SIR . This proposed system contains a generalized version of the SIR model, a formal logical system called SIR1 , and a computer program for testing the truth of SIR1 statements with respect to the generalized model by using partial proof procedures in the predicate calculus. The thesis also describes the formal properties of SIR1 and how they relate to the logical structure of SIR .

Natural Language Input for a Computer Problem Solving System

Tue, 01 Sep 1964 00:00:00 GMT

Natural Language Input for a Computer Problem Solving System Bobrow, Daniel .G The STUDENT problem solving system, programmed in LISP, accepts as input a comfortable but restricted subset of English which can express a wide variety of algebra story problems. STUDENT finds the solution to a large class of these problems. STUDENT can utilize a store of global information not specific to any one problem, and may make assumptions about the interpretation of ambiguities in the wording of the problem being solved. If it uses such information, or makes any assumptions, STUDENT communicates this fact to the user. The thesis includes a summary of other English language question-answering systems. All these systems, and STUDENT are evaluated according to four standard criteria. The linguistic analysis in STUDENT is a first approximation to the analytic portion of a semantic theory of discourse outlined in the thesis. STUDENT finds the set of kernel sentences which are the base of the input discourse, and transforms this sequence of kernel sentences into a set of simultaneous equations which form the semantic base of the Student system. STUDENT then tries to solve this set of equations for the values of requested unknowns. If it is successful it gives the answers in English. If not, STUDENT asks the user for more information, and indicates the nature of the desired information. The STUDENT system is a first step toward natural language communication with computers. Further work on the semantic theory proposed should result in much more sophisticated systems.

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.

CARPS: A Program which Solves Calculus Word Problems

Mon, 01 Jul 1968 00:00:00 GMT

CARPS: A Program which Solves Calculus Word Problems Charniak, Eugene A program was written to solve calculus word problems. The program, CARPS (CALculus Rate Problem Solver), is restricted to rate problems. The overall plan of the program is similar to Bobrow's STUDENT, the primary difference being the introduction of "structures" as the internal model in CARPS. Structures are stored internally as trees. Each structure is designed to hold the information gathered about one object. A description of CARPS is given by working through two problems, one in great detail. Also included is a critical analysis of STUDENT.

A Modern Differential Geometric Approach to Shape from Shading

Thu, 01 Jun 1989 00:00:00 GMT

A Modern Differential Geometric Approach to Shape from Shading Saxberg, Bror V. H. How the visual system extracts shape information from a single grey-level image can be approached by examining how the information about shape is contained in the image. This technical report considers the characteristic equations derived by Horn as a dynamical system. Certain image critical points generate dynamical system critical points. The stable and unstable manifolds of these critical points correspond to convex and concave solution surfaces, giving more general existence and uniqueness results. A new kind of highly parallel, robust shape from shading algorithm is suggested on neighborhoods of these critical points. The information at bounding contours in the image is also analyzed.