TM-198 ``The Propositional Dynamic Logic of Deterministic, Well-Structured Programs'' by J.Y. Halpern and J.H. Reif, March 1981. We consider a restricted propositional dynamic logic, Strict Deterministic Propositional Dynamic Logic (SDPDL), which is appropriate for reasoning about deterministic well-structured programs. In contrast to PDL, for which the validity problem is known to be complete in deterministic exponential time, the validity problem for SDPDL is shown to be polynomial space complete. We also show that SDPDL is less expensive than PDL. The results rely on structure theorems for models of satisfiable SDPDL formulas, and the proofs give insight into the effects of nondeterminism on intractability and expressiveness in program logics. TM-197 ``Conservative Logic'' by E. Fredkin and T. Toffoli, May 1981, AD A101 383. Conservative logic is a comprehensive model of computation which explicitly reflects a number of fundamental principles of physics, such as the reversibility of the dynamical laws and the conservation of certain additive quantities. Because of its closer adherence to physics than found in traditional models of computation, conservative logic is in a better position to provide indications concerning the realizations of high performance computing systems, i.e., of systems that make very efficient use of the "computing resources" actually offered by nature. In particular, conservative logic shows that it is ideally possible to build sequential circuits with zero internal power dissipation. TM-196 ``On Concentration and Connection Networks'' by S.N. Bhatt (S.M. Thesis), March 1981. This thesis deals with the structural complexity of switching networks which realize concentration and connection requests when operated in a rearrangeable or incremental manner. Some of the important results and constructions are briefly reviewed. TM-195 ``Record of the Workshop on Research in Office Semantics'' by G.R. Barber, Feb. 1981. This paper is a compendium of the ideas and issues presented at the Chatham Bars Workshop on Office Semantics. The intent of the workshop was to examine the state of the art in office systems and to elucidate the issues system designers were concerned with in developing next generation office systems. The workshop involved a cross-section of people from government, industry and academia. Presentations in the form of talks and video tapes were made of prototypical systems. TM-194 ``Recursion Theoretic Operators and Morphisms on Numbered Sets'' by H. Barendregt and G. Longo, Feb. 1981. TM-193 ``Algebraic Dependencies'' by M. Yannakakis and C.H. Papadimitriou, Feb. 1981. TM-192 ``The Deducibility Problem in Propositional Dynamic Logic'' by A.R. Meyer, R.S. Streett and G. Mirkowska, Feb. 1981. TM-191 ``Propositional Dynamic Logics of Programs: A Survey'' by R. Parikh, Jan. 198l. TM-190 ``Deterministic Propositional Dynamic Logic: Finite Models, Complexity, and Completeness'' by M. Ben-Ari, J.Y. Halpern and A. Pnueli, Jan. 1981. TM-189 ``Persistence of Vector Replacement Systems is Decidable'' by E. Mayr, Jan. 1981. In a persistent vector replacement system (VRS) or Petri net, an enabled transition can become disabled only by firing itself. Here, an algorithm is presented which allows to decide whether an arbitrary VRS is persistent or not, and if so, to construct a semilinear representation of the set of states reachable in the system. TM-188 ``An Effective Representation of the Reachability Set of Persistent Petri Nets'' by E. Mayr, Jan. 1981. In a persistent net, an enabled transition can become disabled only by firing itself. Here, an algorithm is presented which constructs a semilinear representation of the set of states reachable in an arbitrary persitent Petri net. TM-187 ``W(n log n) Lower Bounds on Length of Boolean Formulas'' by M.J. Fischer, A.R. Meyer and M.S. Paterson, Nov. 1980. TM-186 ``BRAND X Manual'' by P. Szolovits and W.A. Martin, Nov. 1980, AD A093-041/2. BRAND X is a simple representation language implemented as a pure extension of LISP. BRAND X provides the following additional facilities over LISP: Unique and canonical structures, property lists for all objects, labels for all objects, and a syntax to express each of these, supported by a reader and printer. BRAND X is intended as an "assembly language" for representation languages, attempting to provide facilities generally found useful in the simplest manner, without any strong commitment to specific representational conventions. *TM-185 ``An Optimality Theory of Concurrency Control for Databases'' by H.T. Kung and C.H. Papadimitriou, Nov. 1980, AD A092-625. *TM-184 ``A Real Time Garbage Collector that Can Recover Temporary Storage Quickly'' by H. Lieberman and C. Hewitt, Oct. 1980. TM-183 ``A Note on the Length of Craig's Interpolants'' by A.R. Meyer, Oct. 1980. TM-182 ``Hamilton Paths in Grid Graphs'' by A. Itai, C.H. Papadimitriou and J.L. Szwarefiter, Oct. 1980. A grid path is a node-induced finite subgraph of the infinite grid. It is rectangular if its set of nodes is the product of two intervals. Given a rectangular grid graph and two of its nodes, we give necessary and sufficient conditions for the graph to have a Hamilton path between these two nodes. In contrast, the Hamilton path (and circuit) problem for general grid graphs is shown to be NP-complete. This provides a new, relatively simple, proof of the result that the Euclidean traveling salesman problem is NP-complete. TM-181 ``A Fast Algorithm for Testing for Safety and Detecting Deadlocks in Locked Transaction Systems'' by W. Lipski, Jr. and C.H. Papadimitriou, Oct. 1980. TM-180 ``A Theorem in Database Concurrency Control'' by C.H. Papadimitriou, Oct. 1980. TM-179 ``Axiomatic Definitions of Programming Languages, II'' by J.Y. Halpern and A.R. Meyer, Oct. 1980. TM-178 ``I-Structures: An Efficient Data Type for Functional Languages'' by Arvind and R.E. Thomas, Sept. 1980. TM-177 ``TIMEPAD - A Performance Improving Synchronisation Mechanism for Distributed Systems'' by M.K. Sinha, Sept. 1980. A new mechanism for the synchronisation of accesses to distributed data objects is developed. This mechanism, called timepad, is an extension to the timestamp synchronisation scheme and it encaches the concurrency transparency requirement of the user reducing the chance of eventual rejection of a transaction. The timepad scheme will improve the performance of those distributed database systems where the probability of transactions clashing is high. We also discuss how the timepad mechanism can be used as an approximation pad to solve problems which need approximate solution. *TM-176 ``A Semantics of Synchronization'' by C.R. Seaquist (S.M. Thesis), Sept. 1980, AD A091-015. TM-175 ``On Time Versus Space III'' by A.R. Meyer, D. Weise and M.C. Loui, Sept. 1980. Paul and Reischuk devised space efficient simulations of logarithmic cost random access machines and multidimensional Turing machines. We simplify their general space reduction technique and extend it to other models of computation, particularly to the class of storage modification machines (SMM), a model of list processing. TM-174 ``A Dataflow Architecture with Tagged Tokens'' by Arvind, V. Kathail and K. Pingali, Sept. 1980. We are designing a system based on dataflow principles in which each processing element contains a part of the program, and processors communicate by sending information packets to each other. We also present arguments as to why our architecture can tolerate long average delays in the communication network without affecting the overall performance. Schemes for mapping programs onto this machine are also discussed briefly. *TM-173 ``XLMS: A Linguistic Memory System'' by L.B. Hawkinson, Sept. 1980, AD A090-033. TM-172 ``Some New Methods of Music Synthesis'' by W.G. Paseman (S.M. Thesis), August 1980, AD A090-130. The first section discusses music composition, shows why it is a useful domain for Artificial Intelligence research and presents a set of "Design Rules" that facilitate research in the field of tonal music composition. The second section describes some of the problems and issues encountered while designing the initial hardware for the Music Aided Cognition Project at MIT. All of the developed hardware permits computer control, performance and recording of music in real time. *TM-171 ``What is a Model of the Lambda Calculus?'' by A.R. Meyer, August 1980. TM-170 ``Pumping Lemmas for Regular Sets'' by A. Ehrenfeucht, R. Parikh and G. Rozenberg, August 1980. It is well known that regular languages satisfy certain conditions known as pumping lemmas or iteration theorems. However, the question of the converse result has been open. We show that the usual form of the pumping lemma falls very far short of implying regularity, but that there is a form, which we have called the block pumping property, that is equivalent to regularity. TM-169 ``LOOP Iteration Macro'' by G. Burke and D. Moon, July 1980 (revised Jan. 1981), AD A087-372. LOOP is a Lisp macro which provides a programmable iteration facility. The same LOOP module operates compatibly in both Lisp Machine Lisp and Maclisp (PDP-10 and Multics). LOOP was inspired by the "FOR" facility and CLISP in Interlisp; however, it is not compatible and differs in several details. TM-168 ``Programs for Distributed Computing: The Calendar Application'' by I.Greif, July 1980, AD A087-357. The calendar application involves a wide range of issues in distributed computing, from implementation of distributed data bases to design of a user interface that will enable the user to comprehend the complex distributed environment in which he is working. This memo summarizes current status of design and implementation of calendars. TM-167 ``Computer Programs for Research in Gravitation and Differential Geometry'' by R. Pavelle and M. Wester, June 1980. This report contains a description of all current functions and features of the programs CTENSR and ITENSR which are available with MACSYMA. TM-166 ``Report on the Workshop on Self-Timed Systems'' by R.E. Bryant, May 1980. The Workshop on Self-Timed Systems was held at MIT Endicott House on July 8-12, 1979. This workshop served to bring together experts in the field of self-timed systems to review and assess the state of the art and to chart directions for future research. For the purpose of the workshop, self-timed systems were defined to include any system composed of a set of modules which communicate asynchronously. TM-165 ``Theory and Practice of Text Editors or A Cookbook for an Emacs'' by C.A. Finseth (S.B. Thesis), May 1980. A comprehensive summary of the available technology for implementing text editors. It is written to be a guide for the implementor of a text editor. It does not provide a finished, polished algorithm for any part of a text editor. Rather, it provides a breakdown of the problems involved and discusses the pitfalls and the available tradeoffs to be considered when designing a text editor. Specific reference is made to the relevant tradeoffs for an Emacs-type editor, a character-oriented, extensible display editor. *TM-164 ``The Cryptographic Security of Compact Knapsacks (Preliminary Report)'' by A. Shamir, April 1980, AD A084-456. *TM-163 ``Axiomatic Definitions of Programming Languages: A Theoretical Assessment'' by A.R. Meyer and J.Y. Halpern, April 1980. TM-162 ``A Manager for Named, Permanent Objects'' by A.M. Marcum (S.B. & S.M. Thesis), April 1980, AD A083-491. This report describes an object-oriented filing system which stores abstract objects, rather than storing some external representation of the abstractions. TM-161 ``Critical Path Scheduling of Task Systems with Resource and Processor Constraints'' by E.L. Lloyd, March 1980. In this paper we investigate the performance of critical path scheduling for UET task systems with resources and a fixed number of processors. An upper bound for the worst case performance of critical path scheduling is given. This bound depends both on the number of processors and on the number of different resources. Moreover, we show that this is the best possible (asymptotic) upper bound. TM-160 ``On the Computational Complexity of Cardinality Constraints in Relational Databases'' by P.C. Kanellakis, March 1980. We show that the problem of determining whether or not a lossless join property holds for a database, in the presence of key dependencies and cardinality constraints on the domains of the attributes is NP-complete. TM-159 ``Dynamic Algebras and the Nature of Induction'' by V.R. Pratt, March l980. Dynamic algebras constitute the variety (equationally defined class) of models of the Segerberg axioms for propositional dynamic logic. We obtain the following results (to within inseparability). (i) In any dynamic algebra * is reflexive transitive closure. (ii) Every free dynamic algebra can be factored into finite dynamic algebras. (iii) Every finite dynamic algebra is isomorphic to a Kripke structure. (ii) and (iii) imply Parikh"s completeness theorem for the Segerberg axioms. We also present an approach to treating the inductive aspect of recursion within dynamic algebras. TM-158 ``Semaphore Primitives and Starvation-Free Mutual Exclusion'' by E.W. Stark (S.M. Thesis), March 1980. This thesis attempts to alleviate some of the confusion by giving precise definitions of two varieties of semaphore primitives; here called weak and blocked-set primitives. It is then shown that under certain natural conditions, although it is possible to implement starvation-free mutual exclusion with blocked-set semaphores, it is not possible to do so with weak semaphores. Thus weak semaphores are strictly less "powerful" than blocked-set semaphores. TM-157 ``On the Expressive Power of Dynamic Logic'' by A.R. Meyer and K. Winklmann, Feb. 1980. We show that "looping" of while-programs can be expressed in Regular First Order Dynamic Logic, disproving a conjecture made by Harel and Pratt. In addition we show that the expressive power of quantifier-free Dynamic Logic increases when nondeterminism is introduced in the programs that are part of formulae of Dynamic Logic. Allowing assignments of random values to variables also increases expressive power. TM-156 ``Definability in Dynamic Logic'' by A.R. Meyer and R. Parikh, Feb. 1980. TM-155 ``Covering Graphs by Simple Circuits'' by A. Atai, R.J. Lipton, C.H. Papadimitriou and M. Rodeh, Feb. 1980. TM-154 ``On Linear Characterizations of Combinatorial Optimization Problems'' by R.M. Karp and C.H. Papadimitriou, Feb. 1980. We show that there can be no computationally tractable description by linear inequalities of the polyhedron associated with any NP-complete combinatorial optimization problem unless NP=co-NP -- a very unlikely event. We also use the recent result by Khachian to present even stronger evidence that NP-complete combinatorial optimization problems cannot have efficient generators of violated inequalities. TM-153 ``Worst-Case and Probabilistic Analysis of a Geometric Location Problem'' by C.H. Papadimitriou, Feb. 1980. TM-152 ``On the Complexity of Integer Programming'' by C.H. Papadimitriou, Feb. 1980. We give a simple proof that integer programming is in NP. Our proof also establishes that there is a pseudopolynomial time algorithm for integer programming with any (fixed) number of constraints. *TM-151 ``Reversible Computing'' by T. Toffoli, Feb. 1980, AD A082-021. TM-150 ``Ten Thousand and One Logics of Programming'' by A.R. Meyer, Feb. 1980. *TM-149 ``An Efficient Algorithm for Determining the Length of the Longest Dead Path in an "Lifo" Branch-and-Bound Exploration Schema'' by S. Pallottino and T. Toffoli, Jan. 1980, AD A079-912. TM-148 ``Space-Bounded Simulation of Multitape Turing Machines'' by L.M. Adleman and M.C. Loui, Jan. 1980. A new proof of a theorem of Hopcroft, Paul and Valiant is presented: every deterministic multitape Turing machine of time complexity T(n) can be simulated by a deterministic Turing machine of space complexity T(n)/log T(n). The proof includes an overlap argument. TM-147 ``A T = 0(2^[n/2]), S = 0(2^[n/4]) Algorithm for Certain NP-Complete Problems'' by R. Schroeppel and A. Shamir, Jan. 1980, AD A080-385. TM-146 ``A Machine Language Instruction Set for a Data Flow Processor'' by D.J. Aoki (S.M. Thesis), Dec. 1979. TM-145 ``A Space Bound for One-Tape Multidimensional Turing Machines'' by M.C. Loui, Nov. 1979. TM-144 ``Concurrent and Reliable Updates of Distributed Databases'' by A.Takagi, Nov. 1979. TM-143 ``An Intermediate Form for Data Flow Programs'' by J.W. Leth (S.M. Thesis), Nov. 1979. *TM-142 ``On Data Bases with Incomplete Information'' by W. Lipski, Jr., Oct. 1979. TM-141 ``On Database Management System Architecture'' by M. Hammer and D. McLeod, Oct. 1979, AD A076-417. TM-140 ``Artificial Intelligence and Clinical Problem Solving'' by P. Szolovits, Sept. 1979. TM-139 ``Roles, Co-Descriptors and the Formal Representation of Quantified English Expressions'' by W.A. Martin, Sept. 1979, revised May 1980, AD A074-625. TM-138 ``Dynamic Algebras: Examples, Constructions, Applications'' by V.R. Pratt, July 1979. TM-137 ``Algorithms for Scheduling Tasks on Unrelated Processors'' by E. Davis and J.M. Jaffe, June 1979. TM-136 ``Report on the Second Workshop on Data Flow Computer and Program Organization'' by D.P. Misunas, June 1979. The following report comprises an edited transcription of presentations made at the Second Workshop on Data Flow Computer and Program Organization, held at MIT on July 9-13, 1978, and co-sponsored by the Lawrence Livermore Laboratory (LLL) and the Department of Energy, Mathematical Sciences Branch. These informal transcriptions are only intended to provide a general picture of ongoing work in the area, and to that end, have been heavily edited and often summarized. TM-135 ``Timestamps and Capability-Based Protection in a Distributed Computer Facility'' by R.H. Wyleczuk (S.B. & S.M. Thesis), June 1979. *TM-134 ``How to Share a Secret'' by A. Shamir, May 1979, AD A069-397. TM-133 ``The Space Complexity of Two Pebble Games on Trees'' by M.C. Loui, May 1979. In the standard pebble game the number of pebbles required to pebble the root of a tree can be computed in time linearly proportional to the number of nodes. For the black/white pebble game the number of pebbles necessary to pebble root of a complete tree is derived. TM-132 ``Design of a Program for Expert Diagnosis of Acid Base and Electrolyte Disturbances'' by R. Patil, May 1979. This research develops the diagnostic component of an interactive system for providing expert advice for the diagnosis, therapy and ongoing management of patients with acid-base and electrolyte disturbances. *TM-131 ``Time, Space and Randomness'' by L.M. Adleman, March 1979. TM-130 ``Specifying the Semantics of While-Programs: A Tutorial and Critique of a Paper by Hoare and Lauer'' by I. Greif and A. Meyer, April 1979, AD A068-967. TM-129 ``On the Cryptocomplexity of Knapsack Systems'' by A. Shamir, April 1979, AD A067-972. TM-128 ``Minimum Register Allocation is Complete in Polynomial Space'' by M.G. Loui, March 1979. TM-127 ``A Network Traffic Generator for Decnet'' by R.J. Strazdas (S.B. & S.M. Thesis), March 1979. TM-126 ``With What Frequency Are Apparently Intractable Problems Difficult?'' by A.R. Meyer and M.S. Paterson, Feb. 1979. TM-125 ``Mental Poker'' by A. Shamir, R.L. Rivest and L.M. Adleman, Feb. 1979, AD A066-331. Is it possible to play a fair game of "Mental Poker?" We will give a complete (but paradoxical) answer to this question. We will first prove that the problem is intrinsically insoluble, and then describe a fair method of playing "Mental Poker." TM-124 ``Bicontinuous Extensions of Invertible Combinatorial Functions'' by T. Toffoli, Jan. 1979, AD A063-886. We discuss and solve the problem of constructing a diffeomorphic componentwise extension for an arbitrary invertible combinatorial function. Interpreted in physical terms, our solution constitutes a proof of the physical realizability of general computing mechanisms based on reversible primitives. TM-123 ``An Improved Proof of the Rabin-Hartmanis-Stearns Conjecture'' by H.M. Perry (S.M. & E.E. Thesis), Jan. 1979. TM-122 ``Efficient Scheduling of Tasks Without Full Use of Processor Resources'' by J. Jaffe, Jan. 1979. The nonpreemptive scheduling of a partially ordered set of tasks on a machine with m processors of different speeds is studied. Heuristics are presented which benefit from selective non-use of slow processors. *TM-121 ``The Equivalence of R. E. Programs and Data Flow Schemes'' by J. Jaffe, Jan. 1979. *TM-120 ``Operational Semantics of a Data Flow Language'' by J.D. Brock (S.M. Thesis), Dec. 1978, AD A062-997. TM-119 ``On the Security of the Merkle-Hellman Cryptographic Scheme'' by A. Shamir and R.E. Zippel, Dec. 1978, AD A063-104. *TM-118 ``Data Model Equivalence'' by S.A. Borkin, Dec. 1978, AD A062-753. TM-117 ``Six Lectures on Dynamic Logic'' by V.R. Pratt, Dec. 1978. TM-116 ``Applications of Modal Logic to Programming'' by V.R. Pratt, Dec. 1978. *TM-115 ``Concurrent Programming'' by R.E. Bryant and J.B. Dennis, Oct. 1978, AD A061-180. *TM-114 ``Research Directions in Computer Architecture'' by J.B. Dennis, S.H. Fuller, W.B. Ackerman, R.J. Swan and Kung-Song Weng, Sept. 1978, AD A061-222. TM-113 ``A Near-optimal Method for Reasoning about Action'' by V.R. Pratt, Sept. 1978. *TM-112 ``A Decidability Result for a Second Order Process Logic'' by R. Parikh, Sept. 1978. TM-111 ``Bounds on the Scheduling of Typed Task Systems'' by J.M. Jaffe, Sept. l978. TM-110 ``An Analysis of Preemptive Multiprocessor Job Scheduling'' by J.M. Jaffe, Sept. l978. *TM-109 ``Effectiveness'' by R. Parikh, July 1978. TM-108 ``An Analysis of the Solovay and Strassen Test for Primality'' by A.E. Baratz, July 1978. *TM-107 ``A Fast Signature Scheme'' by A. Shamir, July 1978, AD A057-152. *TM-106 ``A Completeness Result for a Propositional Dynamic Logic'' by R. Parikh, July 1978. *TM-105 ``A Faster Algorithm Computing String Edit Distances'' by W.J. Masek and S.M. Paterson, May 1978. *TM-104 ``The Use of Queues in the Parallel Data Flow Evaluation of "If-Then-While" Programs'' by J. Jaffe, May 1978. *TM-103 ``Arithmetical Completeness in Logics of Programs'' by D. Harel, April 1978. *TM-102 ``Lower Bounds on Information Transfer in Distributed Computations'' by H. Abelson, April 1978. *TM-101 ``Descriptions and the Specialization of Concepts'' by W.A. Martin, March 1978, AD A052-773. TM-100 ``A Computer Architecture for Data-Flow Computation'' by D.P. Misunas (S.M. Thesis), March 1978, AD A052-538. TM-99 ``The Subgraph Homeomorphism Problem'' by A.S. LaPaugh (S.M. Thesis), Feb. 1978. TM-98 ``Nondeterminism in Logics of Programs'' by D. Harel and V.R. Pratt, Feb. l978. TM-97 ``Computability and Completeness in Logics of Programs'' by D. Harel, A.R. Meyer and V.R. Pratt, Feb. 1978. *TM-96 ``A Complete Axiomatic System for Proving Deductions about Recursive Programs'' by D. Harel, A. Pnueli and J. Stavi, Feb. 1978. *TM-95 ``Characterizing Second Order Logic with First Order Quantifiers'' by D. Harel, Feb. 1978. *TM-94 ``A Dynamic Debugging System for MDL'' by J.M. Berez (S.B. Thesis), Jan. 1978, AD A050-191. *TM-93 ``A Logic Design for the Cell Block of a Data-Flow Processor'' by K. Amikura (S.M. Thesis), Dec. 1977. *TM-92 ``Report on the Workshop on Data Flow Computer and Program Organization'' by D.P. Misunas, Nov. 1977. *TM-91 ``Factoring Numbers in 0 (log n) Arithmetic Steps'' by A. Shamir, Nov. 1977, AD A047-709. *TM-90 ``An Analysis of Computer Decentralization'' by C.R. d'Oliveira (S.B. Thesis), Oct. 1977, AD A045-526. *TM-89 ``Measuring User Characteristics on the Multics System'' by H. Rodriguez, Jr. (S.B. Thesis), August 1977. TM-88 ``On Triangulations of a Set of Points in the Plane'' by E.L. Lloyd (S.M. Thesis), July 1977. *TM-87 ``Ancillary Reports: Kernel Design Project'' by D.D. Clark, editor, June 1977. TM-86 ``An Overview of OWL, A Language for Knowledge Representation'' by P. Szolovits, L.B. Hawkinson and W.A. Martin, June 1977, AD A041-372. *TM-85 ``Finding Minimum Cutsets in Reducible Graphs'' by A. Shamir, June 1977, AD A040-698. *TM-84 ``The Mutual Exclusion Problem for Unreliable Processes'' by R.L. Rivest and V.R. Pratt, April 1977. TM-83 ``Construction and Analysis of Network Flow Problem which Forces Karzanov Algorithm to 0(n^3) Running Time'' by A.E. Baratz, April 1977. *TM-82 ``A Method for Obtaining Signatures and Public-Key Cryptosystems'' by R.L. Rivest, A. Shamir and L. Adleman, April 1977, AD A039-036. TM-81 ``Hardware Estimation of a Process' Primary Memory Requirements'' by D.K. Gifford (S.B. Thesis), Jan. 1977. TM-80 ``The Max Flow Algorithm of Dinic and Karzanov: An Exposition'' by S. Even, Dec. 1976. *TM-79 ``A System to Process Dialogue: A Progress Report'' by G.P. Brown, Oct. 1976, AD A033-276. *TM-78 ``Improving Information Storage Reliability Using a Data Network'' by A.J. Benjamin (S.M. Thesis), Oct. 1976, AD A033-394. *TM-77 ``Task Scheduling in the Control Robotics Environment'' by A.K. Mok (S.M. Thesis), Sept. 1976, AD A030-402. *TM-76 ``A Note on the Average Time to Compute Transitive Closures'' by P.A. Bloniarz, M.J. Fischer and A.R. Meyer, Sept. 1976. TM-75 ``K+1 Heads are Better than K'' by A.C. Yao and R.L. Rivest, Sept. 1976, AD A030-008. *TM-74 ``The Design of a Modular Laboratory for Control Robotics'' by N. Malvania (S.M. Thesis), Sept. 1976, AD A030-418. *TM-73 ``Optimal Arrangement of Keys in a Hash Table'' by R.L. Rivest, July 1976. *TM-72 ``Protosystem I: An Automatic Programming System Prototype'' by G.R. Ruth, July 1976, AD A026-912. *TM-71 ``On the Worst-Case of Behavior of String-Searching Algorithms'' by R. Rivest, April 1976. *TM-70 ``Automatic Design of Data Processing Systems'' by G.R. Ruth, Feb. 1976, AD A023-451. *TM-69 ``Improved Bounds on the Costs of Optimal and Balanced Binary Search Trees'' by P.J. Bayer (S.M. Thesis), Nov. 1975. *TM-68 ``Stream-Oriented Computation in Recursive Data Flow Schemas'' by K. Weng (S.M. Thesis), Oct. 1975. *TM-67 ``Computational Complexity of the Word Problem for Commutative Semigroups'' by E.W. Cardoza (S.M. Thesis), Oct. 1975. *TM-66 ``Formal Properties of Well-Formed Data Flow Schemas'' by C. Leung (S.B., S.M. & E.E. Thesis), June 1975. TM-65 ``The Complexity Negation-Limited Networks - A Brief Survey'' by M.J. Fischer, June 1975. *TM-64 ``Finding Isomorph Classes for Combinatorial Structures'' by R.B. Weiss (S.M. Thesis), June 1975. *TM-63 ``Encryption Schemes for Computer Confidentiality'' by V. Pless, May 1975, AD A010-217. TM-62 ``An Asynchronous Logic Array'' by S.S. Patil, May 1975. TM-61 ``First Version of a Data Flow Procedure Language'' by J.B. Dennis, May 1975. TM-60 ``CAMAC: Group Manipulation System'' by R.B. Weiss, March 1975, PB 240-495/AS. *TM-59 ``Decision Problems for Petri Nets and Vector Addition Systems'' by M. Hack, March 1975, PB 231-916/AS. *TM-58 ``Decidability of Equivalence for a Class of Data Flow Schemas'' by J.E. Qualitz, March 1975, PB 237-033/AS. *TM-57 ``On Bateson's Logical Levels of Learning'' by M. Levin, Feb. 1975. TM-56 ``Research on Expert Systems'' by G.A. Gorry, Dec. 1974. *TM-55 ``A Class of Boolean Functions with Linear Combinational Complexity'' by W.N. Hsieh, L.H. Harper and J.E. Savage, Oct. 1974, PB 237-206/AS. *TM-54 ``The Inherent Computation Complexity of Theories of Ordered Sets: A Brief Survey'' by A.R. Meyer, Oct. 1974, PB 237-200/AS. *TM-53 ``MDC-Programmer: A Muddle-to-Datalanguage Translator for Information Retrieval'' by S.A. Bengelloun (S.B. Thesis), Oct. 1974, AD 786- 754. *TM-52 ``Computing in Logarithmic Space'' by J.C. Lind, Sept. 1974, PB 236-167/AS. *TM-51 ``An Investigation of Current Language Support for the Data Requirements of Structured Programming'' by J.M. Aiello (S.M. & E.E. Thesis), Sept. 1974, PB 236-815/AS. *TM-50 ``An Enciphering Module for Multics'' by G.G. Benedict (S.B. Thesis), July 1974, AD 782-658. TM-49 ``Complete Classification of (24,12) and (22,11) Self-Dual Codes'' by V. Pless, June 1974, AD 781-335. TM-48 ``The Reduction Method for Establishing Lower Bounds on the Number of Additions'' by Z.M. Kedem, June 1974, PB 233-538/AS. *TM-47 ``Mathematical Foundations of Flip-Flops'' by V. Pless, June 1974, AD 780-901. *TM-46 ``Combining Dimensionality and Rate of Growth Arguments for Establishing Lower Bounds on the Number of Multiplications'' by Z.M. Kedem, June 1974, PB 232-969/AS. *TM-45 ``Fast On-Line Integer Multiplication'' by M.J. Fischer and L.J. Stockmeyer, May 1974, AD 779-889. TM-44 ``Symmetry Codes and Their Invariant Subcodes'' by V. Pless, May 1974, AD 780-243. TM-43 ``Super-Exponential Complexity of Presburger Arithmetic'' by M.J. Fischer and M.O. Rabin, Feb. 1974, AD 775-004. *TM-42 ``On the Complexity of the Theories of Weak Direct Products'' by C. Rackoff, Jan. 1974, PB 228-459/AS. TM-41 ``String-Matching and Other Products'' by M.J. Fischer and M.S. Paterson, Jan. 1974, AD 773-138. TM-40 ``An Improved Overlap Argument for On-Line Multiplication'' by M.S. Paterson, M.J. Fischer and A.R. Meyer, Jan. 1974, AD 773-137. *TM-39 ``Discrete Computation: Theory and Open Problems'' by A.R. Meyer, Jan. 1974, PB 226-836/AS. *TM-38 ``Weak Monadic Second Order Theory of Succesor is Not Elementary- Recursive'' by A.R. Meyer, Dec. 1973, PB 226-514/AS. *TM-37 ``Real-Time Simulation of Multidimensional Turing Machines by Storage Modification Machines'' by A. Schonhage, Dec. 1973, PB 226-103/AS. *TM-36 ``A User's Guide to the Macro Control Language'' by S.P. Geiger, Dec. 1973, AD 771-435. *TM-35 ``An Interactive Implementation of the Todd-Coxeter Algorithm'' by R.J. Bonneau, Dec. 1973, AD 770-565. *TM-34 ``Polynomial Exponentiation: The Fast Fourier Transform Revisited'' by R.J. Bonneau, June 1973, PB 221-742. *TM-33 ``A Decision Procedure for the First Order Theory of Real Addition with Order'' by J. Ferrante and C. Rackoff, May 1973, AD 760-000. *TM-32 ``An Operator Embedding Theorem for Complexity Classes of Recursive Functions'' by R. Moll, May 1973, AD 759-999. *TM-31 ``A Class of Finite Computation Structures Supporting the Fast Fourier Transform'' by R.J. Bonneau, March 1973, AD 757-787. *TM-30 ``SIM360: A S/360 Simulator'' by W. McCray (S.B. Thesis), Oct. 1972, AD 749-365. *TM-29 ``The Emptiness Problem for Automata on Infinite Trees'' by R. Hossley and C. Rackoff, Spring 1972, AD 747-250. *TM-28 ``Construction Heuristics for Geometry and a Vector Algebra Representation of Geometry'' by R. Wong, June 1972, AD 743-487. *TM-27 ``Economy of Descriptions and Minimal Indices'' by A. Bagchi, Jan. 1972, AD 736-960. *TM-26 ``Modeling and Decomposition of Information Systems for Performance Evaluation'' by G.G. Iazeolla, June 1971, AD 733-965. *TM-25 ``Helping People Think'' by R.C. Goldstein, April 1971, AD 721- 998. *TM-24 ``The MacAIMS Data Management System'' by R.C. Goldstein and A.J. Strnad, April 1971, AD 721-620. *TM-23 ``The Relational Approach to the Management of Data Bases'' by A.J. Strnad, April 1971, AD 721-619. *TM-22 ``Transmission of Information Between a Man-Machine Decision System and Its Environment'' by D.M. Wells, April 1971, AD 722-837. *TM-21 ``The Substantive Use of Computers for Intellectual Activities'' by R.C. Goldstein, April 1971, AD 721-618. *TM-20 ``A Computer Model of Simple Forms of Learning'' by T.L. Jones (Ph.D. Dissertation), Jan. 1971, AD 720-337. *TM-19 ``A New List-Tracing Algorithm'' by R.R. Fenichel, Oct. 1970, AD 714-522. *TM-18 ``Automatic Code-Generation from an Object-Machine Description'' by P.L. Miller, Oct. 1970, AD 713-853. *TM-17 ``Complexity Measures for Programming Languages'' by L.I. Goodman (S.M. Thesis), Sept. 1971, AD 729-011. *TM-16 ``Pseudo-Random Sequences'' by G. Bruere-Dawson (S.M. Thesis), Oct. 1970, AD 713-852. *TM-15 ``An Expansion of the Data Structuring Capabilities of PAL'' by S.N. Zilles (S.M. Thesis), Oct. 1970, AD 720-761. *TM-14 ``Suspension of Processes in a Multiprocessing Computer System'' by C.M. Vogt (S.M. Thesis), Sept. 1970, AD 713-989. *TM-13 ``Use of High Level Languages for Systems Programming'' by R.M. Graham, Sept. 1970, AD 711-965. *TM-12 ``File Management and Related Topics'' by R.M. Graham, Sept. 1970, AD 712-068. *TM-11 ``Description and Flow Chart of the PDP-7/9 Communications Package'' by P.W. Ward, July 1970, AD 711-379. *TM-10 ``Interactive Design Coordination for the Building Industry'' by J.N. Jackson, June 1970, AD 708-400.