Browsing LCS Technical Memos (1974 - 2003) by Title
Now showing items 166-185 of 492
-
Factoring Numbers in 0(log n) Arithmetic Steps
(1977-11)In this paper we show that a non-trivial factor of a composite number n can be found by performing arithmetic steps in a number proportional to the number of bits in n, and thus there are extremely short straight-line ... -
Failsafe Key Escrow Systems (Extended Abstract)
(1994-08)This paper describes a method for escrowing cryptographic keys, which we call Failsafe Key Escrow (FKE). The method is substantially more secure than alternative such as the Fair Public Key Cryptosystem approach advocated ... -
A Fast Multiport Memory Based on Single-port Memory Cells
(1991-07)We present a new design for dual-port memories that uses single-port memory cells but guarantees fast deterministic read/write access. The basic unit of storage is the word, rather than the bit, and addresses conflicts ... -
Fast On-line Integer Multiplication
(1974-05)A Turing machine multiplies binary integers on-line if it receives its inputs low-order digits first and produces the jth digit of the product before reading in the (j+l)st digits of the two inputs. We present a general ... -
A Fast Signature Scheme
(1978-05)In this paper we propose a new scheme for generating and verifying "electronic signatures" in public-key communications. The scheme is based on the difficulty of solving the knapsack problem, and its two main advantages ... -
A Faster Algorithm Computing String Edit Distances
(1978-05)The edit-distance between two character strings can be defined as the minimum cost of a sequence of editing operations which transforms one string into the other. The operations allowed are deleteing, inserting and replacing ... -
File Management and Related Topics, June 12, 1970
(1970-09)The subject of these notes is file management. We will develop the problems of file management within the environment of a large information and computing service, often called a computer utility or general purpose ... -
A File Transfer Program for a Personal Computer
(1982-04)This thesis explores engineering decisions involved in implementing a network file transfer program on a personal computer in response to criteria of low cost and reasonable efficiency. The issues include choice of hardware, ... -
Finding Isomorph Classes for Combinatorial Structures
(1975-06)A common problem in combinatorial analysis is finding isomorph classes of combinatorial objects. This process is sometimes known as isomorph rejection. In graph theory, it is used to count labelled and unlabelled graphs ... -
Finding Minimum Cutsets in Reducible Graphs
(1977-06)The analysis of many processes modelled by directed graphs requires the selection of a subset of vertices which cut all the cycles in the graph. Reducing the size of such a cutset usually leads to a simpler and more efficient ... -
Finding Minimum-cost Circulations by Canceling Negative Cycles
(1987-07)A classical algorithm for finding a minimum-cost circultaion consists of repeatedly finding a residual cycle of negative cost and canceling it by pushing enough flow around the cycle to saturate an arc. We show that a ... -
First Version of a Data Flow Procedure Language
(1975-05)A language for representing computational procedures based on the concept of data flow is presented in terms of a semantic model that permits concurrent execution of noninterfering program parts. Procedures in the language ... -
Floyd-Hoare Logic Defines Semantics
(1986-05)The first-order patrial correctness assertions provable in Floyd-Hoare logic about an uninterpreted while-program scheme determine the scheme up to equivalence. This settles an open problem of Meyer and Halpern. The simple ... -
Formal Properties of Well-formed Data Flow Schemas
(1975-06)This thesis presents some results in comparative schematology and some undecidability results for two models of computer programs: the class of flowchart schemas and the class of well-formed data flow schemas (wfdfs's). ... -
Formulation of Tradeoffs in Planning Under Uncertainty
(1987-06)Planning under uncertainty with multiple, competing objectives is impossible when goals are represented as predicates and the effects of actions are modeled as deterministic functions of situations. Decision-theoretic ... -
Forward and Backward Simulations for Timing-based Systems
(1991-11)A general automaton model for timing-based systems is presented and is used as the context for developing a variety of simulation proof techniques for such systems. As a first step, a comprehensive overview of simulation ... -
Forward and Backward Simulations Part I: Untimed Systems (Replaces TM-486)
(1993-03)A unified, comprehensive presentation of simulation techniques for verification of concurrent systems is given, in terms of a simple untimed automaton model. In particular, (1) refinements, (2) forward and backward ... -
Forward and Backward Simulations Part II: Timing-based Systems
(1993-03)A general automaton model for timing-based systems is presented and is used as the context for developing a variety of simulation proof techniques for such systems. These techniques include (1) refinments, (2) forward and ...
