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.