MAC Technical Reports (1963 - 1974)

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.

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.